信息安全數(shù)學(xué) 群

1、信息安全數(shù)學(xué)基礎(chǔ)許春香 編著1第二章 群2第二章 群2.1 群的定義（重要）2.2 子群（掌握）2. 同構(gòu)和同態(tài)（重要）2. 變換群與置換群（掌握）32.1 群的定義定義2.1.1設(shè)G是一非空集合如果在G上定義了一個(gè)代數(shù)運(yùn)算，稱為乘法，記為ab，而且這個(gè)運(yùn)算滿足下列條件，那么G稱為一個(gè)群：1）G對于乘法是封閉，即對于G中任意元素a，b，有abG；2）對于G中任意元素a，b，c，有a(bc) = (ab)c；3）在G中有一個(gè)元素e，對于G中任意元素a，有ea = a；4）對于G中任一元素a都存在G中的一個(gè)元素b，使ba = e4群的定義 群的定義可以簡單的歸結(jié)為帶有運(yùn)算的集合，在集合上的運(yùn)算滿足

2、1）封閉性；2）結(jié)合性；3）單位元；4）逆元；5群的定義例2.1.1 整數(shù)對于加法構(gòu)成了整數(shù)加法群，由我們初等代數(shù)的知識知，任意兩個(gè)整數(shù)相加仍然是整數(shù)（封閉性），且滿足加法結(jié)合性，其單位元為0，即任意整數(shù)加0均為自身，任意整數(shù)a的逆元為-a 全體整數(shù)Z，全體實(shí)數(shù)R，全體復(fù)數(shù)C對于加法是群全體非零實(shí)數(shù)R*=R0對于乘法是群 同樣有非零有理數(shù)，非零復(fù)數(shù)對乘法也構(gòu)成了群分別記作（Z，+），（Q，+）（R，+），（C，+）（Q*， ）（R*， ）（C*， ）其中Q*表示非零有理數(shù)集， R*表示非零實(shí)數(shù)， C*非零復(fù)數(shù)這類群稱為數(shù)群6群的定義關(guān)于群的幾點(diǎn)說明：群的定義有多種描述可以參考近世代數(shù)書籍，本定

3、義2.1.1只給出了一種定義中的“乘法”并不代表具體的乘法，而是抽象的乘法代表一種代數(shù)運(yùn)算 群的定義補(bǔ)充7群的定義例2.1.2自然數(shù)集合N1，2，3，對于通常的加法封閉且滿足結(jié)合律，但不存在左單位元和左逆元，因此對于加法不是群而只是半群整數(shù)Z對乘法也只是半群，即只滿足封閉性和結(jié)合性8群的定義例2.1.3集合0，1對于模2加法“”（或稱異或）是一個(gè)群顯然封閉性和結(jié)合律滿足；這里的單位元e=0，因?yàn)? 00，0 11；每一個(gè)元素的左逆元就是它自己：0 00，1 100，1對于運(yùn)算是加法群9群的定義例2.1.4集合的元素不一定是數(shù)，我們舉一個(gè)集合元素為二階方陣的例子： 該集合對于矩陣的普通乘法是一個(gè)

4、群，單位元是 10群的定義例2.1.5 考慮二階矩陣集合， 其中a，b，c，d為整數(shù)， ，則該集合對于普通矩陣乘法構(gòu)成群：1）封閉性：兩個(gè)矩陣A和B相乘仍然是整數(shù)二階矩陣，而且|AB|A|B|=1；2）結(jié)合律顯然滿足；3）單位矩陣是單位元 ；4）任意元素 的左逆元為 實(shí)際上任意階整數(shù)方陣當(dāng)其行列式等于1時(shí)對于矩陣的普通乘法都構(gòu)成群。集合元素可以是任意事物，其中的運(yùn)算也可以是任意定義的11群的定義定義2.1.2如果群中的運(yùn)算滿足交換律，則這個(gè)群稱為交換群或阿貝爾（Abel）群 比如： （Z，+），（Q，+）（R，+），（C，+）， （Q*， ）（R*， ）（C*， ）都是（Abel）群 12群的

