变换和置换群

.,变换群和置换群,离散数学第15讲,.,上一讲内容的回顾,不变子群商群同态核自然同态群同态基本定理同态基本定理的应用,.,变换群与置换群,变换和变换群置换及其表示置换群任意群与变换群同构置换群的应用,.,变换和变换群,定义：A是非空集合，f:AA称为A上的一个变换。经常讨论的是一一变换，即f是双射。变换就是函数，变换的“乘法”就是函数复合运算。集合A上的一一变换关于变换乘法构成的群称为变换群。,.,非空集合上所有的一一变换构成群,设A是任意的非空集合，A上所有的一一变换一定构成群。封闭性：双射的复合仍是双射。结合律：变换乘法是关系复合运算的特例。单位元：f:AA,xA,f(x)=x满足对于任意g:AA,fg=gf=g(恒等变换)逆元素：任意双射g:AA均有反函数g-1:AA,即其逆元素。,.,变换群的例子,R是实数集，G是R上所有如下形式的变换构成的集合：fa,b:RR,xR,fa,b(x)=ax+b(a,b是有理数，a0)则G是变换群。封闭性：fa,b,fc,dG,fa,bfc,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,1f1,2=f2,3)结合律：变换的乘法即关系复合运算单位元：恒等变换f1,0:RR:xR,f1,0(x)=x是单位元逆元素：对任意的fa,b,f1/a,-b/afa,b=fa,bf1/a,-b/a=f1,0,因此f1/a,-b/a是fa,b的逆元素。(注意：a0),.,置换及其表示,定义：有限集合S上的双射:SS称为S上的n元置换记法：,.,置换的例子,例子：集合S=1,2,3上共有6个不同的置换，它们的集合记为S3：S3是最小的非交换群注意：质数阶群一定是可交换群。,.,轮换与对换,定义:设是S=1,2,n上的n元置换，且：(i1)=i2,(i2)=i3,(ik-1)=ik,(ik)=i1,且xS,xijj=1,2,k,(x)=x,则称是S上的一个k阶轮换，当k=2,也称为对换。记法：(i1i2ik)例子：用轮换形式表示S3的6个元素：e=(1);=(123);=(132);=(23);=(13);=(12),.,不相交的轮换相乘可以交换,给定Sn中两个轮换：=(i1i2ik),=(j1j2js),若i1,i2,ikj1,j2,js=，则称与不相交若与不相交，则=对任意xS,分三种情况讨论：xi1,i2,ik;xj1,j2,js;xS-(i1,i2,ikj1,j2,js)，均有(x)=(x),.,用轮换的乘积表示置换,任一n元置换均可表示成一组互不相交的轮换的乘积。对在下S中发生变化的元素的个数r进行归纳：r=0，即是恒等置换。若r=k0,取一在下改变的元素i1,按照轮换的定义依次找出i2,i3。S是有限集，一定可以找到im,使得i1,i2,im均不同，但im+1i1,i2,im。必有im+1=i1。(否则：若im+1=ij,j1,则(ij-1)=(im)=ij,与是一对一的矛盾。)令1=(i1i2im)，则=1,与1不相交，最多只改变余下的k-m个元素，由归纳假设，=23l。,.,置换的轮换乘积形式的唯一性,如果置换可以表示为12t和12l,令X=1,2,t,Y=1,2,l,则X=Y证明要点：任取jX,不失一般性，令j=(i1i2im)由于(i1)i1,必存在sY,使得i1出现在s中。由轮换的定义以及各轮换不相交，i2,i3,im也必在s中。若存在其它某个元素u也在s中,则u只能在m后面，则(im)=s(im)=u，同时又有(im)=j(im)=i1,矛盾。所以j即s。这说明XY,同理可知YX。,.,置换的轮换乘积形式,例子：=(157)(48)例子：=(1235)(4876),.,用对换的乘积表示置换,k(k1)阶轮换=(i1i2ik)可以表示为k-1个对换的乘积：(i1i2)(i1ik-1)(i1ik)注意：各对换是相交的，因此次序不可以交换。证明要点：对k归纳。k=2时显然成立。考虑=(i1i2ikik+1),只需证明=(i1i2ik)(i1ik+1)。分4种情况证明：xA,(x)=(i1i2ik)(i1ik+1)(x)(1)xi1,i2,ik-1(2)x=ik(3)x=ik+1(4)x为A中其它元素,.,对换乘积表示置换的例子,定义1,2,3,4上的函数f如下：f(1)=2,f(2)=3,f(3)=4,f(4)=1,函数f的轮换形式：(1234),函数f的对换乘积形式：(12)(13)(14),令：函数g:g(1)=2,g(2)=1,g(3)=3,g(4)=4函数h:h(1)=3,h(2)=2,h(3)=1,h(4)=4函数k:k(1)=4,k(2)=2,k(3)=3,k(4)=1,则：ghk(1)=k(h(g(1)=k(h(2)=k(2)=2ghk(2)=k(h(g(2)=k(h(1)=k(3)=3ghk(3)=k(h(g(3)=k(h(3)=k(1)=4ghk(4)=k(h(g(4)=k(h(4)=k(4)=1,.,排列中的逆序,设i1i2in是1,2,n的一种排列。对任意的ij,ik,若ijik,且jk,则称ijik为一个逆序排列中逆序总个数称为该排列的逆序数。例子：(32154)中3和2构成一个逆序，这里的逆序数是4,.,奇置换和偶置换,是S上的一个置换，(j)=ij,(j=1,2,n)。则的对换表示中对换个数与排列i1,i2,in的逆序数同奇偶性。对S的阶数n进行归纳。令的对换个数为()，对应排列的逆序数为()。奠基：当n=1,=(1),()=()=0。,.,奇置换和偶置换归纳证明,假设当n=k时结论成立。考虑k+1元置换。分两种情况讨论；(1)(k+1)=k+1：在1,2,k上的限制是k元置换，令其为，相应排列为,显然：()=(),()=(),由归纳假设，()与()同奇偶性。(2)(k+1)=sk+1:必有t1,2,k,使得(t)=k+1,而相应排列=i1i2it-1(k+1)it+1,ins。构造置换=(k+1,s),则满足(1)中条件，相应排列是=i1i2it-1sit+1,in(k+1)。注意，()与()奇偶性恰好相反，()与()的奇偶性也恰好相反(实际上，受到影响的除了s和k+1本身外，只是it与ik+1之间大于s,小于k+1的诸项)。,.,15-Puzzle,(1,5,3,7)(2,6,4,8)(9,10)(11,14,13,12)(15)(16),(1,5,3,7,15)(2,6,4,8)(9,10)(11,14,13,12)(16),1,2,5,4,7,6,9,14,15,3,13,8,11,10,12,(8,16)(8,12)=(8,16,12),.,置换群,有限集合S上所有置换一定构成群，称为对称群，记为Sn,其中n是S的阶数。Sn的任一子集若构成群，则是置换群。注意：置换群是变换群的特例，对称群是置换群的特例。Sn中所有的偶置换构成子群，称为交错群。(只须证明封闭性)置换群的几何意义：(以S3为例),.,基于已知群定义变换群的例子,对群(G,*)中任意一元素a,可以定义：a:GG,xG,a(x)=x*a,a是一一变换a是显然是函数对任意bG，群方程x*a=b有唯一解，即a是满射由群满足消去律：x*a=y*ax=y,即a是单射令G=a|aG,.,Cayley定理,任意的群G与一个变换群同构。定义:GG:aG,(a)=a,其中G=a|aG。则是同构映射是函数：a=bxG,x*a=x*bxG,a(x)=b(x)a=b是满射：显然是单射：根据消去律，abx*ax*bab同构映射：(a*b)=(ab),xG,(a*b)(x)=(a*b)(x)=x*(a*b)=(x*a)*b=b(a(x),(a*b)=ab=(a)(b)，这里“”是函数复合运算。,.,利用置换群解题的例子,在四个方格子中放置了带有标号的四个盘子(见右图)。可以进行下列操作：(1)上下行互换(2)左右列互换(3)两对对角元素互换进行上述操作任意有限多次，可以按照任意次序进行，包括交替进行。问题：操作停止时与开始时格局相同的充分必要条件是什么？,.,采用置换群建立数学模型,定义集合1,2,3,4上的置换,并用轮换乘积形式表示如下：f1=(1,3)(2,4)，则f1对应于动作1：上下互换；f2=(1,2)(3,4)，则f2对应于动作2：左右互换；f3=(1,4)(2,3)，则f3对应于动作3：对角互换；令e=(1),则(e,f1,f2,f3,)构成可交换置换群注意：(f1f2)=(f2f1)=f3；(f1f3)=(f3f1)=f2；(f2f3)=(f3f2)=f1；因此运算封闭且可交换；且e是单位元，每个元素的逆元即自己。在此模型之下：任意有限多次连续动作即等效于函数f=fi1fi2fin。其中ik1,2,3,.,问题的解,任意有限多次连续动作即等效于函数f=fi1fi2fin。其中ik1,2,3所以：开始格局与结束格局相同当且仅当f=e(e,f1,f2,f3,)是可交换群，f=fi1fi2fin=f1hf2jf3k,其中h,j,k是非负整数。注意：对i=1,2,3,均有fi2k=e,其中k是非负整数；f=f1s(h)f2s(j)f3s(k),s(x)是整数集上的“奇偶特征函数”，当x为奇数，s(x)=1,否则s(x)=0。注意：f1f2f3=e开始格局与结