置換群離散數(shù)學PPT課件

1、置換的例設M=1，2，3，則有3！=6個3元置換，所有元素不動：1一個元素不動：2 34 0個元素不動：5 6故，S3 = 1，2，3，4，5，6321321231321123321312321132321213321第1頁/共37頁置換的乘法對M中任意元素a及M的任意兩個置換，規(guī)定（a）=（a）。例. 設 ，則= ， = = 43124321214343211243432121344321第2頁/共37頁v 滿足結合律：()=()，, Sn。v Sn中有單位元: n元恒等置換，設為0，有：0=0 ，Snv 每個n元置換在Sn 中都有逆元素: = 置換的乘法的性質(zhì)12121nnbbbaaann

2、aaabbb2121第3頁/共37頁 例. 設 ，求2， -1， -1 。 并解方程x=, y = .解： 2= = =-1= -1=x=-1 = y =-1=15342543213415254321153425432115342543212135454321352145432123145543214231554321245135432132541543214512354321第4頁/共37頁n次對稱群n元置換的全體作成的集合Sn對置換的乘法作成一個群，稱為n 次對稱群。 （n 次對稱群的任一子群稱為n 次置換群。 ） n=1，M=a， S1= 在置換的乘法下作成1次對稱群，為Abel群。 n

3、=2, M=a，b, S2= , 在置換的乘法下作成2次對稱群，為Abel群。 當n 3時，Sn不是Abel群。aababaabbannnnnn213321123321312321nnnnnn132321312321123321第5頁/共37頁輪換. 設是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 置換的輪換表法輪換的定義651423654321第6頁/共37頁可以把a a1 1， ，a a

4、r r中的任意元素a ai i排在頭一位而改寫成 （a ai i a ai+1 i+1 a ar r a a1 1 a ai i- -1 1）第7頁/共37頁結論：設（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

5、)(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第8頁/共37頁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）是不相

6、雜輪換，（1 3 4）（2 5）= （2 5） （1 3 4）不相雜輪換第9頁/共37頁不相雜輪換結論：若和是M的兩個不相雜的輪換， 則 =.證明：設=（a1ar），=（b1bs）， 和不相雜。命為M的任意元. 若a1,ar，設=ai，則 ()=(ai)=(ai) = ai+1， ()=(ai)=(ai+1)=ai+1 。 i=r時, ai+1 應改為 a1 。 故,()=()。第10頁/共37頁不相雜輪換 同理可證，若b1,bs，也有（）=（）。 若 a1,ar,b1,bs, 于是， （）=（）=， （）=（）=。 綜上，（）=（），故 =。 第11頁/共37頁定理6.3.2 任意置換恰有一

7、法寫成不相雜輪換的乘積。即，任意置換可以寫成不相雜輪換的乘積（可表性），如果不考慮乘積的順序，則寫法是唯一的(唯一性)。例. =(1 3 5 2)(4)(6 8)(7)=(3 5 2 1)(7)(8 6)(4)置換的這種表法稱為置換的輪換表法去掉單輪換為輪換表法的省略形式：(1 3 5 2) (6 8)6782451387654321第12頁/共37頁證明： （1）可表性。設是M上置換，任取a1M。 若（a1） = a1，則有輪換（a1）。 設（a1）= a2， （a2）= a3，。由于M有限，故到某一個元素ar，(ar)必然不能再是新的元素,即(ar) a1,ar。由于是一對一的，已有（ai

8、）= ai+1,i=1,2,r-1，所以(ar)只能是a1.于是得到一個輪換（a1ar）。第13頁/共37頁 若M已經(jīng)沒有另外的元素，則就等于這個輪換，否則設b1不在a1，ar之內(nèi)，則同樣作法又可得到一個輪換（b1bs）.因為a1，ar各自已有變到它的元素，所以b1，bs中不會有a1，ar出現(xiàn)，即這兩個輪換不相雜。若M的元素已盡，則就等于這兩個輪換的乘積，否則如上又可得到一個輪換。如此類推，由于M有限，最后必得=(a1ar)(b1bs) (c1ct) (1) 即表成了不相雜輪換的乘積。 第14頁/共37頁（2）唯一性.設又可表為不相雜的輪換的乘積如下：=(a1ar )(b1bs) (c1ct)

9、 (2)考慮(1)(1)式中任意輪換( (a1ar) )。 不妨設 a1 a1ar ，且a1a。于是，a2=（a1）=（a1）= a2 ， a3=（a2）=（a2）= a3 ，證明第15頁/共37頁證明 可見，（a1ar）必和（a1ar）完全相同。這就是說，（1）中的任意輪換必出現(xiàn)在（2）中，同樣（2）中的任意輪換必出現(xiàn)在（1）中，因之，（1）和（2）一樣，最多排列方法不同，但不相雜的輪換相乘適合交換律，所以排列的次序本來是可以任意顛倒的。 證畢。第16頁/共37頁例. 設M=1,2,3,4，M的24個置換可寫成：I；(1 2), (1 3), (1 4), (2 3), (2 4), (3

10、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)。第17頁/共37頁輪換的長度 其中所含的元素個數(shù)。 （a1 a2 ar）長度為r。對換 長度為的輪換。結論. 任意輪換可以寫成對換的乘積。證明： 往證(a1 a2ar)(a1 ar)(a1 ar-)(a1 a3)(a1 a2) (3)對r進行歸納，當r=2

11、時命題顯然成立。假設r=t時結論為真，考慮=(a1 a2 at at+1)的情況。對換第18頁/共37頁往證(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

12、；第19頁/共37頁 若l a1,a2,at+1，則(l)=l1 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) )。第20頁/共37頁例 設多項式f=(x1+

13、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 1個4次置換群。 第21頁/共37頁例圖1是一個2 2的方格圖形，它可以圍繞中心旋轉，也可以圍繞對稱軸翻轉，但要求經(jīng)過這樣的變動以后的圖形要與原來的圖形重合（方格

14、中的數(shù)字可以改變）。例如，當它繞中心逆時針旋轉900以后，原來的數(shù)字1，2，3，4分別變?yōu)?，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；1243第22頁/共37頁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) 繞西南-東北軸翻轉

