【文档说明】信息安全数学 群.pptx，共(70)页，257.324 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-289048.html

以下为本文档部分文字说明：

电子科技大学计算机科学与工程学院UESTCPress第二章群信息安全数学基础许春香编著电子科技大学计算机科学与工程学院UESTCPress第二章群第二章群电子科技大学计算机科学与工程学院UESTCPress第二章群第二章

群•2.1群的定义（重要）•2.2子群（掌握）•2.３同构和同态（重要）•2.４变换群与置换群（掌握）电子科技大学计算机科学与工程学院UESTCPress第二章群2.1群的定义定义2.1.1设G是一非空集合．如果在G上定义了一个代

数运算，称为乘法，记为ab，而且这个运算满足下列条件，那么G称为一个群：1）G对于乘法是封闭，即对于G中任意元素a，b，有abG；2）对于G中任意元素a，b，c，有a(bc)=(ab)c；3）在G中有一个元素e，对于G中任意元素a，

有ea=a；4）对于G中任一元素a都存在G中的一个元素b，使ba=e．电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义群的定义可以简单的归结为带有运算的集合，在集合上的运算满足1）封闭性；2）结合性；3）单位元

；4）逆元；电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.1整数对于加法构成了整数加法群，由我们初等代数的知识知，任意两个整数相加仍然是整数（封闭性），且满足加法结合性，其单位元为

0，即任意整数加0均为自身，任意整数a的逆元为-a全体整数Z，全体实数R，全体复数C对于加法是群全体非零实数R*=R\{0}对于乘法是群同样有非零有理数，非零复数对乘法也构成了群分别记作（Z，+），（Q，+）（

R，+），（C，+）（Q*，·）（R*，·）（C*，·）其中Q*表示非零有理数集，R*表示非零实数，C*非零复数这类群称为数群电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义关于群的几

点说明：1.群的定义有多种描述可以参考近世代数书籍，本定义2.1.1只给出了一种2.定义中的“乘法”并不代表具体的乘法，而是抽象的乘法——代表一种代数运算群的定义补充电子科技大学计算机科学与工程学院UESTCPress第二

章群群的定义例2.1.2自然数集合N＝{1，2，3，．．．}对于通常的加法封闭且满足结合律，但不存在左单位元和左逆元，因此对于加法不是群．而只是半群整数Z对乘法也只是半群，即只满足封闭性和结合性电子科技大学计算机科学与工程学院

UESTCPress第二章群群的定义例2.1.3集合{0，1}对于模2加法“”（或称异或）是一个群．显然封闭性和结合律满足；这里的单位元e=0，因为00＝0，01＝1；每一个元素的左逆元就是它自己：00＝0，1

1＝0．{0，1}对于运算是加法群．电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.4集合的元素不一定是数，我们举一个集合元素为二阶方阵的例子：该集合对于矩阵的普通乘法是一个群，单位元是10101010,,,01010

101−−−−电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.5考虑二阶矩阵集合，其中a，b，c，d为整数，，则该集合对于普通矩阵乘法构成群：1）封闭性：两个矩阵A和B相乘仍然是整数二阶矩

阵，而且|AB|＝|A||B|=1；2）结合律显然满足；3）单位矩阵是单位元；4）任意元素的左逆元为．实际上任意阶整数方阵当其行列式等于±1时对于矩阵的普通乘法都构成群。集合元素可以是任意事物，其中的运算也可以是任意定义的．1001abc

ddbca−−电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义定义2.1.2如果群中的运算满足交换律，则这个群称为交换群或阿贝尔（Abel）群比如：（Z，+），（Q，+）（R，+），（C，+），（Q*，·）（R*，·）（C

*，·）都是（Abel）群电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质1）左逆元同时也是右逆元，即对于a，bG，如果ba=e，则ab=e．2）左单位元同时也是右单位元，即如果对于所有aG有ea=a，则对于所有aG也有ae=a．3）单位元是唯一的．4）逆元是唯一的

