《《离散数学》课件：6-4 子群及其陪集》由会员分享，可在线阅读，更多相关《《离散数学》课件：6-4 子群及其陪集（57页珍藏版）》请在金锄头文库上搜索。
1、6.4 子子 群群 及及 其其 陪陪 集集l6.4.1子群的定义l6.4.2子群的判别条件l6.4.3循环群l6.4.4陪集捉大头游戏l它是一种相传很久的有趣游戏,如下图,最上面一排是参加抽签者的名字,最下面一排是签号、奖品或公差。每个人依次顺着竖线往下走，碰到有横线时，即转向横向前进，碰到竖线再往下走，依次类推，则只要横线不要跨过3条竖线（只能跨在两竖线之间），那么此游戏执行完毕后，最上面的每个人会1-1对应到最下面一排的位置。一般在设计游戏时，是由主持人先画好竖线和横线，且在最下面先标好签号，由抽签者自行填上最上面的人名。有时，为了增加趣味性，先画好竖线填好上排的人名和下面的签号，再请参加
2、者自行画上横线（不过速度要快，要不然观察力强者，很快可以找出对应关系）。请同学们考虑是否可以使用置换的复合编程处理6.4.1 子 群 的 定 义子群设（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*
3、，） 为其真子群。l例.行列式等于1的所有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证明：显然1
4、H,即H非空，对H中任意x,y有(x*y)*a=x*(y*a)=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-1H。证毕l使用同样办法可以证明下面练习：l设G是一个群，H是G的一个子群。aG。试证laHa-1=aha-1|hH是G的子群。也称共扼子群。6.4.2 子群的判别条件判别条件一定理6.4.1群G的一个子集H是G的一个子群的充分必要条件是：(1)若aH，bH，则abH；(2)若aH，
5、则a-1H；(3)H非空。判别条件一判别条件一证明：必要性若H是G的子群，则(1)、(3)显然。现要证（2）.先证H中的单位元就是G中的单位元。 设1G是G中的单位元，1H是H中的单位元。任取aH，则在H中有： 1H a=a，故在G中也成立。以a-1右乘得(1Ha)a-1=aa-1，即，1H(aa-1)=1G， 1H1G=1G，故，1H=1G。判别条件一判别条件一(证明续证明续) 由群的定义，对于H中的a，应有bH使，ab=1H=1G，此式在G中亦成立，以a-1左乘得b=a-11G=a-1，因而a-1H，即（2）成立。必要性证毕。判别条件一判别条件一充分性 设(1),(2),(3)成立。由(3
6、)，H非空。l由(1)，H中的两个元素a，b可以在H内相乘.l在G中成立的结合律在子集H中自然成立。l往证H中有单位元1G 。任取aH,由(2),a-1H,由(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
7、，bH，则ab-1H。证明：设(1),(2)成立，往证（*）成立。设aH，bH，由（2），b-1H，故由（1），ab-1H，因而（*）成立。判别条件二判别条件二(证明续证明续) 设（*）成立，往证(1),(2)成立。设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）因
8、为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使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得出的结论：若非空、运算封闭、结合律、消去律、有限，则为群。6.4.3 循循 环环 群群 l定理6.4
9、.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）。故由子群判别条件二，（a）做成G的一个子群。6.4.3 循循 环环 群群l定义.如果群G可以由它的某元素a生成，即有aG使G=（a），则G叫做一个循环群，或巡回群。上面定理中的（a）称为由a生成的循环子群。l例. 整数加法群（Z，+）是由1生成的循环群。（nZ，+）是由n生成的循环群。l容易证明循环群必是 Abel群元素的周期元素的周期看由元素a所
10、生成的循环群（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为适合an=1的最小正整数，则称a的周期（阶）为n。周期的例周期的例例.4次对称群中（1234）的周期是4，因为（1234）2=（13）（24）（1234）3=（1432）（1234）4=I例.在（C*，）中，1的周期为1，-1的周期为2，i的周期为4，模数r1的复数z=rei的周期为无穷大。周期
11、的例l例一个有限群中，周期大于2的元素个数为偶数。l证明：任取群中周期大于2的元素a，于是a21，由群的概念知a有逆元a-1，且aa-1(否则，若a=a-1，有a2=1，矛盾），这就是说a与a的逆a-1是成对出现的且它们的周期都大于2，由于a的任意性知周期大于2的元素个数为偶数。证毕。周期的例l例若有限群G的元数为偶数，则G中周期等于2的元素个数一定是奇数。l例若群中除单位元外，所有其他元素的周期为2，则该群为Abel群。周期的性质周期的性质 定理6.4.5 若群G中元素a的周期为n，则（1）1，a,a2，a3，an-1为n个不同元素；（2）am=1当且仅当nm; （3） as=at当且仅当n
12、(s-t)。 证明：因为任意整数m恒可唯一地表为m=nq+r，0rn故am=anqar=(an)qar=1qar=lar=ar；由于0rn，故按周期的定义知ar=1iff r=0所以am=1iff r=0 iff nm即（2）得证。由（2）即知as=atiff as-t=1iff n(s-t)，即（3）得证，最后由（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次
13、对称群。l（1）若Sn，=(a1a2ak)，则的周期是k。l（2）Sn，=12s是不相杂轮换的乘积，若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,矛盾，这就证明了j=k。周期的例子l（2）设的周期为t，k1,k2,ks=d。由于1,2,s是不相杂的，则d=1d2dsd=(a1)，因此有td。另一方面，t=(a1),l由于两两不相杂，必有id=(a1),i=1,2,s。根据（1）部分的结果知i的周期为ki，因此对于所有的i1,2,s有kit，即t
14、是k1,k2,ks的公倍数，由于d是k1,k2,ks的最小公倍数，必有dt。综合上述结果有t=d。加法群中元素的周期加法群中元素的周期在加法群中，(a)应换为a的所有倍数的集合：，-2a，-a，0，a，2a，*当(*)中的所有元素均彼此不同时，称a的周期为无穷大或为0；否则当n为适合na=0的最小正整数时，称a的周期为n。注意这里的加法表示满足交换律的一种抽象运算。 定理6.4.5若加法群中a的周期为n，则有(1)0，a，2a，（n-1）a为n个不同元素；(2)ma=0当且仅当nm;(3)sa=ta当且仅当n(s-t)循环群的生成元素循环群的生成元素 定理6.4.6（1）无限循环群（a）一共有
15、两个生成元：a及a-1。（2）n元循环群（a）中，元素ak是（a） 的生成元的充要条件是（n，k）=1。 所以（a）一共有(n)个生成元素。证明：如果ak是（a）的一个生成元，那么（a）中每个元素都可表示为ak的方幂。特别地，a也可表示为ak的方幂。设a=(ak)m=akm。（1）由（a）是无限循环群知，km=1。因此，k=1。即，a及a-1为无限循环群（a）的生成元。（2）如果（a）是一个n元有限群，那么a的周期为n。由周期的性质知，n|km-1。因此，km-1=nq，km-nq=1。这说明k与n互质。另一方面，如果k与n互质，则有h和-q，使hk-qn=1，即，hk-1=qn，故n(kh-
16、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个生成元。群的结构l有时需要根据子群H的一些特点将群分解成（划分成）一些不相交的子集合之并。如，在（Z,+)中，取一个正整数m，可得子群nZ=nzzZ，当m=2时，就是所有偶数在加法下作成的子群，通过这个子群就可以把整数加法群分解为奇数和
17、偶数两个不相交子集合，它们就是相对于该子群（等价关系）的等价类-陪集。6.4.4 陪陪 集集合同关系l定义.设G是群，H是G的子群，a，bG，若有hH，使得a=bh，则称a合同于b(右模H)，记为ab（右modH）。l例.设G是三次对称群，H是由（123）生成的子群：H=I，（123），（132）。因为有IH，使得（12）=（12）I，所以（12）（12）（右modH）。因为有(123)H,使得(23)=(12)(123)，所以（23）（12）（右modH）。l结论:合同关系(右模H)是一个等价关系。证明：1)证反身性。因为对任意aG，有1H，使得a=a1，所以aa（右modH）。2）证对称性
18、。即证若ab(右modH)，则ba(右modH)。由a=bh,hH可以推出b=ah-1，而且h-1H，故ba(右modH)。3)证传递性。即证若ab(右modH)，bc(右modH)，则ac(右modH)。由a=bh，b=ck，h，kH，可得a=ckh，其中khH，故ac（右modH）。陪集陪集l定义.群G在合同关系（右模H）下的一个等价类叫做H的一个右陪集。同样，可以界说a合同于b（左模H）：ab（左modH）和H的左陪集。l结论：a所在的右陪集为aH=ah|hH。注意：有些书上把右陪集称做左陪集，这没有关系，只要我们弄清楚就可以了。陪集的例陪集的例设G是整数加法群。H是m的所有倍数作成的子
19、群，因为加法适合交换律，所以左右之分不存在，因而，（左modH）和（右modH）是一样的，左右陪集也是一样的。 ab（modH），即a=b+h(hH),亦即， a=b+km, 故ab（modm）。 可见，H的陪集就是模m的剩余类。陪集的例陪集的例设G是所有非0复数的乘法群，所有其z=1的复数z=ei作成G的一个子群H。ab（modH）等于说a=b。在复平面上，H相当单位圆，H的所有陪集相当以原点为圆心的所有同心圆。求陪集的简单方法求陪集的简单方法若G是一个有限群，求H的右陪集：首先，H本身是一个；任取a H，aG,而求aH，又得到一个；任取b HaH而求bH又得到一个；如此类推，因G有限，最后
20、必被穷尽，而G=HaHbH。例.设G是3次对称群：1,（12）,（13）,（23）,（123）,（132），H：1,（12），H有三个右陪集：1,(12)，(13),(123)，(23),(132)。H有三个左陪集：1,(12)，(23),(123)，(13),(132)定理定理6.4.7设H是群G的有限子群，则H的任意右陪集aH的元数皆等于H的元数。证明：aH=ahhH，又G中有消法律：由a=ay可以推出=y，故H中不同元素以a左乘仍得不同的元素。因而aH的元数等于H的元数。证毕该定理结果表明所有陪集元素个数相等。陪集的性质陪集的性质（1）若H为G的有限子群，则|aH|=|H|。（2）H本身
21、也是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或者相等或者不相交。证明：如果aH和bH不相交，则它们包含公共元素c，即caH，且cbH。因此，由（5）得aH=cH，且bH=cH。故，aH=bH。正规子群正规子群 l
22、定义.设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）-1 H，即，g-1Hg H；以g左乘以g-1右乘之，得H gHg-1因此，H=gHg-1对任意gG都成立,即，gH=Hg,因而H是正规子群。例
23、子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成立。LagrangeLagrange定理定理 设G为有限群，则G的任意子群H的元数整除群G的元数。证明： 设|G|= n，|H|=r。 设H有s个右陪集,则每个右陪集的元数等于H的元数r，再由不同的右陪集没有公共元素，知所有右陪集的并集有元数rs。 而G等于所有右陪集的并集，故|G|=n=rs=|H|s，即，子群H的元数整除群G的元数。反例注意：此定理逆命题不一定成立，换句话说
24、,若正整数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的子群一定是正规子群。应用应用LagrangeLagrange定理定理l定理6.4.8设G为有限群，元数为n，对任意aG，有a
25、n=1。 证明：因为G有限，a的周期必有限，否则a所生成的循环子群（a）将无限，G的元素将无穷多。命a的周期为m，则a生成一个m元循环子群（a）。按Lagrange定理，mn，即n0（modm），因此an=1。Lagrange定理的使用l我们可以使用拉格朗日定理确定一个群内可能存在的子群、元素的周期等，从而搞清一个群的结构。以前我们确定一个群内的子群时，主要利用元素生成的子群。有个这个定理，就可以首先有G的元数的因子来确定可能存在子群的元数以及元素的周期，然后根据子群的元数来寻找子群。例子l证明6元群中一定有周期为3的元素。l证：根据定理6.4.8，G中元素的周期是6的因子，所以G中只能有周期
26、为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在所有子群是H1=1,H2
27、=(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-1bH,l(2)baH,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，证毕。
