离散数学II课件：6_3置换群

1、6.3 置 换 群,6.3.1 置换的定义 6.3.2 置换的轮换表法 6.3.3 置换的顺向圈表示 6.3.4 置换的奇偶性,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元恒等置换。 Sn: n！个置换作成的集合。,置换的例,设M=1，2，3，则有3！=6个3元置换， 所有元素不动：1 一个元素不动：2 3 4 0个元素不动：5 6 故，S3 = 1，2，3，4，

2、5，6,置换的乘法,对M中任意元素a及M的任意两个置换，规定（a）=（a）。 例. 设 ， 则= ， = ,满足结合律：()=()，, Sn。 Sn中有单位元: n元恒等置换，设为0，有：0=0 ，Sn 每个n元置换在Sn 中都有逆元素: =,置换的乘法的性质,n次对称群,n元置换的全体作成的集合Sn对置换的乘法作成一个群，称为n 次对称群。 n=1，M=a， S1= 在置换的乘法作成1次对称群，为Abel群。 n=2, M=a，b, S2= , .在置换的乘法作成2次对称群，为Abel群。 当n 3时，Sn不是交换群。,轮换. 设是M的置换，若可取到M的元素a1, ,ar 使 (a1)a2,

3、(a2)=a3,(ar-1)=ar,(ar)=a1， 而不变M的其余的元素（自己变换到本身），则称为一个轮换， 记为 （a1 a2 ar ）,6.3.2 置换的轮换表法轮换的定义,例 =（134）=（341）=（413）,M的两个轮换 =(a1ar)和=(b1bs)说 是不相杂或不相交，如果 a1,ar和b1,bs 都不相同(即a1, ,arb1,bs= ),不相杂轮换,不相杂轮换,结论：若和是M的两个不相杂的轮换，则=. 证明：设=（a1ar），=（b1bs）， 和不相杂。命为M的任意元 若a1,ar，设=ai，则 ()=(ai)=(ai)=ai+1， ()=(ai)=(ai+1)= ai+

4、1 。 i=r时,ai+1应改为a1。 故,()=()。,不相杂轮换,同理可证，若 b1,bs， ，也有（）=（）。 设 a1,ar,b1,bs, 于是， （）=（）=， （）=（）=。 综上，（）=（），故 =。,定理6.3.2 任意置换恰有一法写成不相杂的 轮换乘积。即，任意置换可以写成不相杂的 轮换的乘积（可表性），如果不考虑乘积的顺 序，则写法是唯一的(唯一性)。,不相杂轮换,证明： （1）可表性。 设是M上置换，任取a1M。 若（a1） = a1，则有轮换（a1）。 设（a1）= a2， （a2）= a3，。由于M有限，故到某一个元素ar，(ar)必然不能再是新的元素,即(ar) a

5、1,ar。由于是一对一的，已有（ai）= ai+1，i=1，2， ，r-1，所以(ar)只能是a1。于是得到一个轮换（a1ar）。,若M已经没有另外的元素，则就等于这个轮换，否则设b1不在a1，ar之内，则同样作法又可得到一个轮换（b1bs）。因为a1，ar各自已有变到它的元素，所以b1，bs中不会有a1，ar出现，即这两个轮换不相杂。若M的元素已尽，则就等于这两个轮换的乘积，否则如上又可得到一个轮换。如此类推，由于M有限，最后必得 =(a1ar)(b1bs) (c1ct) (1) 即表成了不相杂的轮换的乘积。,证明,（2）唯一性. 设又可表为不相杂的轮换的乘积如下： =(a1ar)(b1bs

6、) (c1ct) (2) 考虑(1)式中任意轮换(a1ar)。 不妨设 a1a1ar，且a1a。 于是，a2=（a1）=（a1）= a2， a3=（a2）=（a2）= a3，,证明,证明 可见，（a1ar）必和（a1ar）完全相同。这就是说，（1）中的任意轮换必出现在（2）中，同样（2）中的任意轮换必出现在（1）中，因之，（1）和（2）一样，最多排列的方法不同，但不相杂的轮换相乘适合交换律，所以排列的次序本来是可以任意颠倒的。,例. 设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