．电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质（证明）证明设G是一个群，e是G中的左单位元．1）aG，设其左逆元为b，即ba=e；又设b的左逆元为b’，即b’b=e．于是(b’b)(ab)=e(ab)=

(ea)b=ab；但我们又有(b’b)(ab)＝b’[(ba)b]=b’(eb)=b’b=e，所以我们得到ab=e，即b也是a的右逆元．左逆元同时也是右逆元电子科技大学计算机科学与工程学院UESTCPress第二章群群的

基本性质（证明）证明设G是一个群，e是G中的左单位元．2）aG，设其左（右）逆元为b．则(ab)a=ea=a；又(ab)a=a(ba)=ae；所以ae=a，故左单位元也是右单位元．左单位元同时也是右单位元电子科技大学计算机科学与工程学院UESTCPress第二

章群群的基本性质（证明）证明设G是一个群，e是G中的左单位元．3）如果G中存在另一单位元e’，我们有e=ee’=e’，则单位元是唯一的单位元是唯一的电子科技大学计算机科学与工程学院UESTCPress第二章群群

的基本性质（证明）证明设G是一个群，e是G中的左单位元．4）aG，设b，c都是a的逆元，则b=be=b(ac)=(ba)c=ec=c，则每个元素的逆元是唯一的．逆元是唯一的电子科技大学计算机科学与工程学院UESTCPress第二章群群的阶、元素的阶

定义2.1.3如果一个群G中元素的个数是无限多个，则称G是无限群；如果G中的元素个数是有限多个，则称G是有限群，G中元素的个数称为群的阶，记为|G|．如前面例2.1.1提到的数群是无限群，例2.1.3的模2加法群，阶为2，例2.1.4的群阶为4电子科技大

学计算机科学与工程学院UESTCPress第二章群群的阶、元素的幂由于群里结合律是满足的，所以元素连乘a1a2…an有意义，它也是G中的一个元．我们把a的n次连乘记为an，称为a的n次幂（或称乘方），即．我们还将a的逆元a−1的n次幂记为a−n，即群的逆元（a−1）

−1=a电子科技大学计算机科学与工程学院UESTCPress第二章群群的阶、元素的幂若ab=ba，则（ab）n=anbn另外：a−nan=e，aman=am+n，(an)m=anm电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质定理2.1.1一个群的乘法满足消去

律：如果ax=ax’，则x=x’；（左消去）如果ya=y’a，则y=y’．（右消去）证明假定ax=ax’，那么a−1(ax)=a−1(ax’)，(a−1a)x=(a−1a)x’，ex=ex’，x=x’．同理可证由ya=y’a

，得y=y’．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质定理2.1.2如果G是一个群，a，bG，方程ax=b，ya=b有解；反之，如果上述方程在非空集合G中有解，而且其中的运算封闭且满足结合律（即半群）

，则G是一个群．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质证明先证方程有解如果G是一个群，对于任一元素a有逆元a-1，由ax=b可得a−1(ax)＝a−1b，x=a−1b∈G于是x=a−1b是方程ax=b的解．同理y=b

a−1是方程ya=b的解．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质证明（续）：对于方程有解时，半群（G，·）是群。先证有左单位元：如果a，b，方程ax=b，ya=b在G中有解，则假设a=b时，方程亦有解，即ya=a有解，设其解为e。任取g∈G，方程ax=g有解，

设其解为b，即ab=g，于是有eg=eab=ab=g，因而e是左单位元。再证任a∈G有左逆元：因为方程ya=e有解，其解就是a的左逆元。综上，由定义2.1.1知，G对于运算“·”在满足封闭性结合性前提下，只要方程ax=b，ya=b有解，G关于运算“·”是

群电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质推论2.1.2.1如果一个非空集合G中的运算封闭且满足结合律，则它是一个群的充分必要条件是a，bG，方程ax=b，ya=b有解．电子科技大学计算机科学与工程学院UE

