Operation

Operation

「運算」。名聞天下、流芳百世的函數。因為大家經常使用這些函數,所以大家特地訂立數學符號、特地稱為運算。

一般來說,輸入與輸出是相同類型,但是也有例外。

範例:自然數加法

Operation的輸入可以有許多個

有些時候,運算的輸入只有一個。

例如邏輯敘述的非運算¬a,實數的倒數運算1/a,函數的微分運算da/dx。

一般來說,運算的輸入恰好兩個。

例如加減乘除。

千載難逢,運算的輸入會有三個。

例如三維向量的三重積a∙(b×c),程式語言的整數的條件判斷a?b:c。

英文說法是unary operation、binary operation、ternary operation。

Operation的輸出可以有許多個

一般來說,運算的輸出只有一個。

千載難逢,運算的輸出會有兩個。

例如自然數的帶餘除法a÷b=c…d。

Operation的輸入和輸出可以是不同類型

例如向量的點積運算a∙b,輸入是向量,輸出是純量。

例如多變量函數的梯度運算∇a,輸入是純量場,輸出是向量場。

Operation的輸入們可以是不同類型

例如向量的倍率運算k⋅a,第一輸入是向量,第二輸入是純量。運算符號由右往左讀。

群、環、體

數學家善於分類性質優美的事物。

數學家替運算進行分類。群、環、體是其中一種分類方式,以運算律來分類。科學味道稀薄、工程味道濃厚。不必強記,想用再學。

反元素、單位元素

世界事物往往相對,有前就有後,有上就有下。

創造一個數學運算,往往就出現了反向運算:加法之於減法,乘法之於除法,函數之於反函數。

一般來說,正與反是能夠等量相消的。用以等量相消的元素,稱作「反元素inverse element」:加法的反元素是負數-x,乘法的反元素是倒數1/x,函數的反元素是反函數f⁻¹。所謂的「元素」,視情況是指數值、函數、……,算是一種泛稱。

正與反等量相消之後,成為了一個無能的、沒用的元素,稱作「單位元素identity element」:加法當中,數與負數相加等於單位元素,是零;乘法當中,數與倒數相乘等於單位元素,是一;函數當中,函數與反函數複合等於單位函數。

每當數學家創造新的數系、創造新的數學運算,就會勘查反元素、單位元素。學習這些概念後,就有了個行動綱領,就有了個標準作業流程SOP,用以對付人類還不曉得的數學。

數學系的基礎代數課程,就會提到反元素、單位元素。雖然是形而上,但是這不是什麼深奧的數學概念,讀者不必自己嚇自己。

Group

Group

「群」是兩種東西合體:多個元素(一個集合)、一個運算。必須滿足四個規定。

1. Closure           閉包:無論取誰運算,結果仍是那些元素。
   a∙b = c
   a∈S, b∈S ⇒ c∈S 

2. Associativitiy    結合律:無論誰先運算,結果一致。
   (a∙b)∙c = a∙(b∙c)

3. Identity          單位元素1:實施運算,結果不變。
   a∙1 = 1∙a = a

4. Inverse           反元素a̅:實施運算,結果相消,得到單位元素。
   a∙a̅ = a̅∙a = 1

所有元素必須符合所有規定。

a b c:任意元素。
1 a̅:符合規定的某個元素(某些元素)。必須找到。

順便介紹一下其他數學符號的意義。

S:這個群的元素們(集合)。
∙:這個群的運算。
=:等於。詳情請自行學習集合論。
∈:屬於。詳情請自行學習集合論。
,:與。詳情請自行學習集合論。

範例:整數加法群

集合:整數ℤ                ℤ = {..., -2, -1, 0, 1, 2, ...}
運算:整數加法+

1. 2+3 = 5                 a = 2, b = 3, c = 5
   2∈ℤ, 3∈ℤ ⇒ 5∈ℤ
