答Xiaoyang Su──關於歐拉多面體公式的線性代數證法

網友Xiaoyang Su留言：

請老師指點歐拉多面體公式：頂點數+面數=邊數+2，和綫性代數中的秩─零化度定理的關係是什麽？

答曰：

為方便討論，我沿用法國數學家柯西 (Augustin-Louis Cauchy) 的作法──以多面體圖 (polyhedral graph) 表示凸多面體。圖一顯示一個六面體轉換為平面表示圖的漸進過程。下面先介紹一些圖論的基本詞彙。令 $G=(V,E)$ 為一無向簡單圖 (undirected simple graph)，其中 $V=\{v_1,\ldots,v_{n_0}\}$ 是頂點集合， $E=\{e_1,\ldots,e_{n_1}\}$ 是無向邊 (以下簡稱邊) 集合。若二頂點 $v_i$ 和 $v_j$ 之間存在一連接邊 $e_k$ ，記為 $e_k=\{v_i,v_j\}$ ，我們說邊 $e_k$ 與頂點 $v_i$ 和 $v_j$ 有關聯 (incident)。無向邊不具方向性， $\{v_i,v_j\}$ 可視為兩頂點組成的集合。簡單圖是指任意二相異頂點至多僅存在一連接邊，且頂點與其自身不存在連接邊，即不存在 $\{v_i,v_i\}$ 。若一圖的任意兩頂點之間存在一序列的邊構造的連通路徑 (path)，則稱為連通圖 (connected graph)。

圖一六面體與其平面表示圖

平面圖 (planar graph) 是指可以畫在平面上且任意二相異邊不交疊的圖 (僅交於頂點)。我們另要求平面圖將平面分成互不相通的封閉區域以及圖的外部區域，圖內每一個被頂點和邊分割出來的封閉連通區域稱為內部面，圖外的區域稱為外部面。令 $F=\{f_1,\ldots,f_{n_2}\}$ 表示簡單平面圖 $G(V,E)$ 所定義出的面集合。若二面 $f_i$ 和 $f_j$ 有一共邊 $e_k$ ，則稱邊 $e_k$ 與面 $f_i$ 與 $f_j$ 有關聯。明顯地，簡單平面圖的每一個面至少與三個邊有關聯。

對應一凸多面體，多面體圖是一個無向簡單平面連通圖，其中每一頂點至少與三個邊有關聯。我們的問題是利用線性代數方法證明歐拉多面體公式 (Euler polyhedral formula)

$n_0-n_1+n_2=2$ ，

其中 $n_0$ 是頂點數， $n_1$ 是邊數， $n_2$ 是面數。

定義頂點─邊關聯矩陣 (incidence matrix) $A_1$ 為一 $n_0\times n_1$ 階矩陣，其中 $(A_1)_{ij}=1$ 若頂點 $v_i$ 與邊 $e_j$ 有關聯，否則 $(A_1)_{ij}=0$ (見“線性代數在圖論的應用 (二)：關聯矩陣”)；定義邊─面關聯矩陣 $A_2$ 為一 $n_1\times n_2$ 階矩陣，其中 $(A_2)_{ij}=1$ 若邊 $e_i$ 與面 $f_j$ 有關聯，否則 $(A_2)_{ij}=0$ 。另外定義 $1\times n_0$ 階空集合─頂點關聯矩陣 $A_0$ 與 $n_2\times 1$ 階面─圖關聯矩陣 $A_3$ ，其中每一元為 $1$ 。舉例說明，圖二顯示一個五面體的簡單平面連通圖 $G=(V,E)$ ，其中 $V=\{v_1,\ldots,v_5\}$ ， $E=\{e_1,\ldots,e_8\}$ 。令 $F=\{f_1,\ldots,f_5\}$ ，其中 $f_1,f_2,f_3,f_4$ 是內部面， $f_5$ 是外部面。圖 $G$ 的四個關聯矩陣如下所示：

$\displaystyle A_0=\bordermatrix{ ~&v_1&v_2&v_3&v_4&v_5\cr \emptyset&1&1&1&1&1\cr }$

$\displaystyle A_1=\bordermatrix{ ~& e_1 & e_2 & e_3&e_4&e_5&e_6&e_7&e_8 \cr v_1&1&1&1&1&0&0&0&0\cr v_2&1&0&0&0&1&1&0&0\cr v_3&0&1&0&0&0&1&1&0\cr v_4&0&0&1&0&0&0&1&1\cr v_5&0&0&0&1&1&0&0&1 }$

