§6.3置换群(离散数学).ppt

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，5，6,置换的乘法,对M中任意元素a及M的任意两个置换，规定（a）=（a）。 例. 设 ， 则= ， = ,满足结合律：()=()，, Sn。 Sn中有单位元: n元恒等置换，设为0，有：0=0 ，Sn 每个n元置换在Sn 中都有逆元素: =,置换的乘法的性质,例. 设 ， 求2， -1， -1 。 并解方程x=, y = . 解： 2= = = = -1= -1= x=-1 = y =-1=,n次对称群,n元置换的全体作成的集合Sn对置换的乘法作成一个群，称为n 次对称群。 （n 次对称群的任一子群称为n 次置换群。 ） n=1，M=a， S1= 在置换的乘法下作成1次对称群，为Abel群。 n=2, M=a，b, S2= , 在置换的乘法下作成2次对称群，为Abel群。 当n 3时， Sn不是Abel群。,轮换. 设是M的置换，若可取到M的元素a1, ,ar 使 (a1)a2,(a2)=a3,(ar-1)=ar,(ar)=a1， 而不变M的其余的元素，则称为一个轮换， 记为 （a1 a2 ar ） 例. = =（1 3 4）=（3 4 1）=（4 1 3）,6.3.2 置换的轮换表法 轮换的定义,可以把a1， ，ar中的任意元素ai排在头一位而改写成 （ai ai+1 ar a1 ai-1）,结论：设（a1 a2 ar ） 是M的轮换，则 （a1 a2 ar ）-1 =（ ar a2 a1 ） 证明：往证（ ar a2 a1 ） （a1 a2 ar ）=I 命为M的任意元 若a1,ar-1，设=ai，则 (ar a2 a1)(a1 a2 ar) (ai)=(ara2 a1) (ai+1)= ai 若= ar ,则 (ar a2 a1)(a1 a2 ar) (ar)= (ar a2 a1)(a1)= ar a1,ar，则(ar a2 a1)(a1 a2 ar) (x)=x 总之， (ar a2 a1) (a1 a2 ar)(x)=I(x)=x 即，（ ar a2 a1 ） （a1 a2 ar ）=I 同理， （a1 a2 ar） （ar a2 a1） =I,M的两个轮换 =(a1ar)和=(b1bs)说 是不相杂或不相交，如果 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）=（1 3 7 6 4）， （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）,不相杂轮换,不相杂轮换,结论：若和是M的两个不相杂的轮换， 则 =. 证明：设=（a1ar），=（b1bs）， 和不相杂。命为M的任意元. 若a1,ar，设=ai，则 ()=(ai)=(ai) = ai+1， ()=(ai)=(ai+1)=ai+1 。 i=r时, ai+1 应改为 a1 。 故,()=()。,不相杂轮换,同理可证，若b1,bs，也有（）=（）。 若 a1,ar,b1,bs, 于是， （）=（）=， （）=（）=。 综上，（）=（），故 =。,定理6.3.2 任意置换恰有一法写成不相杂轮 换的乘积。即，任意置换可以写成不相杂轮 换的乘积（可表性），如果不考虑乘积的顺序， 则写法是唯一的(唯一性)。 例. =(1 3 5 2)(4)(6 8)(7)=(3 5 2 1)(7)(8 6)(4) 置换的这种表法称为置换的轮换表法 去掉单轮换为轮换表法的省略形式： (1 3 5 2) (6 8),证明： （1）可表性。 设是M上置换，任取a1M。 若（a1） = a1，则有轮换（a1）。 设（a1）= a2， （a2）= a3，。由于M 有限，故到某一个元素ar，(ar)必然不能再是 新的元素,即(ar) a1,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) (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 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)。,轮换的长度 其中所含的元素个数。 （a1 a2 ar）长度为r。 对换 长度为的轮换。 结论. 任意轮换可以写成对换的乘积。 证明： 往证 (a1 a2ar)(a1 ar)(a1 ar-)(a1 a3)(a1 a2) (3) 对r进行归纳，当r=2时命题显然成立。 假设r=t时结论为真， 考虑=(a1 a2 at at+1)的情况。,对换,往证(a1a2atat+1)= (a1at+1) (a1a2at) 令1=(a1 at+1)，2=(a1 a2 at)， 下面证明= 1 2。 任取lM, 若l a1,a2,at-1，不妨设l=am,则 (l)= (am)=am+1， 1 2(l)= 1 (am+1)=am+1； 若l=at，则 (l)=at+1 12(l)=12(at)=1(2(at)=1(a1)=at+1； 若l=at+1，则 (l)= (at+1)= a1 1 2(l) = 1 (2(at+1) = 1 (at+1) = a1 ；,若l a1,a2,at+1，则 (l)=l 1 2(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 at+1) (a1 at)(a1 at-1)(a1 a2)，归纳完成。 还可以采用直接证明的方法进行证明。 推论. 对任意置换，有一法(未必只有一法)可将其写成一些对换的乘积。 (2)=(1 2)(1 3)(1 3)=(2 3)(1 3)(2 3)。,例 设多项式f=(x1+x2)(x3+x4)，找出使f保持不变的所有下标的置换，这些置换在置换的 乘法下是否构成群？,解：由加法交换律和乘法交换律可得到使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次 置换群。,例,图1是一个22的方格图形，它可以围绕中心旋转， 也可以围绕对称轴翻转，但要求经过这样的变动 以后的图形要与原来的图形重合（方格中的数字 可以改变）。例如，当它绕中心逆 时针旋转900以后，原来的数字1，2， 3，4分别变为2，3，4和1，可以把 这个变化看作是1，2，3，4上的 图1 一个置换（1 2 3 4）。下面给出所有可能的置换： 1=(1)(2)(3)(4) 绕中心逆时针转00； 2=(1 2 3 4) 绕中心逆时针转900； 3=(1 3)(2 4) 绕中心逆时针转1800；,4=(1 4 3 2) 绕中心逆时针转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次置换群。,表1,先把置换表成不相杂轮换之乘积，然后用一组顺向圈来表示。 每个顺向圈的长度，即圈上所含的元素个数，就是该圈所表示的轮换的长度。 一个n元置换对应一组顺向圈，这组圈的长度之总和为n；反之，一组顺向圈表示一置换，置换的元素个数就是组中各图长度之总和。,6.3.3 置换的顺向圈表示,n元置换对应图形表达式 （图型） G = =1z1 +2z2 + +rzr zi表示长度为i的圈, i表示如此的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 置换的顺向圈表示,设表为k个不相杂的轮换的乘积(包 括长度为1的轮换在内)，长度分别为 r1，r2，rk。 若 = n-k为奇数（偶数），则称为奇置换（偶置换）。,6.3.4 置换的奇偶性,因每个长度为r的轮换可写成r-1个对换的乘 积： (a1 a2 ar)(a1 ar)(a1 ar)(a1 a3)(a1 a2) 于是可写成 =n-k 个对换的乘积。 结论：奇置换可表为奇数个对换之积， 偶置换可表为偶数个对换之积。,=(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)(1 6)(1 3)(5 9) 7个对换。,定理6.3.3 每个置换都能分解为对换的乘积， 但偶置换只能分解为偶数个对换的乘积，奇 置换只能分解为奇数个对换的乘积。 证明.只需证明 “只能分解”。 任取Sn，设等于k个不相杂轮换之积， 这些轮换分别含r1，r2，rk个元素，于是 可以写成 个对换之积， 定义置换的符号sgn如下： sgn=,显然，偶置换的符号为1，奇置换的符 号为-1。 首先证明 sgn=sgnsgn （4） 设等于k个不相杂轮换之积， 等于h个不相杂轮换之积， 且写成对换中最后一个为（a b）。 以（a b）乘而看其变化。,(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-1) = -(-1)n-h = -sgn (2)若a和b在的同一个轮换之内: =（a a1 as b b1 bi） 则（a b）=（a a1 as）（b b1 bi） 故， sgn(a b)= (-1)n-(h+1) = -(-1)n-h = -sgn,总之，以一个对换乘则将sgn变号， 今等于（n-k）个对换之积，故以乘 将sgn变号（n-k）次，即 sgn= (-1)n-k sgn=sgnsgn 因此，和的奇偶性与其乘积的奇偶性之关系如下： 偶偶=偶， 奇奇=偶， 奇偶=奇， 偶奇=奇。 因为对换是奇置换，所以只有奇数个 对换之积是奇置换，偶数个对换之积是偶 置换。,定理6.3.4 设M的元数为n，若n1，则奇置换 的个数和偶置换的个数相等，都等于 。 证明：命 1，2，m （5） 为M的所有偶置换，由于n1，故可取到一个对 换，而作下列乘积： 1，2，m （6） 显然i是奇置