離散數(shù)學ii（李占山）6.4子群及其陪集.ppt

6 4子群及其陪集 6 4 1子群的定義6 4 2子群的判別條件6 4 3循環(huán)群6 4 4陪集 捉大頭游戲 它是一種相傳很久的有趣游戲 如下圖 最上面一排是參加抽簽者的名字 最下面一排是簽號 獎品或公差 每個人依次順著豎線往下走 碰到有橫線時 即轉向橫向前進 碰到豎線再往下走 依次類推 則只要橫線不要跨過3條豎線 只能跨在兩豎線之間 那么此游戲執(zhí)行完畢后 最上面的每個人會1 1對應到最下面一排的位置 一般在設計游戲時 是由主持人先畫好豎線和橫線 且在最下面先標好簽號 由抽簽者自行填上最上面的人名 有時 為了增加趣味性 先畫好豎線填好上排的人名和下面的簽號 再請參加者自行畫上橫線 不過速度要快 要不然觀察力強者 很快可以找出對應關系 請同學們考慮是否可以使用置換的復合編程處理 6 4 1子群的定義 子群設 G 是一個群 H G 如果 H 仍是一個群 則 H 叫做 G 的子群 真子群如果G的一個子群H不等于G 即H G 則 H 叫做 G 的真子群 Note G的子群H的運算必須與G的運算一樣 比如 C 不是 C 的子群 在群中成立的性質在子群仍成立 子群的例 例 mZ 是整數(shù)加法群 Z 的一個子群 例 C 以 R Q Z 為其真子群 例 C 以 R Q 為其真子群 例 行列式等于1的所有n階矩陣作成所有n階非奇異矩陣的乘法群的一個子群 例 n次交代群是n次對稱群的一個真子群 平凡子群 群G一般都有兩個明顯的子群 稱為G的平凡子群 由其單位元素組成的子群 1 稱為G的單位子群 G本身 其余的子群 如果有的話 稱為非平凡子群 子群的例 設Z6 0 1 2 3 4 5 是模6的剩余類集合 則Z6在剩余類加法下是一個群 其中 0 和Z6是該群的兩個平凡子群 0 3 和 0 2 4 是其非平凡子群 而 0 1 3 5 不是子群 例子 例設 G 是群 對G中任意a 令H x x a a x x G 試證明 H 是 G 的子群 證明 顯然1 H 即H非空 對H中任意x y有 x y a x y a x a y x a y a x y a x y 故x y H 即H中 運算封閉 在H中 運算顯然仍滿足結合律 對H中任意x有x a a x 于是x 1 x a x 1 x 1 a x x 1 化簡得到a x 1 x 1 a 即x 1 H 證畢使用同樣辦法可以證明下面練習 設G是一個群 H是G的一個子群 a G 試證aHa 1 aha 1 h H 是G的子群 也稱共扼子群 6 4 2子群的判別條件 判別條件一定理6 4 1群G的一個子集H是G的一個子群的充分必要條件是 1 若a H b H 則ab H 2 若a H 則a 1 H 3 H非空 判別條件一 證明 必要性若H是G的子群 則 1 3 顯然 現(xiàn)要證 2 先證H中的單位元就是G中的單位元 設1G是G中的單位元 1H是H中的單位元 任取a H 則在H中有 1Ha a 故在G中也成立 以a 1右乘得 1Ha a 1 aa 1 即 1H aa 1 1G 1H1G 1G 故 1H 1G 判別條件一 證明續(xù) 由群的定義 對于H中的a 應有b H使 ab 1H 1G 此式在G中亦成立 以a 1左乘得b a 11G a 1 因而a 1 H 即 2 成立 必要性證畢 判別條件一 充分性設 1 2 3 成立 由 3 H非空 由 1 H中的兩個元素a b可以在H內(nèi)相乘 在G中成立的結合律在子集H中自然成立 往證H中有單位元1G 任取a H 由 2 a 1 H 由 1 aa 1 H 即1G H 1G在G中適合1a a 故在H中亦有此性質 往證H中任意元素a有逆 因由 2 a 1 H 但是G中 a 1a 1G 此式在H中亦應成立 故a 1即a在H中之逆 綜上 H在G的運算下是一個群 故是G的子群 H的單位元素就是G的單位元素 H中任一元素a在H中的逆元素也就是a在G中的逆元素 子群H與大群G的關系 判別條件二 定理6 4 2判別條件一中的兩個條件 1 2 可以換成下面一個條件 若a H b H 則ab 1 H 證明 設 1 2 成立 往證 成立 設a H b H 由 2 b 1 H 故由 1 ab 1 H 因而 成立 判別條件二 證明續(xù) 設 成立 往證 1 2 成立 設a H 由 可推得 a H a H 故aa 1 H 即1 H 又由 可推得 1 H a H 故1a 1 H 即a 1 H 因而 2 成立 設a H b H 因為 2 已證 故b 1 H 再由 推知 a H b 1 H 故a b 1 1 H 即ab H 故 1 成立 例子 例設H和K都是群G的子群 令HK xy x H y K 試證若HK KH 則HK是G的子群 此題的逆命題就是書中習題6 4的14 因為1 H 1 K 故1 HK 即非空 對于任意的x hk y h1k1 這里h h1 H k k1 K 有xy 1 hk h1k1 1 h kk1 1 h 1 記k2 kk1 1 K 由HK KH 存在h3 H k3 K使k2h1 1 h3k3 從而xy 1 hh3k3 hh3 k3 HK 由定理6 4 2知HK是G的子群 判別條件三 定理6 4 3設H群G的一個有限非空子集 則H是G的子群的充分必要條件是H對G的運算是封閉的 即若a H b H 則ab H 提示 充分性證明用教材201頁習題2得出的結論 若非空 運算封閉 結合律 消去律 有限 則為群 6 4 3循環(huán)群 定理6 4 4設a是群G的一個元素 于是a的所有冪的集合an n 0 1 2 做成G的一個子群 記為 a 此群稱為由a生成的子群 證明 1 a 非空 至少a0 1 a 2 任取 a 中二元素am an 有am an 1 ama n am n a 故由子群判別條件二 a 做成G的一個子群 6 4 3循環(huán)群 定義 如果群G可以由它的某元素a生成 即有a G使G a 則G叫做一個循環(huán)群 或巡回群 上面定理中的 a 稱為由a生成的循環(huán)子群 例 整數(shù)加法群 Z 是由1生成的循環(huán)群 nZ 是由n生成的循環(huán)群 容易證明循環(huán)群必是Abel群 元素的周期 看由元素a所生成的循環(huán)群 a a 2 a 1 a0 a a2 1 情形10如果 1 中所有元素都彼此不同 則稱a的周期為無窮大或0 此時 對任意兩個不同的整數(shù)s與t as at 情形20如果 1 中出現(xiàn)重復的元素 即有整數(shù)s t 使as at 不妨設s t 于是s t 0且as t 1 即有正整數(shù)m使am 1 若n為適合an 1的最小正整數(shù) 則稱a的周期 階 為n 周期的例 例 4次對稱群中 1234 的周期是4 因為 1234 2 13 24 1234 3 1432 1234 4 I例 在 C 中 1的周期為1 1的周期為2 i的周期為4 模數(shù)r 1的復數(shù)z rei 的周期為無窮大 周期的例 例一個有限群中 周期大于2的元素個數(shù)為偶數(shù) 證明 任取群中周期大于2的元素a 于是a2 1 由群的概念知a有逆元a 1 且a a 1 否則 若a a 1 有a2 1 矛盾 這就是說a與a的逆a 1是成對出現(xiàn)的且它們的周期都大于2 由于a的任意性知周期大于2的元素個數(shù)為偶數(shù) 證畢 周期的例 例若有限群G的元數(shù)為偶數(shù) 則G中周期等于2的元素個數(shù)一定是奇數(shù) 例若群中除單位元外 所有其他元素的周期為2 則該群為Abel群 周期的性質 定理6 4 5若群G中元素a的周期為n 則 1 1 a a2 a3 an 1為n個不同元素 2 am 1當且僅當n m 3 as at當且僅當n s t 證明 因為任意整數(shù)m恒可唯一地表為m nq r 0 r n故am anqar an qar 1qar lar ar 由于0 r n 故按周期的定義知ar 1iffr 0所以am 1iffr 0iffn m即 2 得證 由 2 即知as atiffas t 1iffn s t 即 3 得證 最后由 3 立即可得 1 結論 設a為群G的一個元素 1 如果a的周期為無窮大 則 a 是無限循環(huán)群 a 由彼此不同的元素 a 2 a 1 1 a a2 組成 2 如果a的周期為n 則 a 為n元循環(huán)群 它由n個不同的元素1 a a2 a3 an 1組成 周期的例 例設Sn是n次對稱群 1 若 Sn a1a2 ak 則 的周期是k 2 Sn 1 2 s是不相雜輪換的乘積 若 i是ki階輪換 i 1 2 s 則 的周期是 1 2 s的最小公倍數(shù) k1 k2 ks 證 1 k a1a2 ak k a1 假若 的周期j k 則 j a1 a1a2 ak j a1 aj 1 a1 矛盾 這就證明了j k 周期的例子 2 設 的周期為t k1 k2 ks d 由于 1 2 s是不相雜的 則 d 1d 2d sd a1 因此有t d 另一方面 t a1 由于兩兩不相雜 必有 it a1 i 1 2 s 根據(jù) 1 部分的結果知 i的周期為ki 因此對于所有的i 1 2 s 有ki t 即t是k1 k2 ks的公倍數(shù) 由于d是k1 k2 ks的最小公倍數(shù) 必有d t 綜合上述結果有t d 加法群中元素的周期 在加法群中 a 應換為a的所有倍數(shù)的集合 2a a 0 a 2a 當 中的所有元素均彼此不同時 稱a的周期為無窮大或為0 否則當n為適合na 0的最小正整數(shù)時 稱a的周期為n 注意這里的加法表示滿足交換律的一種抽象運算 定理6 4 5 若加法群中a的周期為n 則有 1 0 a 2a n 1 a為n個不同元素 2 ma 0當且僅當n m 3 sa ta當且僅當n s t 循環(huán)群的生成元素 定理6 4 6 1 無限循環(huán)群 a 一共有兩個生成元 a及a 1 2 n元循環(huán)群 a 中 元素ak是 a 的生成元的充要條件是 n k 1 所以 a 一共有 n 個生成元素 證明 如果ak是 a 的一個生成元 那么 a 中每個元素都可表示為ak的方冪 特別地 a也可表示為ak的方冪 設a ak m akm 1 由 a 是無限循環(huán)群知 km 1 因此 k 1 即 a及a 1為無限循環(huán)群 a 的生成元 2 如果 a 是一個n元有限群 那么a的周期為n 由周期的性質知 n km 1 因此 km 1 nq km nq 1 這說明k與n互質 另一方面 如果k與n互質 則有h和 q 使hk qn 1 即 hk 1 qn 故n kh 1 由周期的性質知 a1 akh a ak h 故a可表為ak的若干次方 總之 a可表為ak的若干次方iffk與n互質 但在0 k n中 共有 n 個k與n互質 故共有 n 個元素ak可生成 a 例子 例 Z 的生成元只能是1和 1 若G a 是元數(shù)為12的群 12 4 與12互質的數(shù)有1 5 7 11 因此a a5 a7 a11是G的所有4個生成元 群的結構 有時需要根據(jù)子群H的一些特點將群分解成 劃分成 一些不相交的子集合之并 如 在 Z 中 取一個正整數(shù)m 可得子群nZ nz z Z 當m 2時 就是所有偶數(shù)在加法下作成的子群 通過這個子群就可以把整數(shù)加法群分解為奇數(shù)和偶數(shù)兩個不相交子集合 它們就是相對于該子群 等價關系 的等價類 陪集 6 4 4陪集 合同關系定義 設G是群 H是G的子群 a b G 若有h H 使得a bh 則稱a合同于b 右模H 記為a b 右modH 例 設G是三次對稱群 H是由 123 生成的子群 H I 123 132 因為有I H 使得 12 12 I 所以 12 12 右modH 因為有 123 H 使得 23 12 123 所以 23 12 右modH 結論 合同關系 右模H 是一個等價關系 證明 1 證反身性 因為對任意a G 有1 H 使得a a1 所以a a 右modH 2 證對稱性 即證若a b 右modH 則b a 右modH 由a bh h H可以推出b ah 1 而且h 1 H 故b a 右modH 3 證傳遞性 即證若a b 右modH b c 右modH 則a c 右modH 由a bh b ck h k H 可得a ckh 其中kh H 故a c 右modH 陪集 定義 群G在合同關系 右模H 下的一個等價類叫做H的一個右陪集 同樣 可以界說a合同于b 左模H a b 左modH 和H的左陪集 結論 a所在的右陪集為aH ah h H 注意 有些書上把右陪集稱做左陪集 這沒有關系 只要我們弄清楚就可以了 陪集的例 設G是整數(shù)加法群 H是m的所有倍數(shù)作成的子群 因為加法適合交換律 所以左右之分不存在 因而 左modH 和 右modH 是一樣的 左右陪集也是一樣的 a b modH 即a b h h H 亦即 a b km 故a b modm 可見 H的陪集就是模m的剩余類 陪集的例 設G是所有非0復數(shù)的乘法群 所有其 z 1的復數(shù)z ei 作成G的一個子群H a b modH 等于說 a b 在復平面上 H相當單位圓 H的所有陪集相當以原點為圓心的所有同心圓 求陪集的簡單方法 若G是一個有限群 求H的右陪集 首先 H本身是一個 任取a H a G 而求aH 又得到一個 任取b H aH而求bH又得到一個 如此類推 因G有限 最后必被窮盡 而G H aH bH 例 設G是3次對稱群 1 12 13 23 123 132 H 1 12 H有三個右陪集 1 12 13 123 23 132 H有三個左陪集 1 12 23 123 13 132 定理6 4 7 設H是群G的有限子群 則H的任意右陪集aH的元數(shù)皆等于H的元數(shù) 證明 aH ah h H 又G中有消法律 由a ay可以推出 y 故H中不同元素以a左乘仍得不同的元素 因而aH的元數(shù)等于H的元數(shù) 證畢該定理結果表明所有陪集元素個數(shù)相等 陪集的性質 1 若H為G的有限子群 則 aH H 2 H本身也是H的一個右陪集 3 aH H的充分必要條件是a H 4 a在陪集aH中 根據(jù)這點 把a叫做右陪集aH的一個陪集代表 陪集的性質 5 對于右陪集aH中任意元素b 都有aH bH 證明 由b aH知 存在h H 使得b ah 因此 bH ahH a hH aH 這點說明右陪集aH中任一元素都可以取做陪集代表 從 5 還可推出 6 aH bH的充分必要條件是a 1b H 陪集的性質 7 任意兩個右陪集aH和bH或者相等或者不相交 證明 如果aH和bH相交 則它們包含公共元素c 即c aH 且c bH 因此 由 5 得aH cH 且bH cH 故 aH bH 正規(guī)子群 定義 設H是群G的子群 設對G中的任意元素g 都有gH Hg 則稱H是G的正規(guī)子群 結論1 平凡 子群H 1 和G都是G的正規(guī)子群結論2Abel群的任意子群是正規(guī)子群 結論3H是G的正規(guī)子群 必要而且只要對任意的g G gHg 1 H 證明 必要性 由H是G的正規(guī)子群 知 對于任意g G gH Hg 即 gHg 1 H 故gHg 1 H 充分性 設對任意g G gHg 1 H 既然此式對任意g G成立 則以g 1 G代g仍成立 g 1H g 1 1 H 即 g 1Hg H 以g左乘以g 1右乘之 得H gHg 1因此 H gHg 1對任意g G都成立 即 gH Hg 因而H是正規(guī)子群 例子 結論4 設H是G的一個子群 H是G的正規(guī)子群當且僅當對G中任意的a 都有aHa 1 H 即H只有一個共扼子群 就是H自己 證明 aHa 1 H aH Ha 故有定義可知H是G的正規(guī)子群 aHa 1 H 對G中任意的a成立 Lagrange定理 設G為有限群 則G的任意子群H的元數(shù)整除群G的元數(shù) 證明 設 G n H r 設H有s個右陪集 則每個右陪集的元數(shù)等于H的元數(shù)r 再由不同的右陪集沒有公共元素 知所有右陪集的并集有元數(shù)rs 而G等于所有右陪集的并集 故 G n rs H s 即 子群H的元數(shù)整除群G的元數(shù) 反例 注意 此定理逆命題不一定成立 換句話說 若正整數(shù)d是n的因子 但G不一定有d元子群 如4次交代群 所有偶置換作成的群 A4的元數(shù)為12 6是其因子 但A4沒有6元子群 H在G中的指數(shù) 有限群G的元數(shù)除以H的元數(shù)所得的商 記為 G H 稱作H在G中的指數(shù) 結論 H的指數(shù)也就是H的右 左 陪集的個數(shù) 右代表系 從每個右陪集中選出一個元素為代表 全體代表的集合叫做一個右代表系或右代表團 結論 設G有限而g1 gs作成一個右代表系 則g1H gsH便是H的所有右陪集而G g1H gsH 結論 指數(shù)等于2的子群一定是正規(guī)子群 應用Lagrange定理 定理6 4 8設G為有限群 元數(shù)為n 對任意a G 有an 1 證明 因為G有限 a的周期必有限 否則a所生成的循環(huán)子群 a 將無限 G的元素將無窮多 命a的周期為m 則a生成一個m元循環(huán)子群 a 按Lagrange定理 m n 即n 0 modm 因此an 1 Lagrange定理的使用 我們可以使用拉格朗日定理確定一個群內(nèi)可能存在的子群 元素的周期等 從而搞清一個群的結構 以前我們確定一個群內(nèi)的子群時 主要利用元素生成的子群 有個這個定理 就可以首先有G的元數(shù)的因子來確定可能存在子群的元數(shù)以及元素的周期 然后根據(jù)子群的元數(shù)來尋找子群 例子 證明6元群中一定有周期為3的元素 證 根據(jù)定理6 4 8 G中元素的周期是6的