$\displaystyle A_2=\bordermatrix{ ~&f_1&f_2&f_3&f_4&f_5\cr e_1&1&0&0&1&0\cr e_2&1&1&0&0&0\cr e_3&0&1&1&0&0\cr e_4&0&0&1&1&0\cr e_5&0&0&0&1&1\cr e_6&1&0&0&0&1\cr e_7&0&1&0&0&1\cr e_8&0&0&1&0&1 }$

$\displaystyle A_3=\bordermatrix{ ~&G\cr f_1&1\cr f_2&1\cr f_3&1\cr f_4&1\cr f_5&1 }$

圖二五面體的簡單平面連通圖

若 $B$ 為一 $m\times n$ 階矩陣，秩─零度定理 (rank-nullity theorem) 給出下列等式 (見“運用輸入輸出模型活化秩─零度定理”)：

$\displaystyle \hbox{rank}B+\hbox{nullity}B=n$ ，

其中 $\text{rank}B=\dim C(B)$ 且 $\text{nullity}B=\dim N(B)$ ，這裡 $C(B)$ 表示 $B$ 的行空間^[1](column space)， $N(B)$ 表示 $B$ 的零空間 (nullspace)。稍後我們將證明簡單平面連通圖的關聯矩陣滿足 $\hbox{rank}A_{k+1}=\hbox{nullity}A_k$ ， $k=0,1,2$ 。根據秩─零度定理，

$\displaystyle \begin{aligned} \hbox{rank}A_0+\hbox{nullity}A_0&=n_0\\ -\hbox{rank}A_1-\hbox{nullity}A_1&=-n_1\\ \hbox{rank}A_2+\hbox{nullilty}A_2&=n_2\\ -\hbox{rank}A_3-\hbox{nullity}A_3&=-1. \end{aligned}$

加總上式可得 $\hbox{rank}A_0-\hbox{nullity}A_3=n_0-n_1+n_2-1$ 。明顯地， $\hbox{rank}A_0=1$ 且 $\hbox{nullity}A_3=0$ ，即證得 $n_0-n_1+n_2=2$ 。

關聯矩陣 $A_k$ ， $k=0,1,2,3$ ，為 (0,1) 矩陣，定義於一素體 (素域，prime field) $\mathbb{F}_2=\{0,1\}$ ，加法和乘法運算如下表 (見“有限體與模算術”)：

$\displaystyle \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}$

關聯矩陣的大小使得 $A_kA_{k+1}$ 定義良好， $k=0,1,2$ 。上例中， $A_0A_1$ 的 $(1,1)$ 元計算如下：

$\displaystyle\begin{aligned} (A_0A_1)_{11}&=1\cdot 1+1\cdot 1+1\cdot 0+1\cdot 0+1\cdot 0\\ &=1+1+0+0+0\\ &=0, \end{aligned}$

或用模算術實現 $\mathbb{F}_2$ 的加法與乘法：

$\displaystyle (A_0A_1)_{11}=2\equiv 0\pmod{2}$ 。

按照這個計算方式，可得

$\displaystyle\begin{aligned} A_0A_1&=\begin{pmatrix} 2&2&2&2&2&2&2&2 \end{pmatrix}\equiv 0\pmod{2}\\ A_1A_2&=\begin{pmatrix} 2&2&2&2&0\\ 2&0&0&2&2\\ 2&2&0&0&2\\ 0&2&2&0&2\\ 0&0&2&2&2 \end{pmatrix}\equiv 0\pmod{2}\\ A_2A_3&=\begin{pmatrix} 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2 \end{pmatrix}\equiv 0\pmod{2}. \end{aligned}$

往下閱讀前，讀者不妨花幾分鐘計算驗證這個奇特的結果。

觀察圖二的簡單平面圖可發現頂點─邊關聯矩陣 $A_1$ 和邊─面關聯矩陣 $A_2$ 具有下列性質：

每一邊與兩個頂點有關聯， $A_1$ 的每一行 (column) 有兩個 $1$ 。
每一邊與兩個面有關聯， $A_2$ 的每一列 (row) 有兩個 $1$ 。

使用這兩個性質可證明 $C(A_{k+1})=N(A_k)$ ， $k=0,1,2$ ，就有 $\hbox{rank}A_{k+1}=\hbox{nullity}A_k$ 。我們先證明 $C(A_{k+1})\subseteq N(A_k)$ ，這個子空間包容關係等價於 $A_kA_{k+1}=0$ 。分開三種情況討論：

$k=0$ ：性質1指出 $A_1$ 的每一行有兩個 $1$ ，立得 $A_0A_1=0$ 。