5、基本性質(zhì)1）左逆元同時(shí)也是右逆元，即對于a，bG，如果ba = e，則ab = e2）左單位元同時(shí)也是右單位元，即如果對于所有aG有ea = a，則對于所有aG也有ae = a 3）單位元是唯一的4）逆元是唯一的 13群的基本性質(zhì)（證明）證明設(shè)G是一個(gè)群，e是G中的左單位元1） aG，設(shè)其左逆元為b，即ba = e；又設(shè)b的左逆元為b，即bb = e于是(bb)(ab) = e(ab) = (ea)b = ab；但我們又有(bb)(ab) b(ba)b = b(eb) = bb = e，所以我們得到ab = e，即b也是a的右逆元左逆元同時(shí)也是右逆元14群的基本性質(zhì)（證明）證明設(shè)G是一個(gè)群，e

6、是G中的左單位元2） aG，設(shè)其左（右）逆元為b則(ab)a = ea = a；又(ab)a = a(ba) = ae；所以ae = a，故左單位元也是右單位元左單位元同時(shí)也是右單位元15群的基本性質(zhì)（證明）證明設(shè)G是一個(gè)群，e是G中的左單位元3）如果G中存在另一單位元e，我們有e = ee = e，則單位元是唯一的 單位元是唯一的16群的基本性質(zhì)（證明）證明設(shè)G是一個(gè)群，e是G中的左單位元4） aG，設(shè)b，c都是a的逆元，則b = be = b(ac) = (ba)c = ec = c，則每個(gè)元素的逆元是唯一的 逆元是唯一的17群的階、元素的階定義2.1.3如果一個(gè)群G中元素的個(gè)數(shù)是無限多個(gè)

7、，則稱G是無限群；如果G中的元素個(gè)數(shù)是有限多個(gè)，則稱G是有限群，G中元素的個(gè)數(shù)稱為群的階，記為|G|如前面例2.1.1提到的數(shù)群是無限群，例2.1.3的模2加法群，階為2，例2.1.4的群階為418群的階、元素的冪由于群里結(jié)合律是滿足的，所以元素連乘a1a2an有意義，它也是G中的一個(gè)元我們把a(bǔ)的n次連乘記為an， 稱為a的n次冪（或稱乘方），即 我們還將a的逆元a1的n次冪記為an，即群的逆元（a1） 1=a19群的階、元素的冪若ab=ba，則（ab）n = anbn另外：anan = e，aman = am+n，(an)m = anm 20群的等價(jià)性質(zhì)定理2.1.1一個(gè)群的乘法滿足消去律：

8、如果ax = ax ，則x = x ；（左消去）如果ya = y a，則y = y （右消去）證明 假定ax = ax ，那么a1(ax) = a1 (ax )，( a1a)x = ( a1a)x ，ex = ex ，x = x 同理可證由ya = y a，得y = y 21群的等價(jià)性質(zhì)定理2.1.2如果G是一個(gè)群， a，bG，方程ax = b，ya = b有解；反之，如果上述方程在非空集合G中有解，而且其中的運(yùn)算封閉且滿足結(jié)合律（即半群），則G是一個(gè)群 22群的等價(jià)性質(zhì)證明先證方程有解如果G是一個(gè)群，對于任一元素a有逆元a-1，由ax = b可得a1(ax)a1b，x = a1bG于是x =

9、 a1b是方程ax = b的解同理y = ba1是方程ya = b的解23群的等價(jià)性質(zhì)證明（續(xù)）：對于方程有解時(shí)，半群（G，）是群。先證有左單位元：如果 a，b，方程ax = b，ya = b在G中有解，則假設(shè)a=b時(shí)，方程亦有解，即ya=a有解，設(shè)其解為e。任取g G，方程ax=g有解，設(shè)其解為b，即ab=g，于是有eg=eab=ab=g，因而e是左單位元。再證任a G有左逆元：因?yàn)榉匠蘺a=e有解，其解就是a的左逆元。綜上，由定義2.1.1知，G對于運(yùn)算“ ”在滿足封閉性結(jié)合性前提下，只要方程ax = b，ya = b有解，G關(guān)于運(yùn)算“ ”是群24群的等價(jià)性質(zhì)推論2.1.2.1如果一個(gè)非空