2. (2+3)+4 = 2+(3+4)       a = 2, b = 3, c = 4
3. 2+0 = 0+2 = 2           a = 2, 1 = 0
4. 2+(-2) = (-2)+2 = 0     a = 2, a̅ = -2, 1 = 0

範例:整數乘法群

集合:整數ℤ                ℤ = {..., -2, -1, 0, 1, 2, ...}
運算:整數加法×

1. 2×3 = 6                 a = 2, b = 3, c = 6
   2∈ℤ, 3∈ℤ ⇒ 6∈ℤ
2. (2×3)×4 = 2×(3×4)       a = 2, b = 3, c = 4
3. 2×1 = 1×2 = 2           a = 2, 1 = 1
4. 2×½ = ½×2 = 1           a = 2, a̅ = ½, 1 = 1

範例:餘數加法群

集合:餘數ℤₙ                     ℤ₅ = {0, 1, 2, 3, 4}
運算:餘數加法+

1. 2+3 ≡ 0           (mod 5)     a = 2, b = 3, c = 0
   2∈ℤ₅, 3∈ℤ₅ ⇒ 0∈ℤ₅
2. (2+3)+4 ≡ 2+(3+4) (mod 5)     a = 2, b = 3, c = 4
3. 2+0 ≡ 0+2 ≡ 2     (mod 5)     a = 2, 1 = 0
4. 2+3 ≡ 3+2 ≡ 0     (mod 5)     a = 2, a̅ = 3, 1 = 0

範例:餘數乘法群

集合:與模數互質的數字ℤₙˣ         ℤ₈ˣ = {1, 3, 5, 7}
運算:餘數乘法×

1. 3×5 ≡ 7           (mod 8)     a = 3, b = 5, c = 7
   3∈ℤ₈ˣ, 5∈ℤ₈ˣ ⇒ 7∈ℤ₈ˣ
2. (3×5)×7 ≡ 3×(5×7) (mod 8)     a = 3, b = 5, c = 7
3. 5×1 ≡ 1×5 ≡ 5     (mod 8)     a = 5, 1 = 1
4. 5×5 ≡ 5×5 ≡ 1     (mod 8)     a = 5, a̅ = 5, 1 = 1

反例:向量叉積

集合:實數向量ℝₙ
運算:向量叉積×

2. (a×b)×c ≠ a×(b×c)

結合律不存在。

想要體現非群,我認為向量叉積是經典反例。

Commutative Group(Abelian Group)

「交換群」。追加第五點規則。

5. Commutativity     交換律:輸入交換順序,輸出仍然相同。
   a∙b = b∙a

追加規則聽起來很煩。其實可以把事情想得簡單一點:群分成兩種,要嘛符合交換律,要嘛不符合交換律。

方才的範例都是交換群。下面補充兩個不是交換群的範例。

反例:矩陣乘法群

集合:可逆矩陣
運算:矩陣乘法

1. ⎡ 1 2 ⎤ ⎡ 2 2 ⎤ = ⎡  8 10 ⎤
   ⎣ 3 4 ⎦ ⎣ 3 4 ⎦   ⎣ 18 22 ⎦

   ⎡ 1 2 ⎤ ∈ ℝ₂ₓ₂  ⎡ 2 2 ⎤ ∈ ℝ₂ₓ₂ ⇒ ⎡  8 10 ⎤ ∈ ℝ₂ₓ₂
   ⎣ 3 4 ⎦       , ⎣ 3 4 ⎦          ⎣ 18 22 ⎦

   a = ⎡ 1 2 ⎤   b = ⎡ 2 2 ⎤   c = ⎡  8 10 ⎤
       ⎣ 3 4 ⎦ ,     ⎣ 3 4 ⎦ ,     ⎣ 18 22 ⎦