STCPress第二章群群的等价性质定理2.1.3如果一个非空有限集合G中的运算封闭且满足结合律，则它是一个群的充分必要条件是满足消去律．证明必要条件由定理1立即得到．只证明充分条件．如果消去律满足，则a，bG，方程ax=b，ya=b有解．先证明方程ax=b在G中有解．假设G有n个元素

，G={a1，a2，a3，，an}．用a左乘G中的每个元素得到G’={aa1，aa2，aa3，，aan}，电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质证明（续）由于乘法的封闭性，G’是G的子集，而且G’中的n个元素两两不同，

不然假设aai＝aaj，其中ij，由消去律得ai＝aj，其中ij，这是不可能的．于是G’也有n个两两不同的元素，则G’=G．设b=aak，则ak就是以上方程的解．同样可证ya=b有解．由定理2.1.2，G是一个群．定理证

毕．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群定义2.2.1一个群G的一个子集H如果对于G的乘法构成一个群，则称为G的子群也记作H≤G．一个群G至少有两个子群：G本身；只包含单位元的子集{e}，它们称为G的平凡子群，其

他子群成为真子群(H＜G)．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群例2.2.1设m是一个正整数．整数加群Z中每个元素的m倍数{0，m，2m，3m，…}对加法也构成群，它是Z的子群，记为mZ．电子科技

大学计算机科学与工程学院UESTCPress第二章群2.2子群引理一个群G和它的一个子群H有：1）G的单位元和H的单位元是同一的；2）如果aH，a−1是a在G中的逆元，则a−1H．证明对于任意aH，有aG．1）反证法．设G的单位元为e，H的单

位元为e’，而且ee’．由于e’HG，则G中的单位元不唯一，与群的定义矛盾，故e=e’．2）反证法．对于任意aH，假设a−1H，则a在H中存在另一逆元a’，由于a’G，则a在G中存在两个逆元，得到矛盾，故a−1H．电子科技大学计算机科学与工程学院UES

TCPress第二章群2.2子群定理2.2.1一个群G的一个非空子集H构成一个子群的充分必要条件是：1）a，bH，有abH；2）aH，有a−1H．证明首先证明充分条件．由于1），H是封闭的．结合律在G中，在H中自然成立．现证明H中有单位元．对于任意aH，由于aG

，所以存在a−1使a−1a=e．由2）有a−1H，由1）就有a−1aH，于是a−1a=eH，则G中的单位元在H中．H不可能再有单位元，否则G的单位元不唯一．由2），H中的每个元素都有逆元．故H是一个群．再证明必要条件．1）是封闭性，是必要的．2）由引理也是必要的．证毕．电子科

技大学计算机科学与工程学院UESTCPress第二章群2.2子群定理2.2.2一个群G的一个非空子集H构成一个子群的充分必要条件是：对于任意a，bH，有ab−1H．证明我们证明这个条件和定理2.2.1的两个条件是一致的，即和定理

2.2.1等价．先证明由定理1的两个条件可推出这个条件．a，bH，有b−1H，则ab−1H．反过来，这个条件可推出定理1的两个条件．由aH，有aa−1=eH，于是ea−1=a−1H．又由a，bH，（参

照上一行，）有b−1H，于是a(b−1)−1=abH．证毕．在判定子群时，此定理经常用到电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群定理2.2.3一个群G的一个非空有限子集H构

成一个子群的充分必要条件是：对于任意a，bH，有abH．证明H是有限集合，我们证明H满足1.1中的定理3的3个条件．H显然满足封闭性；结合律在G中满足，在H中自然满足；消去律在G中满足，在H中自然满足．故H是一个群．定

理3表明一个群的一个非空有限子集是一个群的充分必要条件是：只要它满足封闭性．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群例2.2.2例2.2.1用定义判断了mZ是Z的子群，现在我们用定理

