離散數(shù)學(xué)第6講置換群和循環(huán)群

1、1離散數(shù)學(xué)（二）離散數(shù)學(xué)（二）置換群和循環(huán)群置換群和循環(huán)群置換群置換群1 11 1循環(huán)群循環(huán)群2 2主要內(nèi)容主要內(nèi)容: :置換群和循環(huán)群的結(jié)構(gòu)置換群和循環(huán)群的結(jié)構(gòu)重點重點: : 兩面體群兩面體群難點難點: :重點和難點重點和難點: :凱萊表示定理凱萊表示定理3 3一、置換群一、置換群置換的定義：置換的定義： 有限集A上的雙射函數(shù)稱為A上的置換或排列置換或排列。 如A=1,2,3,4, h: AA, h(1)=3, h(2)=2, h(3)=4, h(4)=1，此置換可表示為：14234321p A=a1,a2,an，即|A|=n時，稱為A上的置換為n次置換。A上的n次置換p可表示為：)()()

2、(2121nnapapapaaap一、置換群一、置換群|A|=n時，A上有 n!個n次置換, 如A=1,2,3時,置換的合成運算置換的合成運算： 左合成運算： , p1 p2, 先進行p2置換, 再進行p1置換。 右合成運算：, p1p2, 先進行p1置換, 再進行p2置換。213321132321231321123321312321321321654321pppppp一般地， |A|=n時，記A上所有置換集合為Sn, |Sn|=n!123321132321231321231321312321132321一、置換群一、置換群不難驗證： (右合成運算：, p1p2, 先p1置換, 再p2置換)

3、(1) 是一個代數(shù)； (2) 是一個群。給定集合A, (1) Sn關(guān)于運算封閉 (2) A上所有置換對運算而言滿足結(jié)合律 (3) Sn關(guān)于運算存在么元恒等置換，恒等函數(shù)，又稱么置換 (4)每一置換都有逆置換逆函數(shù)所以是一個群。一、置換群一、置換群給定n個元素組成的集合A: A上的若干置換若干置換所構(gòu)成的群稱為n次置換群次置換群； A上所有置換所有置換構(gòu)成的群稱為n次對稱群次對稱群, 。 n次對稱群的子群即為n次置換群。例例1 令A(yù)1,2,3，A上置換的全體S3=pi i = 1,2,3,4,5,6。3213211p3123212p1233213p2313214p1323215p2133216p

4、p1為恒等置換，p2-1p2，p3-1p3 ，p4-1p4 ，p5-1p6 為三次對稱群 為2階三次置換群為3階三次置換群一、置換群一、置換群為三次對稱群,其運算表如下表所示:3213211p3123212p1233213p2313214p1323215p2133216p一、置換群一、置換群例例2 兩面體群兩面體群 (a) 給定正三角形123(如左下圖所示), 將三角形圍繞重心O旋轉(zhuǎn), 分別旋轉(zhuǎn)0, 120, 240?？梢园衙恳恍D(zhuǎn)看成是三角形的頂點集合1, 2, 3的置換, 于是有)240(213321)120(132321)0(321321651旋轉(zhuǎn)旋轉(zhuǎn)旋轉(zhuǎn)ppp一、置換群一、置換群例例2

5、 兩面體群兩面體群(續(xù)續(xù)) 再將三角形圍繞直線1A、2B、3C翻轉(zhuǎn)。又得到頂點集合的置換:)1(231321)2(123321)3(312321432翻轉(zhuǎn)繞翻轉(zhuǎn)繞翻轉(zhuǎn)繞ApBpCp正三角形的旋轉(zhuǎn)和翻轉(zhuǎn)在合成運算下可構(gòu)成群正三角形的旋轉(zhuǎn)和翻轉(zhuǎn)在合成運算下可構(gòu)成群, 就代表這個群。就代表這個群。 一、置換群一、置換群例例2 兩面體群兩面體群 (續(xù)續(xù)) (b)正四邊形通過旋轉(zhuǎn)和翻轉(zhuǎn)也可以形成四個頂點集合1, 2, 3, 4的置換(見下圖): )360(43214321)270(32144321)180(21434321)90(143243214321旋轉(zhuǎn)旋轉(zhuǎn)旋轉(zhuǎn)旋轉(zhuǎn)pppp)24(41234321)

