變換和置換群

會計學1變換和置換群上一講內(nèi)容的回顧不變子群商群同態(tài)核自然同態(tài)群同態(tài)基本定理同態(tài)基本定理的應用第1頁/共26頁變換群與置換群變換和變換群置換及其表示置換群任意群與變換群同構置換群的應用第2頁/共26頁變換和變換群定義：A是非空集合，f:AA稱為A上的一個變換。經(jīng)常討論的是一一變換，即f是雙射。變換就是函數(shù)，變換的“乘法”就是函數(shù)復合運算。集合A上的一一變換關于變換乘法構成的群稱為變換群。第3頁/共26頁非空集合上所有的一一變換構成群設A是任意的非空集合，A上所有的一一變換一定構成群。封閉性：雙射的復合仍是雙射。結(jié)合律：變換乘法是關系復合運算的特例。單位元：f:AA,xA,f(x)=x滿足對于任意g:AA,f?g=g?f=g(恒等變換)逆元素：任意雙射g:AA均有反函數(shù)g-1:AA,即其逆元素。

第4頁/共26頁變換群的例子R是實數(shù)集，G是R上所有如下形式的變換構成的集合：

fa,b:RR,xR,fa,b(x)=ax+b(a,b是有理數(shù)，a0)

則G是變換群。封閉性：

fa,b,fc,dG,fa,b?fc,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,2(f2,1(x))=2x+3,即f2,1?f1,2=f2,3)結(jié)合律：變換的乘法即關系復合運算單位元：恒等變換f1,0:RR:xR,f1,0(x)=x是單位元逆元素：對任意的fa,b,f1/a,-b/a?fa,b=fa,b?f1/a,-b/a=f1,0,因此f1/a,-b/a是fa,b的逆元素。(注意：a0)第5頁/共26頁置換及其表示定義：有限集合S上的雙射:SS稱為S上的n元置換記法：第6頁/共26頁置換的例子例子：集合S={1,2,3}上共有6個不同的置換，它們的集合記為S3

：S3是最小的非交換群注意：質(zhì)數(shù)階群一定是可交換群。

第7頁/共26頁輪換與對換定義:設是S={1,2,…,n}上的n元置換，且：(i1)=i2,(i2)=i3,…,(ik-1)=ik,(ik)=i1,且xS,xijj=1,2,…,k,(x)=x,則稱是S上的一個k階輪換，當k=2,也稱為對換。記法：(i1i2…ik)例子：用輪換形式表示S3的6個元素：e=(1);=(123);=(132);=(23);=(13);=(12)第8頁/共26頁不相交的輪換相乘可以交換給定Sn中兩個輪換：

=(i1i2…ik),=(j1j2…js),

若{i1,i2,…,ik}{j1,j2,…,js}=，則稱與不相交若與不相交，則

=對任意xS,分三種情況討論：x{i1,i2,…,ik};x{j1,j2,…,js};xS-({i1,i2,…,ik}{j1,j2,…,js})，均有(x)=(x)第9頁/共26頁用輪換的乘積表示置換任一n元置換均可表示成一組互不相交的輪換的乘積。對在下S中發(fā)生變化的元素的個數(shù)r

進行歸納：

r=0，即是恒等置換。若r=k>0,取一在下改變的元素i1,按照輪換的定義依次找出i2,i3…。

S是有限集，一定可以找到im,使得i1,i2,…,im均不同，但im+1{i1,i2,…,im}。必有im+1=i1。(否則：若im+1=ij,j1,則(ij-1)=(im)=ij,與是一對一的矛盾。)令1=(i1i2…im)，則

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

j(im)=i1,矛盾。所以j即s。這說明XY,同理可知YX。第11頁/共26頁置換的輪換乘積形式例子：=(157)(48)例子：=(1235)(4876)第12頁/共26頁用對換的乘積表示置換k(k>1)階輪換

=(i1i2…ik)可以表示為k-1個對換的乘積：(i1i2)…(i1ik-1)(i1ik)注意：各對換是相交的，因此次序不可以交換。證明要點：對k歸納。

k=2時顯然成立?？紤]

=(i1i2…ikik+1),只需證明

=(i1i2…ik)(i1ik+1)。分4種情況證明：xA,(x)=(i1i2…ik)(i1ik+1)(x)(1)x{i1,i2,…,ik-1}(2)x=ik(3)x=ik+1(4)x為A中其它元素

第13頁/共26頁對換乘積表示置換的例子定義{1,2,3,4}上的函數(shù)f如下：

f(1)=2,f(2)=3,f(3)=4,f(4)=1函數(shù)f的輪換形式：(1234)函數(shù)f的對換乘積形式：

