群論01 Group Theory Abstract Algebra

http://chowkafat.net/Rubik2.html

群論與魔方：群論基礎知識

要了解破解魔方攻略背後的數學原理，「群論」(Group Theory)是必不可少的知識，本章介紹群論的基礎知識。群論是「抽象代數學」(Abstract Algebra)的重要分支，是有關「群」(Group)的理論。抽象代數學跟一般代數學或線性代數學不同，其要旨不是解方程或方程組，而是研究各種代數結構的特性，「群」就是一種非常重要的代數結構。

群的基本定義

設有一個集合G和G上的「二元運算」(Binary Operation)「•」。如果G的元素和「•」滿足以下「公理」(Axiom)，我們便說(G, •)構成一個「群」(為了行文方便，有時可以把「群(G, •)」逕直稱為「群G」)：

1. 「封閉性」(Closure)－對G中任何兩個元素a和b而言，a • b ∈ G。
2. 「結合性」(Associativity)－對G中任何三個元素a、b和c而言，(a • b) • c = a • (b • c)。
3. 「單位元」(Identity)－存在G中一個元素e (稱為「單位元」)，使得對於G中任何元素a而言，e • a = a • e = a。
4. 「逆元」(Inverse)－對於G中任何元素a而言，都有G中的元素a⁻¹ (稱為a的「逆元」)，使得a • a⁻¹ = a⁻¹ • a = e。

請注意由於「•」滿足結合性，在寫出三個或以上元素之間的運算時，可以不用括號，即寫成a • b • c。如果某個運算涉及同一個元素，我們可以像一般乘法那樣採用「指數」記法，例如可以把a • a • a寫成a³。我們還可以仿照一般乘法規定零指數和負指數的定義如下：a⁰ = e，a⁻ⁿ = (a⁻¹)ⁿ。另外，可以證明上述定義中的「單位元」是唯一的，而且對於G中任一元素a而言，其「逆元」a⁻¹也是唯一的。根據「封閉性」，若a和b是G的元素，則(a • b)也是G的元素，因此我們也可以談論(a • b)的逆元，而且這個逆元滿足

(a • b)⁻¹ = b⁻¹ • a⁻¹ (1)
如果(G, •)還滿足「交換性」(Commutativity)，即對G中任何兩個元素a、b而言，a • b = b • a，我們便說(G, •)是「交換群」(Commutative Group)或「阿貝爾群」(Abelian Group)。

此外，如果在G中存在一個元素g使得對G中任何元素a，都有a = gⁿ，其中n為0、正整數或負整數，我們便說(G, •)是「循環群」(Cyclic Group)。在此情況下，我們說G由g生成，記作G = < g >，其中< g >稱為g的「生成集合」(Span)，其定義為< g > = {gⁿ: n是整數}，我們也說g是G的「生成元」(Generator)。

舉例說，如果我們把G定為整數集Z，把「•」定為整數的加法「+」，那麼容易驗證(Z, +)構成一個交換群，這個群的「單位元」是0，對每個整數n而言，其「逆元」就是其負數−n。而且(Z, +)也是一個循環群，其生成元就是1，因為Z中的元素要麼是0，要麼是正整數，要麼是負整數，而對任何正整數n而言，我們有n = 1 + 1 + ... 1 (共n個1)，以及−n = (−1) + (−1) + ... (−1) (共n個−1)。由此我們有Z = < 1 >。

類似地，如果我們把G定為非零實數集R*，把「•」定為實數的乘法「×」，那麼容易驗證(R*, ×)也構成一個交換群，這個群的「單位元」是1，對每個非零實數x而言，其「逆元」就是其倒數1 / x。但(R*, ×)不是一個循環群，因為我們無法找到R*的生成元。

「群」是一個非常廣泛的概念，其定義中的集合G的元素可以是各式各樣的對象，除了上述較為具體的整數／非零實數外，還可以是某些抽象數學對象，例如「幾何變換」。以下介紹一種特殊的幾何變換－「對稱變換」，即可保持幾何圖形的形狀不變的變換，以下圖為例：