10、集合G中的運(yùn)算封閉且滿足結(jié)合律，則它是一個(gè)群的充分必要條件是 a，bG，方程ax = b，ya = b有解25群的等價(jià)性質(zhì)定理2.1.3如果一個(gè)非空有限集合G中的運(yùn)算封閉且滿足結(jié)合律，則它是一個(gè)群的充分必要條件是滿足消去律證明必要條件由定理1立即得到只證明充分條件如果消去律滿足，則 a，bG，方程ax = b，ya = b有解先證明方程ax = b在G中有解假設(shè)G有n個(gè)元素，G=a1，a2，a3，an用a左乘G中的每個(gè)元素得到G=aa1，aa2，aa3，aan，26群的等價(jià)性質(zhì)證明（續(xù)）由于乘法的封閉性，G是G的子集，而且G中的n個(gè)元素兩兩不同，不然假設(shè)aaiaaj，其中ij，由消去律得aia

11、j，其中ij，這是不可能的于是G也有n個(gè)兩兩不同的元素，則G= G設(shè)b = aak，則ak就是以上方程的解同樣可證ya = b有解由定理2.1.2，G是一個(gè)群定理證畢272.2 子群定義2.2.1一個(gè)群G的一個(gè)子集H如果對于G的乘法構(gòu)成一個(gè)群，則稱為G的子群也記作HG一個(gè)群G至少有兩個(gè)子群：G本身；只包含單位元的子集e，它們稱為G的平凡子群，其他子群成為真子群(HG)282.2 子群例2.2.1 設(shè)m是一個(gè)正整數(shù)整數(shù)加群Z中每個(gè)元素的m倍數(shù)0，m，2m，3m，對加法也構(gòu)成群，它是Z的子群，記為mZ292.2 子群引理一個(gè)群G和它的一個(gè)子群H有：1）G的單位元和H的單位元是同一的；2）如果aH，

12、a1是a在G中的逆元，則a1H證明對于任意aH，有aG1）反證法設(shè)G的單位元為e，H的單位元為e，而且e e由于eH G，則G中的單位元不唯一，與群的定義矛盾，故e = e2）反證法對于任意aH，假設(shè)a1H，則a在H中存在另一逆元a，由于aG，則a在G中存在兩個(gè)逆元，得到矛盾，故a1H302.2 子群定理2.2.1一個(gè)群G的一個(gè)非空子集H構(gòu)成一個(gè)子群的充分必要條件是：1） a，bH，有abH；2） aH，有a1H證明首先證明充分條件由于1），H是封閉的結(jié)合律在G中，在H中自然成立現(xiàn)證明H中有單位元對于任意aH，由于aG，所以存在a1使a1a = e由2）有a1H，由1）就有a1aH，于是a1a

13、 = eH，則G中的單位元在H中H不可能再有單位元，否則G的單位元不唯一由2），H中的每個(gè)元素都有逆元故H是一個(gè)群再證明必要條件1）是封閉性，是必要的2）由引理也是必要的證畢312.2 子群定理2.2.2一個(gè)群G的一個(gè)非空子集H構(gòu)成一個(gè)子群的充分必要條件是：對于任意a，bH，有ab1H證明我們證明這個(gè)條件和定理2.2.1的兩個(gè)條件是一致的，即和定理2.2.1等價(jià)先證明由定理1的兩個(gè)條件可推出這個(gè)條件a，bH，有b1H，則ab1H反過來，這個(gè)條件可推出定理1的兩個(gè)條件由aH，有aa1 = eH，于是ea1 = a1H又由a，bH，（參照上一行，）有b1H，于是a(b1) 1 = abH證畢在判定