2.2.2来判断mZ是Z的子群．设a，bmZ，则有t1，t2Z，使a=mt1，b=mt2．b在Z中的加法逆元是−b，于是a+(−b)=mt1+(−mt2)=m(t1−t2)由于t3=t1−t2Z，所以a+(−b)=mt3mZ则mZ是子群电子科技大学计算机科学与工程学院UE

STCPress第二章群2.2子群例3复数域上的8次方程z8−1=0的根集合{，k=0，1，2，…，7}是一个乘法群．由定理3可验证其中的子集{，k=0，1，2，3}是一个子群电子科技大学计算机科学与工程学院UESTCPress第二章群定义1一个集合A到另一个集合

B的映射f是aA，都有一个确定的b=f(a)B与之对应．b称为a在f下的像，而a称为b在f下的一个逆像（原像）．2.3同构与同态——映射AfabB电子科技大学计算机科学与工程学院UESTCPress第二章群映射a，bA，如果ab，就有f(a)f(b)，则称f为单射．bB，总有a

A，使f(a)=b，则称f为满射．既是满射又是单射的映射称为一一映射．单射的含义就是A中的每个元素在B中有不同的像，满射是B中的每个元素都成为A中元素的一个像，一一映射是A中的元素与B中的元素一一对应．电子科技

大学计算机科学与工程学院UESTCPress第二章群例2.3.1设A={1，2，3}，B={2，4，6}．下图中的映射f是一个单射，又是一个满射，它是一一映射．例2.3.1设A={1，2，3}，B={2，4，6}．下图中的映射f是一个单射，又是一个满射，它是一一映射．例2.3.1设A

={1，2，3}，B={2，4，6}．下图中的映射f是一个单射，又是一个满射，它是一一映射．例2.3.1设A={1，2，3}，B={2，4，6}．下图中的映射f是一个单射，又是一个满射，它是一一映射．例2.3.1设A={1，2，3}，B={2，4，

6}．下图中的映射f是一个单射，又是一个满射，它是一一映射．映射例2.3.1设A={1，2，3}，B={2，4，6}．下图中的映射f是一个单射，又是一个满射，它是一一映射．AB12326f4电子科技大学计算机科学与工程学院UESTCPress第二章群映射显然一个一一映射f：A→

B存在一个逆映射f−1：B→A，它也是一一映射．AB12326f-14电子科技大学计算机科学与工程学院UESTCPress第二章群映射如果A=B，映射f也称为变换，即一个集合到自身的映射称为变换如果一个集合A到自身的映射f定义为：对于任意aA，f(a)=a，则称映射f为恒等映射，单位映

射或恒等变换，记为I．电子科技大学计算机科学与工程学院UESTCPress第二章群同态和同构定义2.3.2假设（A，·）和（B，⊙）是两个群，若存在映射f：A→B满足：任意a，b∈A，均有f（a·b）=f（a）⊙f（b）则称f是A到B的一个同态映射或简称同态。

同态映射也简称为同态．如果f是单射，则称f是单同态，如果f是满射，则称f是满同态，如果f是一一映射，则称f是同构映射．如果G=G’，同态f称为自同态，同构映射f称为自同构映射．电子科技大学计算机科学与工程学院UESTCPress第二章群同态

和同构例2.3.2假设整数集合Z里的运算是加法，Z通过映射f：a→ea产生一个实数集合（这里的e是自然常数）：｛ea｜aZ｝，我们定义这个实数集合里的运算是乘法，于是有f(a＋b)=f(a)f(b)，显然Z中的运算在｛ea｜aZ｝中得到了保持，f就是一个同态映射电子科

技大学计算机科学与工程学院UESTCPress第二章群同态和同构如果同态映射还是一一映射，则称为同构映射．例2.3.2的映射f：a→ea就是一个一一映射，所以f为同构映射电子科技大学计算机科学与工程学院UESTCPress第二章群同态和同构定理2.3

