变换和置换群ppt课件.ppt

变换群和置换群变换群和置换群离散数学 第15讲1.上一讲内容的回顾上一讲内容的回顾l不变子群l商群l同态核l自然同态l群同态基本定理l同态基本定理的应用2.变换群与置换群变换群与置换群l变换和变换群l置换及其表示l置换群l任意群与变换群同构l置换群的应用3.变换和变换群变换和变换群 l定义：A是非空集合，f:AA称为A上的一个变换变换l经常讨论的是一一变换，即f是双射l变换就是函数，变换的“乘法”就是函数复合运算l集合A上的一一变换关于变换乘法构成的群称为变换群变换群4.非空集合上所有的一一变换构成群非空集合上所有的一一变换构成群l设A是任意的非空集合，A上所所有有的的一一变换一定构成群l封闭性：双射的复合仍是双射l结合律：变换乘法是关系复合运算的特例l单位元：f:AA, xA, f(x)=x满足对于任意g:AA, fg=gf=g (恒等变换)l逆元素：任意双射g:AA均有反函数g -1:AA, 即其逆元素 5.变换群的例子变换群的例子 lR是实数集，G是R上所有如下形式的变换构成的集合： fa,b:RR, xR, fa,b(x)=ax+b (a,b是有理数，a0) 则G是变换群l封闭性： fa,b, fc,d G, 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 )l结合律：变换的乘法即关系复合运算l单位元：恒等变换f1,0:RR: xR, f1,0(x)=x 是单位元l逆元素：对任意的fa,b , f1/a,-b/afa,b = fa,b f1/a,-b/a= f1,0, 因此f1/a,-b/a是fa,b 的逆元素。

注意：a0)6.置换及其表示置换及其表示 l定义：有限集合S上的双射:SS称为S上的n元置换l记法：7.置换的例子置换的例子l例子：集合S=1,2,3上共有6个不同的置换， 它们的集合记为S3 ：lS3是最小的非交换群l注意：质数阶群一定是可交换群 8.轮换与对换轮换与对换 l定义: 设是S=1,2,n上的n元置换，且： (i1)=i2, (i2)=i3, , (ik-1)=ik, (ik)=i1, 且xS, xij j=1,2,k, (x)=x, 则称是S上的一个k阶阶轮轮换换，当k=2, 也称为对换对换l记法：(i1 i2 ik ) l例子：用轮换形式表示S3的6个元素：le=(1); =(1 2 3); =(1 3 2); =(2 3); =(1 3); =(1 2) 9.不相交的轮换相乘可以交换不相交的轮换相乘可以交换l给定Sn中两个轮换： =(i1 i2 ik ), =(j1 j2 js ), 若i1, i2, , ik j1, j2, , js=，则称 与 不相交不相交l若 与 不相交，则 = l对任意xS, 分三种情况讨论：lxi1, i2, , ik; lxj1, j2, , js; lxS-(i1, i2, , ikj1, j2, , js)， 均有(x) = (x)10.用轮换的乘积表示置换用轮换的乘积表示置换 l任一任一n元置换元置换 均可表示成一组互不相交的轮换的乘积均可表示成一组互不相交的轮换的乘积。

l对在下S中发生变化的元素的个数r 进行归纳： r =0，即是恒等置换 若r =k0, 取一在下改变的元素i1, 按照轮换的定义依次找出i2, i3 S是有限集，一定可以找到im, 使得i1, i2, , im均不同，但im+1 i1, i2, , im 必有im+1=i1否则：若im+1=ij, j1, 则(ij-1)=(im)=ij, 与是一对一的矛盾) 令1=(i1 i2 im)，则 = 1, 与1不相交，最多只改变余下的k-m个元素，由归纳假设， =23l 11.置换的轮换乘积形式的唯一性置换的轮换乘积形式的唯一性 l如果置换可以表示为12t和12l, 令X=1, 2, , t, Y=1, 2, , l , , 则X=Yl证明要点：l任取jX, 不失一般性，令j=(i1 i2 im )l由于(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 12.置换的轮换乘积形式置换的轮换乘积形式l例子： = (1 5 7) (4 8) l例子： =(1 2 3 5) (4 8 7 6)13.用对换的乘积表示置换用对换的乘积表示置换 lk(k1)阶轮换 =(i1 i2 ik )可以表示为k-1个对换的乘积：(i1i2)(i1ik-1) (i1ik)l注意：各对换是相交的，因此次序不可以交换。

l证明要点：对k归纳 k=2时显然成立考虑 =(i1 i2 ik ik+1 ), 只需证明 =(i1 i2 ik)(i1 ik+1 ) 分4种情况证明：xA, (x)=(i1 i2 ik)(i1 ik+1 )(x)(1) x i1, i2, , ik-1(2) x=ik(3) x=ik+1(4) x为A中其它元素 14.对换乘积表示置换的例子对换乘积表示置换的例子定义1,2,3,4上的函数 f 如下： f (1)=2, f (2)=3, f (3)=4, f (4)=1函数 f 的轮换形式：(1 2 3 4)函数 f 的对换乘积形式： (1 2) (1 3) (1 4)令：函数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)=115.排列中的逆序排列中的逆序l设i1i2in是1,2,n的一种排列。

