有限體與模算術

本文的閱讀等級:中級

從前,在一個遙遠的小城裡住著 n 個居民,他們主要的職業是組成各式各樣的俱樂部。由於某種不明的原因,不斷擴增的俱樂部開始威脅小城的生存。為了管制俱樂部總量,市議會決議通過兩條看似天真的法令:

  • 每一個俱樂部必須有奇數個會員。
  • 任兩個俱樂部必須有偶數個相同的會員。

小城市長宣稱:「有了這兩條法令,本城的俱樂部總數不會多於居民人口。」下面我們用線性代數方法來證明這個組合數學定理[1]

 
設小城居民的身分證號為 1, 2, \ldots,n,俱樂部則以 C_1,\ldots,C_m 表示。定義 m\times n 階會籍 (membership) 矩陣,或稱關聯 (incidence) 矩陣[2]A=[a_{ij}],如下:a_{ij}=1j\in C_ia_{ij}=0j\notin C_i。考慮 m\times m 階交互乘積矩陣 AA^T,其中 (i,k)

\displaystyle  (AA^T)_{ik}=\sum_{j=1}^na_{ij}a_{kj}

表示 C_iC_k 的相同會員總數,記為 \vert C_i\cap C_k\vert。若主對角元 (AA^T)_{ii} 是奇數且非主對角元 (AA^T)_{ik}i\neq k,是偶數,則 A 稱為合法會籍矩陣。例如,

\displaystyle  A=\begin{bmatrix}  0&1&1&0&1&0\\  1&0&0&0&0&0\\  0&0&1&0&1&1\\  0&1&1&0&0&1  \end{bmatrix}

交互乘積為

\displaystyle  AA^T=\begin{bmatrix}  3&0&2&2\\  0&1&0&0\\  2&0&3&2\\  2&0&2&3  \end{bmatrix}

合法會籍矩陣 A 完全由 AA^T 各元的奇偶性所決定。我們需要引用一些抽象代數來證明給定的命題:所有 m\times n 階合法會籍矩陣 A 必滿足 m\le n

 
首先我介紹一個關於「數」的代數結構。一個體 (域,field) {F} 是賦予加法與乘法運算的集合,並滿足下列性質:

  1. 加法封閉性:若 a, b\in{F}, 則 a+b\in{F}
  2. 加法交換律:若 a, b\in{F}, 則 a+b=b+a
  3. 加法結合律:若 a, b, c\in{F}, 則 a+(b+c)=(a+b)+c
  4. 加法單位元:對於每一 a\in{F},僅存在唯一 0\in{F} 使得 a+0=a
  5. 加法逆元:對於每一 a\in{F}, 存在唯一 (-a)\in{F} 使得 a+(-a)=0
  6. 乘法封閉性:若 a, b\in{F}, 則 ab\in{F}
  7. 乘法交換律:若 a, b\in{F}, 則 ab=ba
  8. 乘法結合律:若 a, b, c\in{F}, 則 a(bc)=(ab)c
  9. 乘法單位元:對於每一 a\in{F}, 僅存在唯一 1\in{F} 使得 a1=a
  10. 乘法逆元:對於每一 a\in{F}a\neq 0, 存在唯一 a^{-1}\in{F} 使得 aa^{-1}=1
  11. 分配律:若 a, b, c\in{F},則 a(b+c)=ab+ac

體的界定性質可以濃縮成三個公理:(1) ({F},+) 是阿貝爾群 (abelian group),(2) ({F}^{\ast},\cdot) 是阿貝爾群,其中 {F}^\ast={F}-\{0\},(3) 分配律 (阿貝爾群的定義請見“線性代數裡的代數結構”)。我們常用「數」或「純量 (標量)」來代表任一體的元素。粗淺地說,一個體是具有如「數」的加、減、乘、除運算,同時這些運算遵守上述公理。我們熟悉的複數集合 \mathbb{C}、實數集合 \mathbb{R} 和有理數集合 \mathbb{Q}=\{p/q\vert p,q\in\mathbb{Z},q\neq 0\} 都是體。如果體 {F}\mathbb{C} 的部分集合,則稱 {F} 是複數體 \mathbb{C} 的一個子體 (subfield)。譬如,實數體 \mathbb{R} 和有理數體 \mathbb{Q} 是複數體 \mathbb{C} 的子體。但正整數集合和整數集合 \mathbb{Z} 不是複數體 \mathbb{C} 的子體。此外,不難驗證形式為 x+y\sqrt{2}x,y\in\mathbb{Q},的所有數所成的集合是 \mathbb{C} 的一個子體。

 
在線性代數中,我們經常定義矩陣於實數體 \mathbb{R} 或複數體 \mathbb{C}。事實上,所有的線性代數理論適用於任一體 {F}。除了常見的複數體 \mathbb{C} 的子體,包含有限個元素的體稱為有限體 (finite field,也稱 Galois 體),其中最簡單的例子是素體 (prime field)。給定整數 m>1,任一整數可按照它除以 m 的餘數 0,1,2,\ldots,m-1 分為 m 個剩餘類。例如,若 m=6,所有的整數可分為6個子集,對應餘數 0,1,2,3,4,5。如果兩整數 ab 除以 m 的餘數相同,也就是說 a-bm 整除,則它們被歸為同一剩餘類,我們稱「ab 對於模 (modulo) m 同餘」,記為

