离散数学64子群及其陪集课件.ppt

1、6.4 子子 群群 及及 其其 陪陪 集集 6.4.1 子 群 的 定 义 6.4.2 子群的判别条件 6.4.3 循 环 群 6.4.4 陪 集 l它是一种相传很久的有趣游戏,如下图,最上面一排是参加抽签者的名字,最下面一排是签号、奖品或公差。每个人依次顺着竖线往下走，碰到有横线时，即转向横向前进，碰到竖线再往下走，依次类推，则只要横线不要跨过3条竖线（只能跨在两竖线之间），那么此游戏执行完毕后，最上面的每个人会1-1对应到最下面一排的位置。一般在设计游戏时，是由主持人先画好竖线和横线，且在最下面先标好签号，由抽签者自行填上最上面的人名。有时，为了增加趣味性，先画好竖线填好上排的人名和下面的

2、签号，再请参加者自行画上横线（不过速度要快，要不然观察力强者，很快可以找出对应关系）。请同学们考虑是否可以使用置换的复合编程处理子群 设（G，）是一个群，H G，如果(H，)仍是一个群，则 （H，）叫做（G，）的子群。真子群 如果G的一个子群H不等于G，即H G，则（H，）叫做 （G，）的真子群。Note:G的子群H的运算必须与G的运算一样，比如，（C*，）不是（C，+）的子群。在群中成立的性质在子群仍成立。l例.（mZ，+）是整数加法群（Z，+）的一个子群。l例.（C，+）以（R，+）、（Q，+）、（Z，+）为其真子群。l例.（C*，）以（R*，）、（Q*，）为其真子群。l例.行列式等于1的

3、所有n阶矩阵作成所有n阶非 奇异矩阵的乘法群的一个子群。l例.n次交代群是n次对称群的一个真子群。群G一般都有两个明显的子群,称为G的平凡子群：l由其单位元素组成的子群1，称为G的单位子群；lG本身。其余的子群（如果有的话）称为非平凡子群。l设Z6=0,1,2,3,4,5是模6的剩余类集合，则Z6在剩余类加法下是一个群，其中0和Z6是该群的两个平凡子群，0，3和0，2，4是其非平凡子群，而0，1，3，5不是子群。l例 设(G,*)是群，对G中任意a,令H=x|x*a=a*x,xG,试证明(H,*)是(G,*)的子群。l证明：显然1H,即H非空，对H中任意x,y 有(x*y)*a=x*(y*a)

4、=x*(a*y)=(x*a)*y=(a*x)*y=a*(x*y)，故x*yH，即H中*运算封闭。在H中*运算显然仍满足结合律。对H中任意x 有x*a=a*x，于是x-1*(x*a)*x-1=x-1*(a*x)*x-1，化简得到a*x-1=x-1*a，即x-1 H。证毕l使用同样办法可以证明下面练习：l设G是一个群，H是G的一个子群。aG。试证laHa-1=aha-1|hH是G的子群。也称共扼子群。判别条件一定理6.4.1 群G的一个子集H是G的一个子群的充分必要条件是：(1)若aH，bH，则abH；(2)若aH，则a-1H；(3)H非空。证明：必要性 若H是G的子群，则(1)、(3)显然。现要

5、证（2）.先证H中的单位元就是G中的单位元。设1G是G中的单位元，1H是H中的单位元。任取aH，则在H中有：1H a=a，故在G中也成立。以a-1右乘得(1H a)a-1=aa-1，即，1H(aa-1)=1G，1H 1G=1G，故，1H=1G。由群的定义，对于H中的a，应有bH使，ab=1H=1G，此式在G中亦成立，以a-1左乘得b=a-1 1G=a-1，因而a-1H，即（2）成立。必要性证毕。充分性 设(1),(2),(3)成立。l由(3)，H非空。l由(1)，H中的两个元素a，b可以在H内相乘.l在G中成立的结合律在子集H中自然成立。l往证H中有单位元1G。任取aH,由(2),a-1H,由

