《变换和置换群》PPT课件.ppt

《《变换和置换群》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、变换群和置换群离散数学第15讲上一讲内容的回顾不变子群商群同态核自然同态群同态基本定理同态基本定理的应用变换群与置换群变换和变换群置换及其表示置换群任意群与变换群同构置换群的应用变换和变换群定义：A是非空集合，f:AA称为A上的一个变换。经常讨论的是一一变换，即f是双射。变换就是函数，变换的“乘法”就是函数复合运算。集合A上的一一变换关于变换乘法构成的群称为变换群。非空集合上所有的一一变换构成群设A是任意的非空集合，A上所有的一一变换一定构成群。封闭性：双射的复合仍是双射。结合律：变换乘法是关系复合运算的特例。单位元：f:AA,xA,f(x)=x满足对于任意g:AA,f◦g

2、=g◦f=g(恒等变换)逆元素：任意双射g:AA均有反函数g-1:AA,即其逆元素。变换群的例子R是实数集，G是R上所有如下形式的变换构成的集合：fa,b:RR,xR,fa,b(x)=ax+b(a,b是有理数，a0)则G是变换群。封闭性：fa,b,fc,dG,fa,b◦fc,d=fac,bc+d(注意：fc,d(fa,b(x))=fc,d(ax+b)=acx+bc+d,例如：f2,1(x)=2x+1,f1,2(x)=x+2,f1,2(f2,1(x))=2x+3,即f2,1◦f1,2=f2,3)结合律：变换的乘法即关系复合运算单位元：恒等变换f1,0:RR:xR,

3、f1,0(x)=x是单位元逆元素：对任意的fa,b,f1/a,-b/a◦fa,b=fa,b◦f1/a,-b/a=f1,0,因此f1/a,-b/a是fa,b的逆元素。(注意：a0)置换及其表示定义：有限集合S上的双射:SS称为S上的n元置换记法：置换的例子例子：集合S={1,2,3}上共有6个不同的置换，它们的集合记为S3：S3是最小的非交换群注意：质数阶群一定是可交换群。轮换与对换定义:设是S={1,2,…,n}上的n元置换，且：(i1)=i2,(i2)=i3,…,(ik-1)=ik,(ik)=i1,且xS,xijj=1,2,…,k,(x)=x,则称是S上的

4、一个k阶轮换，当k=2,也称为对换。记法：(i1i2…ik)例子：用轮换形式表示S3的6个元素：e=(1);=(123);=(132);=(23);=(13);=(12)不相交的轮换相乘可以交换给定Sn中两个轮换：=(i1i2…ik),=(j1j2…js),若{i1,i2,…,ik}{j1,j2,…,js}=，则称与不相交若与不相交，则=对任意xS,分三种情况讨论：x{i1,i2,…,ik};x{j1,j2,…,js};xS-({i1,i2,…,ik}{j1,j2,…,js})，均有(x)=(x)用轮换的乘积表示置换任一n元置换

5、均可表示成一组互不相交的轮换的乘积。对在下S中发生变化的元素的个数r进行归纳：r=0，即是恒等置换。若r=k>0,取一在下改变的元素i1,按照轮换的定义依次找出i2,i3…。S是有限集，一定可以找到im,使得i1,i2,…,im均不同，但im+1{i1,i2,…,im}。必有im+1=i1。(否则：若im+1=ij,j1,则(ij-1)=(im)=ij,与是一对一的矛盾。)令1=(i1i2…im)，则=1','与1不相交，'最多只改变余下的k-m个元素，由归纳假设，'=23…l。置换的轮换乘积形式的唯一性如果置换可以表示为12…t和1

6、2…l,令X={1,2,…,t},Y={1,2,…,l,},则X=Y证明要点：任取jX,不失一般性，令j=(i1i2…im)由于(i1)i1,必存在sY,使得i1出现在s中。由轮换的定义以及各轮换不相交，i2,i3,…,im也必在s中。若存在其它某个元素u也在s中,则u只能在m后面，则(im)=s(im)=u，同时又有(im)=j(im)=i1,矛盾。所以j即s。这说明XY,同理可知YX。置换的轮换乘积形式例子：=(157)(48)例子：=(1235)(4876)用对换的乘积表示置换k(k>1)阶轮换=(i1i2…ik)可以表示为k

7、-1个对换的乘积：(i1i2)…(i1ik-1)(i1ik)注意：各对换是相交的，因此次序不可以交换。证明要点：对k归纳。k=2时显然成立。考虑=(i1i2…ikik+1),只需证明=(i1i2…ik)(i1ik+1)。分4种情况证明：xA,(x)=(i1i2…ik)(i1ik+1)(x)(1)x{i1,i2,…,ik-1}(2)x=ik(3)x=ik+1(4)x为A中其它元素对换乘积表示置换的例子定义{1,2,3,4}上的函数f如下：f(1)