\displaystyle  a\equiv b\pmod m

其中 \equiv 是同餘相等符號 (見“利用模算術判定可逆矩陣”)。模算術遵守下列運算法則。若 a\equiv b\pmod mc\equiv d\pmod m,則

a+c\equiv b+d\pmod m

a\cdot c\equiv b\cdot d\pmod m

例如,從 17\equiv 5\pmod 626\equiv 2\pmod 6,可得

43=17+26\equiv 5+2=7\pmod 6

442=17\cdot 26\equiv 5\cdot 2=10\pmod 6

同餘保持加法和乘法等價性質允許我們僅對模 m 的餘數執行算術運算。下例說明如何以模算術求得一算式對於模 6 的同餘類:

17\cdot 26-15\cdot 34\equiv 5\cdot 2-3\cdot 4=-2\equiv 4\pmod 6

 
\mathbb{Z}/m\mathbb{Z} 代表 m 的同餘類。譬如,若 m=6,則 \displaystyle  \mathbb{Z}/m\mathbb{Z}=\{0,1,2,3,4,5\}。模算術的加法和乘法遵守體的所有性質,但乘法逆元除外。例如,不存在整數 b 使得 2b\equiv 1\pmod 6。不過,令人意外的是,若 p 是一質數 (或稱素數),則每一非零同餘類確實存在唯一的乘法逆元。

定理:若 p 為一質數,a\in\mathbb{Z}/p\mathbb{Z}a 不可被 p 整除,則存在唯一 b\in\mathbb{Z}/p\mathbb{Z} 使得 ab\equiv 1\pmod p

任一質數 p 都具備這個特性:若 p 整除 ab,其中 a, b\in\mathbb{Z},則 p 整除 ap 整除 b。令 b=c-d,其中 c,d\in\mathbb{Z}。如果 p 不可整除 a,則 p 必整除 c-d。這個結果可以表示為

消去律:令 a,c,d 是整數且 a 不被質數 p 整除。若 ac\equiv ad\pmod p,則 c\equiv d\pmod p