6、(1),aa-1H，即1GH；1G在G中适合1a=a，故在H中亦有此性质。l往证H中任意元素a有逆.因由(2),a-1H，但是G中，a-1a=1G，此式在H中亦应成立，故a-1即a在H中之逆。综上，H在G的运算下是一个群，故是G的子群。H的单位元素就是G的单位元素，H中任一元素a在H中的逆元素也就是a在G中的逆元素。子群H与大群G的关系定理6.4.2 判别条件一中的两个条件（1），（2）可以换成下面一个条件（*）若aH，bH，则ab-1H。证明：设(1),(2)成立，往证（*）成立。设aH，bH，由（2），b-1H，故由（1），ab-1H，因而（*）成立。设（*）成立，往证(1),(2)成立。

7、设aH，由（*）可推得，aH，aH，故aa-1H,即1H。又由（*）可推得，1H，aH，故1a-1H，即a-1H，因而（2）成立。设aH，bH，因为（2）已证,故b-1H。再由(*)推知,aH,b-1H,故a（b-1）-1H，即 abH，故（1）成立。l例 设H和K都是群G的子群，令HK=xy|xH,yK。试证若HK=KH，则HK是G的子群（此题的逆命题就是书中习题6.4的14）因为1H,1K，故1HK，即非空。l对于任意的x=hk,y=h1k1,这里h,h1H,k,k1K，有xy-1=(hk)(h1k1)-1=h(kk1-1)h-1。l记k2=kk1-1K,由HK=KH，存在h3H,k3K使

8、k2h1-1=h3k3。l从而xy-1=hh3k3=(hh3)k3HK。由定理6.4.2知HK是G的子群。定理6.4.3 设H群G的一个有限非空子集，则H是G的子群的充分必要条件是H对G的运算是封闭的，即若aH，bH，则abH。提示：充分性证明用教材201页习题2得出的结论：若非空、运算封闭、结合律、消去律、有限，则为群。l定理6.4.4 设a是群G的一个元素。于是a的所有幂的集合 an，n=0，1，2，做成G的一个子群，记为（a）。此群称为由a生成的子群。证明：（1）（a）非空，至少a0=1（a）。（2）任取（a）中二元素am，an，有 am（an）-1=ama-n=am-n（a）。故由子群

9、判别条件二，（a）做成G的一个子群。l定义.如果群G可以由它的某元素a生成，即有aG使G=（a），则G叫做一个循环群，或巡回群。上面定理中的（a）称为由a生成的循环子群。l例.整数加法群（Z，+）是由1生成的循环群。（nZ，+）是由n生成的循环群。l容易证明循环群必是 Abel群看由元素a所生成的循环群（a）：，a-2，a-1，a0，a，a2，（1）情形10 如果（1）中所有元素都彼此不同，则称a的周期为无穷大或0。此时，对任意两个不同的整数s与t，asat。情形20 如果（1）中出现重复的元素，即有整数 st，使as=at。不妨设st，于是s-t0且as-t=1，即有正整数m使am=1。若n

