《离散数学》课件第八章

書式設定,*,代数结构：,群,第,8,讲,群,Group,“无论在什么地方，只要能应用群论，从一切纷乱混淆中立刻结晶出简洁与和谐，群的概念是近世科学思想的出色的新工具之一,.”,E,T,Bell,群与组合计数,物理,化学,计算机科学（逻辑,/,语义、密码学、通信编码、数据表示、,计数,）,确定,Ramsey,数,是著名的组合数学难题之一，不仅具有重大的理论意义，而且在计算机科学，通信、管理决策等许多领域有实际,应用,。,著名数学家G. C. Rota曾说过：如果别人问我们，组合数学中最精彩的东西是什么？那么大多数组合数学家都会说是Ramsey数问题。,应用数论、群论、组合数学、图论中的一系列概念和方法，创新算法，优化程序设计，通过计算机的大量计算寻找更好的结果：,具体,应用了数论中的同余与同余方程求解、剩余系的构造、原根、指数与标数、勒让德符号、高斯二次互反律、有限域等方法，应用了,群论,中的循环群、陪集和商群、同构与自同构、线性变换与等价类、群的可迁性与本原性等方法，组合数学中的集合的分拆、组合计数、容斥原理等方法，,图论,中的图的同构、完全图的分拆、边的着色、导出子图、独立集、团数与独立数、顶点的度、顶点可迁与边可迁、图的连通性、路、链等方法。,群与组合计数,物理,化学,计算机科学（逻辑,/,语义、密码学、通信编码、数据表示、,计数,）,以人造卫星仪器舱布局为例，如何求解全局最优的一种布局方案,？,可以应用图论、群对集合的作用、轨道与等价关系等刻划各种布局方案的同构、等价类等内在性质，从而在此基础上找出一种全局优化算法。,简化为,着色问题,置换群,所有可能的着色方案构成,集合,等价类（,轨道,）,计数,置换群、循环群,子群,陪集,/,拉格朗日定理,计数定理,群,主要内容,1,群（群性质、子群、,置换群,、拉格朗日定理）,2,群同态定理（正规子群、商群）,8,.1,群及其基本性质,8,.2,群的元素阶,8,.3,子群,8,.4,置换群,8,.5,循环群,8,.4,陪集与拉格朗日定理,8,.5,正规子群与群同态基本定理,i),存在单位元,e,ii)G,中每个元素存在逆元,广群,半群,结合律？,代数结构,独异点,单位元？,循环独异点,g,A,s.t,.,a,A,有,a=g,m,(m,N,),子半群、子独异点,群,(Group),Abel,群,交换律？,循环群,子群,8,.1,群及其性质,置换群,上述代数结构之间的关系,Abel,群,循环群,置换群,半群,独异点,群,广群,8,.1,群及其性质,8.1.1,群及其性质,定义,8.1,设,为代数结构，其中,G,是一个非空集合，*是,G,上的一个二元运算，若,1,）运算*满足结合律，即,a,，,b,，,c,G,，,(a*b)*c=a*(b*c),，,2,）运算*存在单位元,e,G,：,e*a=a*e=a,，,a,G,，,3,）对任意,a,G,，存在逆元,a,-1,G,，使得,a*a,-1,=a,-1,*a=e,，,则称代数结构,是一个,群,(Group),。,对于群,任意的二元素,a,，,bG,，均有,a*b=b*a,，则称,为,交换群,或称为,阿贝尔群,(Abel),。,8.1,群及其性质,群是抽象代数中具有简单的二元运算的代数结构，有时为了方便，在不致混淆的情况下，也常把群的代数运算称作,“,乘法,”,，且把,a*b,简记为,ab,。 另外，也常用,G,来表示群,。,如果一个群只包含有限个元素，则称为,有限群,，否则称为,无限群,。 若有限群,G,的元素个数为,n,，则称,n,为,群,G,的阶,，并记为,|G|=n,。 若,n=1,，则称,G,为平凡群。无限群的阶称为无限。,8.1,群及其性质,例,8.2,设,S=R-1,，,S,上定义运算*：,a*b=,a+b+ab,，试证明,是群。,证明,从以下几方面进行证明：,1),运算*在,S,上封闭：,任意,a,，,bS,，有,a*b=,a+b+abR,，且,a-1,，,b-1,。,若,a*b=-1,即,a+b+ab,=-1,，则,a=-1,或,b=-1,，与题,设矛盾，故,a*b-1.,所以,a*bS,，即运算*在,S,上封闭。,8.1,群及其性质,2),运算*满足结合律：,任意,a,，,b,，,cS,，,有,(a*b)*c=(,a+b+ab,)*c=,a+b+ab+c+(a+b+ab)c,=,a+b+c+ab+ac+bc+abc,且,a*(b*c)=a*(,b+c+bc,)=,a+b+c+bc+a(b+c+bc,),=,a+b+c+ab+ac+bc+abc,所以，,(a*b)*c=a*(b*c),，即*满足结合律。,3),存在单位元：,对任意,a,，,bS,，若,a*b=a,即,a+b+ab,=a,，,b,（,1+a,）,=0,，注意到,a-1,，故,b=0S,，从而有,a*0=a,。又,0*a=0+a+0,a=a,所以,0,为单位元。,8.1,群及其性质,4),每个元素存在逆元：,对于任意,aS,若,a*b=0,即,a+b+ab,=0, b=(-a)/(1+a),S,，即 有,a*(-a)/(1+a)=0,又,(-a)/(1+a),*,a=(-a)/(1+a)+a+(-a),a/(1+a),a(1+a)/(1+a)+a=0,故,(-a)/(1+a),为,a,之逆元。,综上知,是群。,8.1,群及其性质,示例,1,某通讯编码由,4,个数据位,x1,、,x2,、,x3,、,x4,和,3,位校验位,x5,、,x7,、,x8,构成，它们的关系如下：,x5=x1x2x3,x6=x1x2x4,x7=x1x3x4,其中，,为异或运算。若,S,为满足上述关系的码字的集合，且当,x,y,S,时有,xy,=,（,x1y1,x7y7,）。,则，,是群，试证明之。,8,.1,群及其性质,定理,8.1,性质,1,可约性,群,适合消去律,即对于任意,a,b,cG,，,则有：,(1),若,a*b=a*c,则,b=c,；,(2),若,b*a=c*a,则,b=c,。,性质,2,设,是一个群,对于任意的,a,bG,.,有：,(1),存在唯一元素,xG,，使得,a*x=b,；,(2),存在唯一元素,yG,，使得,y*a=b,。,性质,3,如果,G,；*,是一个群，对于任意的,a,，,bG,.,则有,(a*b),-1,=b,-1,*a,-1,8,.1,群及其性质,思考,4,一阶群仅有1个,二阶群仅有1个,三阶群仅有1个, 四阶群仅有2个,*,e,e,e,*,e,a,e,e,a,a,a,e,*,e,a,b,e,e,a,b,a,a,b,e,b,b,e,a,8,.1,群及其性质,示例,3,设,G，*,是一个群，则,G，*,是阿贝尔,(Abel),群的充要条件是,a,b,G,有,(a*b)*(a*b)=(a*a)*(b*b),8,.1,群及其性质,示例,4,1,设,是半群，若,a,b,M,，方程,aox,=b,，,yoa,=b,有解，则称,是可解的，请证明：此可解半群是群。,2,证明：有限半群,G,是群的充要条件是，,G,中消去律成立。,3,证明： 半群是群的充要条件是满足如下两个条件：,1）,G中有左单位元,e,L,;,2）,对,a,G,有元素a,-1,G,使得a,-1,o,a=e,L,8,.1,群及其性质,8.1.2,群中元素的阶,定义,8.2,设,a,为群,G,的一个元素，使,a,n,=e,的最小正整数,n,，称为,元素,a,的阶,（,Order,或,周期,）。若这样的,n,不存在，则称元素,a,的阶为无限，常记为。元素,a,的阶常用,|a|,表示。,根据定义，易知，单位元的阶为,1,，其它元素的阶均大于,1,。在群,中，,0,的阶为,1,，其它元素的阶皆是无限的。,R-0,对普通乘法构成群中，,1,的阶为,1,，,-1,的阶为,2,，其它元素的阶均为无限。,8.1,群及其性质,定理,8.2,设,a,是群,G,；*,中的一个周期为,r,的元素，,k,是一个整数，则有,(1),a,k,=e,当且仅当,k,为,r,的倍数。,(2) a,与,a,-1,的周期相同。,(3) r,小于或等于群,G,；*,中元素的个数。,8.1,群及其性质,例,8.6,证明：,若群,G,中元素,a,的阶是,n,，则,H =a,0,a,1,a,2,a,n-1,为群。,证明,首先注意到，,H,显然非空。 且,H,中任意,n,个元素是互异的，否则，假设,a,i,=a,j,(0ijn),，则,a,j-i,=,e,j-i,n,与,|a|=n,矛盾。,1,）,e=a,n,=a,0,H,为,G,单位元，也为,H,单位元。,2,）显然群,G,上的运算在,H,上满足结合律。,3,）任意元素,xH,，则存在,k,，,0kn,，使得,x=,a,k,，于是,x,的逆元为,a,n-k,是显然的。,8.1,群及其性质,4,）,H,为,G,的子集，且对任意二元素,a,i,a,j,H,(0,ijn),，,a,i,a,j,=,a,i+j,，,根据数论知识，存在整数,m,k,使得,i+j,=,m+kn,其中，,0mn,。,从而，,a,i,a,j,=,a,m+kn,=,a,m,a,kn,=,a,m,(a,n,),k,=,a,m,H,，即群,G,上的运算在,H,上满足封闭性。,综上，,H,为群。,8.1,群及其性质,请你思考,在有限群,中,每一元素具有有限阶,且阶数至多为,|G|.,证,:,a,G,则在序列,a,a,2,a,3,a,|G|+1,中至少有两个元素相同,不妨设,a,r,=a,s,(1s1,，则群,G,至少有两个子群，一个为由单位元,e,作成的子群,e,（以后常记为,e,），另一个是,G,自身，这两个子群被称为群,G,的,平凡子群,。 如果还存在其它子群，则被称为,非平凡子群,或,真子群,。,8.1,群及其性质,如果,H,是,G,的子群，则容易得到如下结论：,1,）若,a,，,bH,，则,abH,；,2,）,G,的单位元,e,也是,H,的单位元；,3,）,aH,，则,a,-1,H,。,结论,1,）是由于,H,在,G,的运算下满足封闭性，,2,）成立是因为：设,e,为,G,单位元，,e,为,H,单位元，则在,G,中，,ee,=e,，在,H,中有,e=,ee,于是,ee,=,ee,从而由群,G,的消去律有,e,=e,。,3,）可按,2,）,同样方式得到结论，或按如下方法讨论：设,a,H,在,H,中的逆元为,b,，则,ab,=e,，于是，在,G,中变换此式可得,b=a,-1,。从而,a,-1,H,。,8.1,群及其性质,3,子群判定,定理,8.3,判定定理,1,群,G,的非空子集,H,是,G,的子群的充要条件是：,a,b,H,，有,ab,-1,H.,2,群,G,的非空有限子集,H,是,G,的子群的充要条件,是,：,a,b,H,，有,ab,H,.,定理中的条件,a,bH,，则,ab,-1,H,，显然也可以改写成,a,bH,，则,a,-1,bH,。,8.1,群及其性质,例,8.8,设,为群，,R,为,G,上等价关系，且对任意的,x,，,y,，,z,G,，若（,x*z,）,R(y,*z),则,xRy,。令,H=,h|h,G,且,hRe,，其中，,e,是,的单位元。 证明：,是,的子群。,证明,由,R,为,G,上的等价关系有,e,G,eRe,，故,e,H,，从而,H,。,于是，对于,a,，,b,H,，有,aRe,，,bRe,，由,R,为,G,上的等价关系有,aRb,。,即,aeReb,，亦即,ab,-1,bReb,。,由题设，可得,ab,-1,Re,。,而,ab,-1,G,是显然的。,故,ab,-1,H,。,所以,是,的子群。,8.1,群及其性质,例,8.9,若群,G,中元素,a,的阶是,n,，则,H=a,0,a,1,a,2,a,n-1,为,G,之,n,阶子群。,证明,首先，,H,中任意,n,个元素是互异的，否则，假设,a,i,=a,j,(0ijn),，则,a,j-i,=,e,j-i,n,与,|a|=n,矛盾。,其次，,H,为,G,的有限子集，且对任意二元素,a,i,a,j,H(0ijn),，,a,i,a,j,=,a,i+j,根据数论知识，存在整数,m,k,使得,i+j,=,m+kn,其中，,0mn,。,从而，,a,i,a,j,=,a,m+kn,=,a,m,a,kn,=,a,m,(a,n,),k,=,a,m,H,。,根据子群判定定理，,H,为,G,的,n,阶子群。,8.1,群及其性质,思考与练习,1,是群,有G之非空子集T,若,a,b,T,有,a*b,T,a,-1,T,则,是,的子群,.,证,:,下面按照定义进行证明,a),运算封闭：,a,b,T,，由前提，,a*,b,T,b),结合律：,继承成立,c),单位元：,a,T,a,-1,T,于是,a*a,-1,T,，即,e,T,d),逆元存在：,a,T,，有,a,-1,T,所以，,是群,从而,是,的子群,7.3,子群,2,是,Abel,群,、,是其子群,设,AB=a*,b|a,A,b,B,则：,亦为,之子群,.,3,设,H=,a+b,*2,1/2,|a,b,Q,但,a,b,不同时为,0,试证,:,是,的子群,4,设,是群，若,H,G,a,b,H,a,-1,*,b,H,则,是,的子群,5,设,f、g,是从群,到群,的同态，,C=,x|x,A,且,f(x,)=,g(x,),请证明：,是,的子群。,6,有限群,G,的非空子集,H,是,G,的子群的充要条件是：,a,b,H,，有,ab,H,.,7,阅读教材例题,8.8,，,8.9,7.3,子群,7.4,置换群,图着色计数问题,变换,满射、单射、双射变换,变换群,(Transformation Group),有限集合上的双射变换？,置换,、,对称群,、,置换群,n,次置换,对称群，,n,次对称群，置换群,(Permutation Group),示例,置换及置换乘法,集合,X=1,，,2,，,3, 4,，共有,4,！,=24,个,4,次置换,7.4,置换群,示例,轮换,P,1,=(2143), P,2,=(13)(24), P,3,=(12)(34), P,1,P,3,=(1)(24)(3),7.4,置换群,对称群、置换群,对称群：,非空集合,X,上的全体双射变换构成的集合,S(X),关于,双射变换的乘法构成一个群,X,上的,n,次对称群,(,Symmetric group,), n=|X|,S,n,),S,n,的任意一个子群，称为一个,X,上的,n,次置换群，简称,X,上的,置换群,(Permutation group),。,7.4,置换群,示例,小球着色问题中，设每一个填置到正方形的顶点上的小球都着不同的颜色（不妨分别标记为,1,2,3,4,，如图所示），试求出其旋转构成的置换群。,(,Cayley,定理,),任意一个群都同一个双射变换群同构。,证明,设,G,是任意一个给定的群，任取,a,G,对,x,G,令,f,a,(x,)=ax,，,则易知,f,a,是,G,的一个,双射变换,。,S(G),为,G,的对称群，令,G=,f,a,|a,G,S(G,),。,现任取,f,a,f,b,G,则,f,a,f,b,(x,)=,fa(bx,)=,a(bx,)=,abx,=,f,ab,(x,),x,G, =b,-1,x= ,即有,f,a,f,b,=,f,ab,G, =,G,从而,f,a,=,f,a,=,G,从而,G,是,S(G),的子群，是一个,双射变换群,。,又令,：,GG,，使对,a,G,，有,(a)=,f,a,。,显然，,是一个双射。 且对,a,b,G,(,ab,)=,f,ab,=,f,a,f,b,=,(,a),(b,),即映射满足保运算性。,故群,G,与一个双射变换群,G,同构。,7.5,置换群,群 置换群,每一个有限群均与一个置换群同构。,置换群,G,作用在集合,X,上,等价,划分,：,G,可以诱导出,X,上的一个等价关系,R:,x,y(xRy,g,G(g(x,)=y),X,在,G,作用下的一个,轨道,(Orbit),：,x,R,=,g(x)|g,G,记为：,(x),a,为,g,的一个,不动点,(Fixed Element):,设,gG,，,aX,，若,g(a,) = a.,Fix,X,(g,)=,a|a,X,g(a,)=a ?,即在,g,作用下所有的不动点集合。,G,中使,x,保持不动的,不动置换类,:,以,x,为不动点的群,G,的所有元素的集合，即,g|g,G,g(x,)=x,，简记为,Fix,G,(x,),。,7.4,置换群,示例,X=,a,b,c,d, G=I,s,P,1,P,2,P,3,。,G,为,X,上的置换群？,G,在,X,上诱导出的等价关系,R?,X,在,G,作用下的轨道？,保持,X,中元素不动的不动置换类？,7.4,置换群,观察,|G|,、,|,(x)|,与,|,Fix,G,(x,)|,之间关系,？,|G|=|,(,x)|Fix,G,(x,)|,(,群论中的,Lagrange,定理,),7.4,置换群,Burnside,定理,G,是作用在有限集合,X,上的一个有限群，,X,在,G,作用下的轨道数为,7.4,置换群,7.4,置换群,Plya,计数原理,G,是作用在集合,X,上的一个有限群，如果用,k,种颜色对,X,中元素着色，则本质不同的着色数为,C(k,)=,其中，,m(g,),为,作用在,X,上的轨道数量，,称为,循环群,。,7.5,置换群,循环群的存在性问题、构造问题、数量问题以及子循环群问题等都已完全研究清楚,什么是循环群？,如果群,G,可以由一个元素,a,生成，即,G=,a,k,|k,Z,则称,G,为由,a,生成的一个,循环群,(Cyclic Group),，记为,G=,称,a,称为,G,的一个,生成元,（,Generator,）。,8,.,2,循环群,8,.,2,循环群,示例,1,）容易证明循环群是,Abel,群。,2,）整数加群,Z,是无限阶循环群。,3,）,n,次单位根群,U,n,= |k=0,，,1,，,n-1,是,n,阶循环群，其生成元,=,，即,U,n,=,。,几个结论,1),设群,G=,若,|a|=,，则,=, a,-2,a,-1,e,a,1,a,2,2),设群,G=,若,|a|=n,，则,为,n,阶群，,=a,0,a,1,a,2,a,n-1,可以看出，循环群的阶与其生成元的阶是相同的,3),无限循环群,有两个生成元，即,a,与,a,-1,; n,阶循环群有,(n),个生成元,4),设,是任意一个循环群，若,|a|=,，则,与整数加群,Z,同构；若,|a|=n,则,与,n,次单位根群,Un=(,为,n,次单位根,),同构。,5),无限循环群有无限多个子群,:,，,都是全部互异的的子群,6),循环群的子群也是循环群,7),当,为,n,阶循环群时，对,n,的每个正因数,k,，,有且仅有一个,k,阶子群，此时,所有的循环子群为,H,k,=,（其中,k|n,）。,8,.,2,循环群,例,8.18,1),无限循环群有多少个子群？,2),循环群的子群是否为循环群？,证明,1),设无限阶循环群为,则易知,，,都是全部互异的的子群。 所以，无限循环群有无限多个子群。,2),设,H,是循环群,的任一子群，,H=e,显然是循环群，下设,He,。,设,a,m,为,H,中,a,的最小正幂，则,a,-,m,H,于是由,H,是子群，易得,(,a,m,),k,H,k,Z,，从而,H,。,另一方面，任取,a,s,H,，令,s=,mq+r,，,0rm,。 则由,a,s,a,m,H,有,a,r,=a,s-,mq,=,a,s,(a,m,),-q,H,。,但,a,m,是,H,中最小正幂的元素，而,0rm,故,r=0,。从而,a,s,=a,mq,=(a,m,),q,。,于是有,H,。所以，,H=,。故,H,也是循环群。,所以,，,循环群的子群仍然为循环群。,8.2,循环群,例,8.19,当,为,n,阶循环群时，对,n,的每个正因数,k,，,有且仅有一个,k,阶子群，此时,所有的循环子群为,e, H,k,=,（其中,k|n,）,。,例如，,12,阶循环群,共有,6,个循环子群，分别是：,1,阶子群,2,阶子群,3,阶子群,4,阶子群,6,阶子群,12,阶子群,。试证明之。,证明,对于,n,阶循环群,设,|a|=n,且,n=,kq,n,q,为正整数，则根据例,8.7,，,|,a,q,|=,n/(n,q,) =,kq/q,=k,从而根据例,8.9,是,的一个,k,阶子群。,8.2,循环群,又设,H,亦是,的一个,k,阶子群，则可设,H=,则,|a,m,|=k,。 从而有,|a,m,|=,n/(n,m,),=k,，即,n=,k(n,m,),则,kq,=,k(n,m,),，从而,q=(n,，,m),q|m,。于是,a,m,故,。,又,|,|,=|,|=k,所以,=,。 因此，,n,阶循环群,的,k,阶子群是惟一的，即为,，亦即,。 所以,所有的循环子群为,e,以及,H,k,=,（其中,k|n,）。,8.2,循环群,1,左陪集、右陪集,(,coset,),利用一个整数,n,可以把全体整数,Z,分成剩余类，即利用等价关系,R=(,a,b,)|,a,b(mod n), nZ+,令,n=3,，则可以将,Z,分为如下,3,个等价类：,0=,-6,，,-3,，,0,，,3,，,6,，,1=,-5, -2,，,1,，,4,，,7,，,2=,-4, -1, 2, 5, 8, ,于是,aRb,当且仅当,n,a-b,如果把包含所有,n,的倍数的集合记为,H,，即有,H=,hn|h,=,，,-2,，,-1,，,0,，,1,，,2,，,则有,aRb,当且仅当,a-,bH,。,代数的观点,易验证,为,的子群,(+,为一般加法,),推广之,H,为,G,的子群，等价关系,R,：,对于,a,bG,，,a,R,b,当且仅当,ab,-1,H,于是，,等价类,a=,x|xG,xRa,=,x|x,G,xa,-1,H,=x|xG,xa,-1,=,h,hH,=x|xG,x=ha,hH,=,ha|hH,=,Ha,8,.,3,陪集与拉格朗日定理,定义,8.7,设,H,是群,G,的一个子群，,aG,，则称群,G,的子集,Ha=,ha|hH,为群,G,关于子群,H,的一个,右陪集,(Right,Coset,),。 而称,aH,=,ah|hH,为群,G,的关于子群,H,的一个,左陪集,(Left,Coset,),。,a,称为右陪集（左陪集）的代表元。,显然，当,G,是,Abel,群时，子群,H,的右陪集,Ha,与左陪集,aH,相等。,8.3,陪集和拉格朗日定理,练习,7,求出,关于子群,的所有左陪集,右陪集。 其中,N,6,=0,1,2,3,4,5,令,H=0,3,则左陪集,:,右陪集,:,0H=0,3=3H H0=0,3=H3,1H=1,4=4H H1=1,4=H4,2H=2,5=5H H2=2,5=H5,从中可以看出：,0H,1H,2H,是,G,的一个划分。,8.3,陪集和拉格朗日定理,定理,8.9,设,H,是群,G,的子群，则,若,HaHb,则,Ha=,Hb,。,证明,若,HaHb,设,c,HaHb,于是，,h,1,，,h,2,H,，使,c=h,1,*a=h,2,*b,从而，,a=h,1,-1,*h,2,*,b,Hb,对于任意,x,Ha,，存在,h,3,H,使得,x=h,3,*a=h,3,*h,1,-1,*h,2,*,b,Hb,故,Ha,Hb,。,同理,Hb,Ha,。,所以,Ha=,Hb,。,8.3,陪集和拉格朗日定理,上述定理表明，对任二右陪集来说，要么无公共元素，要么相等。,此外，容易证明右陪集还具有如下基本性质：,1) a,Ha; 2) b,Ha,Ha=Hb;,3) a,H,Ha=H; 4) Ha=Hb,ab,-1,H,。,8.3,陪集和拉格朗日定理,于是，群,G,的每个元素必属于一个右陪集，且不能属于不同的右陪集，因此，,G,的全体不同的右陪集构成群,G,的一个划分,即：,G=,HaHbHc,其中，,Ha,，,Hb,，,Hc,，,表示子群,H,在群,G,中的所有不同的右陪集，上述等式称为群,G,关于子群,H,的,右陪集分解,，而称,a,b,c,为,G,关于,H,的一个,右陪集代表系,。 上述划分也称为群,G,关于子群,H,的,右商集,，记作,(G/,H),r,。相应地,左商集,记作,(G/,H),l,。,8.3,陪集和拉格朗日定理,需要注意到，子群,H,本身是,G,的一个右陪集（,He,）,但,G,的任何其它右陪集不是,G,的子群，因为其皆没有单位元。 此外，,G,是一个有限群时，求,H,的右陪集可用如下方法,：首先，,H,本身是一个右陪集；之后，如果,H,为,G,真子群，则任取,a,H,而求得,Ha,；继续任取,b,HHa,而求得,Hb,；依次类推，因,G,有限，最后必被穷尽，从而,G=,HHaHb,8.3,陪集和拉格朗日定理,练习,7,求出,关于子群,的所有左陪集,右陪集。 其中,N,6,=0,1,2,3,4,5,令,H=0,3,则左陪集,:,0H=0,3=3H,1H=1,4=4H,2H=2,5=5H,G=0H,1H,2H,8.3,陪集和拉格朗日定理,此外，群,G,关于子群,H,的左商集与右商集之间有什么关系？,令,f,：,(G/,H),l,(G/H),r,f(aH,)=Ha,-1.,显然,f,是满射；下面证明,f,是单射。即需证明：,aH,=bH,Ha,-1,=Hb,-1,。,下面仅证明,aH,=bH,Ha,-1,=Hb,-1,。,若,aH,=,bH,，则有,ah,1,=bh,2,，则,a,-1,ah,1,=a,-1,bh,2,即,h,1,=a,-1,bh,2, h,1,h,2,-1,= a,-1,b,从而,a,-1,=h,1,h,2,-1,b,-1,且,b,-1,=h,2,h,1,-1,a,-1,。,于是，对于任意,x,Ha,-1,存在,h,H,使得,x=ha,-1,即,x=h(h,1,h,2,-1,b,-1,) =(hh,1,h,2,-1,)b,-1,Hb,-1,。,故,x,H,b,-1,。,所以,Ha,-1,Hb,-1,。,同理，对于任意,x,Hb,-1,有，,x=(hh,2,h,1,-1,)a,-1,Ha,-1,。,即：,Hb,-1,Ha,-1,。,于是，,Ha,-1,=Hb,-1,。,所以，,f,为映射。类似地，可以证明,f,为单射。,8.3,陪集和拉格朗日定理,从而,f,为群,G,关于子群,H,的左商集与右商集之间的双射关系。 这表明群,G,关于子群,H,的左商集与右商集的基数相同,这还表明，,有,G,的左陪集分解：,G=,aHbHcH,可以立即得到,G,的右陪集分解：,G=Ha,-1,Hb,-1,Hc,-1,。,8.3,陪集和拉格朗日定理,定义,8.8,群,G,关于子群,H,的左商集（右商集）的基数称为,H,在,G,中的,指数,(Index),，记作,G:H,。,定理,8.10,设,H,为有限群,G,的一子群，则,|G|=|H|G:H,。,本定理称为,拉格朗日定理,（,Joseph-Louis Lagrange,，,1736 - 1813,）。,8.3,陪集和拉格朗日定理,练习,7,求出,关于子群,的所有左陪集,右陪集。 其中,N,6,=0,1,2,3,4,5,令,H=0,3,则左陪集,:,0H=0,3=3H,1H=1,4=4H,2H=2,5=5H,左商集,0H,1H,2H,的基数是,3,，,H,的基数是,2,8.3,陪集和拉格朗日定理,例,8.20,设,H, K,是群,G,的两个有限子群，则,|HK|=|H|K|/|HK|,证明,由于,HK,显然是,H,的子群，根据,拉格朗日定理,可设,|H|/|HK|=m,其中,m,是,H,关于,HK,的商集的基数,且,H=h,1,(HK)h,2,(HK),h,m,(HK),其中，,h,i,H,当,ij,时，,h,j,h,i,K,，,1i,jm,。,从而易得,HK=h,1,Kh,2,K,h,m,K,，其中,h,i,Kh,j,K=, ij,。,从而,|HK|=m|K|,，即,|HK|=|H|K|/|HK|,。,8.3,陪集和拉格朗日定理,例,8.21,H,1,=(1),(12), H,2,=(1),(13),显然是,3,次对称群,S,3,的子群，请问,H,1,H,2,是否还是,S,3,的子群？,解,因为,H,1,H,2,=(1),(12),(13),(123),，于是，,|H,1,H,2,|=4,，不能整除,|S,3,|=6.,根据拉格朗日定理，,H,1,H,2,不是的子群。,8.3,陪集和拉格朗日定理,例,8.22,有限群中每个元素的阶都整除群的阶。,证明,设,a,是有限群,G,的一个,r,阶元素，则,H=e,，,a,a,r-1,是,G,的一个,r,阶子群，故由拉格朗日定理知，,r,|G|,。,8.3,陪集和拉格朗日定理,8.4.1,正规子群,定义,8.9,设,N,是群,G,的一个子群，如果对,G,中每个元素,a,都有,aN,=Na,，即,aNa,-1,=N,则称,N,是群,G,的一个,正规子群,（,Normal Subgroup,或不变子群）。,这样，正规子群的任一个左陪集也是右陪集，可简称为陪集。,群,G,的平凡子群,e,、,G,显然都是,G,的正规子群，称为,平凡正规子群,。,8.4,正规子群与群同态基本定理,例,8.23,对于任意正整数,m,是群,的正规子群，且其所有陪集构成集合,M,m,=0,1,m-1,。,8.4,正规子群与群同态基本定理,例,8.24,指数为,2,的子群必是正规子群。,证明,设,H,是群,G,的子群且,H,在,G,中的指数,G:H=2.,任取,a,G,若,a,H,则,aH,=H=Ha,下面设,a,H,。则由,G:H=2,有,G=,aHH,，,G=,HHa,。,即,aHH,=,HHa,。,由,a,H,，故,HaH,=,HHa,=,。,于是，,aH,=Ha,。,所以,H,是,G,之正规子群。,8.4,正规子群与群同态基本定理,定理,8.11,群,G,的一个子群,H,是,G,的正规子群当且仅当对任意,a,G,，,h,H,，皆有,aha,-1,H,。,例,8.25,G,是全体,n,n,实可逆矩阵关于矩阵乘法构成的群，,H,是,G,中全体行列式之值为,1,的矩阵集合，则,H,是,G,的子群，且,H,也是,G,的正规子群。这是因为，,对于任意,AG,，,XH,，有：,|A,-1,XA|=|A,-1,|X|A|=|X|A|/|A|=|X|=1,所以,A,-1,XAH,，由正规子群判定定理知,H,是,G,的正规子群。,8.4,正规子群与群同态基本定理,例,8.26,设,H,和,K,都是群,G,的正规子群，则,HK,也是,G,的正规子群。,证明,HK,显然是,G,的子群。对于任意,a,G,，由,H,是正规子群有,aH,=Ha,，于是,a(HK)a,-1,aHa,-1,=(aH)a,-1,=(Ha)a,-1,=H(aa,-1,)=H,同理，,a(HK)a,-1,K,。,于是可得,a(HK)a,-1,HK,，因此，,HK,也是,G,的正规子群。,8.4,正规子群与群同态基本定理,练习,8,设,是一个群，定义,G,的子集,H,为：,H=,a|a,*x=x*a,，对于任意的,x,G,证明：,是群,的正规子群。,8.4,正规子群与群同态基本定理,练习,9,设,和,都是群,的正规子群，试证明：,A*B,对于运算*也构成群,的正规子群。,8.4,正规子群与群同态基本定理,小结与作业,小结,1,）群的概念；,2,）元素的周期；,3,）置换群的概念与性质；,4,）循环群的性质；,5,）子群,、正规子群,；,6,）陪集与拉格朗日定理；,7,）商群与群的同态基本定理。,其中，子群、陪集与拉格朗日定理,是重点,置换群及其在,Burnside,定理与,Plya,计数原,正规子群、商群与群同态,基本定理是难点。,作业,1,反复阅读教材,(,结合例题、练习,),、思考，直到理解,2,书面作业：,2,、,6,、,11,、,1,5,、,19,、,28,、,31,群论补充例题,1,设,是,n,阶有限群，,e,为单位元，,a,1,a,2,a,n,是,G,的任意,n,个元素（不一定两两不同）。试证明：存在整数,p,q,，,1,p,q,n,，使得,a,p,*a,p+1,*,a,q,=e.,2,G,；*,是群，,H,，,K,为其子群，在,G,上定义二元关系,R,：,任意,a,bG,aRb,存在,hH,kK,使得,b=h*a*k.,证明,: R,是,G,上的等价关系,.,3,设,R,为实数集合，,G=(a,b)|a,bR,a,0.,定义,G,上的运算*：对任意,(a,1,b,1,),(a,2,b,2,)G,，,(a,1,b,1,)*(a,2,b,2,)=(a,1,a,2,b,1,a,2,+b,2,),其中,+,、,分别是一般的加法、乘法，证明：,1) ,是群,.,2,）设,S=(1,b)|bR,则,是,的子群,.,4,G,为群，,x,yG,且,yxy,-1,=x,2,，其中,x,e,，,|y|=2,，这里,e,是单位元。求,x,的阶。,