对任意的ij, ik, 若ijik, 且jk, 则称ijik为一个逆序逆序l排列中逆序总个数称为该排列的逆序数逆序数l例子：(3 2 1 5 4)中3和2构成一个逆序，这里的逆序数是416.奇置换和偶置换奇置换和偶置换 l是S上的一个置换，(j)=ij, (j=1,2,n)则的对换表示中对换个数与排列i1, i2, , in的逆序数同奇偶性l对S的阶数n进行归纳l令的对换个数为()，对应排列的逆序数为()l奠基：当n=1, =(1), ()=()=0 17.奇置换和偶置换奇置换和偶置换 归纳证明归纳证明l假设当n=k时结论成立考虑k+1元置换l分两种情况讨论；(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的诸项)。

18.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)125476914 153138111012(8,16)(8,12) = (8,16,12)125476914 1531312111085638141013 15712111492563815410131 71211149219.置换群置换群 l有有限限集集合合S上上所所有有置置换换一一定定构构成成群群，称为对称群，记为Sn, 其中n是S的阶数lSn的任一子集若构成群，则是置换群l注意：置换群是变换群的特例，对称群是置换群的特例lSn中所有的偶置换构成子群，称为交错群只须证明封闭性)l置换群的几何意义：(以S3为例) 123顺时针旋转：0度：e120度：240度：绕轴翻转20.基于已知群定义变换群的例子基于已知群定义变换群的例子l对群(G,*)中任意一元素a, 可以定义： a:GG, xG, a(x)=x*a, la是一一变换la是显然是函数l对任意bG，群方程x*a=b有唯一解，即a是满射l由群满足消去律：x*a=y*a x=y, 即a是单射l令G=a|aG21.Cayley定理定理l任意的群任意的群G与一个变换群同构与一个变换群同构。

l定义: GG: aG, (a)=a ,其中G=a|aG l则是同构映射l是函数：a=b xG, x*a=x*b xG, a(x)=b(x) a=bl是满射：显然l是单射：根据消去律，ab x*ax*b abl同构映射：(a*b)=(ab), xG, (a*b)(x)=(a*b)(x)=x* (a*b) =(x*a)*b=b(a(x), (a*b)=ab=(a)(b)，这里“”是函数复合运算22.利用置换群解题的例子利用置换群解题的例子l在四个方格子中放置了带有 标号的四个盘子(见右图) 可以进行下列操作： (1) 上下行互换 (2) 左右列互换 (3) 两对对角元素互换 进行上述操作任意有限多次，可以按照任意次序进行，包括交替进行l问题：操作停止时与开始时格局相同的充分必要条件是什么？操作停止时与开始时格局相同的充分必要条件是什么？123423.采用置换群建立数学模型采用置换群建立数学模型l定义集合1,2,3,4上的置换, 并用轮换乘积形式表示如下：lf1=(1,3)(2,4)，则f1对应于动作1：上下互换；lf2=(1,2)(3,4)，则f2对应于动作2：左右互换；lf3=(1,4)(2,3)，则f3对应于动作3：对角互换；l令e=(1), 则(e, f1, f2, f3, )构成可交换置换群可交换置换群l注意：(f1 f2)= (f2 f1)= f3；(f1 f3)= (f3 f1)= f2；(f2 f3)= (f3 f2)= f1；因此运算封闭且可交换；且e是单位元，每个元素的逆元即自己。

l在此模型之下：任意有限多次连续动作即等效于函数任意有限多次连续动作即等效于函数 f =fi1 fi2 fi n 其中ik1,2,324.问题的解问题的解l任意有限多次连续动作即等效于函数 f =fi1 fi2 fi n 其中ik1,2,3l所以：开始格局与结束格局相同开始格局与结束格局相同 当且仅当当且仅当 f = el(e, f1, f2, f3, )是可交换群， f =fi1 fi2 fi n = f1h f2j f3k ,其中h, j, k是非负整数l注意：对i=1,2,3, 均有fi 2k = e, 其中k是非负整数； f = f1s(h) f2s(j) f3s(k) , s(x)是整数集上的“奇偶特征函数”，当x为奇数，s(x)=1, 否则s(x)=0l注意：f1 f2 f3 =el开始格局与结束格局相同 当且仅当 动作动作1,2,3分别施行的次数同分别施行的次数同奇偶性奇偶性(与顺序无关) 25.作业作业lp.228l36l假设A,B,C,D是正方形的四个顶点; 定义集合A,B,C,D上8个置换,分别对应于正方形在平面内顺时针旋转0, 90, 180, 270, 以及分别围绕对角线或对边中点连线(各有两条)翻转。

证明这8个置换与复合运算构成群，画出群表，并列出所有的子群。