§6.3-離散數(shù)學(xué)-置-換-群

1、§6.3 置 換 群,6.3.1 置換的定義 6.3.2 置換的輪換表法 6.3.3 置換的順向圈表示 6.3.4 置換的奇偶性,6.3.1 置換的定義,定義. 設(shè)M是一個(gè)非空的有限集合，M的一個(gè)一對(duì)一變換稱(chēng)為一個(gè)置換。設(shè)M={a1,a2,…,an},則M的置換σ可簡(jiǎn)記為 σ＝ ，bi=σ(ai)，i=1,2,…,n 結(jié)論：M的置換共

2、有n！個(gè)。 M上的置換稱(chēng)為n元置換。 特別地， 若σ(ai)=ai, i=1,2,…,n,則σ為n元恒等置換。 Sn: n！個(gè)置換作成的集合。,置換的例,設(shè)M={1，2，3}，則有3！=6個(gè)3元置換，所有元素不動(dòng)：σ1＝一個(gè)元素不動(dòng)：σ2＝ σ3＝σ4＝ 0個(gè)元素不動(dòng)：σ5＝ σ6＝故，S3 = {σ1，σ2，σ3，σ4，σ5，σ6}

3、,置換的乘法,對(duì)M中任意元素a及M的任意兩個(gè)置換σ，τ，規(guī)定στ（a）=σ（τ（a））。例. 設(shè)σ＝ ，τ＝則στ= ， τσ= ≠ στ,滿足結(jié)合律：(στ)ρ=σ(τρ)，σ,τ,ρ∈ Sn。Sn中有單位元: n元恒等置換，設(shè)為σ0，有：σ0τ=τσ0 ，τ∈Sn每個(gè)n元置換在Sn 中都有逆元素:

4、 =,置換的乘法的性質(zhì),例. 設(shè)σ＝ ，τ＝求σ2，στ，τσ， σ-1， τ -1 。 并解方程σx=τ, y τ= σ.解： σ2= =στ= τσ=σ-1=

5、 τ-1=x=σ-1 τ= y =στ-1=,n次對(duì)稱(chēng)群,n元置換的全體作成的集合Sn對(duì)置換的乘法作成一個(gè)群，稱(chēng)為n 次對(duì)稱(chēng)群。 （n 次對(duì)稱(chēng)群的任一子群稱(chēng)為n 次置換群。 ） n=1，M={a}， S1={ }—在置換的乘法下作成1次對(duì)稱(chēng)群，為Abel群。 n=2, M={a，b}, S2={ ,

6、 } 在置換的乘法下作成2次對(duì)稱(chēng)群，為Abel群。 當(dāng)n≥ 3時(shí)，Sn不是Abel群。,輪換. 設(shè)σ是M的置換，若可取到M的元素a1, …,ar 使σ(a1)＝a2,σ(a2)=a3,…,σ(ar-1)=ar,σ(ar)=a1，而σ不變M的其余的元素，則σ稱(chēng)為一個(gè)輪換， 記為 （a1 a2 … ar ）例. σ= =（1 3 4）=（3 4 1）=（4 1 3）,6.3.2 置換的輪換表法

7、輪換的定義,可以把a(bǔ)1，… ，ar中的任意元素ai排在頭一位而改寫(xiě)成 （ai ai+1 … ar a1 … ai-1）,,結(jié)論：設(shè)（a1 a2 … ar ） 是M的輪換，則（a1 a2 … ar ）-1 =（ ar … a2 a1 ）證明：往證（ ar … a2 a1 ） （a1 a2 … ar ）=I命χ為M的任意元若χ∈｛a1,…,ar-1｝，設(shè)χ=ai，則 (ar … a2 a1)(a1 a2 … ar)