2. ⎛ ⎡ 1 2 ⎤ ⎡ 2 2 ⎤ ⎞ ⎡ 3 2 ⎤ = ⎡ 1 2 ⎤ ⎛ ⎡ 2 2 ⎤ ⎡ 3 2 ⎤ ⎞
   ⎝ ⎣ 3 4 ⎦ ⎣ 3 4 ⎦ ⎠ ⎣ 3 4 ⎦   ⎣ 3 4 ⎦ ⎝ ⎣ 3 4 ⎦ ⎣ 3 4 ⎦ ⎠

   a = ⎡ 1 2 ⎤ , b = ⎡ 2 2 ⎤ , c = ⎡ 3 2 ⎤
       ⎣ 3 4 ⎦       ⎣ 3 4 ⎦       ⎣ 3 4 ⎦

3. ⎡ 4 3 ⎤ ⎡ 1 0 ⎤ = ⎡ 1 0 ⎤ ⎡ 4 3 ⎤ = ⎡ 4 3 ⎤
   ⎣ 3 2 ⎦ ⎣ 0 1 ⎦   ⎣ 0 1 ⎦ ⎣ 3 2 ⎦   ⎣ 3 2 ⎦

   a = ⎡ 4 3 ⎤ , 1 = ⎡ 1 0 ⎤
       ⎣ 3 2 ⎦       ⎣ 0 1 ⎦

4. ⎡ 4 3 ⎤ ⎡ -2 3 ⎤ = ⎡ -2 3 ⎤ ⎡ 4 3 ⎤ = ⎡ 1 0 ⎤
   ⎣ 3 2 ⎦ ⎣  3 4 ⎦   ⎣  3 4 ⎦ ⎣ 3 2 ⎦   ⎣ 0 1 ⎦

   a = ⎡ 4 3 ⎤ , a̅ = ⎡ -2 3 ⎤ , 1 = ⎡ 1 0 ⎤
       ⎣ 3 2 ⎦       ⎣  3 4 ⎦       ⎣ 0 1 ⎦

5. ⎡ 1 2 ⎤ ⎡ 2 2 ⎤ ≠ ⎡ 2 2 ⎤ ⎡ 1 2 ⎤
   ⎣ 3 4 ⎦ ⎣ 3 4 ⎦   ⎣ 3 4 ⎦ ⎣ 3 4 ⎦

   a = ⎡ 1 2 ⎤ , b = ⎡ 2 2 ⎤
       ⎣ 3 4 ⎦       ⎣ 3 4 ⎦

反例:三維旋轉群SO(3)

集合:三維旋轉矩陣(正規正交矩陣,determinant是1)
運算:矩陣乘法

先轉後轉,結果不同。

想要體現非交換群,我認為三維旋轉群是經典反例。

Order

「秩」。群的大小。元素數量。集合大小。

Generating Set

「生成集合」。取出一些元素。以這些元素及其反元素,實施一長串運算,例如a∙b∙a̅∙b∙b∙b,可以得到每一種元素。

白話:萬能材料。

Subgroup

「子群」。取出一些元素。以這些元素及其反元素,實施一長串運算,還是只能得到這些元素。

白話:關住了、出不去了。

註:教科書採用遞推版本「運算結果及其反元素,反覆實施運算」。兩種版本等價。反元素唯一、反反元素是自身a̿ = a、反元素公式a ∙ b = ba,證明這三者,接著就能證明兩種版本等價。

數學定理

Lagrange's Theorem:子群的大小,整除群的大小。

Cauchy's Theorem:當質數p整除群的大小(例如排列群),那麼此群存在一個元素g(例如一個排列),使得 g^p = 1(此排列套用p次,每個軌道剛好走零步)。

Cayley's Theorem:隨便一個群,一定可以等價地變成某個對稱群的子群(例如排列群)。

延伸閱讀

Cyclic Group

Cyclic Group

「循環群」。生成集合,大小可以是一。想要生成每一種元素,只需一個元素,無需一組元素。

存在一個元素g,g的連續運算,恰好生成每一種元素。

g
g∙g
g∙g∙g
g∙g∙g∙g
:

當元素數量有限,最後一定循環,故得名「循環群」。最後一個元素,一定是單位元素。再下一個元素,又回到g。

註:循環群一定是交換群。

Generator

循環群的情況下,生成集合簡化為生成子。