6、13(23414321)(34124321)(123443218765翻轉(zhuǎn)繞翻轉(zhuǎn)繞翻轉(zhuǎn)繞翻轉(zhuǎn)繞ppBBpAAp一、置換群一、置換群例例2 兩面體群兩面體群 (續(xù)續(xù)) 正方形的翻轉(zhuǎn)和旋轉(zhuǎn)在合成運算下可構(gòu)成群, 如下表所示。構(gòu)成一個四次構(gòu)成一個四次8階置換群。階置換群。這不是對稱群這不是對稱群, 元素沒有元素沒有4!個個, 是一置是一置換群。一般地說換群。一般地說, 在合成運算作用在合成運算作用下下, n邊正多邊形的所有旋轉(zhuǎn)和翻轉(zhuǎn)的邊正多邊形的所有旋轉(zhuǎn)和翻轉(zhuǎn)的集合構(gòu)成一個集合構(gòu)成一個n次的次的2n階的置換群階的置換群, 這這類群通稱兩面體群。類群通稱兩面體群。 二、循環(huán)群二、循環(huán)群循環(huán)群的定義循環(huán)

7、群的定義 在群中,如果存在一個元素gG, 對于每一個元素 aG都有一個相應(yīng)的正整數(shù)iI, 能把a表示成gi形式, 則稱是一個循環(huán)群循環(huán)群，g是該循環(huán)群的生成元生成元。 定理定理9：任何一個循環(huán)群必定是阿貝爾群(可交換群)。證明證明：設(shè)是一個循環(huán)群，它的生成元為g,那么對于任意的a, bG, 必有i, jI,使得gi=a, gj=b那么a*b=gi*gj=gi+j=gj+i=gj*gi=b*a，因此，是一個阿貝爾群。二、循環(huán)群二、循環(huán)群定理定理10：設(shè)是由gG生成的有限循環(huán)群, 如果|G|=n,則gn=e, G =g, g2, g3, , gn=e且n是使gn=e的最小正整數(shù)。證明證明：(1)先

8、證先證gm=e而而mn是不可能的。是不可能的。 假定有正整數(shù)mn使 gm=e, 則對G中任一元素gk, 設(shè)k=mq+r, 0rm, 于是gk = gmq+r = (gm)q * gr = e* gr = gr 這意味著G中每一元素都可寫成gr形式, 但rm, 所以G中至多有m個不同元素, 這與|G|=n矛盾。所以gm=e而mn是不可能的。(2)再證再證g, g2, g3, , gnG中的元素全不相同。中的元素全不相同。 若不然有g(shù)i=gj, 不妨設(shè)ij, 于是gj-i=e。但j-in, 這與(1)相矛盾。由于是群, 其中必有么元, 由(2)得G= g, , g2, , g3, , ,gn,又由

9、(1)得gn =e。二、循環(huán)群二、循環(huán)群例3 (1) 是無限階循環(huán)群；對生成元為1， iI, (1) i0(2) i=0, 0=10(3) i0, 令i=-j, iii1111 個ijjjjji11)1 () 1() 1() 1() 1(1個生成元為-1,可類似地討論封閉，可結(jié)合，么元0，xI,存在逆元 x-1=-x生成元為1，-1； 故是無限階循環(huán)群。二、循環(huán)群二、循環(huán)群例例3 (2) 是有限階循環(huán)群(k0)；例如k=4時, 這個群如右表所示, 其中0是么元, 1或3是生成元。Nk=0,1,k-1，x是I中模k等價類。+k定義為: x+ky =(x+y)mod k。 可驗證：封閉，可結(jié)合，么

10、元0 ，iNk,存在逆元k-i生成元為1；故是有限階循環(huán)群。0)1(0,)1( 1 1 1 ),0(其中個iiikii 二、循環(huán)群二、循環(huán)群定理定理11：設(shè)是由gG為生成元的循環(huán)群。(a)若G是無限集，則與同構(gòu)。(b)若G是有限集且|G|=k,則與同構(gòu)。證明證明：(a) G=g0,g1,gn, 設(shè)映射f: GI, f(gi)=i。 (i) 證明證明f是雙射函數(shù)是雙射函數(shù) 對于任意xG,均存在唯一的kI,使得gk=x (因為是無限循環(huán)群，所以g的階(周期)是無限的) 。任取gk, ghG, 若gk gh,則必有kh, 所以f是單射。任取iI,存在x=giG,使得f(x)=i,所以f是滿射的。故f

11、是雙射函數(shù)。 (ii)證明證明f從從G到到I運算保持。運算保持。任取x,yG, i,jI, 使得 gi=x, gj=y, 那么f(x*y)=f(gi*gj)=f(gi+j)=i+j= f(gi)+f(gj) =f(x)+f(y)。 (iii)幺元相對應(yīng)。幺元相對應(yīng)。 f(g0)=0 。綜上所述，綜上所述，f是是到到的同構(gòu)映射。的同構(gòu)映射。定理定理1111說明，循環(huán)群只說明，循環(huán)群只有兩類：無限循環(huán)群和有兩類：無限循環(huán)群和k k階循環(huán)群階循環(huán)群二、循環(huán)群二、循環(huán)群定理定理11證明證明：(b)若G是有限集且|G|=k,則與同構(gòu)。(i)證明證明f是雙射函數(shù)是雙射函數(shù) f是單射是單射 : 任取gt,

12、ghG, 若gt gh,則必有th。假如t=h,則t-h=mk, t=h+mk,gt = gh+mk =gh*(gk)m = gh* (e)m = gh ,這與gt gh相矛盾。 容易看出f滿射滿射，所以f是雙射。(ii)證明證明f從從G到到I運算保持。運算保持。任取x,yG, i,j I,使得x=gi, y=gj有f(gi * gj)=f(gi+j)= i+j=i +k j=f(gi) +k f(gj)。(iii)幺元相對應(yīng)。幺元相對應(yīng)。 f(g0)=0綜上所述，綜上所述，f是是到到的同構(gòu)映射。的同構(gòu)映射。因為G是有限循環(huán)群,且|G|=k,故可設(shè)G = g0, g1, g2, , gk-1N

13、k= 0, 1, 2, ,k-1作映射作映射f: GNk, f(gi)=i二、循環(huán)群二、循環(huán)群例例4 求求的所有子群。的所有子群。解答：解答：有兩個平凡子群：，非平凡子群有：,。注：考慮注：考慮有四個子群，與它的哪個特性相關(guān)？有四個子群，與它的哪個特性相關(guān)？如何不用做表直接寫出循環(huán)群的所有子群？如何不用做表直接寫出循環(huán)群的所有子群？對于循環(huán)群對于循環(huán)群，其子群的個數(shù)與，其子群的個數(shù)與k的因子數(shù)相同。的因子數(shù)相同。求子群時，根據(jù)因子，因子是幾就隔幾寫出子群的各求子群時，根據(jù)因子，因子是幾就隔幾寫出子群的各個元素。個元素。三、凱萊表示定理三、凱萊表示定理定理定理12：每一個n階有限群, 同構(gòu)于n次

14、置換群。證明證明： 設(shè)k=mq+r, 0rm,設(shè)是一個n階群, 由定理6.7-4知道, 的合成表中每一行和列都是G的一個置換。對應(yīng)于元素aG的列的置換是pa(x) = x * a記對應(yīng)于G的所有元素的列的置換集合為P。下面首先證明下面首先證明是一個群，再證明是一個群，再證明G與與P同構(gòu)。同構(gòu)。(a) 封閉性封閉性 對任意元素a、bG, 有 (papb)(x) = (x * a) * b =x * (a * b) =pa*b(x)P (1) (b) 存在幺元存在幺元 設(shè)e是的么元, aG是任一元素,則有 pepa = pape = pa，所以, pe是么元。(c) 存在逆元存在逆元 對任意元素aG, 存在元素a-1G,有 Pa-1 pa = pa Pa-1 = pe，所以, 對任一pa存在逆元Pa-1 。(d) 滿足結(jié)合律滿足結(jié)合律 置換的合成滿足結(jié)合律。三、凱萊表示定理三、凱萊表示定理定理定理12證明證明(續(xù)續(xù))：下面證明下面證明G與與P同構(gòu)。同構(gòu)。作映射h: G Ph(a) = pah顯然是雙射函數(shù)。再將已證明的等式(1)改寫為h(a * b) = h(a)h(b)根據(jù)群同態(tài)的定義以及h為雙射函數(shù)，