7、 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)。,轮换的长度 其中所含的元素个数。 （a1a2ar）长度为r。 对换 长度为的轮换。 结论. 任意轮换可以写成对换的乘积。 (a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) (3) 证明：对r进行归纳，当r=2时命题显然成立，假设r=t时结论为真，考虑=(a1a2arat+1)的情况。令1=(a

8、1at+1)， 2=(a1a2at)，下面证明= 1 2。,对换,任取lS,若l a1,a2,at-1，不妨设l=am,则(l)= (am)=am+1， 1 2(l)= 1 (am+1)=am+1； 若l=at，则(l)=at+1= 1(a1)= 1 (2(at)= 1 2(at)= 1 2(l)； 若l=at+1，则(l)= (at+1)= a1=1 (at+1)= 1 (2(at+1)= 1 2(l)； 若l a1,a2,at+1，则 (l)=l= 1(l)= 1 (2(l)= 1 2(l)，即 = 1 2 =(a1at+1) 2。由归纳假设， 2=(a1a2at)，可表为(a1at)(a

9、1at-1)(a1a2)，所以= (a1at+1) (a1at)(a1at-1)(a1a2)，归纳法完成。,有兴趣的同学可以采用直接证明的方法进行证明。 推论. 对任意置换，有一法(未必只有一法)可将其写成一些对换的乘积。 ()=(1 2)(1 3)(1 3)=(2 3)(1 3)(2 3)。,先把置换表成不相杂轮换之乘积，然后用一组顺向圈来表示 每个顺向圈的长度，即圈上所含的元素个数，就是该圈所表示的轮换的长度。 一个n元置换对应一组顺向圈，这组圈的长度之总和为n；反之，一组顺向圈表示一置换，置换的元素个数就是组中各图长度之总和。,6.3.3 置换的顺向圈表示,1 3 2 4,n元置换对应图

10、形表达式 （图型） G = =1z1 +2z2 + +rzr zi表示长度为i的圈,而zi的系数i表示如此的zi的个 数;诸为非负整数, 01n,n=0或1； 1+22+rr = n,6.3.3 置换的顺向圈表示,设表为k个不相杂的轮换的乘积(包 括长度为1的轮换在内)，长度分别为 r1，r2，rk。 若 =n-k为奇数（偶数），则称为奇置换（偶置换）。 例如 = =（134）是偶置换 是奇置换,6.3.4 置换的奇偶性,因每个长度为r的轮换可写成r-1个对换的乘 积： (a1a2ar)(a1ar)(a1ar)(a1 a3)(a1a2) 于是可写成 =n-k 个对换的乘积。 结论：奇置换可表为

11、奇数个对换之积， 偶置换可表为偶数个对换之积。,定理6.3.3 每个置换都能分解为对换的乘积，但偶置换只能分解为偶数个对换的乘积，奇置换只能分解为奇数个对换的乘积。 证明.只需证明 “只能分解”。 任取Sn，设等于k个轮换之积，这些 轮换分别含r1，r2，rk个元素，于是 可以写成 个对换之积， 定义置换的符号sgn如下： sgn=,显然，偶置换的符号为1，奇置换的符 号为-1。 首先证明 sgn=sgnsgn （4） 设等于k个不相杂轮换之积，等于h个不相杂轮换之积，且写成对换乘积时最后一个对换为（a b）。 以（a b）乘而看其变化。,(1)若a和b在的两个不同的轮换之内: =（aa1as

12、）（bb1bi） 则 （ab）=（aa1asbb1bi） 若为h个不相杂轮换之积，则（ab）为（h-1）个不相杂轮换之积, 故，sgn(ab)= (-1)n-(h-1) = -(-1)n-h = -sgn (2)若a和b在的同一个轮换之内: =（aa1asbb1bi） 则（ab）=（aa1as）（bb1bi） 故， sgn(ab)= (-1)n-(h+1) = -(-1)n-h = -sgn,补充证明,(ab)=(ab)(aa1as)(bb1bi) =,总之，以一个对换乘则将sgn变号， 今等于（n-k）个对换之积，故以乘 将sgn变号（n-k）次，即 sgn= (-1)n-ksgn=sgns

13、gn 因此，和的奇偶性与其乘积的奇偶性之关系如下： 偶偶=偶， 奇奇=偶， 奇偶=奇， 偶奇=奇。 因为对换是奇置换，所以只有奇数个 对换之积是奇置换，偶数个对换之积是偶 置换。,定理6.3.4 设M的元数为n，若n1，则奇置换的个数和偶置换的个数相等，都等于 。 证明：命 1，2，m （5） 为M的所有偶置换，由于n1，故可取到一个对换，而作下列乘积： 1，2，m （6） 显然i是奇置换，而且诸i互不相同， 即（6）中无重复元素。反证，若i=j，则以-1左乘得i=j，矛盾，这说明M的奇置换不少于偶置换。,反之，若为M的任意奇置换，则 -1为偶置换，故必等于某一个i， -1=i，因而=i，这说

14、明M的 任意奇置换必在（6）中，（6）就是M的 所有奇置换，M的奇置换不多于偶置换。 于是奇置换的个数和偶置换的个数相等， 各占置换总数n！的一半。,定义之奇偶性的整数 = n-k称为的定性数。 定理6.3.5 设n元置换有图型G= 则之定性数等于= 证明.n=1+22+rr+nn k=1+2+r+n n-k=2+（r-1）r+（n-1）n =,置换的定性数,例子,图1是一个22的方格图形，它可以围绕中心旋转，也可以围绕对称轴翻转，但要求经过这样的变动以后的图形要与原来的图形重合（方格中的数字可以改变）。例如，当它绕中心逆 时针旋转900以后，原来的数字1，2， 3，4分别变为2，3，4和1，

15、可以把 这个变化看作是1，2，3，4上的 图1 一个置换（4321）。下面给出所有可能的置换： 1=(1) 绕中心顺时针转00； 2=(1234) 绕中心顺时针转900； 3=(13)(24) 绕中心顺时针转1800；,4=(1432) 绕中心顺时针转2700； 5=(12)(34) 绕垂直轴翻转1800； 6=(14) (23) 绕水平轴翻转1800 ； 7=(24) 绕西北-东南轴翻转1800； 8=(13) 绕西南-东北轴翻转1800。 表1给出它们的运算表。令D4=1, 2, 8，易见D4关于置换的乘法是封闭的。 1=(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,构成一个群，且是S4的子群。,表1,例子,例 设