10、为适合an=1的最小正整数，则称a的周期（阶）为n。例.4次对称群中（1 2 3 4）的周期是4，因为 （1 2 3 4）2=（1 3）（2 4）（1 2 3 4）3=（1 4 3 2）（1 2 3 4）4=I例.在（C*，）中，1的周期为1，-1的周期为2，i的周期为4，模数r1的复数z=rei的周期为无穷大。l例 一个有限群中，周期大于2的元素个数为偶数。l证明：任取群中周期大于2的元素a，于是a21，由群的概念知a有逆元a-1，且a a-1(否则，若a=a-1，有a2=1，矛盾），这就是说a与a的逆a-1是成对出现的且它们的周期都大于2，由于a的任意性知周期大于2的元素个数为偶数。证毕。

11、l例 若有限群G的元数为偶数，则G中周期等于2的元素个数一定是奇数。l例 若群中除单位元外，所有其他元素的周期为2，则该群为Abel群。定理6.4.5 若群G中元素a的周期为n，则 （1）1，a,a2，a3，an-1为n个不同元素；（2）am=1当且仅当n m;（3）as=at当且仅当n(s-t)。证明：因为任意整数m恒可唯一地表为m=nq+r，0rn故am=anqar=(an)qar=1qar=lar=ar；由于0rn，故按周期的定义知ar=1 iff r=0所以am=1 iff r=0 iff nm即（2）得证。由（2）即知 as=at iff as-t=1 iff n(s-t)，即（3）

12、得证，最后由（3）立即可得（1）。l 结论：设a为群G的一个元素，（1）如果a的周期为无穷大，则（a）是无限循环群，（a）由彼此不同的元素 ，a-2，a-1，1，a，a2，组成。（2）如果a的周期为n，则（a）为n元循环群，它由n个不同的元素1，a，a2，a3，an-1组成。l例 设Sn是n次对称群。l（1）若Sn，=(a1a2ak)，则 的周期是k。l（2）Sn，=1 2 s是不相杂轮换的乘积，若i是ki阶轮换，i=1,2,s，则的周期是1,2,s的最小公倍数k1,k2,ksl证（1）k=(a1a2ak)k=(a1)，假若 的周期jk，则 j(a1)=(a1a2ak)j(a1)=aj+1a1

13、,矛盾，这就证明了j=k。l（2）设的周期为t，k1,k2,ks=d。由于1,2,s是不相杂的，则d=1d2d sd=(a1)，因此有td。另一方面，t=(a1),l由于两两不相杂，必有it=(a1),i=1,2,s。根据（1）部分的结果知i的周期为ki，因此对于所有的i 1,2,s有kit，即t是k1,k2,ks的公倍数，由于d是k1,k2,ks的最小公倍数，必有dt。综合上述结果有t=d。在加法群中，(a)应换为a的所有倍数的集合：，-2a，-a，0，a，2a，*当(*)中的所有元素均彼此不同时，称a的周期为无穷大或为0；否则当n为适合na=0的最小正整数时，称a的周期为n。注意这里的加法

14、表示满足交换律的一种抽象运算。定理6.4.5 若加法群中a的周期为n，则有(1)0，a，2a，（n-1）a为n个不同元素；(2)ma=0当且仅当n m;(3)sa=ta当且仅当n(s-t)定理6.4.6（1）无限循环群（a）一共有两个生成元：a及a-1。（2）n元循环群（a）中，元素ak 是（a）的生成元的充要条件是（n，k）=1。所以（a）一共有(n)个生成元素。证明：如果ak是（a）的一个生成元，那么（a）中每个元素都可表示为ak的方幂。特别地，a也可表示为ak的方幂。设 a=(ak)m=ak m。（1）由（a）是无限循环群知，km=1。因此，k=1。即，a及a-1为无限循环群（a）的生成

15、元。（2）如果（a）是一个n元有限群，那么a的周期为n。由周期的性质知，n|km-1。因此，km-1=nq，km-nq=1。这说明k与n互质。另一方面，如果k与n互质，则有h和-q，使h k-qn=1，即，hk-1=qn，故 n(kh-1)，由周期的性质知，a1=akh，a=(ak)h.故a可表为ak的若干次方.总之，a可表为ak的若干次方 iff k与n互质。但在0kn中，共有(n)个k与n互质，故共有(n)个元素ak可生成（a）。l例(Z,+)的生成元只能是1和-1.l若G=(a)是元数为12的群，(12)=4，与12互质的数有1，5，7，11，因此a,a5,a7，a11是G的所有4个生成

16、元。l有时需要根据子群H的一些特点将群分解成（划分成）一些不相交的子集合之并。如，在（Z,+)中，取一个正整数m，可得子群nZ=nzzZ，当m=2时，就是所有偶数在加法下作成的子群，通过这个子群就可以把整数加法群分解为奇数和偶数两个不相交子集合，它们就是相对于该子群（等价关系）的等价类-陪集。合同关系l定义.设G是群，H是G的子群，a，bG，若有hH，使得a=bh，则称a合同于b(右模H)，记为ab（右mod H）。l例.设G是三次对称群，H是由（1 2 3）生成的子群：H=I，（1 2 3），（1 3 2）。因为有IH，使得（1 2）=（1 2）I，所以（1 2）（1 2）（右mod H）。

