變換和置換群.ppt

變換群和置換群 離散數(shù)學(xué)第15講 上一講內(nèi)容的回顧 不變子群商群同態(tài)核自然同態(tài)群同態(tài)基本定理同態(tài)基本定理的應(yīng)用 變換群與置換群 變換和變換群置換及其表示置換群任意群與變換群同構(gòu)置換群的應(yīng)用 變換和變換群 定義 A是非空集合 f A A稱為A上的一個(gè)變換 經(jīng)常討論的是一一變換 即f是雙射 變換就是函數(shù) 變換的 乘法 就是函數(shù)復(fù)合運(yùn)算 集合A上的一一變換關(guān)于變換乘法構(gòu)成的群稱為變換群 非空集合上所有的一一變換構(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 即其逆元素 變換群的例子 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 置換及其表示 定義 有限集合S上的雙射 S S稱為S上的n元置換記法 置換的例子 例子 集合S 1 2 3 上共有6個(gè)不同的置換 它們的集合記為S3 S3是最小的非交換群注意 質(zhì)數(shù)階群一定是可交換群 輪換與對(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 不相交的輪換相乘可以交換 給定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 用輪換的乘積表示置換 任一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 置換的輪換乘積形式的唯一性 如果置換 可以表示為 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 這說明X Y 同理可知Y X 置換的輪換乘積形式 例子 157 48 例子 1235 4876 用對(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中其它元素 對(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 1 排列中的逆序 設(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ù)是4 奇置換和偶置換 是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 奇置換和偶置換 歸納證明 假設(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) 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 1 2 5 4 7 6 9 14 15 3 13 8 11 10 12 8 16 8 12 8 16 12 置換群 有限集合S上所有置換一定構(gòu)成群 稱為對(duì)稱群 記為Sn 其中n是S的階數(shù) Sn的任一子集若構(gòu)成群 則是置換群 注意 置換群是變換群的特例 對(duì)稱群是置換群的特例 Sn中所有的偶置換構(gòu)成子群 稱為交錯(cuò)群 只須證明封閉性 置換群的幾何意義 以S3為例 基于已知群定義變換群的例子 對(duì)群 G 中任意一元素a 可以定義 a G G x G a x x a a是一一變換 a是顯然是函數(shù)對(duì)任意b G 群方程x a b有唯一解 即 a是滿射由群滿足消去律 x a y a x y 即 a是單射令G a a G Cayley定理 任意的群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)算 利用置換群解題的例子 在四個(gè)方格子中放置了帶有標(biāo)號(hào)的四個(gè)盤子 見右圖 可以進(jìn)行下列操作 1 上下行互換 2 左右列互換 3 兩對(duì)對(duì)角元素互換進(jìn)行上述操作任意有限多次 可以按照任意次序進(jìn)行 包括交替進(jìn)行 問題 操作停止時(shí)與開始時(shí)格局相同的充分必要條件是什么 采用置換群建立數(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 問題的解 任意有限多次連續(xù)動(dòng)作即等效于函數(shù)f fi1 fi2 fin 其中ik 1 2 3 所以 開始格局與結(jié)束格局相同當(dāng)且僅當(dāng)f e e f1 f2 f3 是可交換群 f fi1 fi2 fin f1h f2j f3k 其中h j k是非負(fù)整數(shù) 注意 對(duì)i 1 2 3 均有fi2k e 其中k是非負(fù)整數(shù) f f1s h f2s j f3s k s x 是整數(shù)集上的 奇偶特征函數(shù) 當(dāng)x為奇數(shù) s x 1 否則s x 0 注意 f1 f2 f3 e 開始格局與結(jié)束格局