變換和置換群

變換群和置換群離散數(shù)學(xué)第15講2021/6/271上一講內(nèi)容的回顧不變子群商群同態(tài)核自然同態(tài)群同態(tài)基本定理同態(tài)基本定理的應(yīng)用2021/6/272變換群與置換群變換和變換群置換及其表示置換群任意群與變換群同構(gòu)置換群的應(yīng)用2021/6/273變換和變換群定義：A是非空集合，f:A

A稱為A上的一個(gè)變換。經(jīng)常討論的是一一變換，即f是雙射。變換就是函數(shù)，變換的“乘法”就是函數(shù)復(fù)合運(yùn)算。集合A上的一一變換關(guān)于變換乘法構(gòu)成的群稱為變換群。2021/6/274非空集合上所有的一一變換構(gòu)成群設(shè)A是任意的非空集合，A上所有的一一變換一定構(gòu)成群。封閉性：雙射的復(fù)合仍是雙射。結(jié)合律：變換乘法是關(guān)系復(fù)合運(yùn)算的特例。單位元：f:A

A,

x

A,f(x)=x滿足對(duì)于任意g:A

A,f?g=g?f=g(恒等變換)逆元素：任意雙射g:A

A均有反函數(shù)g-1:A

A,即其逆元素。

2021/6/275變換群的例子R是實(shí)數(shù)集，G是R上所有如下形式的變換構(gòu)成的集合：

fa,b:R

R,

x

R,fa,b(x)=ax+b(a,b是有理數(shù)，a

0)

則G是變換群。封閉性：

fa,b,fc,d

G,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é)合律：變換的乘法即關(guān)系復(fù)合運(yùn)算單位元：恒等變換f1,0:R

R:

x

R,f1,0(x)=x是單位元逆元素：對(duì)任意的fa,b,f1/a,-b/a?fa,b=fa,b?f1/a,-b/a=f1,0,因此f1/a,-b/a是fa,b的逆元素。(注意：a

0)2021/6/276置換及其表示定義：有限集合S上的雙射

:S

S稱為S上的n元置換記法：2021/6/277置換的例子例子：集合S={1,2,3}上共有6個(gè)不同的置換，它們的集合記為S3

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

2021/6/278輪換與對(duì)換定義:設(shè)

是S={1,2,…,n}上的n元置換，且：

(i1)=i2,

(i2)=i3,…,

(ik-1)=ik,

(ik)=i1,且

x

S,x

ijj=1,2,…,k,

(x)=x,則稱

是S上的一個(gè)k階輪換，當(dāng)k=2,

也稱為對(duì)換。記法：(i1i2…ik)例子：用輪換形式表示S3的6個(gè)元素：e=(1);

=(123);

=(132);

=(23);

=(13);

=(12)2021/6/279不相交的輪換相乘可以交換給定Sn中兩個(gè)輪換：

=(i1i2…ik),

=(j1j2…js),

若{i1,i2,…,ik}

{j1,j2,…,js}=

，則稱

與

不相交若

與

不相交，則

=

對(duì)任意x

S,分三種情況討論：x

{i1,i2,…,ik};x

{j1,j2,…,js};x

S-({i1,i2,…,ik}

{j1,j2,…,js})，均有

(x)=(x)2021/6/2710用輪換的乘積表示置換任一n元置換

均可表示成一組互不相交的輪換的乘積。對(duì)在

下S中發(fā)生變化的元素的個(gè)數(shù)r

進(jìn)行歸納：

r=0，即

是恒等置換。若r=k>0,取一在

下改變的元素i1,按照輪換的定義依次找出i2,i3…。

S是有限集，一定可以找到im,使得i1,i2,…,im均不同，但im+1

{i1,i2,…,im}。必有im+1=i1。(否則：若im+1=ij,j

1,則

(ij-1)=

(im)=ij,與

是一對(duì)一的矛盾。)令

1=(i1i2…im)，則

=

1

',

'與

1不相交，

'最多只改變余下的k-m個(gè)元素，由歸納假設(shè)，

'=

2

3…

l。2021/6/2711置換的輪換乘積形式的唯一性如果置換

可以表示為

1

2…

t和

1

2…

l,令X={

1,

2,…,

t},Y={

1,

2,…,

l,},則X=Y證明要點(diǎn)：任取

j

X,不失一般性，令

j=(i1i2…im)由于

(i1)

i1,必存在

s

Y,使得i1出現(xiàn)在

s中。由輪換的定義以及各輪換不相交，i2,i3,…,im也必在

s中。若存在其它某個(gè)元素u也在

s中,則u只能在m后面，則

(im)=s(im)=u，同時(shí)又有

(im)=

j(im)=i1,矛盾。所以

j即

s。這說(shuō)明X

Y,同理可知Y

X。2021/6/2712置換的輪換乘積形式例子：=(157)(48)例子：=(1235)(4876)2021/6/2713用對(duì)換的乘積表示置換k(k>1)階輪換

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

k=2時(shí)顯然成立。考慮

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

=(i1i2…ik)(i1ik+1)。分4種情況證明：

x

A,

(x)=(i1i2…ik)(i1ik+1)(x)(1)x

