北京大学：《离散数学》离散数学之二《代数结构与组合数学》第17章 群（3/5）17.4 变换群与置换群 17.5 群的分解

174变换群与置换群 ■变换群 变换群的定义 变换群的实例 ■n元置换群 置换的表示 置换的乘法和求逆运算 置换群中元素的阶与子群 置换群的实例

1 17.4 变换群与置换群 „ 变换群 „ 变换群的定义 „ 变换群的实例 „ n元置换群 „ 置换的表示 „ 置换的乘法和求逆运算 „ 置换群中元素的阶与子群 „ 置换群的实例

变换群 变换群的定义 A上的变换: f:A-4 A上的一一变换:双射f:A-4 A上的一一变换群:E(4)={f|f:A-A为双射} 关于变换乘法构成群 A上的变换群G:GE(4) 实例 G为群,a∈G,令:→>G,f(x)=ax,则后为一一变换 H={f∈G}关于变换乘法构成G上的变换群. HSE(G

2 变换群 变换群的定义 A 上的变换： f:A→A A 上的一一变换： 双射 f:A→A A 上的一一变换群：E(A)={ f | f:A→A 为双射} 关于变换乘法构成群 A 上的变换群 G： G⊆E(A) 实例 G 为群，a∈G，令 fa:G→G, fa(x)=ax，则 fa为一一变换. H={ fa | a∈G}关于变换乘法构成 G 上的变换群. H≤ E(G)

变换群的实例 例如G ∫{e,e>,>,b,b>,C, fake, a,a, e>, , j J6={e,b>,,C>,b,e>,C,> J∫={e,C>,,b>,,C,e} H=ffe, fa,b,fc) 思考:怎样证明H同构于G 与独异点的表示定理进行比较

3 例如 G={ e, a, b, c }， fe={,,,} fa={,,,} fb={,,,} fc={,,,} H={ fe , fa , fb , fc } 思考：怎样证明 H 同构于 G 与独异点的表示定理进行比较 变换群的实例

n元置换群 A上的n元置换:|4=n时A上的一一变换 表示法 (1)置换的表示法:令A={1,2,…,n}, (1)(2)…(n) (2)不交轮换的分解式:σ=102rt 其中τ12,,为不交轮换 (3)对换分解式: 对换(i)=(ji (1i2…i)=(iik)(i1k1)…(i1i2)

4 A 上的 n 元置换：|A| = n 时 A 上的一一变换 表示法 (1) 置换的表示法：令 A={ 1, 2, …, n },   = (1) (2) ... ( ) 1 2 ... nn σ σ σ σ (2) 不交轮换的分解式：σ = τ1τ2…τt, 其中 τ1,τ2, …,τt为不交轮换 (3) 对换分解式： 对换 ( i j ) =( j i ) (i1 i2…ik) = (i1 ik) (i1 ik-1) … (i1 i2) n元置换群

n元置换的轮换表示 定理1任何n元置换都可以表成不交的轮换之积, 并且表法是唯一的.即 o=σ1σ2…,oto=τ12T→{o1,o2,,ot={1,τ2,,T} 证明思路 (1)σ可以表成不交的轮换之积.归纳证明 (2)唯一性.假设 O-o1o2ot,o=i2·v 令X={ai,02…,o},F={τ1,τ2…,t} 任取G∈X,=(i2,im,m>1,证明∈Y使得σ=τs, 从而XY.同理YX

5 定理 1 任何 n 元置换都可以表成不交的轮换之积， 并且表法是唯一的. 即： σ=σ1σ2…σt, σ=τ1τ2…τl ⇒ {σ1,σ2,…,σt}={τ1,τ2,…,τl } 证明思路 (1) σ可以表成不交的轮换之积. 归纳证明. (2) 唯一性. 假设 σ=σ1σ2…σt, σ=τ1τ2…τl. 令 X={σ1,σ2,…,σt}, Y={τ1,τ2,…,τl} 任取σj ∈X, σj=(i1i2…im), m>1, 证明∃τs∈Y 使得σj=τs， 从而 X⊆Y. 同理 Y⊆X. n元置换的轮换表示

n元置换的轮换指数 轮换指数:1o2().n),Ck(o):k轮换的个数 12345678 例如 5238761 (157)(48 指数为1323145678=1323 不同指数的个数是如下方程的非负整数解的个数 x1+2x2+..+nxn=n 例如: A={1,2,3}上的置换(1)、(12),(13),(23),(123132) 轮换指数为13:o1;12:a2o3,04;3:so6

6 轮换指数： ( ) ( ) ( ) 1 2 ... C1 σ C2 σ Cn σ n ，Ck(σ): k-轮换的个数 例如 (1 5 7)(4 8) 5 2 3 8 7 6 1 4 1 2 3 4 5 6 7 8 =  指数为 1321314050607080 = 132131 不同指数的个数是如下方程的非负整数解的个数 x1 + 2x2 + … + nxn = n 例如： A={1,2,3}上的置换 (1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2) 轮换指数为 13：σ1； 1121：σ2,σ3,σ4； 31：σ5,σ6 n元置换的轮换指数

n元置换的对换表示 任意轮换都可以表成对换之积 对换可以有交 表法不唯一,但是对换个数的奇偶性不变 12345678 523876140157)(48)=(17)548)=(57)(17)48) 奇置换、偶置换 奇置换:表成奇数个对换之积 偶置换:表成偶数个对换之积 奇置换与偶置换之间存在一一对应,因此各有n!/2个

7 任意轮换都可以表成对换之积 对换可以有交 表法不唯一，但是对换个数的奇偶性不变 ( 1 5 7 ) ( 4 8 ) (17)(15)(48 ) (57)(17)(48 ) 5 2 3 8 7 6 1 4 1 2 3 4 5 6 7 8 = = =         奇置换、偶置换 奇置换：表成奇数个对换之积 偶置换：表成偶数个对换之积 奇置换与偶置换之间存在一一对应，因此各有 n!/2 个 n元置换的对换表示

置换的乘法与求逆 置换的乘法:函数的合成 例如:8元置换σ=(132)(5648),τ=(18246573),则 oτ=(15728)(3)(4)(6)=(15728) 置换求逆:求反函数 σ=(132)(5648),o=(8465)(231), 令Sn为{1,2,,上所有n元置换的集合 Sn关于置换乘法构成群,称为n元对称群 Sn的子群称为n元置换群 例3元对称群S3={(1),(12)13),(23)123),(132)} 3元交代群A3={(1),(123),(132)

8 置换的乘法：函数的合成 例如：8 元置换σ=(132)(5648)，τ=(18246573), 则 στ=(15728)(3)(4)(6)=(15728) 置换求逆：求反函数 σ=(132)(5648)，σ−1=(8465)(231), 令 Sn为{1,2,…,n}上所有 n 元置换的集合. Sn关于置换乘法构成群，称为 n 元对称群. Sn的子群称为 n 元置换群. 例 3 元对称群 S3={(1),(12),(13),(23),(123),(132)} 3 元交代群 A3={(1),(123),(132)} 置换的乘法与求逆

置换群中元素的阶与子群 元素的阶 k阶轮换(i2,)的阶为k o=τ12…:T是不交轮换的分解式,则|o=cc2l,,cl 子群 (1)},Sn,n元交代群An 例如S3 子群6个 2 ,S3 (12)>, ,A3=

9 元素的阶 k 阶轮换(i1 i2…ik) 的阶为 k σ=τ1τ2…τl是不交轮换的分解式，则 |σ|=[|τ1|,|τ2|,…,|τl|] 子群 {(1)}, Sn，n 元交代群 An 例如 S3 子群 6 个 , S3, , , , A3= 置换群中元素的阶与子群

置换群的实例 Cayley定理每个群G都与一个变换群同构 推论每个有限群都与一个置换群同构 D,4x4的方格图形,在空间旋转、翻转 43 12 D4={(1),(1234,(13)(24),(1432),(12)34), (14)(Q23),(13)(2)(4),(24)(1)(3)} D4≤S4

10 Cayley 定理 每个群 G 都与一个变换群同构. 推论 每个有限群都与一个置换群同构 D4，4×4 的方格图形，在空间旋转、翻转. D4={ (1), (1234), (13)(24), (1432), (12)(34), (14)(23), (13)(2)(4), (24)(1)(3) } D4 ≤ S4 置换群的实例