$k=1$ ：對於 $1\le i\le n_0$ ， $1\le j\le n_2$ ， $(A_1A_2)_{ij}=\sum_{k=1}^{n_1}(A_1)_{ik}(A_2)_{kj}$ 代表頂點 $v_i$ 透過邊 $e_k$ 與面 $f_j$ 發生關聯總數的奇偶性 ( $1$ 表示奇數， $0$ 表示偶數)。簡單平面圖的每一個面 $f_j$ 對應一條由關聯頂點 (與兩個關聯邊有關聯的頂點) 形成的迴路 (loop)，以 $L(f_j)$ 表示迴路的頂點集。上例中， $L(f_1)=\{v_1,v_2,v_3\}$ 。若 $v_i\in L(f_j)$ ，性質1和迴路的閉合性表明存在兩個邊同時與頂點 $v_i$ 和面 $f_j$ 有關聯，因此 $(A_1A_2)_{ij}=1\cdot 1+1\cdot 1=2\equiv 0\pmod{2}$ 。若 $v_i\notin L(f_j)$ ，則不存在同時與頂點 $v_i$ 和面 $f_j$ 相關聯的邊，故得 $(A_1A_2)_{ij}=0$ 。

$k=2$ ：性質2指出 $A_2$ 的每一列有兩個 $1$ ，立得 $A_2A_3=0$ 。

接著證明 $N(A_k)\subseteq C(A_{k+1})$ ， $k=0,1,2$ 。同樣分開三種情況討論：

$k=0$ ：對應一頂點子集 $S\subseteq V$ ，頂點標記向量 $\mathbf{x}=(x_1,\ldots,x_{n_0})\in\mathbb{F}_2^{n_0}$ 定義為 $x_i=1$ 若 $v_i\in S$ ， $x_i=0$ 若 $v_i\notin S$ 。假設 $A_0\mathbf{x}=\mathbf{0}$ ，即 $\mathbf{x}$ 有 $2m$ 個元為 $1$ 。將標記向量 $\mathbf{x}$ 對應的頂點子集 $S$ 包含的 $2m$ 個頂點分成 $m$ 組頂點對。對於一連通圖，任意兩頂點 $v_i$ 與 $v_j$ 之間存在連通路徑。上例中， $v_2$ 與 $v_4$ 的連通路徑之一如下：

$v_2\xrightarrow[]{~e_5~}v_5\xrightarrow[]{~~e_8~}v_4$

據此，頂點對 (並非一邊) $\{v_2,v_4\}$ 的標記向量 $(0,1,0,1,0)$ 可表示為頂點─邊關聯矩陣 $A_1$ 中 $e_5$ 與 $e_8$ 的行向量和：

$\displaystyle \begin{pmatrix} 0\\ 1\\ 0\\ 1\\ 0 \end{pmatrix}=\bordermatrix{ &e_5\cr &0\cr &1\cr &0\cr &0\cr &1 }+\bordermatrix{ &e_8\cr &0\cr &0\cr &0\cr &1\cr &1 }$ 。

因為每一頂點對的標記向量屬於 $C(A_1)$ ，且 $\mathbf{x}$ 等於 $m$ 個標記向量和，推得 $\mathbf{x}\in C(A_1)$ 。

$k=1$ ：同前，標記向量 $\mathbf{y}=(y_1,\ldots,y_{n_1})\in\mathbb{F}_2^{n_1}$ 對應一邊子集 $T\subseteq E$ 。假設 $A_1\mathbf{y}=\mathbf{0}$ ，即 $\mathbf{y}$ 對應的邊子集 $T$ 與每一頂點的關聯次數和為偶數，表示 $T$ 所含的邊形成一個閉合迴路。我們可以用 $T$ 的邊構造出一個或數個簡單迴路 (對應一個面的迴路)。上例中，若 $T=\{e_1,e_3,e_6,e_7\}$ ，則 $T$ 可組成兩個簡單迴路其關聯邊為 $\{e_1,e_2,e_6\}$ 和 $\{e_2,e_3,e_7\}$ ，分別對應面 $f_1$ 和 $f_2$ 。換句話說， $T$ 的標記向量 $\mathbf{y}=(1,0,1,0,0,1,1,0)$ 可表示為邊─面關聯矩陣 $A_2$ 中 $f_1$ 與 $f_2$ 的行向量和：

$\displaystyle \begin{pmatrix} 1\\ 0\\ 1\\ 0\\ 0\\ 1\\ 1\\ 0 \end{pmatrix}=\bordermatrix{ &f_1\cr &1\cr &1\cr &0\cr &0\cr &0\cr &1\cr &0\cr &0 }+\bordermatrix{ &f_2\cr &0\cr &1\cr &1\cr &0\cr &0\cr &0\cr &1\cr &0 }$ ，