.1假设G和G’是两个群，在G到G’的一个同态（映射）f之下，1）G的单位元e的像f(e)是G’的单位元e’，即f(e)=e’．2）G的任意元a的逆元a－１的像f(a−1)是f(a)的逆元，即f(a−1)=f(a

)−1．3）G在f下的像的集合{f(a)aG}是G’的子群，称为f的像子群．当f是满同态时，像子群就是G’本身．电子科技大学计算机科学与工程学院UESTCPress第二章群同态和同构证明1）：由于f(

e)f(e)=f(e2)=f(e)，两边同乘f(e)−1，得f(e)=e’．2）aG有f(a−1)f(a)=f(a−１a)=f(e)=e’所以f(a)−1=f(a−1)．3）如果a’，b’{f(a)aG}，设a’=f(a)，b’=f(b)，则

a’b’−1=f(a)f(b)−1=f(a)f(b−1)=f(ab−1){f(a)aG}=G’，由定理2.2.2，得{f(a)aG}是G’的子群．电子科技大学计算机科学与工程学院UESTCPress第二章群同态和同

构定义2.3.3设G和G’是两个群，如果存在一个G到G’的同构映射，则称G与G’同构，记为GG’．如果G=G’，则称G自同构．例2.3.3整数加法群Z和偶数加法群E同构．例2.3.4实数加法群R和正实数乘法群R+同构．同构映射为f(a)=ea．例2.3.5任意一个二阶群都与乘法群{1，−

1}同构．证明：设一个任意二阶群为A={e，a}，e为单位元．构造如下A到乘法群{1，−1}的映射：f：e→1，b→−1显然f是同构映射，于是A与乘法群{1，−1}同构．电子科技大学计算机科学与工程学院UESTCPress第二章群同态和同构可以看出

，群的同构具有反身性，对称性和传递性，即它是等价关系：1）GG；2）由GG’可推出G’G；3）由GG’和G’G’’可推出GG’’．电子科技大学计算机科学与工程学院UESTCPress第二章群同态映射的核假设f是G到

G’的同态映射．a’G’，集合{af(a)=a’,aG}可能是空集，也可能包含一个以上的元素（当f不是单射时可能有多个元素）．我们称这个集合是a’的完全反像．特别地，单位元的完全反像称为同态映射f的核

，记为ker(f)，即ker(f)={aaG,f(a)=e’}=f-1(e’)．电子科技大学计算机科学与工程学院UESTCPress第二章群同态映射的核定理2.3.2ker(f)是G的子群，称为f的核子群．证明由于一定有eker(f)，所以ker(f)不会是空集．如果a

，bker(f)，则f(a)=e’，f(b)=e’，f(b)−1=(e’)−1=e’，于是f(ab−1)=f(a)f(b−1)=f(a)f(b)−1=e’e’=e’，所以ab−1ker(f)，故ker(f)是G的子群．电子科技大学计算机科学与工程学院UES

TCPress第二章群同态映射的核定理3G到G’的同态映射f是单同态的充分必要条件是ker(f)={e}，即核子群只含有单位元．证明先证充分条件．用反证法．如果ker(f)={e}，但存在a，bG，ab，有f(a)=f(

b)，于是f(a)f(b)−1=e’，由于f是同态，则f(ab−1)=e’．而由ab，有ab−1e，这与ker(f)={e}矛盾，故f是单射，因而是单同态．必要条件证明：由于eker(f)，如果ker(f)还包含其他元素，则f不是单射，故ker(f)={e}．电子科技大学计

算机科学与工程学院UESTCPress第二章群同态映射的核同态映射和核子群、像子群的关系可以形象地表示如图2.3.1．e’ker(f)像子群G’Gf电子科技大学计算机科学与工程学院UESTCPress第二章群2.4变换群与置换群变换是一个集合到自身的映射．例2.4.1实数集