15、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次置換群。第23頁/共37頁12345678112345678223418756334126587441237865557681324668573142776854213885762431第24頁/共37頁先把置換表成不相雜輪換之乘積，然后用一組順向圈來表示。每個順向圈的長度，即圈上所含的元素個數(shù)，就是該圈所表示的輪換的長度。

16、一個n元置換對應一組順向圈，這組圈的長度之總和為n；反之，一組順向圈表示一置換，置換的元素個數(shù)就是組中各圖長度之總和。 6.3.3 置換的順向圈表示 第25頁/共37頁 n元置換對應圖形表達式 （圖型）G = =1z1 +2z2 + +rzrzi表示長度為i的圈, , i表示如此的zi的個數(shù); ; 諸為非負整數(shù), 01n,n=0或1； 1+22+rr = n 例.M=.M=1,2,3,4,5,6,7,8,=(1 6)(3 4 5)(2 8)， G= z z1 1+ + 2z z2 2+z+z3 3。11+22+31=8 6.3.3 置換的順向圈表示niiiz1第26頁/共37頁設表為k個不相雜

17、的輪換的乘積(包括長度為1的輪換在內(nèi)) )，長度分別為r1，r2，rk。 若 = n-k為奇數(shù)（偶數(shù)），則稱為奇置換（偶置換）。 6.3.4 置換的奇偶性 kjjr1) 1(第27頁/共37頁因每個長度為r的輪換可寫成r-1個對換的乘積：(a1 a2 ar)(a1 ar)(a1 ar)(a1 a3)(a1 a2) 于是可寫成 =n-k 個對換的乘積。 結論：奇置換可表為奇數(shù)個對換之積， 偶置換可表為偶數(shù)個對換之積。 kjjr1) 1(第28頁/共37頁=(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)

18、(1 6)(1 3)(5 9)7個對換。548792613987654321第29頁/共37頁 定理6.3.3 每個置換都能分解為對換的乘積，但偶置換只能分解為偶數(shù)個對換的乘積，奇置換只能分解為奇數(shù)個對換的乘積。證明. .只需證明 “只能分解”。任取SSn n，設等于k個不相雜輪換之積，這些輪換分別含r1，r2，rk個元素，于是可以寫成 個對換之積，定義置換的符號sgnsgn如下： sgnsgn= = kjjr1) 1(kjjr1)1() 1(第30頁/共37頁 顯然，偶置換的符號為1，奇置換的符號為-1。 首先證明 sgn=sgnsgn （4） 設等于k個不相雜輪換之積， 等于h個不相雜輪換之積， 且寫成對換中最后一個為（a b）。以（a b）乘而看其變化。第31頁/共37頁(1 1)若a和b在的兩個不同的輪換之內(nèi): =（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在的同一個輪換之內(nèi): =（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第32頁/共37頁 總