上圖顯示一個等邊三角形的三個頂點A、B、C以及三條對稱軸。上圖共有以下六種對稱變換：恆等變換(Identity Transformation，記作I，即不作任何變換，亦等同於逆時針旋轉0°)、逆時針旋轉120° (記作R)、逆時針旋轉240° (記作R²)、以通過三角形上方頂點(即上圖中的A點)的軸為對稱軸的反射(記作R_A)、以通過三角形左下方頂點(即上圖中的B點)的軸為對稱軸的反射(記作R_B)、以通過三角形右下方頂點(即上圖中的C點)的軸為對稱軸的反射(記作R_C)(註1)。

我們可以把上述六種對稱變換組成一個集合，記作S₃ (下標"3"代表三角形)。這個集合中的元素有一種二元運算，稱為「複合」(Composition)，記作「•」。兩個變換的「複合」就是先後進行該兩個變換，舉例說，R_A • R²便代表先以通過A點的軸為對稱軸進行反射，然後逆時針旋轉120° (註2)。基於上述定義，容易推出(S₃, •)構成一個群，稱為「對稱群」(Symmetry Group)。首先，任何兩個對稱變換的複合顯然也是一個對稱變換，例如R_A • R² = R_B，因此「•」滿足封閉性。其次，「•」顯然也滿足結合性。第三，I顯然就是S₃中的單位元。最後，每個對稱變換都有其逆變換，而且這個逆變換顯然也是對稱變換，例如R⁻¹ = R²，(R_A)⁻¹ = R_A等。

我們也可以把S₃的元素看成對頂點集合{A, B, C}進行「排列」(Permutation，亦譯作「置換」)的結果，一個集合的排列就是該集合上的一個「雙射」(Bijection)。例如前述的R_A就相當於把A映射為A，B映射為C和C映射為B的變換。由於這個集合有3個元素，所以共有3! = 6種排列，剛好對應著前述的六種對稱變換，因此S₃也稱為「排列群」(Permutation Group，亦譯作「置換群」)(註3)。

(S₃, •)既非交換群，亦非循環群。首先，變換的複合並不滿足交換性。舉例說，R_A • R² ≠ R² • R_A，因為上式的左方等於R_B，而右方則等於R_C。其次，S₃也不存在生成元，因為旋轉和反射是兩類很不相同的變換，不能把某一類變換表達為重複進行另一類中某變換的結果。

子群

接著我們引入「子群」(Subgroup)的概念。給定群(G, •)和G的子集H，如果(H, •)本身也是群，那麼我們說(H, •)是(G, •)的「子群」。由於H的運算跟G的運算相同，若(G, •)滿足結合性，(H, •)自然也滿足結合性，所以給定G的某子集H，如要檢驗(H, •)是否(G, •)的子群，只需檢驗

1. 「封閉性」－對H中任何兩個元素a和b而言，a • b ∈ H。
2. 「單位元」－G的「單位元」e ∈ H。
3. 「逆元」－對於H中任何元素a而言，a⁻¹ ∈ H。

如果在H中存在一個元素h使得對H中任何元素a，都有a = hⁿ，其中n為整數，我們便說(H, •)是(G, •)的「循環子群」(Cyclic Subgroup)，並記作H = < h >。

請注意即使G不是循環群，它也可以有循環子群。事實上，給定群G和G的某個元素h，不難構造出由h生成的循環子群< h >，方法是先寫出h⁰ = e，然後依次寫出h、h² ... 直至hⁿ = e，其中n為使hⁿ = e成立的最小正整數。容易驗證< h > = {e, h, h² ... hⁿ⁻¹}是G的一個循環子群。請注意對G中任何元素h而言，必有某個最小的正整數n使得hⁿ = e，我們把這個n稱為h的「階」(Order)，這個數字也就是< h >的基數。

以前述的等邊三角形對稱群S₃為例，這個群不是循環群，但卻包含多個循環子群。舉例說，所有旋轉變換便組成一個循環子群：< R > = {I, R, R²}。此外，每個反射變換也各自生成一個循環子群，例如< R_A > = {I, R_A}。最後，I本身也構成一個(平凡)循環子群：< I > = {I}。

魔方群