合R到R的一个变换f：对于aR，f(a)＝a2．例2.4.2集合A={1，2}，它的全部变换为：f1：1→1，2→1，f2：1→2，2→2，f3：1→1，2→2，f4：1→2，2→1．其中f3和f4是一一变换．电子科技

大学计算机科学与工程学院UESTCPress第二章群变换群我们规定集合A上的两个变换f和g的乘法(变换的复合)如下：aR，fg(a)=f(g(a))．例2.4.3集合A={1，2，3，4}．设变换

f为：1→2，2→4，3→1，4→3．变换g为：1→3，2→1，3→2，4→4．则fg为：1→1，2→2，3→4，4→3．定义2.4.1一个集合的若干变换如果对于变换的乘法构成群，则称为变换群．电子科技大学计算机科学与工程学院UESTCPress第二章群变换群定理2.4.1（Cayley定理）任

何一个群都同构于一个变换群．证明证明的思路是对于任意一个群，我们构造出与之同构的一个变换群．设G是一个群，我们构造一个变换集合T如下：T={xG，f(x)=ux|uG}我们可以证明T是一个一一变换群现在我们构造G到T的同构映射．我们建

立一个G到T的映射如下：：aG，a→(xG，f(x)=ax)对于a，bG，(ab)=(xG，f(x)=abx)=(a)(b)，是一个同构映射，所以G与T同构．电子科技大学计算机科学与工程学

院UESTCPress第二章群变换群例2.4.4构造与非零实数乘法群R*＝R\{0}同构的变换群．R*的变换集合T={xR*，f(x)=ux|uR*}是一个变换群．R*到T的同构映射：：aR*，a→(xR*，f(x)=ax)．T与R*同构．电子科

技大学计算机科学与工程学院UESTCPress第二章群置换群定义2.4.2一个有限集合的一一变换称为置换．设一个有限集合A有n个元素，A={a1，a2，a3，，an}，则一个置换可以表示为：ai→，i=1，2，3，…，n也可表示为：如果抽掉元素的具

体内容，置换还可表示为：实际上，第一行元素的任意一个排列都是一种表示，但一般情况下我们还是用(1，2，3，…，n)次序表达．1212nnkkk电子科技大学计算机科学与工程学院UESTCPress

第二章群置换群例2.4.5n=3，置换：a1→a2，a2→a3，a3→a1于是一个有限集合的若干置换构成的群称为置换群．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群定理2.4.2一个有限集合的所有置换对于变换的乘法构成一个群．证明设一个有限集合A的所有置换

的集合为S．假设f，gS，对于任意a，bA，如果ab，则有g(a)g(b)，f(g(a))f(g(b))，fg(a)fg(b)所以fg是单射，又由于g和f是满射，因此fg也是满射，故fg是一一变换，S对于乘法是封闭的．假设f，g，hS，对于任意aA，有f(gh

)(a)=f(g(h(a)))，又有(fg)h(a)=f(g(h(a)))，故结合律成立．S中存在乘法单位元，即恒等变换I．任意fS是一一映射，所以它存在逆映射f−1，f−1也是一一变换，是S中f的逆元所以S对于变换的乘法是一个群．证毕．电子科技大学

计算机科学与工程学院UESTCPress第二章群置换群•一个包含n个元素的集合的全体置换构成的群称为n次对称群，记为Sn．置换群是对称群的子群．•由初等数学中排列组合知识可以得知，一个置换实际上就是A元素的

一次排列，n个元素的总排列次数是n!，所以n次对称群Sn的阶|Sn|=n!．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群例2.4.63次对称群S3，它有3!=6个元素：读者可以验证，S3是一个非交换群．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群

定理2.4.3每一个有限群都与对称群的一个子群，即一个置换群同构．现在我们讨论置换中非常重要的循环置换，或简称循环．定义3Sn的一个如下置换：其余元素保持不变，即称为k－循环．K－循环可以用下面的符号表示：电子科技大学计算机科学与工程学院UESTCPress第

