§6.3置换群(离散数学)

§6.3

置

换

群

6.3.1置换的定义

6.3.2置换的轮换表法

6.3.3置换的顺向圈表示

6.3.4置换的奇偶性

6.3.1

置换的定义

定义.设M是一个非空的有限集合，M的一个一对一变换称为一个置换。设M={a1,a2,…,an},则M的置换σ可简记为

σ＝，bi=σ(ai)，i=1,2,…,n

结论：M的置换共有n！个。

M上的置换称为n元置换。特别地，若σ(ai)=ai,i=1,2,…,n,则σ为n元恒等置换。

Sn:n！个置换作成的集合。置换的例设M={1，2，3}，则有3！=6个3元置换，所有元素不动：σ1＝一个元素不动：σ2＝σ3＝σ4＝0个元素不动：σ5＝σ6＝故，S3={σ1，σ2，σ3，σ4，σ5，σ6}置换的乘法对M中任意元素a及M的任意两个置换σ，τ，规定στ（a）=σ（τ（a））。例.设σ＝

，τ＝则στ=，

τσ=≠

στ满足结合律：(στ)ρ=σ(τρ)，σ,τ,ρ∈

Sn。Sn中有单位元:n元恒等置换，设为σ0，有：σ0τ=τσ0，τ∈Sn每个n元置换在Sn

中都有逆元素:=置换的乘法的性质例.设σ＝，τ＝求σ2，στ，τσ，σ-1，τ-1。

并解方程σx=τ,yτ=σ.解：σ2==στ=τσ=σ-1=τ-1=x=σ-1τ=y=στ-1=n次对称群n元置换的全体作成的集合Sn对置换的乘法作成一个群，称为n次对称群。（n次对称群的任一子群称为n次置换群。）

n=1，M={a}，S1={

}—在置换的乘法下作成1次对称群，为Abel群。

n=2,M={a，b},S2={

,

}在置换的乘法下作成2次对称群，为Abel群。当n≥3时，Sn不是Abel群。轮换.设σ是M的置换，若可取到M的元素a1,…,ar使σ(a1)＝a2,σ(a2)=a3,…,σ(ar-1)=ar,σ(ar)=a1，而σ不变M的其余的元素，则σ称为一个轮换，记为（a1a2…ar）例.

σ==（134）=（341）=（413）

6.3.2

置换的轮换表法

轮换的定义可以把a1，…

，ar中的任意元素ai排在头一位而改写成

（aiai+1…ar

a1…ai-1）结论：设（a1a2…ar）是M的轮换，则（a1a2…ar）-1=（ar…a2a1）证明：往证（ar…a2a1）（a1a2…ar）=I命χ为M的任意元若χ∈｛a1,…,ar-1｝，设χ=ai，则(ar…a2a1)(a1a2…ar)(ai)=(ar…a2a1)(ai+1)=ai若χ=ar,则(ar…a2a1)(a1a2…ar)(ar)=(ar…a2a1)(a1)=arχ

｛a1,…,ar｝，则(ar…a2a1)(a1a2…ar)(x)=x总之，(ar…a2a1)(a1a2…ar)(x)=I(x)=x即，（ar…a2a1）（a1a2…ar）=I同理，（a1a2…ar）（ar…a2a1）=IM的两个轮换

σ=(a1…ar)和τ=(b1…bs)说是不相杂或不相交，如果

a1,…,ar和b1,…,bs都不相同(即{a1,…

,ar}∩{b1,…,bs}=

)例.设M={1,2,3,4,5,6,7}，（134）与（637）是相杂轮换，（134）（637）=（13764），（637）（134）=（17634）;

（134）与（25）是不相杂轮换，（134）（25）=（25）（134）不相杂轮换不相杂轮换结论：若σ和τ是M的两个不相杂的轮换，则στ=τσ.证明：设σ=（a1…ar），τ=（b1…bs），σ和τ不相杂。命χ为M的任意元.若χ∈｛a1,…,ar｝，设χ=ai，则

στ(χ)=στ(ai)=σ(ai)=ai+1，τσ(χ)=τσ(ai)=τ(ai+1)=ai+1。

i=r时,ai+1

应改为a1。

故,στ(χ)=τσ(χ)。不相杂轮换同理可证，若χ∈｛b1,…,bs｝，也有στ（χ）=τσ（χ）。若χ

{a1,…,ar,b1,…,bs},于是，

στ（χ）=σ（χ）=χ，τσ（χ）=τ（χ）=χ。

综上，στ（χ）=τσ（χ），故

στ=τσ。

定理6.3.2