(12)(13)(14)令：函數(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則：g?h?k(1)=k(h(g(1)))=k(h(2))=k(2)=2g?h?k(2)=k(h(g(2)))=k(h(1))=k(3)=3g?h?k(3)=k(h(g(3)))=k(h(3))=k(1)=4g?h?k(4)=k(h(g(4)))=k(h(4))=k(4)=1第14頁/共26頁排列中的逆序設i1i2…in是1,2,…,n的一種排列。對任意的ij,ik,若ij>ik,且j<k,則稱ijik為一個逆序排列中逆序總個數(shù)稱為該排列的逆序數(shù)。例子：(32154)中3和2構成一個逆序，這里的逆序數(shù)是4第15頁/共26頁奇置換和偶置換是S上的一個置換，(j)=ij,(j=1,2,…,n)。則的對換表示中對換個數(shù)與排列i1,i2,…,in的逆序數(shù)同奇偶性。對S的階數(shù)n進行歸納。令的對換個數(shù)為()，對應排列的逆序數(shù)為()。奠基：當n=1,=(1),()=()=0。

第16頁/共26頁奇置換和偶置換–歸納證明假設當n=k時結(jié)論成立?？紤]k+1元置換。分兩種情況討論；

(1)(k+1)=k+1：在{1,2,…,k}上的限制是k元置換，令其為‘，相應排列為’,顯然：()=(‘),()=(’),由歸納假設，(')與(')同奇偶性。(2)(k+1)=sk+1:必有t{1,2,…,k},使得(t)=k+1,而相應排列=i1i2…it-1(k+1)it+1,…,ins。構造置換'=(k+1,s),則'滿足(1)中條件，相應排列是'=i1i2…it-1sit+1,…,in(k+1)。注意，()與(')奇偶性恰好相反，()與(')的奇偶性也恰好相反(實際上，受到影響的除了s和k+1本身外，只是it與ik+1之間大于s,小于k+1的諸項)。第17頁/共26頁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)125476914153138111012(8,16)(8,12)=(8,16,12)125476914153131211108563814101315712111492563815410131712111492第18頁/共26頁置換群有限集合S上所有置換一定構成群，稱為對稱群，記為Sn,其中n是S的階數(shù)。Sn的任一子集若構成群，則是置換群。注意：置換群是變換群的特例，對稱群是置換群的特例。Sn中所有的偶置換構成子群，稱為交錯群。(只須證明封閉性)置換群的幾何意義：(以S3為例)

123順時針旋轉(zhuǎn)：0度：e120度：240度：繞軸翻轉(zhuǎn)第19頁/共26頁基于已知群定義變換群的例子對群(G,*)中任意一元素a,可以定義：a:GG,xG,a(x)=x*a,a是一一變換a是顯然是函數(shù)對任意bG，群方程x*a=b有唯一解，即a是滿射由群滿足消去律：x*a=y*ax=y,即a是單射令G‘={a|aG}第20頁/共26頁Cayley定理任意的群G與一個變換群同構。定義:GG‘:aG,(a)=a,其中G'={a|aG}。則是同構映射是函數(shù)：a=b

xG,x*a=x*b

xG,a(x)=b(x)

a=b是滿射：顯然是單射：根據(jù)消去律，abx*ax*b

ab同構映射：(a*b)=(a?b),xG,(a*b)(x)=(a*b)(x)=x*(a*b)=(x*a)*b=b(a(x)),

(a*b)=a?b=(a)?(b)，這里“?”是函數(shù)復合運算。第21頁/共26頁利用置換群解題的例子在四個方格子中放置了帶有標號的四個盤子(見右圖)?？梢赃M行下列操作：

(1)上下行互換

(2)左右列互換

(3)兩對對角元素互換進行上述操作任意有限多次，可以按照任意次序進行，包括交替進行。問題：操作停止時與開始時格局相同的充分必要條件是什么？1234第22頁/共26頁采用置換群建立數(shù)學模型定義集合{1,2,3,4}上的置換,并用輪換乘積形式表示如下：f1=(1,3)(2,4)，則f1對應于動作1：上下互換；f2=(1,2)(3,4)，則f2對應于動作2：左右互換；f3=(1,4)(2,3)，則f3對應于動作3：對角互換；令e=(1),則({e,f1,f2,f3},

?)構成可交換置換群注意：(f1?f2)=(f2?f1)=f3；(f1?f3)=(f3?f1)=f2；(f2?f3)=(f3?f2)=f1；因此運算封閉且可交換；且e是單位元，每個元素的逆元即自己。在此模型之下：任意有限多次連續(xù)動作即等效于函數(shù)

f

=fi1?fi2?…?fin

。其中ik{1,2,