二章群置换群＝(i1i2…ik)．同样可以表示为：＝(i2i3…iki1)＝…＝(iki1i2…ik−1)．定义中的k－循环多种表示与一种置换的多种表示是同样的道理．容易证明k=I．（I—恒等变换）在K－循环中，2－循环称为对换．电子科技大学计算机科学与

工程学院UESTCPress第二章群置换群例2.4.7我们列举S5中三个循环的例子：1==(123)=(231)=(312)，2==(12345)=(23451)=…=(51234)，3==(12)．1是3－循环；2是5－循环；3是2－循环，即对换．1221

电子科技大学计算机科学与工程学院UESTCPress第二章群置换群两个循环=(i1i2…ik)和=(j1j2…jm)如果对于任意r和s，都有irjs，则称和是不相交循环．置换的乘积一般是不可交换的，但对于不相交循环我们有下列定理．定理2.4.4不相交

循环的乘积是可交换的．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群定理2.4.5任一置换都可表示为若干个两两不相交的循环的乘积，而且表示是唯一的．证明：假设是一个n元置换：首先将置换中的1阶循环元素划掉．从剩下的元素中任选a

1，连续做置换：a1→a2→a3→a4→a5→a6→…由于元素个数是有限的，则这个序列进行下去一定有ai=aj．我们可以证明i=1．因为是一一变换，则如果ai=aj，就有ai−1=aj−1，接着又有ai−2=aj−2，

ai−3=aj−3，….，a1=aj−i+1．如此反复最后直到将n个元素全部划掉，分解成了若干两两不相交的循环的乘积电子科技大学计算机科学与工程学院UESTCPress第二章群置换群于是上面的置换序列是

以a1开始的若干元素的循环．将这些元素划掉，再从剩下的元素中任选一个元素重复上述过程，又会得到一个循环，且与上一个循环不相交．唯一性证明：如果分解不唯一，假设有两个不同的分解式，则会存在两个元素i，j，在第一个分解式里j紧接着i出现，但在第二种分解式紧

接着i的却不是j，这意味着在第一个分解式里(i)=j，而在第二种分解式里(i)j，得到矛盾．定理证毕．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群我们指出，任何循环(i1i2…ik)都可表示为对换的乘积，即(i1i2…i

k)=(i1i2)(i1i3)…(i1ik)利用变换的乘法我们很容易验证上式，计算(i1i2)(i1i3)…(i1ik)：i1→ik，ik→i1→ik−1，ik−1→i1→ik−2，ik−2→i1→ik−3，…i3→i1→

i2，i2→i1，即i1→ik→ik−1→ik−2…→i2→i1，正好等于循环(i1i2…ik)．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群定义2.4.4如果一个置换可以表示为偶数个对换的乘积，则称为偶置换；如果一个置换可以表示为奇数个对换的乘积，则称为奇置换．显

然两个偶置换的乘积为偶置换，两个基置换的乘积也是偶置换，但一个偶置换和一个基置换的乘积为基置换．n元偶置换全体组成的集合为An．电子科技大学计算机科学与工程学院UESTCPress第二章群置换群定理2.4.6An对乘法构成一个群，称为交错群，其阶|An|=n!/2

．证明：An={|Sn，是偶置换}，An是对称群Sn的一个有限子集．如果1，2An，由两个偶置换的乘积是偶置换，有12An，由定理2.2.3得An是Sn的一个子群．设Bn={|Sn，是奇置换}，则Sn=An∪Bn

．取一个奇置换Bn，由于Sn是有限群，于是有Sn=An∪Bn．由于奇置换和偶置换的乘积为奇置换，现在An是奇置换集合而Bn成为偶置换集合，于是Sn=An∪An，|Sn|=|An|+|An|=2|An|，|An|=|Sn|/2=n!

/2．电子科技大学计算机科学与工程学院UESTCPress第二章群谢谢!