《《离散数学》课件: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,证毕。