Monday, March 11, 2013

群論01 如果某個運算涉及同一個元素,我們可以像一般乘法那樣採用「指數」記法,例如可以把a • a • a寫成a3。我們還可以仿照一般乘法規定零指數和負指數的定義如下:a0 = e,a−n = (a−1)n。

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



要了解破解魔方攻略背後的數學原理,「群論」(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−1 (稱為a的「逆元」),使得a • a−1 = a−1 • a = e。

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

(a • b)−1 = b−1 • a−1 (1)

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

此外,如果在G中存在一個元素g使得對G中任何元素a,都有a = gn,其中n為0、正整數或負整數,我們便說(G, •)是「循環群」(Cyclic Group)。在此情況下,我們說G由g生成,記作G = < g >,其中< g >稱為g的「生成集合」(Span),其定義為< g > = {gn: 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° (記作R2)、以通過三角形上方頂點(即上圖中的A點)的軸為對稱軸的反射(記作RA)、以通過三角形左下方頂點(即上圖中的B點)的軸為對稱軸的反射(記作RB)、以通過三角形右下方頂點(即上圖中的C點)的軸為對稱軸的反射(記作RC)(註1)。

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

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

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

子群


接著我們引入「子群」(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−1 ∈ H。

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

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

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

魔方群


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

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

8! × 12! × 38 × 212 / 12 = 4.3252 × 1019 (2)

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

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

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

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

54! = 2.3084 × 1071 (3)

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

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

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

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

No comments:

Post a Comment