《變換和置換群》課件

1、變換和置換群,變換群和置換群,離散數(shù)學(xué) 第15講,變換和置換群,上一講內(nèi)容的回顧,不變子群 商群 同態(tài)核 自然同態(tài) 群同態(tài)基本定理 同態(tài)基本定理的應(yīng)用,變換和置換群,變換群與置換群,變換和變換群 置換及其表示 置換群 任意群與變換群同構(gòu) 置換群的應(yīng)用,變換和置換群,變換和變換群,定義：A是非空集合，f:AA稱為A上的一個(gè)變換。 經(jīng)常討論的是一一變換，即f是雙射。 變換就是函數(shù)，變換的“乘法”就是函數(shù)復(fù)合運(yùn)算。 集合A上的一一變換關(guān)于變換乘法構(gòu)成的群稱為變換群。,變換和置換群,非空集合上所有的一一變換構(gòu)成群,設(shè)A是任意的非空集合，A上所有的一一變換一定構(gòu)成群。 封閉性：雙射的復(fù)合仍是雙射。 結(jié)合

2、律：變換乘法是關(guān)系復(fù)合運(yùn)算的特例。 單位元：f:AA, xA, f(x)=x滿足對于任意g:AA, fg=gf=g (恒等變換) 逆元素：任意雙射g:AA均有反函數(shù)g -1:AA, 即其逆元素。,變換和置換群,變換群的例子,R是實(shí)數(shù)集，G是R上所有如下形式的變換構(gòu)成的集合： fa,b:RR, xR, fa,b(x)=ax+b (a,b是有理數(shù)，a0) 則G是變換群。 封閉性： fa,b, fc,d G, fa,bfc,d =fac,bc+d ( 注意：fc,d (fa,b(x) = fc,d(ax+b) = acx+bc+d, 例如：f2,1(x)=2x+1, f1,2(x)=x+2, f1,

3、2(f2,1(x)= 2x+3, 即f2,1f1,2 = f2,3 ) 結(jié)合律：變換的乘法即關(guān)系復(fù)合運(yùn)算 單位元：恒等變換f1,0:RR: xR, f1,0(x)=x 是單位元 逆元素：對任意的fa,b , f1/a,-b/afa,b = fa,b f1/a,-b/a= f1,0, 因此f1/a,-b/a是fa,b 的逆元素。(注意：a0),變換和置換群,置換及其表示,定義：有限集合S上的雙射:SS稱為S上的n元置換 記法：,變換和置換群,置換的例子,例子：集合S=1,2,3上共有6個(gè)不同的置換， 它們的集合記為S3 ： S3是最小的非交換群 注意：質(zhì)數(shù)階群一定是可交換群。,變換和置換群,輪換

4、與對換,定義: 設(shè)是S=1,2,n上的n元置換，且： (i1)=i2, (i2)=i3, , (ik-1)=ik, (ik)=i1, 且xS, xij j=1,2,k, (x)=x, 則稱是S上的一個(gè)k階輪換，當(dāng)k=2, 也稱為對換。 記法：(i1 i2 ik ) 例子：用輪換形式表示S3的6個(gè)元素： e=(1); =(1 2 3); =(1 3 2); =(2 3); =(1 3); =(1 2),變換和置換群,不相交的輪換相乘可以交換,給定Sn中兩個(gè)輪換： =(i1 i2 ik ), =(j1 j2 js ), 若i1, i2, , ik j1, j2, , js=，則稱 與 不相交 若

5、與 不相交，則 = 對任意xS, 分三種情況討論： xi1, i2, , ik; xj1, j2, , js; xS-(i1, i2, , ikj1, j2, , js)， 均有(x) = (x),變換和置換群,用輪換的乘積表示置換,任一n元置換均可表示成一組互不相交的輪換的乘積。 對在下S中發(fā)生變化的元素的個(gè)數(shù)r 進(jìn)行歸納： r =0，即是恒等置換。 若r =k0, 取一在下改變的元素i1, 按照輪換的定義依次找出i2, i3 。 S是有限集，一定可以找到im, 使得i1, i2, , im均不同，但im+1i1, i2, , im。 必有im+1=i1。(否則：若im+1=ij, j1,

6、則(ij-1)=(im)=ij, 與是一對一的矛盾。) 令1=(i1 i2 im)，則 = 1, 與1不相交，最多只改變余下的k-m個(gè)元素，由歸納假設(shè)， =23l。,變換和置換群,置換的輪換乘積形式的唯一性,如果置換可以表示為12t和12l, 令X=1, 2, , t, Y=1, 2, , l , , 則X=Y 證明要點(diǎn)： 任取jX, 不失一般性，令j=(i1 i2 im ) 由于(i1)i1, 必存在sY, 使得i1出現(xiàn)在s中。由輪換的定義以及各輪換不相交，i2, i3, im也必在s中。若存在其它某個(gè)元素u也在s中, 則u只能在m后面，則(im)=s(im) =u，同時(shí)又有(im)= j(

7、im)=i1, 矛盾。所以j即s。這說明XY, 同理可知YX。,變換和置換群,置換的輪換乘積形式,例子： = (1 5 7) (4 8) 例子： =(1 2 3 5) (4 8 7 6),變換和置換群,用對換的乘積表示置換,k(k1)階輪換 =(i1 i2 ik )可以表示為k-1個(gè)對換的乘積：(i1i2)(i1ik-1) (i1ik) 注意：各對換是相交的，因此次序不可以交換。 證明要點(diǎn)：對k歸納。 k=2時(shí)顯然成立?？紤] =(i1 i2 ik ik+1 ), 只需證明 =(i1 i2 ik)(i1 ik+1 )。 分4種情況證明：xA, (x)=(i1 i2 ik)(i1 ik+1 )(x

8、) (1) x i1, i2, , ik-1 (2) x=ik (3) x=ik+1 (4) x為A中其它元素,變換和置換群,對換乘積表示置換的例子,定義1,2,3,4上的函數(shù) f 如下： f (1)=2, f (2)=3, f (3)=4, f (4)=1,函數(shù) f 的輪換形式：(1 2 3 4),函數(shù) f 的對換乘積形式： (1 2) (1 3) (1 4),令： 函數(shù)g: g(1)=2, g(2)=1, g(3)=3, g(4)=4 函數(shù)h: h(1)=3, h(2)=2, h(3)=1, h(4)=4 函數(shù)k: k(1)=4, k(2)=2, k(3)=3, k(4)=1,則： ghk

9、(1)=k(h(g(1)=k(h(2)=k(2)=2 ghk(2)=k(h(g(2)=k(h(1)=k(3)=3 ghk(3)=k(h(g(3)=k(h(3)=k(1)=4 ghk(4)=k(h(g(4)=k(h(4)=k(4)=1,變換和置換群,排列中的逆序,設(shè)i1i2in是1,2,n的一種排列。對任意的ij, ik, 若ijik, 且jk, 則稱ijik為一個(gè)逆序 排列中逆序總個(gè)數(shù)稱為該排列的逆序數(shù)。 例子：(3 2 1 5 4)中3和2構(gòu)成一個(gè)逆序，這里的逆序數(shù)是4,變換和置換群,奇置換和偶置換,是S上的一個(gè)置換，(j)=ij, (j=1,2,n)。則的對換表示中對換個(gè)數(shù)與排列i1, i

10、2, , in的逆序數(shù)同奇偶性。 對S的階數(shù)n進(jìn)行歸納。 令的對換個(gè)數(shù)為()，對應(yīng)排列的逆序數(shù)為()。 奠基：當(dāng)n=1, =(1), ()=()=0。,變換和置換群,奇置換和偶置換 歸納證明,假設(shè)當(dāng)n=k時(shí)結(jié)論成立。考慮k+1元置換。 分兩種情況討論； (1) (k+1)=k+1：在1,2,k上的限制是k元置換，令其為，相應(yīng)排列為, 顯然：()=(), ()=(), 由歸納假設(shè)，()與()同奇偶性。 (2) (k+1)=sk+1: 必有t1,2,k, 使得(t)=k+1, 而相應(yīng)排列=i1i2it-1(k+1)it+1,ins。構(gòu)造置換=(k+1,s), 則滿足(1)中條件，相應(yīng)排列是=i1i

11、2it-1sit+1,in(k+1)。注意，()與()奇偶性恰好相反，()與()的奇偶性也恰好相反(實(shí)際上，受到影響的除了s和k+1本身外，只是it與ik+1之間大于s, 小于k+1的諸項(xiàng))。,變換和置換群,15-Puzzle,(1,5,3,7)(2,6,4,8)(9,10)(11,14,13,12)(15)(16),(1,5,3,7,15)(2,6,4,8)(9,10)(11,14,13,12)(16),1,2,5,4,7,6,9,14,15,3,13,8,11,10,12,(8,16)(8,12) = (8,16,12),變換和置換群,置換群,有限集合S上所有置換一定構(gòu)成群，稱為對稱群，記

12、為Sn, 其中n是S的階數(shù)。 Sn的任一子集若構(gòu)成群，則是置換群。 注意：置換群是變換群的特例，對稱群是置換群的特例。 Sn中所有的偶置換構(gòu)成子群，稱為交錯(cuò)群。(只須證明封閉性) 置換群的幾何意義：(以S3為例),變換和置換群,基于已知群定義變換群的例子,對群(G,*)中任意一元素a, 可以定義： a:GG, xG, a(x)=x*a, a是一一變換 a是顯然是函數(shù) 對任意bG，群方程x*a=b有唯一解，即a是滿射 由群滿足消去律：x*a=y*a x=y, 即a是單射 令G=a|aG,變換和置換群,Cayley定理,任意的群G與一個(gè)變換群同構(gòu)。 定義: GG: aG, (a)=a ,其中G=a

13、|aG 。 則是同構(gòu)映射 是函數(shù)：a=b xG, x*a=x*b xG, a(x)=b(x) a=b 是滿射：顯然 是單射：根據(jù)消去律，ab x*ax*b ab 同構(gòu)映射：(a*b)=(ab), xG, (a*b)(x)=(a*b)(x)=x* (a*b) =(x*a)*b=b(a(x), (a*b)=ab=(a)(b)，這里“”是函數(shù)復(fù)合運(yùn)算。,變換和置換群,利用置換群解題的例子,在四個(gè)方格子中放置了帶有 標(biāo)號(hào)的四個(gè)盤子(見右圖)。 可以進(jìn)行下列操作： (1) 上下行互換 (2) 左右列互換 (3) 兩對對角元素互換 進(jìn)行上述操作任意有限多次，可以按照任意次序進(jìn)行，包括交替進(jìn)行。 問題：操作

14、停止時(shí)與開始時(shí)格局相同的充分必要條件是什么？,變換和置換群,采用置換群建立數(shù)學(xué)模型,定義集合1,2,3,4上的置換, 并用輪換乘積形式表示如下： f1=(1,3)(2,4)，則f1對應(yīng)于動(dòng)作1：上下互換； f2=(1,2)(3,4)，則f2對應(yīng)于動(dòng)作2：左右互換； f3=(1,4)(2,3)，則f3對應(yīng)于動(dòng)作3：對角互換； 令e=(1), 則(e, f1, f2, f3, )構(gòu)成可交換置換群 注意：(f1 f2)= (f2 f1)= f3；(f1 f3)= (f3 f1)= f2；(f2 f3)= (f3 f2)= f1；因此運(yùn)算封閉且可交換；且e是單位元，每個(gè)元素的逆元即自己。 在此模型之下

15、：任意有限多次連續(xù)動(dòng)作即等效于函數(shù) f =fi1 fi2 fi n 。其中ik1,2,3,變換和置換群,問題的解,任意有限多次連續(xù)動(dòng)作即等效于函數(shù) f =fi1 fi2 fi n 。其中ik1,2,3 所以：開始格局與結(jié)束格局相同 當(dāng)且僅當(dāng) f = e (e, f1, f2, f3, )是可交換群， f =fi1 fi2 fi n = f1h f2j f3k ,其中h, j, k是非負(fù)整數(shù)。 注意：對i=1,2,3, 均有fi 2k = e, 其中k是非負(fù)整數(shù)； f = f1s(h) f2s(j) f3s(k) , s(x)是整數(shù)集上的“奇偶特征函數(shù)”，當(dāng)x為奇數(shù)，s(x)=1, 否則s(x)=0。 注意：f1 f2