14、子群時(shí)，此定理經(jīng)常用到322.2 子群定理2.2.3一個(gè)群G的一個(gè)非空有限子集H構(gòu)成一個(gè)子群的充分必要條件是：對于任意a，bH，有abH證明H是有限集合，我們證明H滿足1.1中的定理3的3個(gè)條件H顯然滿足封閉性；結(jié)合律在G中滿足，在H中自然滿足；消去律在G中滿足，在H中自然滿足故H是一個(gè)群定理3表明一個(gè)群的一個(gè)非空有限子集是一個(gè)群的充分必要條件是：只要它滿足封閉性332.2 子群例2.2.2 例2.2.1用定義判斷了mZ是Z的子群，現(xiàn)在我們用定理2.2.2來判斷mZ是Z的子群設(shè)a，bmZ，則有t1，t2Z，使a = mt1，b = mt2b在Z中的加法逆元是b，于是a+(b) = mt1+(m

15、t2) = m(t1t2) 由于t3 = t1t2Z，所以a+(b) = mt3mZ則mZ是子群 342.2 子群例3復(fù)數(shù)域上的8次方程z81=0的根集合 ，k=0，1，2，7是一個(gè)乘法群由定理3可驗(yàn)證其中的子集 ，k=0，1，2，3是一個(gè)子群35定義1一個(gè)集合A到另一個(gè)集合B的映射f是 aA，都有一個(gè)確定的b = f(a)B與之對應(yīng)b稱為a在f下的像，而a稱為b在f下的一個(gè)逆像（原像）2.3 同構(gòu)與同態(tài) 映射AfabB36映射 a，bA，如果a b，就有f(a) f(b)，則稱f為單射 bB，總有aA，使f(a) = b，則稱f為滿射既是滿射又是單射的映射稱為一一映射單射的含義就是A中的每個(gè)

16、元素在B中有不同的像，滿射是B中的每個(gè)元素都成為A中元素的一個(gè)像，一一映射是A中的元素與B中的元素一一對應(yīng)37例2.3.1 設(shè)A=1，2，3，B=2，4，6下圖中的映射f是一個(gè)單射，又是一個(gè)滿射，它是一一映射例2.3.1 設(shè)A=1，2，3，B=2，4，6下圖中的映射f是一個(gè)單射，又是一個(gè)滿射，它是一一映射例2.3.1 設(shè)A=1，2，3，B=2，4，6下圖中的映射f是一個(gè)單射，又是一個(gè)滿射，它是一一映射例2.3.1 設(shè)A=1，2，3，B=2，4，6下圖中的映射f是一個(gè)單射，又是一個(gè)滿射，它是一一映射例2.3.1 設(shè)A=1，2，3，B=2，4，6下圖中的映射f是一個(gè)單射，又是一個(gè)滿射，它是一一映射

17、映射例2.3.1 設(shè)A=1，2，3，B=2，4，6下圖中的映射f是一個(gè)單射，又是一個(gè)滿射，它是一一映射AB12326f438映射顯然一個(gè)一一映射f：AB存在一個(gè)逆映射f 1：BA，它也是一一映射AB12326f -1439映射如果A = B，映射f也稱為變換，即一個(gè)集合到自身的映射稱為變換如果一個(gè)集合A到自身的映射f定義為：對于任意aA，f(a) = a，則稱映射f為恒等映射，單位映射或恒等變換，記為I40同態(tài)和同構(gòu) 定義2.3.2 假設(shè)（A，）和（B，）是兩個(gè)群，若存在映射f：AB滿足：任意a，bA，均有f（a b）=f（a） f（b）則稱f是A到B的一個(gè)同態(tài)映射或簡稱同態(tài)。 同態(tài)映射也簡稱