「生成子」。取出一個元素。以這個元素(及其反元素),實施一長串運算,例如g∙g∙g∙g∙g,可以得到每一種元素。

註:途中肯定遇到反元素。因此「及其反元素」五字是多餘的。

生成子通常有許多種。目前沒有快速的演算法。

範例:餘數加法群

集合:餘數ℤ₈                ℤ₈ = {0, 1, 2, 3, 4, 5, 6, 7}
運算:餘數加法+
生成子:跟模數互質的數字    g = {1, 3, 5, 7}

g ≡ 3 (mod 8)
g+g ≡ 6 (mod 8)
g+g+g ≡ 1 (mod 8)
g+g+g+g ≡ 4 (mod 8)
g+g+g+g+g ≡ 7 (mod 8)
g+g+g+g+g+g ≡ 2 (mod 8)
g+g+g+g+g+g+g ≡ 5 (mod 8)
g+g+g+g+g+g+g+g ≡ 0 (mod 8)  至此得到每一種元素

範例:餘數乘法群

餘數乘法群不一定是循環群。某些特殊的模數,才能找到生成子,才能形成循環群。幸運的是,數學家已經發現哪些模數有生成子、哪些模數沒有生成子。此處省略。

順帶一提,餘數乘法群的生成子,又稱作「原根」。

Permutation Group

Permutation

「排列」可以看成是雙射函數,每個數字變成另一個數字。

以下用「」解釋「排列」。「排列」畫成圖,每個點恰有一條出邊、一條入邊,必然形成許多環。一個「排列」就是許多環!

因此「排列」經常寫成循環節的形式。

UVa 11071 ICPC 6899

Orbit

套用一個排列,就是各點同時走一步。

持續套用同一個排列,就是各點同時走一步、走兩步、……。

每個點總是繞行於自己的環裡面。

持續套用兩個不同的排列,順序隨意。相交的環,都能走到。

每個點總是漫步於自己的連通分量裡面。

持續套用多個不同的排列,以此類推。

每一塊走動範圍稱作「軌道」。

Permutation Group

給定一個排列,我們可以找出許多排列,令每個點總是繞行於自己的環裡面,不會離開環。

例如給定一個排列,共有四個環。符合上述條件的其中一個排列是:第一個環走兩步,第二個環走零步,第三個環走三步,第四個環走一步。

符合上述條件的所有的相異排列,總數量等於:每個環的長度相乘!這些排列們稱為一個「排列群」。

另外,若有長度一樣的環(甚至呈倍數關係),可令這些環一齊走相同步數。排列數量減少了,但是仍是一個「排列群」。

給定多個不同的排列,亦得如法炮製。我們可以找出許多排列,令每個點總是繞行於自己的連通分量裡面。符合條件的所有的相異排列,也是一個「排列群」。若有構造一樣的連通分量(甚至呈倍數關係),可令這些連通分量一齊走相同步法,仍是一個「排列群」。

注意到,數學家給予「群」、「排列群」、「群作用」非常明確的定義。此處省略了許多細節。

Orbit–Stabilizer Theorem

o(x) = { g‧x | g∈G }      從x可走到的點們。
orbit                    (一個環、一個連通分量)

s(x) = { g∈G | g‧x = x }  讓x走回原處的排列們。
stabilizer               (x的環走零步,其他環走隨意步)

f(g) = { x∈X | g‧x = x }  套用一個排列g,走回原處的點們。
fixed point              (某些環所走的步數,恰等於環的長度的倍數)
                         (某些連通分量所走的步法,恰回到原處)

軌道衛星定理:一個排列群,任選一點x,|o(x)| |s(x)|相乘,等於排列群大小、等於排列總數量。

將x所在的軌道(暨同步軌道們),分離出來罷了。

不動點計數定理【沒有正式學術名稱】

sum_all_x |s(x)| = sum_all_g |f(g)|

不動點計數定理:一個排列群,所有排列的所有不動點,共有兩種計數方式。