17、因为有(1 2 3)H,使得(2 3)=(1 2)(1 2 3)，所以 （2 3）（1 2）（右mod H）。l结论:合同关系(右模H)是一个等价关系。证明：1)证反身性。因为对任意aG，有1H，使得a=a1，所以aa（右mod H）。2）证对称性。即证若ab(右mod H)，则ba(右mod H)。由a=bh,hH 可以推出b=ah-1，而且h-1H，故ba(右mod H)。3)证传递性。即证若ab(右mod H)，bc(右mod H)，则ac(右mod H)。由a=bh，b=ck，h，kH，可得a=ckh，其中khH，故ac（右mod H）。l定义.群G在合同关系（右模H）下的一个等价类叫

18、做H的一个右陪集。同样，可以界说a合同于b（左模H）：ab（左modH）和H的左陪集。l 结论：a所在的右陪集为 aH=ah|h H。注意：有些书上把右陪集称做左陪集，这没有关系，只要我们弄清楚就可以了。设G是整数加法群。H是m的所有倍数作成的子群，因为加法适合交换律，所以左右之分不存在，因而，（左mod H）和（右mod H）是一样的，左右陪集也是一样的。ab（mod H），即a=b+h(hH),亦即，a=b+km,故ab（mod m）。可见，H的陪集就是模m的剩余类。设G是所有非0复数的乘法群，所有其z=1的复数z=ei作成G的一个子群H。ab（mod H）等于说a=b。在复平面上，H相当

19、单位圆，H的所有陪集相当以原点为圆心的所有同心圆。若G是一个有限群，求H的右陪集：首先，H本身是一个；任取a H，aG,而求aH，又得到一个；任取b HaH而求bH又得到一个；如此类推，因G有限，最后必被穷尽，而G=HaHbH。例.设G是3次对称群：1,（1 2）,（1 3）,（2 3）,（1 2 3）,（1 3 2），H：1,（12），H有三个右陪集：1,(1 2)，(1 3),(1 2 3)，(2 3),(1 3 2)。H有三个左陪集：1,(1 2)，(2 3),(1 2 3)，(1 3),(1 3 2)设H是群G的有限子群，则H的任意右陪集aH的元数皆等于H的元数。证明：aH=ahhH，

20、又G中有消法律：由a=ay可以推出=y，故H中不同元素以a左乘仍得不同的元素。因而aH的元数等于H的元数。证毕该定理结果表明所有陪集元素个数相等。（1）若H为G的有限子群，则|aH|=|H|。（2）H本身也是H的一个右陪集。（3）aH=H的充分必要条件是aH。（4）a在陪集aH中。根据这点，把a叫做右陪集aH的一个陪集代表。（5）对于右陪集aH中任意元素b，都有aH=bH。证明：由baH知，存在hH，使得b=ah。因此，bH=ahH=a（hH）=aH。这点说明右陪集aH中任一元素都可以取做陪集代表。从（5）还可推出：（6）aH=bH的充分必要条件是a-1bH。（7）任意两个右陪集aH和bH或者

21、相等或者不相交。证明：如果aH和bH相交，则它们包含公共元素c，即caH，且cbH。因此，由（5）得aH=cH，且bH=cH。故，aH=bH。l定义.设H是群G的子群,设对G中的任意元素g,都有gH=Hg,则称H是G的正规子群。l 结论1 “平凡”子群H=1和G都是G的正规子群l 结论2 Abel群的任意子群是正规子群。l结论3 H是G的正规子群，必要而且只要对任意的gG，gHg-1 H.证明：必要性.由H是G的正规子群，知，对于任意gG，gH=Hg,即,gHg-1=H，故 gHg-1 H.充分性.设对任意gG，gHg-1 H。既然此式对任意gG成立，则以g-1G代g仍成立：g-1H（g-1）