8、(ai)=(ar…a2 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

9、 a2 … ar） （ar … a2 a1） =I,M的兩個(gè)輪換 σ=(a1…ar)和τ=(b1…bs)說(shuō)是不相雜或不相交，如果 a1,…,ar和b1,…,bs都不相同(即{a1,… ,ar}∩{b1,…,bs}= ?)例.設(shè)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）;

10、 （1 3 4）與（2 5）是不相雜輪換，（1 3 4）（2 5）= （2 5） （1 3 4）,不相雜輪換,不相雜輪換,結(jié)論：若σ和τ是M的兩個(gè)不相雜的輪換， 則 στ=τσ.證明：設(shè)σ=（a1…ar），τ=（b1…bs）， σ和τ不相雜。命χ為M的任意元.若χ∈｛a1,…,ar｝，設(shè)χ=ai，則 στ(χ)=στ(ai)=σ(ai) = ai+1， τσ(χ)=

11、τσ(ai)=τ(ai+1)=ai+1 。 i=r時(shí), ai+1 應(yīng)改為 a1 。 故,στ(χ)=τσ(χ)。,不相雜輪換,同理可證，若χ∈｛b1,…,bs｝，也有στ（χ）=τσ（χ）。若χ ? {a1,…,ar,b1,…,bs}, 于是， στ（χ）=σ（χ）=χ， τσ（χ）=τ（χ）=χ。 綜上，στ（χ）=τσ（χ），故 στ=τσ

12、。,定理6.3.2 任意置換σ恰有一法寫(xiě)成不相雜輪換的乘積。即，任意置換σ可以寫(xiě)成不相雜輪換的乘積（可表性），如果不考慮乘積的順序，則寫(xiě)法是唯一的(唯一性)。例. =(1 3 5 2)(4)(6 8)(7)=(3 5 2 1)(7)(8 6)(4)置換的這種表法稱(chēng)為置換的輪換表法去掉單輪換為輪換表法的省略形式：(1 3 5 2)

13、(6 8),證明： （1）可表性。設(shè)σ是M上置換，任取a1∈M。若σ（a1） = a1，則有輪換（a1）。設(shè)σ（a1）= a2， σ（a2）= a3，…。由于M有限，故到某一個(gè)元素ar，σ(ar)必然不能再是新的元素,即σ(ar) ∈｛a1,…,ar｝。由于σ是一對(duì)一的，已有σ（ai）= ai+1,i=1,2,…,r-1，所以σ(ar)只能是a1.于是得到一個(gè)輪換（a1…ar）。,若M已經(jīng)沒(méi)有另外的元素，則σ就等于這個(gè)

14、輪換，否則設(shè)b1不在a1，…，ar之內(nèi)，則同樣作法又可得到一個(gè)輪換（b1…bs）.因?yàn)閍1，…，ar各自已有變到它的元素，所以b1，…，bs中不會(huì)有a1，…，ar出現(xiàn)，即這兩個(gè)輪換不相雜。若M的元素已盡，則σ就等于這兩個(gè)輪換的乘積，否則如上又可得到一個(gè)輪換。如此類(lèi)推，由于M有限，最后必得σ=(a1…ar)(b1…bs) …(c1…ct) (1) 即σ表成了不相雜輪換的乘積。,（2）唯一性.設(shè)σ又可

15、表為不相雜的輪換的乘積如下：σ=(a’1…a’r’)(b’1…b’s’) …(c’1…c’t’) (2)考慮(1)式中任意輪換(a1…ar)。 不妨設(shè) a1∈{a’1…a’r’}，且a1＝a’１。于是，a2=σ（a1）=σ（a’1）= a’2 ， a3=σ（a2）=σ（a’2）= a’3 ，…，,證明,證明 可見(jiàn)，（a1…ar）必和（a’1…a’r’）完全相同。這就是說(shuō)

16、，（1）中的任意輪換必出現(xiàn)在（2）中，同樣（2）中的任意輪換必出現(xiàn)在（1）中，因之，（1）和（2）一樣，最多排列方法不同，但不相雜的輪換相乘適合交換律，所以排列的次序本來(lái)是可以任意顛倒的。 證畢。,例. 設(shè)M={1,2,3,4}，M的24個(gè)置換可寫(xiě)成：I；(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)；(1 2 3), (1 3 2), (1 2 4), (1 4

17、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)。,輪換的長(zhǎng)度 其中所含的元素個(gè)數(shù)。 （a1 a2… ar）長(zhǎng)度為r。對(duì)換 長(zhǎng)度為２的輪換。結(jié)論. 任意輪換可以寫(xiě)成對(duì)換的乘積