任意置换σ恰有一法写成不相杂轮换的乘积。即，任意置换σ可以写成不相杂轮换的乘积（可表性），如果不考虑乘积的顺序，则写法是唯一的(唯一性)。例.=(1352)(4)(68)(7)=(3521)(7)(86)(4)置换的这种表法称为置换的轮换表法去掉单轮换为轮换表法的省略形式：(1352)(68)证明：

（1）可表性。设σ是M上置换，任取a1∈M。若σ（a1）=a1，则有轮换（a1）。设σ（a1）=a2，σ（a2）=a3，…。由于M有限，故到某一个元素ar，σ(ar)必然不能再是新的元素,即σ(ar)∈｛a1,…,ar｝。由于σ是一对一的，已有σ（ai）=ai+1,i=1,2,…,r-1，所以σ(ar)只能是a1.于是得到一个轮换（a1…ar）。

若M已经没有另外的元素，则σ就等于这个轮换，否则设b1不在a1，…，ar之内，则同样作法又可得到一个轮换（b1…bs）.因为a1，…，ar各自已有变到它的元素，所以b1，…，bs中不会有a1，…，ar出现，即这两个轮换不相杂。若M的元素已尽，则σ就等于这两个轮换的乘积，否则如上又可得到一个轮换。如此类推，由于M有限，最后必得σ=(a1…ar)(b1…bs)…(c1…ct)(1)

即σ表成了不相杂轮换的乘积。

（2）唯一性.设σ又可表为不相杂的轮换的乘积如下：σ=(a’1…a’r’)(b’1…b’s’)…(c’1…c’t’)(2)考虑(1)式中任意轮换(a1…ar)。

不妨设

a1∈{a’1…a’r’}，且a1＝a’１。于是，a2=σ（a1）=σ（a’1）=a’2

，a3=σ（a2）=σ（a’2）=a’3，…，证明证明

可见，（a1…ar）必和（a’1…a’r’）完全相同。这就是说，（1）中的任意轮换必出现在（2）中，同样（2）中的任意轮换必出现在（1）中，因之，（1）和（2）一样，最多排列方法不同，但不相杂的轮换相乘适合交换律，所以排列的次序本来是可以任意颠倒的。证毕。例.

设M={1,2,3,4}，M的24个置换可写成：I；(12),(13),(14),(23),(24),(34)；(123),(132),(124),(142),(134),(143),(234),(243)；(1234),(1243),(1324),(13

42),(1423),(1432),(12)(34),(13)(24),(14)(23)。轮换的长度

其中所含的元素个数。（a1a2…ar）长度为r。对换

长度为２的轮换。结论.任意轮换可以写成对换的乘积。证明：往证(a1a2…ar)＝(a1

ar)(a1

ar-１)…(a1a3)(a1a2)(3)对r进行归纳，当r=2时命题显然成立。假设r=t时结论为真，考虑σ=(a1a2…atat+1)的情况。对换往证(a1a2…atat+1)=(a1at+1)(a1a2…at)令σ1=(a1at+1)，σ2=(a1a2…at)，下面证明σ=σ1σ2。任取l∈M,若l{a1,a2,…,at-1}，不妨设l=am,则σ(l)=σ(am)=am+1，σ1σ2(l)=σ1(am+1)=am+1；若l=at，则

σ(l)=at+1σ1σ2(l)=σ1σ2(at)=σ1(σ2(at))=σ1(a1)=at+1；若l=at+1，则σ(l)=σ(at+1)=a1σ1σ2(l)=σ1(σ2(at+1))=σ1(at+1)=a1；若l{a1,a2,…,at+1}，则σ(l)=lσ1σ2(l)=σ1(σ2(l))=σ1(l)=l。因此，σ=σ1σ2=(a1at+1)(a1a2…at)

。由归纳假设，(a1a2…at)

=(a1at)(a1at-1)…(a1a2)，所以σ=(a1at+1)(a1at)(a1at-1)…(a1a2)，归纳完成。还可以采用直接证明的方法进行证明。推论.对任意置换，有一法(未必只有一法)可将其写成一些对换的乘积。(１2)=(12)(13)(13)=(23)(13)(23)。例设多项式f=(x1+x2)(x3+x4)，找出使f保持不变的所有下标的置换，这些置换在置换的

乘法下是否构成群？

解：由加法交换律和乘法交换律可得到使f保持不变的所有下标的置换的集合为：G={(1)(2)(3)(4)，(12)(3)(4)，(1)(2)(34)，(12)(34)，(13)(24)，(14)(23)}。G是S4的有限非空子集，可以验证置换乘法在G上是封闭的，置换乘法满足结合律，所有元素的逆都是自身，故G在置换的乘法下做成1个4次置换群。