18、為同態(tài)如果f是單射，則稱f是單同態(tài)，如果f是滿射，則稱f是滿同態(tài)，如果f是一一映射，則稱f是同構(gòu)映射 如果G= G，同態(tài)f稱為自同態(tài)，同構(gòu)映射f稱為自同構(gòu)映射41同態(tài)和同構(gòu)例2.3.2 假設(shè)整數(shù)集合Z里的運(yùn)算是加法，Z通過映射f：aea產(chǎn)生一個(gè)實(shí)數(shù)集合（這里的e是自然常數(shù)）：eaaZ，我們定義這個(gè)實(shí)數(shù)集合里的運(yùn)算是乘法，于是有f(ab) = f(a)f(b)，顯然Z中的運(yùn)算在eaaZ中得到了保持，f就是一個(gè)同態(tài)映射 42同態(tài)和同構(gòu)如果同態(tài)映射還是一一映射，則稱為同構(gòu)映射 例2.3.2的映射f：aea就是一個(gè)一一映射，所以f為同構(gòu)映射 43同態(tài)和同構(gòu)定理2.3.1假設(shè)G和G是兩個(gè)群，在G 到G的

19、一個(gè)同態(tài)（映射）f之下，1）G的單位元e的像f(e)是G的單位元e，即f(e) = e2）G的任意元a的逆元a的像f(a1)是f(a)的逆元，即f(a1) = f(a) 13）G在f下的像的集合f(a)aG是G的子群，稱為f的像子群當(dāng)f是滿同態(tài)時(shí)，像子群就是G本身44同態(tài)和同構(gòu)證明1）：由于f(e)f(e) = f(e2) = f(e)，兩邊同乘f(e) 1，得f(e) = e2） aG有f(a1)f(a) = f(a a) = f(e) = e所以 f(a)1 = f(a1) 3）如果a，bf(a)aG，設(shè)a = f(a)，b = f(b)，則ab1 = f(a) f(b)1 = f(a)

20、f(b1) = f(ab1)f(a)aG= G ，由定理2.2.2，得f(a)aG是G的子群45同態(tài)和同構(gòu)定義2.3.3設(shè)G和G是兩個(gè)群，如果存在一個(gè)G到G的同構(gòu)映射，則稱G與G同構(gòu)，記為G G如果G = G，則稱G自同構(gòu)例2.3.3整數(shù)加法群Z和偶數(shù)加法群E同構(gòu)例2.3.4 實(shí)數(shù)加法群R和正實(shí)數(shù)乘法群R+同構(gòu)同構(gòu)映射為f(a) = ea例2.3.5任意一個(gè)二階群都與乘法群1，1同構(gòu)證明：設(shè)一個(gè)任意二階群為A=e，a，e為單位元構(gòu)造如下A到乘法群1，1的映射：f：e1，b 1顯然f是同構(gòu)映射，于是A與乘法群1，1同構(gòu)46同態(tài)和同構(gòu)可以看出，群的同構(gòu)具有反身性，對稱性和傳遞性，即它是等價(jià)關(guān)系：1

21、）G G；2）由G G可推出G G；3）由G G和G G可推出G G47同態(tài)映射的核 假設(shè)f是G到G的同態(tài)映射 aG，集合a f(a) = a ,aG 可能是空集，也可能包含一個(gè)以上的元素（當(dāng)f不是單射時(shí)可能有多個(gè)元素）我們稱這個(gè)集合是a的完全反像特別地，單位元的完全反像稱為同態(tài)映射f的核，記為ker(f)，即ker(f) = a aG ,f(a) = e= f -1(e ) 48同態(tài)映射的核定理2.3.2ker(f)是G的子群，稱為f的核子群證明由于一定有eker(f)，所以ker(f)不會是空集如果a，bker(f)，則f(a) = e，f(b) = e，f(b) 1 = (e) 1= e

22、，于是f(ab1) = f(a)f(b1) = f(a)f(b)1 = ee = e，所以ab1ker(f)，故ker(f)是G的子群49同態(tài)映射的核定理3G到G的同態(tài)映射f是單同態(tài)的充分必要條件是ker(f) = e，即核子群只含有單位元證明先證充分條件用反證法如果ker(f) = e，但存在a，bG，a b，有f(a) = f(b)，于是f(a)f(b)1 = e，由于f是同態(tài)，則f(ab1) = e而由a b，有ab1 e，這與ker(f) = e矛盾，故f是單射，因而是單同態(tài)必要條件證明：由于eker(f)，如果ker(f)還包含其他元素，則f不是單射，故ker(f) = e50同態(tài)映