{i1,i2,…,ik-1}(2)x=ik(3)x=ik+1(4)x為A中其它元素

2021/6/2714對(duì)換乘積表示置換的例子定義{1,2,3,4}上的函數(shù)f如下：

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

(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)=12021/6/2715排列中的逆序設(shè)i1i2…in是1,2,…,n的一種排列。對(duì)任意的ij,ik,若ij>ik,且j<k,則稱ijik為一個(gè)逆序排列中逆序總個(gè)數(shù)稱為該排列的逆序數(shù)。例子：(32154)中3和2構(gòu)成一個(gè)逆序，這里的逆序數(shù)是42021/6/2716奇置換和偶置換

是S上的一個(gè)置換，

(j)=ij,(j=1,2,…,n)。則

的對(duì)換表示中對(duì)換個(gè)數(shù)與排列i1,i2,…,in的逆序數(shù)同奇偶性。對(duì)S的階數(shù)n進(jìn)行歸納。令

的對(duì)換個(gè)數(shù)為

(

)，對(duì)應(yīng)排列

的逆序數(shù)為

(

)。奠基：當(dāng)n=1,

=(1),

(

)=

(

)=0。

2021/6/2717奇置換和偶置換–歸納證明假設(shè)當(dāng)n=k時(shí)結(jié)論成立。考慮k+1元置換

。分兩種情況討論；

(1)

(k+1)=k+1：

在{1,2,…,k}上的限制是k元置換，令其為

‘，相應(yīng)排列為

’,顯然：

(

)=

(

‘),

(

)=

(

’),由歸納假設(shè)，

(

')與

(

')同奇偶性。(2)

(k+1)=s

k+1:必有t

{1,2,…,k},使得

(t)=k+1,而相應(yīng)排列

=i1i2…it-1(k+1)it+1,…,ins。構(gòu)造置換

'=

(k+1,s),則

'滿足(1)中條件，相應(yīng)排列是

'=i1i2…it-1sit+1,…,in(k+1)。注意，

(

)與

(

')奇偶性恰好相反，

(

)與

(

')的奇偶性也恰好相反(實(shí)際上，受到影響的除了s和k+1本身外，只是it與ik+1之間大于s,小于k+1的諸項(xiàng))。2021/6/271815-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)1254769141531312111085638141013157121114925638154101317121114922021/6/2719置換群有限集合S上所有置換一定構(gòu)成群，稱為對(duì)稱群，記為Sn,其中n是S的階數(shù)。Sn的任一子集若構(gòu)成群，則是置換群。注意：置換群是變換群的特例，對(duì)稱群是置換群的特例。Sn中所有的偶置換構(gòu)成子群，稱為交錯(cuò)群。(只須證明封閉性)置換群的幾何意義：(以S3為例)

123順時(shí)針旋轉(zhuǎn)：0度：e120度：

240度：

繞軸翻轉(zhuǎn)

2021/6/2720基于已知群定義變換群的例子對(duì)群(G,*)中任意一元素a,可以定義：

a:G

G,

x

G,

a(x)=x*a,

a是一一變換

a是顯然是函數(shù)對(duì)任意bG，群方程x*a=b有唯一解，即a是滿射由群滿足消去律：x*a=y*ax=y,即a是單射令G‘={

a|a

G}2021/6/2721Cayley定理任意的群G與一個(gè)變換群同構(gòu)。定義

:G

G‘:

a

G,

(a)=

a,其中G'={

a|a

G}。則是同構(gòu)映射

是函數(shù)：a=b

x

G,x*a=x*b

x

G,

a(x)=

b(x)

a=

b

是滿射：顯然

是單射：根據(jù)消去律，a

b

x*a

x*b

a

b同構(gòu)映射：

(a*b)=

(a?b),

x

G,

(a*b)(x)=

(a*b)(x)=x*(a*b)=(x*a)*b=

b(

a(x)),

(a*b)=

a?

b=

(a)?

(b)，這里“?”是函數(shù)復(fù)合運(yùn)算。2021/6/2722利用置換群解題的例子在四個(gè)方格子中放置了帶有標(biāo)號(hào)的四個(gè)盤子(見右圖)。可以進(jìn)行下列操作：

(1)上下行互換

(2)左右列互換

(3)兩對(duì)對(duì)角元素互換進(jìn)行上述操作任意有限多次，可以按照任意次序進(jìn)行，包括交替進(jìn)行。問(wèn)題：操作停止時(shí)與開始時(shí)格局相同的充分必要條件是什么？12342021/6/2723采用置換群建立數(shù)學(xué)模型定義集合{1,2,3,4}上的置換,并用輪換乘積形式表示如下：f1=(1,3)(2,4)，則f1對(duì)應(yīng)于動(dòng)作1：上下互換；f2=(1,2)(3,4)，則f2對(duì)應(yīng)于動(dòng)作2：左右互換；f3=(1,4)(2,3)，則f3對(duì)應(yīng)于動(dòng)作3：對(duì)角互換；令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è)元素的逆元即自己。在此模型之下：任意有限多次連續(xù)動(dòng)作即等效于函數(shù)

f

=fi1?fi2?…?fin

。其中ik

{1,2,3}2021/6/2724