故證明 $\mathbf{y}\in C(A_2)$ 。

$k=2$ ：假設 $A_2\mathbf{z}=\mathbf{0}$ ， $\mathbf{z}=(z_1,\ldots,z_{n_2})\in\mathbb{F}_2^{n_2}$ 。使用反證法。設面子集 $U\subset F$ ( $U$ 是 $F$ 的真子集) 對應標記向量 $\mathbf{z}$ 。令 $U^c=F\setminus U$ ， $U^c\neq\emptyset$ 。在簡單平面連通圖上，任意兩相異面必定存在一條穿越邊的路徑 (避免穿越頂點)，故至少有一個邊 $e_k$ 同時與 $f_i\in U$ 和 $f_j\in U^c$ 有關聯。換句話說， $(A_2)_{ki}=(A_2)_{kj}=1$ 且 $(A_2)_{kp}=0$ ， $p\neq i$ ， $p\neq j$ 。但 $z_i=1$ 且 $z_j=0$ ，可知 $(A_2\mathbf{z})_{k}=1$ ，故 $A_2\mathbf{z}\neq\mathbf{0}$ ，得到一個矛盾，證得 $U=F$ ，即 $\mathbf{z}=(1,\ldots,1)\in C(A_3)$ 。直白地說，所有的面疊加在一起才能把每一個邊數兩遍。

歐拉 (多面體) 公式並不僅適用於凸多面體 (多面體圖)。從我們的證明過程只使用頂點─邊關聯矩陣 $A_1$ 和邊─面關聯矩陣 $A_2$ 的兩個基本性質即可確認：對於任一簡單平面連通圖 (移除每一頂點至少與三個邊有關聯的條件)，歐拉公式依然成立。圖三所示的平面圖有 $7$ 個頂點， $13$ 個邊， $8$ 個面，歐拉公式給出 $7-13+8=2$ 。另外，我們還得到下列結果：一簡單平面連通圖的頂點─邊關聯矩陣 $A_1$ 滿足 $\hbox{rank}A_1=\hbox{nullity}A_0=n_0-\hbox{rank}A_0=n_0-1$ ，邊─面關聯關聯矩陣 $A_2$ 滿足 $\hbox{rank}A_2=n_2-\hbox{nullity}A_2=n_2-\hbox{rank}A_3=n_2-1$ 。

圖三一簡單平面連通圖

註解
[1] 在台灣，橫向稱為列，縱向稱為行。在中國大陸，橫向稱為行，縱向稱為列。

4 Responses to 答Xiaoyang Su──關於歐拉多面體公式的線性代數證法

Xiaoyang Su says:

08/24/2015 at 10:26 pm

謝謝老師的指點！非常精彩！

Xiaoyang Su says:

08/27/2015 at 1:37 am

我的理解如下：

首先要說的是，所有的矩陣、秩和零化度都是在F2内討論的。譬如A1，通常我們會認爲Rank為5，但在F2裏Rank是4。

證明的核心部分在於前一個關聯矩陣的零空間等於后一個矩陣的列空間，爲此分了兩部分進行證明，即列空間屬於零空間，以及零空間屬於列空間。

用白話文描述證明的后半部分的是這樣的幾個性質：
一條邊上有兩個頂點，一個頂點通過兩條邊存在于一個面上，一條邊屬於兩個面。這三條説明了后一個矩陣的列空間是前一個的零空間。
任意兩個頂點可以由邊相連，邊的閉合回路存在于一個或幾個面上，所有的面加在一起才能把所有的邊數兩遍。這三條説明了前一個矩陣的零空間是后一個矩陣的列空間。

- ccjou says:
  
  08/27/2015 at 5:02 am
  
  這個證明其實並不困難，麻煩的是要如何將它說清楚。數學是一種語言，過於依賴記號與符號反而容易忽略說明，成了難懂的文言文。我將「邊的閉合回路存在于一個或幾個面上，所有的面加在一起才能把所有的邊數兩遍」增添上去，讓原證明更有可讀性。
  
  我在推演這個證明時，心想：你是怎麼知道歐拉公式與秩─零化度定理有關係？
  
  - Xiaoyang Su says:
    
    08/27/2015 at 9:45 am
    
    我一直认为秩-零化度定理是显而易见的事实，直到在Wikipedia上看到它的推广是Atiyah–Singer index theorem，方才知道这个定理来头不小。某次和一个数学系的朋友谈及此事，他说Euler characteristic和index有很深的联系，于是我就想到兴许秩─零化度定理可以用来证明欧拉多面体公式。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