18、。證明： 往證(a1 a2…ar)＝(a1 ar)(a1 ar-１)…(a1 a3)(a1 a2) (3)對(duì)r進(jìn)行歸納，當(dāng)r=2時(shí)命題顯然成立。假設(shè)r=t時(shí)結(jié)論為真，考慮σ=(a1 a2… at at+1)的情況。,對(duì)換,往證(a1a2…atat+1)= (a1at+1) (a1a2…at)令σ1=(a1 at+1)，σ2=(a1 a2… at)，下面證明σ= σ1 σ2。任取l∈M,若l ?{a1,a2

19、,…,at-1}，不妨設(shè)l=am,則σ(l)= σ(am)=am+1， σ1 σ2(l)= σ1 (am+1)=am+1；若l=at，則 σ(l)=at+1 σ1σ2(l)=σ1σ2(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 ；

20、,若l? {a1,a2,…,at+1}，則σ(l)=lσ1 σ2(l) = σ1 (σ2(l)) =σ1(l)= l 。因此，σ= σ1σ2 = (a1 at+1) (a1 a2… at) 。由歸納假設(shè)， (a1 a2… at) =(a1 at)(a1 at-1)…(a1 a2)，所以σ= (a1 at+1) (a1 at)(a1 at-1)…(a1 a2)，歸納完成。還可以采用直接證明的方法進(jìn)行證明。推論. 對(duì)任意置換

21、，有一法(未必只有一法)可將其寫(xiě)成一些對(duì)換的乘積。(１2)=(1 2)(1 3)(1 3)=(2 3)(1 3)(2 3)。,例 設(shè)多項(xiàng)式f=(x1+x2)(x3+x4)，找出使f保持不變的所有下標(biāo)的置換，這些置換在置換的乘法下是否構(gòu)成群？,解：由加法交換律和乘法交換律可得到使f保持不變的所有下標(biāo)的置換的集合為：G={(1)(2)(3)(4)， (1 2)(3)(4)， (1)(2)(3 4)，(1 2)(3 4)

22、， (1 3)(2 4)，(1 4)(2 3)}。G是S4的有限非空子集，可以驗(yàn)證置換乘法在G上是封閉的，置換乘法滿足結(jié)合律， 所有元素的逆都是自身，故G在置換的乘法下做成1個(gè)4次置換群。,例,圖1是一個(gè)2?2的方格圖形，它可以圍繞中心旋轉(zhuǎn)，也可以圍繞對(duì)稱(chēng)軸翻轉(zhuǎn)，但要求經(jīng)過(guò)這樣的變動(dòng)以后的圖形要與原來(lái)的圖形重合（方格中的數(shù)字可以改變）。例如，當(dāng)它繞中心逆時(shí)針旋轉(zhuǎn)900以后，原來(lái)的數(shù)字1，2，3，4分別變?yōu)?/p>

23、2，3，4和1，可以把這個(gè)變化看作是{1，2，3，4}上的 圖1一個(gè)置換（1 2 3 4）。下面給出所有可能的置換：σ1=(1)(2)(3)(4) 繞中心逆時(shí)針轉(zhuǎn)00；σ2=(1 2 3 4) 繞中心逆時(shí)針轉(zhuǎn)900；σ3=(1 3)(2 4) 繞中心逆時(shí)針轉(zhuǎn)1800；,σ4=(1 4 3 2) 繞中心逆

24、時(shí)針轉(zhuǎn)2700；σ5=(1 2)(3 4) 繞垂直軸翻轉(zhuǎn)1800；σ6=(1 4) (2 3) 繞水平軸翻轉(zhuǎn)1800 ；σ7=(2 4) 繞西北---東南軸翻轉(zhuǎn)1800；σ8=(1 3) 繞西南---東北軸翻轉(zhuǎn)1800。表1給出運(yùn)算表。令D4={σ1, σ2,…, σ8}，易見(jiàn)D4關(guān)于置換的乘法是封閉的。置換乘法滿足結(jié)合律

25、。 σ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關(guān)于置換的乘法構(gòu)成一個(gè)4次置換群。,表1,先把置換表成不相雜輪換之乘積，然后用一組順向圈來(lái)表示。每個(gè)順向圈的長(zhǎng)度，即圈上所含的元素個(gè)數(shù)，就是該圈所表示的輪換的長(zhǎng)度。 一個(gè)n元置換對(duì)應(yīng)一組順向圈，這組圈的長(zhǎng)度之總和為n；反之，一組順向圈表示一置換，