22、-1 H，即，g-1Hg H；以g左乘以g-1右乘之，得H gHg-1因此，H=gHg-1对任意gG都成立,即，gH=Hg,因而H是正规子群。l结论4；设H是G的一个子群。H是G的正规子群当且仅当对G中任意的a，都有aHa-1=H，即H只有一个共扼子群，就是H自己。l证明：aHa-1=HaH=Ha，故有定义可知H是G的正规子群 aHa-1=H，对G中任意的a成立。设G为有限群，则G的任意子群H的元数整除群G的元数。证明：设|G|=n，|H|=r。设H有s个右陪集,则每个右陪集的元数等于H的元数r，再由不同的右陪集没有公共元素，知所有右陪集的并集有元数rs。而G等于所有右陪集的并集，故|G|=n

23、=rs=|H|s，即，子群H的元数整除群G的元数。注意：此定理逆命题不一定成立，换句话说,若正整数d是n的因子，但G不一定有d元子群。l如4次交代群（所有偶置换作成的群）A4的元数为12，6是其因子，但A4没有6元子群。lH在G中的指数:有限群G的元数除以H的元数所得的商，记为（G：H），称作H在G中的指数。l结论：H的指数也就是H的右(左)陪集的个数。l右代表系:从每个右陪集中选出一个元素为代表，全体代表的集合叫做一个右代表系或右代表团。l结论：设G有限而g1，gs作成一个右代表系，则g1H，gsH便是H的所有右陪集而 G=g1HgsH。l结论：指数等于2的子群一定是正规子群。l定理6.4.

24、8 设G为有限群，元数为n，对任意aG，有an=1。证明：因为G有限，a的周期必有限，否则a所生成的循环子群（a）将无限，G的元素将无穷多。命a的周期为m，则a生成一个m元循环子群（a）。按Lagrange定理，mn，即n0（mod m），因此an=1。l我们可以使用拉格朗日定理确定一个群内可能存在的子群、元素的周期等，从而搞清一个群的结构。以前我们确定一个群内的子群时，主要利用元素生成的子群。有个这个定理，就可以首先有G的元数的因子来确定可能存在子群的元数以及元素的周期，然后根据子群的元数来寻找子群。l证明6元群中一定有周期为3的元素。l证：根据定理6.4.8，G中元素的周期是6的因子，所以

25、G中只能有周期为1、2、3和6的元素，但G中有周期为6的元素a时，a2的周期就是3。l若G中不含有周期为6的元素，则G中除1 外，元素周期只能为2或3。下面用反证法证明G中必含周期为3的元素。若不然G中所有元素a，满足a2=1，即a=a-1。任取G中 a,b有lab=(ab)-1=b-1a-1=ba,G是Abel群。取G中非1的a和b，令H=1,a,b,ab，使用子群判定定理易证H是G的子群且有4个元素，与Lagrange定理矛盾。l例子 确定S3的所有子群。l因 S3=6,除平凡子群外，S3中只能有2或3元子群，又因2和3都是质数，因而它们都是循环子群，有周期为2或3的元素生成。故S3在所有

26、子群是H1=1,H2=(12),H3=(13),H4=(23),H5=(123)和H6=S3。l例子 确定所有可能的4元群。l因为元素的周期是群的元数的因子，故可分为以下几种情况讨论：l（1）G中存在周期为4的元a，则G=(a)。l（2）G无周期为4的元，则除单位元1外均为2，G是Abel群。可设G=1,a,b,c,(a),(b),(c)的元数为2。因ab1、a、b，所以ab=c，类似有ba=c,bc=cb=a,ac=ca=b，所以G=Klein四元群。l故4元群只有两种可能：4元循环群或Klein四元群。l设H是G的子群，a,bG,证明下列命题等价：l(1)a-1b H,l(2)b aH,l(3)aH=bH,l(4)aHbH。l设H是G的子群，证明如果H的任意两个右陪集的乘积仍是一个右陪集，则H是G的正规子群。l证明：首先证明，对任意的a,bG,aHbH=abH。事实上，由题设aHbH是H的一个右陪集，令其为 cH，显然有abcH,故abH=cH=aHbH。下面证H是G的正规子群。对任意aG,hH,ahaH,a-1a-1H，得到aha-1aHa-1H=aa-1H=H。有h的任意性知aHa-1H，证毕。