例图1是一个22的方格图形，它可以围绕中心旋转，也可以围绕对称轴翻转，但要求经过这样的变动以后的图形要与原来的图形重合（方格中的数字可以改变）。例如，当它绕中心逆时针旋转900以后，原来的数字1，2，3，4分别变为2，3，4和1，可以把这个变化看作是{1，2，3，4}上的图1一个置换（1234）。下面给出所有可能的置换：σ1=(1)(2)(3)(4)绕中心逆时针转00；σ2=(1234)

绕中心逆时针转900；σ3=(13)(24)

绕中心逆时针转1800；1243σ4=(1432)绕中心逆时针转2700；σ5=(12)(34)

绕垂直轴翻转1800；σ6=(14)(23)

绕水平轴翻转1800；σ7=(24)

绕西北---东南轴翻转1800；σ8=(13)

绕西南---东北轴翻转1800。表1给出运算表。令D4={σ1,σ2,…,σ8}，易见D4关于置换的乘法是封闭的。置换乘法满足结合律。

σ1是单位元。σ1-1=σ1,σ2-1=σ4,σ3-1=σ3,σ4-1=σ2,σ5-1=σ5,σ6-1=σ6,σ7-1=σ7,σ8-1=σ8,D4关于置换的乘法构成一个4次置换群。表1·σ1σ2σ3σ4σ5σ6σ7σ8σ1σ1σ2σ3σ4σ5σ6σ7σ8σ2σ2σ3σ4σ1σ8σ7σ5σ6σ3σ3σ4σ1σ2σ6σ5σ8σ7σ4σ4σ1σ2σ3σ7σ8σ6σ5σ5σ5σ7σ6σ8σ1σ3σ2σ4σ6σ6σ8σ5σ7σ3σ1σ4σ2σ7σ7σ6σ8σ5σ4σ2σ1σ3σ8σ8σ5σ7σ6σ2σ4σ3σ1先把置换表成不相杂轮换之乘积，然后用一组顺向圈来表示。每个顺向圈的长度，即圈上所含的元素个数，就是该圈所表示的轮换的长度。

一个n元置换对应一组顺向圈，这组圈的长度之总和为n；反之，一组顺向圈表示一置换，置换的元素个数就是组中各图长度之总和。

6.3.3

置换的顺向圈表示

n元置换σ对应图形表达式

（图型）Gσ==α1z1+α2z2+…+αrzrzi表示长度为i的圈,αi表示如此的zi的个数;诸α为非负整数,0≤α1≤n,αn=0或1；

α1+2α2+…+rαr=n例.M={1,2,3,4,5,6,7,8},σ=(16)(345)(28)，

Gσ=z1+2z2+z3。1×1+2×2+3×1=8

6.3.3

置换的顺向圈表示设σ表为k个不相杂的轮换的乘积(包括长度为1的轮换在内)，长度分别为r1，r2，…，rk。若=n-k为奇数（偶数），则称σ为奇置换（偶置换）。

6.3.4置换的奇偶性因每个长度为r的轮换可写成r-1个对换的乘积：(a1a2…ar)＝(a1

ar)(a1

ar－１)…(a1a3)(a1a2)于是σ可写成=n-k个对换的乘积。

结论：奇置换可表为奇数个对换之积，偶置换可表为偶数个对换之积。

=(1367842)(59)

n-k=9-2=7

(1367842)(59)

=(12)(14)(18)(17)(16)(13)(59)

7个对换。定理6.3.3

每个置换都能分解为对换的乘积，但偶置换只能分解为偶数个对换的乘积，奇置换只能分解为奇数个对换的乘积。证明.只需证明“只能分解”。任取σ∈Sn，设σ等于k个不相杂轮换之积，这些轮换分别含r1，r2，…，rk个元素，于是σ可以写成

个对换之积，定义置换σ的符号sgnσ如下：

sgnσ=

显然，偶置换的符号为1，奇置换的符号为-1。首先证明sgnστ=sgnσsgnτ（4）

设σ等于k个不相杂轮换之积，

τ等于h个不相杂轮换之积，且σ写成对换中最后一个为（ab）。以（ab）乘τ而看其变化。(1)若a和b在τ的两个不同的轮换之内:

τ=（aa1…as）（bb1…bi）…则（ab）τ=（aa1…asbb1…bi）…即,（ab）τ为（h-1）个不相杂轮换之积,故，sgn(ab)τ=(-1)n-(h-1)=-(-1)n-h=-sgnτ(2)若a和b在τ的同一个轮换之内:

τ=（aa1…asbb1…bi）…则（ab）τ=（aa1…as）（bb1…bi）…故，

sgn(ab)τ=(-