首先觀察單一軌道:

左式:第一點,分別走零一二三……步,走回原處的次數;第二點,分別走零一二三……步,走回原處的次數;……。通通加起來。

右式:所有點各走零步,走回原處的點數;所有點各走一步,走回原處的點數;……。通通加起來。

接著把單一軌道推廣成多個軌道,接著把環上的步數推廣成連通分量上的步法,即得証。

順帶一提,此定理即是微積分Fubini's Theorem的實際應用。

Orbit Counting Theorem

              |o(x)| |s(x)| =          #(g)   [orbit-stabilizer theorem]
sum_one_orbit |o(x)| |s(x)| =   |o(x)| #(g)   [repeat |o(x)| times]
|o(x)| sum_one_orbit |s(x)| =   |o(x)| #(g)   [constant]
       sum_one_orbit |s(x)| =          #(g)
       sum_all_orbit |s(x)| = #(orbit) #(g)
           sum_all_x |s(x)| = #(orbit) #(g)
           sum_all_g |f(g)| = #(orbit) #(g)   [Fubini's theorem]

           sum_all_g |f(g)|
           ―――――――――――――――― = #(orbit)
                 #(g)

軌道計數定理:一個排列群,不動點的平均數,就是軌道數量。

軌道不好算,不動點很好算,因此數學家兜出這個式子。

Pólya Counting Theorem

                               #(cycles of g)
sum_all_g |f(g)|   sum_all_g  k
―――――――――――――――― = ―――――――――――――――――――――――――― = #(orbit)
      #(g)                    #(g)

這是特殊案例。排列的對象,不是n個東西,而是nᵏ個東西:n個相同元件,k種不同顏色,每個元件塗上其中一種顏色,全部的可能性。

雖然有nᵏ個東西,但是排列規則只有排列n個元件,並未提及元件的顏色。

波利亞計數定理:一、僅排列n個元件,求得虛擬排列群。此時看清楚nᵏ個東西的排列情況,恰好是真的排列群。可以套用軌道計數定理。二、此時一個排列的不動點數量,恰好是k的次方,次方值是該排列的循環節數量。

證明省略。請看範例。

範例:方格著色

四個方格呈田字,每個方格是白色或黑色,總共2⁴ = 16種。

當旋轉視為相同,那麼就剩下6種。

我們的目標是:不比對所有田字,快速算出答案是6種。

旋轉即排列。此例當中,旋轉的基本單位是90°。

以90°為基礎,建構虛擬的排列群,涵蓋所有旋轉方式:順時針旋轉90°、180°、270°、360° = 0°。此排列群是虛擬的排列群,僅考慮4個方格,而非2⁴種田字。

看清楚2⁴種田字的排列情況,這四個排列恰好是真的排列群:以90°作為基礎,每個環走每種步數、一些同步軌道。

我們的目標是:此排列群的軌道數量,就是答案,一共6種。

實務上沒有人像我這樣把所有排列詳細畫出來,然後找連通分量。快速的方法是軌道計數定理、波利亞計數定理,直接列出不動點,求平均數。此例的不動點,就是旋轉之後,仍舊一樣的田字。

顏色k=2種                      循環節數量
旋轉       排列     不動點數量  括號數量
     |       g      | |f(g)| ||  cycle  | k^cycle 
---- | -------------|--------||---------|---------
  0° | (1)(2)(3)(4) |   16   ||    4    | 2^4 = 16
 90° | (1234)       |    2   ||    1    | 2^1 = 2 
180° | (13)(24)     |    4   ||    2    | 2^2 = 4 
270° | (1432)       |    2   ||    1    | 2^1 = 2 

orbit counting theorem: (16+2+4+2)/4 = 6
Pólya counting theorem: [(2^4)+(2^1)+(2^2)+(2^1)]/4 = 6

以上就是波利亞計數定理的用途。

以下另外提供顏色數量為1、2、3時的不動點。讀者可以從中觀察波利亞定理的精神。

UVa 10601 10733 11255 11540