23、射的核同態(tài)映射和核子群、像子群的關(guān)系可以形象地表示如圖2.3.1eker(f)像子群GGf512.4 變換群與置換群 變換是一個(gè)集合到自身的映射例2.4.1實(shí)數(shù)集合R到R的一個(gè)變換f：對于 aR，f(a) a2例2.4.2集合A = 1，2，它的全部變換為：f1：11，21，f2：12，22，f3：11，22，f4：12，21其中f3和f4是一一變換52變換群我們規(guī)定集合A上的兩個(gè)變換f和g的乘法(變換的復(fù)合)如下： aR，fg(a) = f(g(a)例2.4.3集合A = 1，2，3，4設(shè)變換f為：12，24，31，43變換g為：13，21，32，44則fg為：11，22，34，43定義2.

24、4.1一個(gè)集合的若干變換如果對于變換的乘法構(gòu)成群，則稱為變換群53變換群定理2.4.1（Cayley定理）任何一個(gè)群都同構(gòu)于一個(gè)變換群證明證明的思路是對于任意一個(gè)群，我們構(gòu)造出與之同構(gòu)的一個(gè)變換群設(shè)G是一個(gè)群，我們構(gòu)造一個(gè)變換集合T如下：T = xG，f(x) = ux | uG我們可以證明T是一個(gè)一一變換群現(xiàn)在我們構(gòu)造G到T的同構(gòu)映射我們建立一個(gè)G到T的映射如下：aG，a(xG，f(x) = ax)對于a，bG，(ab) = (xG，f(x) = abx) = (a)(b)，是一個(gè)同構(gòu)映射，所以G與T同構(gòu) 54變換群例2.4.4 構(gòu)造與非零實(shí)數(shù)乘法群R*R0同構(gòu)的變換群 R*的變換集合T =

25、 x R*，f(x) = ux | u R*是一個(gè)變換群R*到T的同構(gòu)映射：a R*，a(x R*，f(x) = ax)T與R*同構(gòu)55置換群 定義2.4.2一個(gè)有限集合的一一變換稱為置換設(shè)一個(gè)有限集合A有n個(gè)元素，A = a1，a2，a3，an，則一個(gè)置換可以表示為：ai ，i = 1，2，3，n也可表示為：如果抽掉元素的具體內(nèi)容，置換還可表示為：實(shí)際上，第一行元素的任意一個(gè)排列都是一種表示，但一般情況下我們還是用(1，2，3，n)次序表達(dá)56置換群例2.4.5n = 3，置換：a1 a2，a2 a3，a3 a1于是一個(gè)有限集合的若干置換構(gòu)成的群稱為置換群 57置換群定理2.4.2一個(gè)有限集

26、合的所有置換對于變換的乘法構(gòu)成一個(gè)群證明設(shè)一個(gè)有限集合A的所有置換的集合為S假設(shè)f，gS，對于任意a，bA，如果a b，則有g(shù)(a) g(b)，f(g(a) f(g(b)，fg(a) fg(b)所以fg是單射，又由于g和f是滿射，因此fg也是滿射，故fg是一一變換，S對于乘法是封閉的假設(shè)f，g，hS，對于任意aA，有f(gh)(a) = f(g(h(a)，又有(fg)h(a) = f(g(h(a)，故結(jié)合律成立S中存在乘法單位元，即恒等變換I任意fS是一一映射，所以它存在逆映射f 1，f 1也是一一變換，是S中f的逆元所以S對于變換的乘法是一個(gè)群證畢58置換群一個(gè)包含n個(gè)元素的集合的全體置換構(gòu)

27、成的群稱為n次對稱群，記為Sn置換群是對稱群的子群由初等數(shù)學(xué)中排列組合知識可以得知，一個(gè)置換實(shí)際上就是A元素的一次排列，n個(gè)元素的總排列次數(shù)是n!，所以n次對稱群Sn的階|Sn| = n!59置換群例2.4.63次對稱群S3，它有3!=6個(gè)元素：讀者可以驗(yàn)證，S3是一個(gè)非交換群60置換群定理2.4.3每一個(gè)有限群都與對稱群的一個(gè)子群，即一個(gè)置換群同構(gòu)現(xiàn)在我們討論置換中非常重要的循環(huán)置換，或簡稱循環(huán)定義3Sn的一個(gè)如下置換：其余元素保持不變，即稱為k循環(huán)K循環(huán)可以用下面的符號表示：61置換群(i1 i2ik)同樣可以表示為：(i2 i3ik i1)(ik i1 i2ik1)定義中的k循環(huán)多種表示

28、與一種置換的多種表示是同樣的道理容易證明k = I（I恒等變換）在K循環(huán)中，2循環(huán)稱為對換62置換群例2.4.7我們列舉S5中三個(gè)循環(huán)的例子：1 = = (1 2 3) = (2 3 1) = (3 1 2)，2 = =(1 2 3 4 5)=(2 3 4 5 1)=(5 1 2 3 4)，3 = = (1 2)1是3循環(huán)；2是5循環(huán)；3是2循環(huán)，即對換 63置換群 兩個(gè)循環(huán) = (i1 i2ik)和 = (j1 j2jm) 如果對于任意r和s，都有ir js，則稱和是不相交循環(huán) 置換的乘積一般是不可交換的，但對于不相交循環(huán)我們有下列定理定理2.4.4 不相交循環(huán)的乘積是可交換的64置換群定理

29、2.4.5 任一置換都可表示為若干個(gè)兩兩不相交的循環(huán)的乘積，而且表示是唯一的證明：假設(shè)是一個(gè)n元置換：首先將置換中的1階循環(huán)元素劃掉從剩下的元素中任選a1，連續(xù)做置換：a1 a2 a3 a4 a5 a6由于元素個(gè)數(shù)是有限的，則這個(gè)序列進(jìn)行下去一定有ai = aj我們可以證明i = 1因?yàn)槭且灰蛔儞Q，則如果ai = aj，就有ai1 = aj1，接著又有ai2 = aj2，ai3 = aj3，.，a1 = aji+1如此反復(fù)最后直到將n個(gè)元素全部劃掉，分解成了若干兩兩不相交的循環(huán)的乘積65置換群于是上面的置換序列是以a1開始的若干元素的循環(huán)將這些元素劃掉，再從剩下的元素中任選一個(gè)元素重復(fù)上述過程

30、，又會得到一個(gè)循環(huán)，且與上一個(gè)循環(huán)不相交唯一性證明：如果分解不唯一，假設(shè)有兩個(gè)不同的分解式，則會存在兩個(gè)元素i，j，在第一個(gè)分解式里j緊接著i出現(xiàn)，但在第二種分解式緊接著i的卻不是j，這意味著在第一個(gè)分解式里(i) = j，而在第二種分解式里(i) j，得到矛盾定理證畢66置換群我們指出，任何循環(huán)(i1 i2ik)都可表示為對換的乘積，即(i1 i2ik) = (i1 i2) (i1 i3)(i1 ik)利用變換的乘法我們很容易驗(yàn)證上式，計(jì)算(i1 i2) (i1 i3)(i1 ik)：i1 ik，ik i1 ik1，ik1 i1 ik2，ik2 i1 ik3，i3 i1 i2，i2 i1，即i1 ik ik1 ik2 i2 i1，正好等于循環(huán)(i1 i2ik)67置換群定義2.4.4如果一個(gè)置換可以表示為偶數(shù)個(gè)對換的乘積，則稱為偶置換；如果一個(gè)置換可以表示為奇數(shù)個(gè)對換的乘積，則稱為奇置換顯然兩個(gè)偶置換的乘積為偶置換，兩個(gè)基置換的乘積也是偶置換，但一個(gè)偶置換和一個(gè)基置換