下面我們利用消去律來證明。令 a 為一整數且 a\not\equiv 0\pmod p。考慮數列 1,a,a^2,\ldots,由於 \mathbb{Z}/p\mathbb{Z} 包含有限元素,故必存在 mnm<n,使得 a^m\equiv a^n\pmod p。因為 p 不可整除 a,連續使用消去律可得 1\equiv a^{n-m}\pmod p。所以,b\in\mathbb{Z}/p\mathbb{Z} 滿足 b\equiv a^{n-m-1}\pmod pa 的逆元。接著證明 a 有唯一的逆元。假設 b,b'\in\mathbb{Z}/p\mathbb{Z} 使得 ab\equiv 1\pmod pab'\equiv 1\pmod p,則 a(b-b')\equiv 0\pmod p。這說明 p 整除 b-b',但 -p+1\le b-b'\le p-1,故 b=b'

 
上述證明過程提供了一個求同餘類 a 的逆元的系統化方法。例如,設 p=13。若 a=3,則 a^2\equiv 9\pmod{13}a^3=27\equiv 1\pmod{13},故得 a^{-1}\equiv a^2=9\pmod{13}。若 a=6,則需計算至 a^{12}\equiv 1\pmod{13}。當 p 的數值不大時,不妨採用嘗試錯誤法,此例 a^{-1}=11,因為 6\cdot 11=66\equiv 1\pmod{13}

 
p 是一質數,同餘類集合 \mathbb{Z}/p\mathbb{Z} 是一個體,稱作素體,記為

\displaystyle  \mathbb{F}_p=\{0,1,2,\ldots,p-1\}=\mathbb{Z}/p\mathbb{Z}

在素體 \mathbb{F}_p,我們可以用模算術實現加法與乘法,但如何計算除法呢?為了排除這個困難,除法可以留待最後一個步驟才執行。舉例來說,考慮定義於 \mathbb{F}_p 的線性方程 A\mathbf{x}=\mathbf{b},其中 An\times n 階整數矩陣,\mathbf{b}n 維整數向量。在 \mathbb{F}_p 中,若 \det A\neq 0 (即 \det A 不被 p 整除),則 A\mathbf{x}=\mathbf{b} 有唯一解。見下例,

\displaystyle  A=\begin{bmatrix}  6&3\\  2&8  \end{bmatrix},~~~\mathbf{b}=\left[\!\!\begin{array}{r}  4\\  -1  \end{array}\!\!\right]

因為 \det A=42,如果 p 不等於 2,3 或 7,線性方程在 \mathbb{F}_p 有唯一解。若 p=13,則 \det A\equiv 3\pmod{13},先前結果指出 (\det A)^{-1}\equiv 3^{-1}\equiv 9\pmod{13}。代入逆矩陣公式,

\displaystyle  A^{-1}=(\det A)^{-1}\hbox{adj}A\equiv 9\left[\!\!\begin{array}{rr}  8&-3\\  -2&6  \end{array}\!\!\right]=\left[\!\!\begin{array}{rr}  72&-27\\  -18&54  \end{array}\!\!\right]\equiv\left[\!\!\begin{array}{rr}  7&12\\  8&2  \end{array}\!\!\right]\pmod{13}

可得

\displaystyle  \mathbf{x}=A^{-1}\mathbf{b}=\left[\!\!\begin{array}{rr}  7&12\\  8&2  \end{array}\!\!\right]\left[\!\!\begin{array}{r}  4\\  -1  \end{array}\!\!\right]=\left[\!\!\begin{array}{c}  16\\  30  \end{array}\!\!\right]\equiv\begin{bmatrix}  3\\  4  \end{bmatrix}\pmod{13}

 
有限體 {F}=\mathbb{F}_p\mathbb{C} 的子體的最主要差異在於

\displaystyle  \underbrace{1+1+\cdots+1}_{p~\text{terms}}=0

上式以等號 = 取代同餘等號 \equiv。我們稱體 {F} 的特徵數 (characteristic) 為 p,若 p 是滿足上式的最小正整數。對於 \mathbb{C} 的子體,因為不存在這樣的正整數 p,我們說特徵數等於零。任一體 {F} 的特徵數等於零或為一質數 (證明從略)。為了簡化模算術的表達,定義素體 \mathbb{F}_2=\{0,1\} 的加法和乘法運算如下表:

\begin{array}{cccc}  +&\vline& 0 & 1\\ \hline  0&\vline& 0& 1\\  1&\vline& 1& 0  \end{array}~~~~~~~~~~\begin{array}{cccc}  \cdot &\vline& 0 & 1\\ \hline  0&\vline& 0& 0\\  1&\vline& 0& 1  \end{array}

類似地,素體 \mathbb{F}_3=\{0,1,2\} 的加法和乘法運算如下:

\begin{array}{ccccc}  +&\vline& 0 & 1& 2\\ \hline  0&\vline& 0& 1 & 2\\  1&\vline& 1& 2 &0\\  2& \vline& 2&0 &1  \end{array}~~~~~~~~~~\begin{array}{ccccc}  \cdot &\vline& 0 & 1 &2\\ \hline  0&\vline& 0& 0 &0\\  1&\vline& 0& 1 &2\\  2& \vline& 0&2&1  \end{array}

雖然4不為質數,但仍可定義有限體 \mathbb{F}_4=\{0,1,\text{A},\text{B}\},按下列方式計算:

\begin{array}{cccccc}  +&\vline& 0 & 1& \text{A}& \text{B}\\ \hline  0&\vline& 0& 1 & \text{A}&\text{B}\\  1&\vline& 1& 0 &\text{B}&\text{A}\\  \text{A}& \vline& \text{A}&\text{B} &0&1\\  \text{B}& \vline&\text{B}&\text{A}&1&0  \end{array}~~~~~~~~~~\begin{array}{cccccc}  \cdot &\vline& 0 & 1 &\text{A}&\text{B}\\ \hline  0&\vline& 0& 0 &0 &0\\  1&\vline& 0& 1 &\text{A}&\text{B}\\  \text{A}& \vline& 0&\text{A}&\text{B}&1\\  \text{B}& \vline& 0& \text{B}& 1&\text{A}   \end{array}

注意,\mathbb{F}_4 並非一素體,其特徵數為 2

 
現在我們可以回答小城俱樂部的總量管制問題。如果會籍矩陣 A 定義於 \mathbb{F}_2,則 (AA^T)_{ij}=1\vert C_i\cap C_j\vert 是奇數,(AA^T)_{ij}=0\vert C_i\cap C_j\vert 是偶數。對於任一定義於 \mathbb{F}_2m\times n 階合法會籍矩陣 A,恆有 AA^T=I_m,也就是說,\hbox{rank}(AA^T)=m (這是整個論證的核心)。然而,

\displaystyle  \hbox{rank}(AA^T)\le\hbox{rank}A\le n

m\le n,證明俱樂部總數必不多於居民人口。倘若有一天市議會將法令修改為

  • 每一個俱樂部必須有偶數個會員。
  • 任兩個俱樂部必須有奇數個相同的會員。

小城的俱樂部總數仍不會多於居民人口嗎?答案是肯定的,證明工作就留給讀者自行完成。

 
來源與註解:
[1] 取自Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra,1991,頁7-8。
[2] 這裡的關聯矩陣不同於圖論的關聯矩陣,見“線性代數在圖論的應用 (二):關聯矩陣”。

Advertisements
This entry was posted in 線性代數專欄, 向量空間 and tagged , , , , , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s