变换和置换群

变换群和置换群离散数学第15讲2021/6/271上一讲内容的回顾不变子群商群同态核自然同态群同态基本定理同态基本定理的应用2021/6/272变换群与置换群变换和变换群置换及其表示置换群任意群与变换群同构置换群的应用2021/6/273变换和变换群定义：A是非空集合，f:A

A称为A上的一个变换。经常讨论的是一一变换，即f是双射。变换就是函数，变换的“乘法”就是函数复合运算。集合A上的一一变换关于变换乘法构成的群称为变换群。2021/6/274非空集合上所有的一一变换构成群设A是任意的非空集合，A上所有的一一变换一定构成群。封闭性：双射的复合仍是双射。结合律：变换乘法是关系复合运算的特例。单位元：f:A

A,

x

A,f(x)=x满足对于任意g:A

A,f◦g=g◦f=g(恒等变换)逆元素：任意双射g:A

A均有反函数g-1:A

A,即其逆元素。

2021/6/275变换群的例子R是实数集，G是R上所有如下形式的变换构成的集合：

fa,b:R

R,

x

R,fa,b(x)=ax+b(a,b是有理数，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)结合律：变换的乘法即关系复合运算单位元：恒等变换f1,0:R

R:

x

R,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的逆元素。(注意：a

0)2021/6/276置换及其表示定义：有限集合S上的双射

:S

S称为S上的n元置换记法：2021/6/277置换的例子例子：集合S={1,2,3}上共有6个不同的置换，它们的集合记为S3

：S3是最小的非交换群注意：质数阶群一定是可交换群。

2021/6/278轮换与对换定义:设

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

(i1)=i2,

(i2)=i3,…,

(ik-1)=ik,

(ik)=i1,且

x

S,x

ijj=1,2,…,k,

(x)=x,则称

是S上的一个k阶轮换，当k=2,

也称为对换。记法：(i1i2…ik)例子：用轮换形式表示S3的6个元素：e=(1);

=(123);

=(132);

=(23);

=(13);

=(12)2021/6/279不相交的轮换相乘可以交换给定Sn中两个轮换：

=(i1i2…ik),

=(j1j2…js),

若{i1,i2,…,ik}

{j1,j2,…,js}=

，则称

与

不相交若

与

不相交，则

=

对任意x

S,分三种情况讨论：x

{i1,i2,…,ik};x

{j1,j2,…,js};x

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

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

(x)=(x)2021/6/2710用轮换的乘积表示置换任一n元置换

均可表示成一组互不相交的轮换的乘积。对在

下S中发生变化的元素的个数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,j

1,则

(ij-1)=

(im)=ij,与

是一对一的矛盾。)令

1=(i1i2…im)，则

=

1

',

'与

1不相交，

'最多只改变余下的k-m个元素，由归纳假设，

'=

2

3…

l。2021/6/2711置换的轮换乘积形式的唯一性如果置换

可以表示为

1

2…

t和

1

2…

l,令X={

1,

2,…,

t},Y={

1,

2,…,

l,},则X=Y证明要点：任取

j

X,不失一般性，令

j=(i1i2…im)由于

(i1)

i1,必存在

s

Y,使得i1出现在

s中。由轮换的定义以及各轮换不相交，i2,i3,…,im也必在

s中。若存在其它某个元素u也在

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

(im)=s(im)=u，同时又有

(im)=

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

j即

s。这说明X

Y,同理可知Y

X。2021/6/2712置换的轮换乘积形式例子：=(157)(48)例子：=(1235)(4876)2021/6/2713用对换的乘积表示置换k(k>1)阶轮换

=(i1i2…ik)可以表示为k-1个对换的乘积：(i1i2)…(i1ik-1)(i1ik)注意：各对换是相交的，因此次序不可以交换。证明要点：对k归纳。

k=2时显然成立。考虑

=(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对换乘积表示置换的例子定义{1,2,3,4}上的函数f如下：

f(1)=2,f(2)=3,f(3)=4,f(4)=1函数f的轮换形式：(1234)函数f的对换乘积形式：

(12)(13)(14)令：函数g:g(1)=2,g(2)=1,g(3)=3,g(4)=4函数h:h(1)=3,h(2)=2,h(3)=1,h(4)=4函数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排列中的逆序设i1i2…in是1,2,…,n的一种排列。对任意的ij,ik,若ij>ik,且j<k,则称ijik为一个逆序排列中逆序总个数称为该排列的逆序数。例子：(32154)中3和2构成一个逆序，这里的逆序数是42021/6/2716奇置换和偶置换

是S上的一个置换，

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

的对换表示中对换个数与排列i1,i2,…,in的逆序数同奇偶性。对S的阶数n进行归纳。令

的对换个数为

(

)，对应排列

的逆序数为

(

)。奠基：当n=1,

=(1),

(

)=

(

)=0。

2021/6/2717奇置换和偶置换–归纳证明假设当n=k时结论成立。考虑k+1元置换

。分两种情况讨论；

(1)

(k+1)=k+1：

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

‘，相应排列为

’,显然：

(

)=

(

‘),

(

)=

(

’),由归纳假设，

(

')与

(

')同奇偶性。(2)

(k+1)=s

k+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的诸项)。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上所有置换一定构成群，称为对称群，记为Sn,其中n是S的阶数。Sn的任一子集若构成群，则是置换群。注意：置换群是变换群的特例，对称群是置换群的特例。Sn中所有的偶置换构成子群，称为交错群。(只须证明封闭性)置换群的几何意义：(以S3为例)

123顺时针旋转：0度：e120度：

240度：

绕轴翻转

2021/6/2720基于已知群定义变换群的例子对群(G,*)中任意一元素a,可以定义：

a:G

G,

x

G,

a(x)=x*a,

a是一一变换

a是显然是函数对任意bG，群方程x*a=b有唯一解，即a是满射由群满足消去律：x*a=y*ax=y,即a是单射令G‘={

a|a

G}2021/6/2721Cayley定理任意的群G与一个变换群同构。定义

:G

G‘:

a

G,

(a)=

a,其中G'={

a|a

G}。则是同构映射

是函数：a=b

x

G,x*a=x*b

x

G,

a(x)=

b(x)

a=

b

是满射：显然

是单射：根据消去律，a

b

x*a

x*b

a

b同构映射：

(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)，这里“◦”是函数复合运算。2021/6/2722利用置换群解题的例子在四个方格子中放置了带有标号的四个盘子(见右图)。可以进行下列操作：

(1)上下行互换

(2)左右列互换

(3)两对对角元素互换进行上述操作任意有限多次，可以按照任意次序进行，包括交替进行。问题：操作停止时与开始时格局相同的充分必要条件是什么？12342021/6/2723采用置换群建立数学模型定义集合{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是单位元，每个元素的逆元即自己。在此模型之下：任意有限多次连续动作即等效于函数

f

=fi1◦fi2◦…◦fin

。其中ik

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