26、置換的元素個(gè)數(shù)就是組中各圖長(zhǎng)度之總和。,6.3.3 置換的順向圈表示,n元置換σ對(duì)應(yīng)圖形表達(dá)式 （圖型）Gσ = =α1z1 +α2z2 + … +αrzrzi表示長(zhǎng)度為i的圈, αi表示如此的zi的個(gè)數(shù); 諸α為非負(fù)整數(shù), 0≤α1≤n,αn=0或1； α1+2α2+…+rαr = n 例.M={1,2,3,4,5,6,7,8},σ=(1 6)(3 4 5)(2 8)，

27、 Gσ= z1+ 2z2+z3。1×1+2×2+3×1=8,6.3.3 置換的順向圈表示,設(shè)σ表為k個(gè)不相雜的輪換的乘積(包括長(zhǎng)度為1的輪換在內(nèi))，長(zhǎng)度分別為r1，r2，…，rk。若 = n-k為奇數(shù)（偶數(shù)），則稱(chēng)σ為奇置換（偶置換）。,6.3.4 置換的奇偶性,因每個(gè)長(zhǎng)度為r的輪換可寫(xiě)成r-1個(gè)對(duì)換的乘積：(a1 a2… ar)＝(a1 ar)(a1 ar－

28、１)…(a1 a3)(a1 a2) 于是σ可寫(xiě)成 =n-k 個(gè)對(duì)換的乘積。 結(jié)論：奇置換可表為奇數(shù)個(gè)對(duì)換之積， 偶置換可表為偶數(shù)個(gè)對(duì)換之積。,=(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個(gè)對(duì)換。,定理6.3.3 每個(gè)置換都能分解為對(duì)換的乘積，但

29、偶置換只能分解為偶數(shù)個(gè)對(duì)換的乘積，奇置換只能分解為奇數(shù)個(gè)對(duì)換的乘積。證明.只需證明 “只能分解”。任取σ∈Sn，設(shè)σ等于k個(gè)不相雜輪換之積，這些輪換分別含r1，r2，…，rk個(gè)元素，于是σ可以寫(xiě)成 個(gè)對(duì)換之積，定義置換σ的符號(hào)sgnσ如下： sgnσ=,顯然，偶置換的符號(hào)為1，奇置換的符號(hào)為-1。首先證明 sgnστ=sgnσsgnτ （4） 設(shè)σ等于k個(gè)不相

30、雜輪換之積， τ等于h個(gè)不相雜輪換之積， 且σ寫(xiě)成對(duì)換中最后一個(gè)為（a b）。以（a b）乘τ而看其變化。,(1)若a和b在τ的兩個(gè)不同的輪換之內(nèi): τ=（a a1… as）（b b1… bi） …則 （a b）τ=（a a1… as b b1… bi）…即,（a b）τ為（h-1）個(gè)不相雜輪換之積,故，sgn(a b)τ= (-1)n-(h-1) = -(-1)n-h = -sgnτ(2)

31、若a和b在τ的同一個(gè)輪換之內(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τ,總之，以一個(gè)對(duì)換乘τ則將sgnτ變號(hào)，今σ等于（n-k）個(gè)對(duì)換之積，故以σ乘τ將sgnτ變號(hào)（n-k）次，即sgnστ= (-1)n-k sgnτ=sgnσsgnτ

32、因此，σ和τ的奇偶性與其乘積στ的奇偶性之關(guān)系如下： 偶×偶=偶， 奇×奇=偶， 奇×偶=奇， 偶×奇=奇。 因?yàn)閷?duì)換是奇置換，所以只有奇數(shù)個(gè)對(duì)換之積是奇置換，偶數(shù)個(gè)對(duì)換之積是偶置換。,定理6.3.4 設(shè)M的元數(shù)為n，若n>1，則奇置換的個(gè)數(shù)和偶置換的個(gè)數(shù)相等，都等于 。證明：命 τ1，τ2，…，τm （5）為M的所有偶置換，由于n>1，

33、故可取到一個(gè)對(duì)換ρ，而作下列乘積： ρτ1，ρτ2，…，ρτm （6）顯然ρτi是奇置換，而且諸ρτi互不相同，即（6）中無(wú)重復(fù)元素。反證，若ρτi=ρτj，則以ρ-1左乘得τi=τj，矛盾，這說(shuō)明M的奇置換不少于偶置換。,反之，若σ為M的任意奇置換，則ρ-1σ為偶置換，故必等于某一個(gè)τi，ρ-1σ=τi，因而σ=ρτi，這說(shuō)明M的任意奇置換必在（6）中，（6）就是M的所有奇置換，M的奇置換不