《《离散数学》课件：6-3-置换群》由会员分享，可在线阅读，更多相关《《离散数学》课件：6-3-置换群（39页珍藏版）》请在金锄头文库上搜索。
1、6.3 置换群置换群 6.3.1 置换的定义置换的定义 6.3.2 置换的轮换表法置换的轮换表法 6.3.3 置换的顺向圈表示置换的顺向圈表示 6.3.4 置换的奇偶性置换的奇偶性 1 1定义定义6.3.1 设设M是一个非空的有限集合，是一个非空的有限集合，M的一的一个一对一变换称为一个个一对一变换称为一个置换置换。设设M=a1,a2,an，则，则M的置换的置换可简记为可简记为= ，bi=(ai)，i=1,2,n 结论：结论：M的置换共有的置换共有n！个个。M上的置换也称为上的置换也称为n元置换元置换。 特别地，特别地， 若若(ai)=ai，i=1,2,n，则，则为为n元恒等置换。元恒等置换。
2、Sn：n！个置换作成的集合个置换作成的集合。6.3.1 置换的定义置换的定义2 2例：例：设设M=1, 2, 3，则有则有3！=6个个3元置换：元置换：所有元素不动：所有元素不动：1=一个元素不动：一个元素不动：2= 3=4= 0个个元素不动：元素不动： 5= 6=故，故，S3 = 1, 2, 3, 4, 5, 63 3置换的乘法置换的乘法对对M中中任任意意元元素素a及及M的的任任意意两两个个置置换换，规定规定(a)=(a)。例：例：设设= ，=则则= ， = 4 4满足结合律满足结合律：()=()，, Sn。Sn中中有单位元：有单位元：n元恒等置换，设为元恒等置换，设为0，有：有：0=0 ，
3、Sn每个每个n元置换在元置换在Sn 中都中都有逆有逆元素元素: = 置换的乘法的性质置换的乘法的性质5 5例：例：设设= ，=求求2，-1，-1。并。并解解方程方程x=，y=。解：解：2= = = -1= -1= x=-1= y=-1=6 6n次对称群次对称群定理定理6.3.1 n元置换的全体作成的集合元置换的全体作成的集合Sn对置换对置换的乘法作成一个群，称为的乘法作成一个群，称为n次对称群次对称群。(n次对称次对称群的任一子群称为群的任一子群称为n次置换群次置换群。)n=1，M=a， S1= 在置换的乘法下作成在置换的乘法下作成1次对称群，为次对称群，为Abel群。群。 n=2，M=a,
4、b，S2= , 在置换的在置换的乘法下作成乘法下作成2次对称群，为次对称群，为Abel群。群。 当当n3时，时，Sn不是不是Abel群。群。7 7定义定义6.3.2 设设是是M的置换，若可取到的置换，若可取到M的的元素元素a1, , ar，使，使(a1)=a2, (a2)=a3, , (ar-1)=ar, (ar)=a1，而，而不变不变M的其余的元素，则的其余的元素，则称为一个称为一个轮换轮换，记为：记为：(a1 a2 ar)。注：注：可以把可以把a1, , ar中的任意元素中的任意元素ai排排在头一位而改写成：在头一位而改写成：(ai ai+1 ar a1 ai-1)例：例：= =(1 3
5、4)=(3 4 1)=(4 1 3) 6.3.2 置换的轮换表法置换的轮换表法8 8设设设设(a(a1 1 a a2 2 a ar r) )是是是是MM的轮换，则的轮换，则的轮换，则的轮换，则(a(a1 1 a a2 2 a ar r) )-1 -1 = = ( (a ar r a a2 2 a a1 1) )证明：证明：证明：证明：往证往证往证往证( (a ar r a a2 2 a a1 1)(a)(a1 1 a a2 2 a ar r)=I)=I命命命命x x为为为为MM的任意元，的任意元，的任意元，的任意元，若若若若x xaa1 1,a,ar-1r-1 ，设，设，设，设x=x=a ai
6、 i，则：，则：，则：，则：( (a ar r a a2 2 a a1 1)(a)(a1 1 a a2 2 a ar r)(a)(ai i)=()=(a ar raa2 2 a a1 1)(a)(ai+1i+1)=)=a ai i若若若若x=x=a ar r，则：，则：，则：，则：( (a ar r a a2 2 a a1 1)(a)(a1 1 a a2 2 a ar r)(a)(ar r)=()=(a ar r a a2 2 a a1 1)(a)(a1 1)=)=a ar r若若若若x x a a1 1,a ar r ，则，则，则，则( (a ar r a a2 2 a a1 1)(a)(a
7、1 1 a a2 2 a ar r)(x)(x)=x)=x总之，总之，总之，总之，( (a ar r a a2 2 a a1 1)(a)(a1 1 a a2 2 a ar r)(x)(x)=x=)=x=I(xI(x) ) 即，即，即，即，( (a ar r a a2 2 a a1 1)(a)(a1 1 a a2 2 a ar r)=I )=I 同理，同理，同理，同理，(a(a1 1 a a2 2 a ar r)(a)(ar r a a2 2 a a1 1)=I)=I，证毕。，证毕。，证毕。，证毕。结论：结论：9 9M的两个轮换的两个轮换=(a1ar)和和=(b1bs)说说是不相杂或不相交，如果
8、是不相杂或不相交，如果 a1, , ar和和b1, , bs都不相同。都不相同。(即即a1, , arb1,bs= )例：例：设设M=1, 2, 3, 4, 5, 6, 7，(1 3 4)与与(6 3 7)是相杂轮换：是相杂轮换：(1 3 4)(6 3 7)=(6 4 1 3 7)，(6 3 7)(1 3 4)=(1 7 6 3 4)；(1 3 4)与与(2 5)是不相杂轮换：是不相杂轮换：(1 3 4)(2 5)=(2 5)(1 3 4)不不相杂轮换相杂轮换1010结结论论：若若和和是是M的的两两个个不不相相杂杂的的轮轮换换，则则=。证明：证明：设设=(a1ar)，=(b1bs)，和和不相杂
9、。命不相杂。命x为为M的任意元，的任意元，若若xa1, , ar，设，设x=ai，则则 (x)=(ai)=(ai)=ai+1， (x)=(ai)=(ai+1)=ai+1。 i=r时，时，ai+1应改为应改为a1。 故，故，(x)=(x)。不不相杂轮换相杂轮换1111同理可证，同理可证，若若xb1,bs，也有，也有(x)=(x)。若若x a1, , ar, b1, , bs，于于是，是，(x)=(x)=x， (x)=(x)=x。综上，综上，(x)=(x)，故，故 =。证毕。证毕。 不不相杂轮换相杂轮换1212任意置换任意置换恰有一法写成不相杂轮换的乘恰有一法写成不相杂轮换的乘积。积。即，任意置换
10、即，任意置换可以写成不相杂轮换可以写成不相杂轮换的乘积的乘积(可表性可表性)，如果不考虑乘积的顺，如果不考虑乘积的顺序，则写法是唯一的序，则写法是唯一的(唯一性唯一性)。例：例： =(1 3 5 2)(4)(6 8)(7)=(3 5 2 1)(7)(8 6)(4)置换的这种表法称为置换的轮换表法。置换的这种表法称为置换的轮换表法。去掉单轮换为轮换表法的省略形式：去掉单轮换为轮换表法的省略形式：(1 3 5 2)(6 8)定理定理6.3.21313证明：证明：(1)可表性。可表性。设设是是M上置换，任取上置换，任取a1M。若若(a1)=a1，则有轮换则有轮换(a1)。设设(a1)=a2，(a2)
11、=a3, 。由于由于M有限，有限，故到某一个元素故到某一个元素ar，(ar)必然不能再是新必然不能再是新的元素，即的元素，即(ar)a1, , ar。由于由于是一对一的，已有是一对一的，已有(ai)=ai+1，i=1,2,r-1，所以所以(ar)只能是只能是a1。于是。于是得到一个轮换得到一个轮换(a1ar)。1414若若M已已经经没没有有另另外外的的元元素素，则则就就等等于于这这个个轮轮换换，否否则则设设b1不不在在a1, , ar之之内内，则同样作法又可得到一个轮换则同样作法又可得到一个轮换(b1bs)。因因为为a1, , ar各各自自已已有有变变到到它它的的元元素素，所所以以b1, ,
12、bs中中不不会会有有a1, , ar出出现现，即即这这两两个个轮轮换换不不相相杂杂。若若M的的元元素素已已尽尽，则则就就等等于于这这两两个个轮轮换换的的乘乘积积，否否则则如上又可得到一个轮换。如上又可得到一个轮换。如此类推，由于如此类推，由于M有限，最后必得有限，最后必得=(a1ar)(b1bs)(c1ct) (1)即即表成了不相杂轮换的乘积。表成了不相杂轮换的乘积。 1515证明：证明：(2)唯一性唯一性.设设又可表为不相杂的轮换的乘积如下：又可表为不相杂的轮换的乘积如下：=(a1ar)(b1bs)(c1ct) (2)考虑考虑(1)式中任意轮换式中任意轮换(a1ar)。a1必出现必出现在在(
13、2)式中的某个轮换之内，不妨设式中的某个轮换之内，不妨设 a1a1ar，且且a1=a1。于是，于是， a2=(a1)=(a1)=a2 ,a3=(a2)=(a2)=a3 , ,1616证明：证明：可见，可见，(a1ar)必和必和(a1ar)完全相完全相同。这就是说，同。这就是说，(1)中的任意轮换必出现中的任意轮换必出现在在(2)中，同样中，同样(2)中的任意轮换必出现在中的任意轮换必出现在(1)中。因此，中。因此，(1)和和(2)一样，最多排列一样，最多排列方法不同，但不相杂的轮换相乘适合交换方法不同，但不相杂的轮换相乘适合交换律，所以排列的次序本来是可以任意颠倒律，所以排列的次序本来是可以任
14、意颠倒的。的。证毕。证毕。1717设设M=1,2,3,4，M的的24个个置置换换可可写写成成：I；(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)；(1 2 3), (1 3 2), (1 2 4), (1 4 2),(1 3 4), (1 4 3), (2 3 4), (2 4 3)；(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2),(1 4 2 3), (1 4 3 2)；(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)。例：例：1818轮换的长度轮换的长度 其中所含的元素个数。其中所含的元素个数。 例
15、：例：(a1 a2 ar)长度为长度为r。对换对换 长度为长度为2的轮换。的轮换。结论结论 任意轮换可以写成对换的乘积。任意轮换可以写成对换的乘积。证明：证明：往证往证(a1 a2ar)=(a1 ar)(a1 ar-1)(a1 a3)(a1 a2) (3)对对r进行归纳，当进行归纳，当r=2时命题显然成立。时命题显然成立。假设假设r=t时结论为真，时结论为真，考虑考虑=(a1 a2 at at+1)的情况。的情况。对换对换1919往证往证(a1a2atat+1)=(a1at+1)(a1a2at)令令1=(a1 at+1)，2=(a1 a2 at)，下面证明下面证明=12。任取任取lM，若若l
16、a1, a2, , at-1，不妨设不妨设l=am，则，则(l)=(am)=am+1， 12(l)=1(am+1)=am+1；若若l=at，则则 (l)=at+112(l)=12(at)=1(2(at)=1(a1)=at+1；若若l=at+1，则则(l)=(at+1)=a112(l)=1(2(at+1)=1(at+1)=a1；2020若若l a1, a2, , at+1，则则(l)=l12(l)=1(2(l)=1(l)=l。因此，因此，=12=(a1 at+1)(a1 a2 at)。由归纳假设，由归纳假设， (a1 a2 at)=(a1 at)(a1 at-1)(a1 a2)，所以所以=(a1
17、 at+1)(a1 at)(a1 at-1)(a1 a2)，归纳完成。归纳完成。还可以采用直接证明的方法进行证明。还可以采用直接证明的方法进行证明。推推论论 对对任任意意置置换换，有有一一法法(未未必必只只有有一一法法)可可将将其写成一些对换的乘积。其写成一些对换的乘积。例：例：(1 2)=(1 2)(1 3)(1 3)=(2 3)(1 3)(2 3)。2121例：例：设多项式设多项式f=(x1+x2)(x3+x4)，找出使，找出使f保持不变的保持不变的所有下标的置换，这些置换在置换的乘法下是所有下标的置换，这些置换在置换的乘法下是否构成群？否构成群？解：解：由加法交换律和乘法交换律可得到使由
18、加法交换律和乘法交换律可得到使f保持保持不变的所有下标的置换的集合为：不变的所有下标的置换的集合为：G=(1)(2)(3)(4)，(1 2)(3)(4)，(1)(2)(3 4)， (1 2)(3 4)，(1 3)(2 4)，(1 4)(2 3)。G是是S4的有限非空子集，可以验证置换乘法在的有限非空子集，可以验证置换乘法在G上是封闭的，置换乘法满足结合律，上是封闭的，置换乘法满足结合律， 所有元素所有元素的逆都是自身，故的逆都是自身，故G在置换的乘法下做成在置换的乘法下做成1个个4次次置换群。置换群。 2222先把置换表成不相杂轮换之乘先把置换表成不相杂轮换之乘积，然后用一组顺向圈来表示。积，
19、然后用一组顺向圈来表示。每个顺向圈的长度，即圈上所每个顺向圈的长度，即圈上所含的元素个数，就是该圈所表含的元素个数，就是该圈所表示的轮换的长度。示的轮换的长度。 一个一个n元置换对应一组顺向圈，这组圈的元置换对应一组顺向圈，这组圈的长度之总和为长度之总和为n；反之，一组顺向圈表示反之，一组顺向圈表示一置换，置换的元素个数就是组中各图长一置换，置换的元素个数就是组中各图长度之总和。度之总和。 6.3.3 置换的顺向圈表示置换的顺向圈表示 2 21 14 43 32323n元置换元置换对应图形表达式对应图形表达式 (图型图型)G= =1z1+2z2+rzrzi表示长度为表示长度为i的圈，的圈，i表
20、示如此的表示如此的zi的个数；的个数；诸诸为非负整数，为非负整数，01n，n=0或或1；1+22+rr=n 例：例：M=1,2,3,4,5,6,7,8， =(1 6)(3 4 5)(2 8)，G=z1+2z2+z3。11+22+31=8 6.3.3 置换的顺向圈表示置换的顺向圈表示24246.3.4 置换的奇偶性置换的奇偶性 设设表为表为k个不相杂的轮换的乘积个不相杂的轮换的乘积(包括长包括长度为度为1的轮换在内的轮换在内)，长度分别为，长度分别为r1, r2, , rk。若若 = n-k为奇数为奇数(偶数偶数)，则称，则称为为奇置换奇置换(偶置换偶置换)。例如例如: := 是偶置换是偶置换
21、= 是奇置换是奇置换 2525因因每每个个长长度度为为r的的轮轮换换可可写写成成r-1个个对对换换的的乘积：乘积：(a1 a2ar)=(a1 ar)(a1 ar-1)(a1 a3)(a1 a2)于是于是可写成可写成 =n-k个对换的乘个对换的乘积。积。结论：结论：奇置换可表为奇数个对换之积，奇置换可表为奇数个对换之积，偶置换可表为偶数个对换之积。偶置换可表为偶数个对换之积。 6.3.4 置换的奇偶性置换的奇偶性 2626例：例：= (1 3 6 7 8 4 2)(5 9)n-k=9-2=7，为奇置换。，为奇置换。(1 3 6 7 8 4 2)(5 9)= (1 2)(1 4)(1 8)(1 7
22、)(1 6)(1 3)(5 9)可表为可表为7个对换之积。个对换之积。2727每个置换都能分解为对换的乘积，但偶置每个置换都能分解为对换的乘积，但偶置换只能分解为偶数个对换的乘积，奇置换换只能分解为偶数个对换的乘积，奇置换只能分解为奇数个对换的乘积。只能分解为奇数个对换的乘积。证明：证明：只需证明只需证明 “只能分解只能分解”。任取任取Sn，设，设等于等于k个不相杂轮换之积，个不相杂轮换之积，这些轮换分别含这些轮换分别含r1，r2，rk个元素，个元素，于是于是可以写成可以写成 个对换之积，个对换之积，定义置换定义置换的符号的符号sgn如下：如下： sgn= 定理定理6.3.32828显然，偶置
23、换的符号为显然，偶置换的符号为1，奇置换的符号，奇置换的符号为为-1。首先证明首先证明 sgn=sgnsgn (4)设设等于等于k个不相杂轮换之积，个不相杂轮换之积， 等于等于h个不相杂轮换之积，个不相杂轮换之积，且且写成对换中最后一个为写成对换中最后一个为(a b)。以。以(a b)乘乘而看其变化。而看其变化。证明：证明：2929(1)若若a和和b在在的两个不同的轮换之内：的两个不同的轮换之内： =(a a1 as)(b b1 bi) 则则(a b)=(a a1 as b b1 bi) 即即(a b)为为(h-1)个不相杂轮换之积个不相杂轮换之积, 故：故：sgn(a b)=(-1)n-(h
24、-1)=-(-1)n-h=-sgn(2)若若a和和b在在的同一个轮换之内：的同一个轮换之内：=(a a1 as b b1 bi)则则(a b)=(a a1 as)(b b1 bi) 即即(a b)为为(h+1)个不相杂轮换之积个不相杂轮换之积,故：故：sgn(a b)=(-1)n-(h+1) =-(-1)n-h=-sgn证明：证明：3030总总之之，以以一一个个对对换换乘乘则则将将sgn变变号号，今今等等于于(n-k)个个对对换换之之积积，故故以以乘乘将将sgn变号变号(n-k)次，即次，即sgn= (-1)n-k sgn=sgnsgn因此，因此，和和的奇偶性与其乘积的奇偶性与其乘积的奇偶性的
25、奇偶性之关系如下：之关系如下：偶偶偶偶= =偶，奇偶，奇奇奇= =偶，偶，奇奇偶偶= =奇，偶奇，偶奇奇= =奇。奇。 因为对换是奇置换，所以奇数个对换之积因为对换是奇置换，所以奇数个对换之积只能是奇置换，偶数个对换之积只能是偶只能是奇置换，偶数个对换之积只能是偶置换。置换。证毕。证毕。3131设设M的元数为的元数为n，若，若n1，则奇置换的个数则奇置换的个数和偶置换的个数相等，都等于和偶置换的个数相等，都等于 。证明：证明：命命1,2, ,m (5)为为M的的所所有有偶偶置置换换，由由于于n1，故故可可取取到到一个对换一个对换，而作下列乘积：而作下列乘积： 1,2, ,m (6)显然显然i是
26、奇置换，而且诸是奇置换，而且诸i互不相同，互不相同，即即(6)中无重复元素。反证，若中无重复元素。反证，若i=j，则以，则以-1左乘得左乘得i=j，矛盾，这说明矛盾，这说明M的的奇置换不少于偶置换奇置换不少于偶置换。定理定理6.3.43232反之，若反之，若为为M的任意奇置换，则的任意奇置换，则-1为偶置换，故必等于某一个为偶置换，故必等于某一个i，-1=i，因而因而=i。这说明这说明M的任意奇置换必在的任意奇置换必在(6)中，中，(6)就就是是M的所有奇置换，的所有奇置换，M的的奇置换不多于偶奇置换不多于偶置换。置换。于是奇置换的个数和偶置换的个数相等，于是奇置换的个数和偶置换的个数相等，各
27、占置换总数各占置换总数n！的一半。的一半。 证明：证明：3333定义定义之奇偶性的整数之奇偶性的整数 = n-k称为称为的的定性数定性数。定理定理6.3.5 设设n元置换元置换有图型有图型G=则则之定性数等于之定性数等于=证明：证明：n=1+22+rr+nnk=1+2+r+n n-k=2+(r-1)r+(n-1)n =置换的定性数置换的定性数3434图图1是一个是一个2 2的方格图形，它可以围绕中心旋的方格图形，它可以围绕中心旋转，也可以围绕对称轴翻转，但要求经过这样转，也可以围绕对称轴翻转，但要求经过这样的变动以后的图形要与原来的图形重合的变动以后的图形要与原来的图形重合(方格中方格中的数字
28、可以改变的数字可以改变)。例如，当它绕中心。例如，当它绕中心逆时针旋转逆时针旋转900以后，原来的数字以后，原来的数字1,2,3,4分别变为分别变为2,3,4和和1, 可以把这个变化可以把这个变化看作是看作是1,2,3,4上的上的一个置换一个置换(1 2 3 4)。 图图图图1 1下面给出所有可能的置换：下面给出所有可能的置换：1=(1)(2)(3)(4) 绕中心逆时针转绕中心逆时针转00；2=(1 2 3 4) 绕中心逆时针转绕中心逆时针转900；3=(1 3)(2 4) 绕中心逆时针转绕中心逆时针转1800；1 12 24 43 3习题：习题：35354=(1 4 3 2)绕中心逆时针转绕
29、中心逆时针转2700；5=(1 2)(3 4)绕垂直轴翻转绕垂直轴翻转1800；6=(1 4)(2 3)绕水平轴翻转绕水平轴翻转1800 ；7=(2 4)绕西北绕西北-东南轴翻转东南轴翻转1800；8=(1 3)绕西南绕西南-东北轴翻转东北轴翻转1800。表表1给出运算表。令给出运算表。令D4=1, 2, 8，易，易见见D4关于置换的乘法是封闭的。置换乘法满足关于置换的乘法是封闭的。置换乘法满足结合律。结合律。1是单位元。是单位元。1-1=1, 2-1=4, 3-1=3, 4-1=2, 5-1=5, 6-1=6, 7-1=7, 8-1=8,D4关于置换的乘法构成一个关于置换的乘法构成一个4次置
30、换群。次置换群。3636表表1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 2 2 2 2 3 3 4 4 1 1 8 8 7 7 5 5 6 6 3 3 3 3 4 4 1 1 2 2 6 6 5 5 8 8 7 7 4 4 4 4 1 1 2 2 3 3 7 7 8 8 6 6 5 5 5 5 5 5 7 7 6 6 8 8 1 1 3 3 2 2 4 4 6 6 6 6 8 8 5 5 7 7 3 3 1 1 4 4 2 2 7 7 7 7 6 6 8 8 5 5 4 4 2 2 1 1 3 3
31、8 8 8 8 5 5 7 7 6 6 2 2 4 4 3 3 1 13737例：例：设设G=a1,a2,an为群，则为群，则G的运算表的每行的运算表的每行每列都是每列都是G中元素的一个置换。中元素的一个置换。证明：证明：对任意的对任意的i=1,2,n，设，设ai1,ai2,ain是是运算表的第运算表的第i行，假设行，假设ais=ait，根据运算表的定，根据运算表的定义有义有aias=aiat。由于群中运算满足消去律，因此。由于群中运算满足消去律，因此有有as=at，与，与G中有中有n个元素矛盾，这就证明了个元素矛盾，这就证明了G中任意元素在运算表的一行中至多出现一次。中任意元素在运算表的一行
32、中至多出现一次。任取任取G中中as(对于对于i=1,2,n)方程方程aix=as在在G中有中有解，若解，若x=at，则，则as出现在第出现在第i行第行第t列上，因此列上，因此as在运算表的每一行至少出现一次在运算表的每一行至少出现一次。综上所述证。综上所述证毕。毕。3838作业作业31. P208-12. 设设 =(1 2 3)， =(2 3)，计算，计算 -1。3. 令令M是除去是除去0，1以外的全体实数作成的以外的全体实数作成的集合，集合，G为为M的以下六个变换作成的集合：的以下六个变换作成的集合：1(x)=x, 2(x)=1/x, 3(x)=1-x, 4(x)=1/(1-x), 5(x)=(x-1)/x, 6(x)=x/(x-1).G在变换的乘法下是否作成群？如果不是，在变换的乘法下是否作成群？如果不是，请给出原因；若是，给出以上每个元素的请给出原因；若是，给出以上每个元素的逆元。逆元。 3939