把以上介紹的內容推廣應用於魔方，便可得到一個「魔方群」(Rubik Group)，記作(RUBIK, •)，其中集合RUBIK包含對魔方的各種操作，這些操作包括筆者在上一章，即《群論與魔方：魔方的基本概念》中介紹的操作以及這些操作的複合。舉例說，上一章介紹了以下兩種操作：「順時針旋轉前面90°」(F)和「逆時針旋轉上面180°」(U⁻²)，這兩個操作的複合(F • U⁻²)也是一個操作，代表「先順時針旋轉前面90°，然後再逆時針旋轉上面180°」，因此也是RUBIK的元素(註4)。「魔方群」的二元運算「•」則代表魔方上各種運算之間的複合。

請注意「複合」(•)在這裡出現於兩個不同層面。一方面它是RUBIK中元素之間的二元運算，另一方面它又是RUBIK中某些複合元素的代號的一個組成部分，例如前述的F • U⁻²。之所以出現這個情況，是因為RUBIK包含非常多元素。根據某些數學家的計算，RUBIK元素的數目為

8! × 12! × 3⁸ × 2¹² / 12 = 4.3252 × 10¹⁹ (2)
由於RUBIK的元素極多，難以亦無必要為每一個元素提供一個獨特的代號，所以無可避免要把某些複合元素寫成其他較簡單元素的複合。不過，有時我們也需要區分上述兩個層面。為此，以下將把作為複合元素代號一部分的「•」略去不寫。在這個約定下，FU⁻²代表一個複合元素，而F • U⁻²則代表兩個元素的複合。

容易驗證(RUBIK, •)滿足上述公理。首先，如前所述，任意兩個操作的複合顯然也是一個操作，故滿足封閉性。其次，操作之間的複合顯然滿足「結合性」。第三，RUBIK的單位元就是「恆等變換」，即不作任何操作，以下記作I。最後，RUBIK的每個元素都有逆元。對於簡單元素而言，其逆元在上一章中已有所定義，例如F的逆元就是F⁻¹。對於複合元素而言，只需應用前述的公式(1)便可找到其逆元，例如FU⁻²的逆元就是U²F⁻¹。RUBIK顯然不是交換群，因為調換兩個操作的先後次序，所得結果可能不同，例如F • U ≠ U • F。

RUBIK包含多個循環子群，上一章介紹的各種90°旋轉(包括順時針和逆時針)便可生成4階的循環子群，例如< F > = {I, F, F², F⁻¹}和< F⁻¹ > = {I, F⁻¹, F², F}。除此以外，各種180°旋轉也可生成2階的循環子群，例如< F² > = {I, F²}。

從某一角度看，我們可以把RUBIK看成某個排列群的子群，這個排列群的元素是對魔方小面的所有可能排列。由於魔方共有54個小面，這個排列群可記作S₅₄，其元素數目是

54! = 2.3084 × 10⁷¹ (3)
比較(2)和(3)，我們看到S₅₄的元素數目遠遠多於RUBIK的元素數目，這說明了在魔方小面的所有可能排列中，只有極小部分可以透過魔方的操作實現。舉例說，魔方上的方塊分為角塊、邊塊和中心塊這三類，魔方的操作只能把某一類中的方塊送到同類方塊的位置上，因此如果某一排列是把「fru」角塊的前面送到「fu」邊塊的前面，那麼這個排列就是不可能實現的，因而不屬於RUBIK。魔方小面的可能排列還有其他限制，這些限制將在以後各章中提到。
註1：R_A、R_B和R_C下標中的A、B和C是就三角形的初始狀態而言的。三角形經變換後，A、B和C可能已轉到不同位置，但R_A仍是指以通過當前三角形上方頂點(不一定是A點)的軸為對稱軸的反射，其餘類推。

註2：本文不採用大多數群論教科書表示複合變換的方法(即用X • Y代表先進行Y，後進行X)，這是為了與大多數魔方書籍／網址用來表示魔方複合操作的方法(詳見下文)保持一致。

註3：「對稱群」與「排列群」是兩個不同的概念。儘管S₃既是「對稱群」，又是「排列群」，但一般而言這兩個概念並不重合。請注意當n > 3時，S_n專指「排列群」。

註4：請注意上一章介紹的某些操作也可以看成複合的結果，例如C_U便可以表達為U • M_U • D⁻¹，因為把整個魔方繞其垂直軸轉動90°實質上等同於把魔方的頂、中、底層逐層轉動90°。由此可見，RUBIK的成員可以有多於一種等價表達法。