相連矩陣的子矩陣行列式值

圖的拉普拉斯矩陣 \(L\) 可以用相鄰矩陣 \(N\) 寫成 \(L = NN\trans\) 的形式，在描述明確定義之前，我們先來看看幾個例子。我們從 \(K_2\) 的拉普拉斯矩陣開始，它可以分解為

\[ \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 1 \\ -1 \end{bmatrix} \begin{bmatrix} 1 & -1 \end{bmatrix}. \]

這邊我們會發現兩件事。第一，上述的分解可以寫成是 \(\bd\bd\trans\)，由於它是一個向量乘上自己的轉置，所以 \(\bd\) 不管選為 \((1,-1)\trans\) 或是 \((-1,1)\trans\) 都會得到同樣的結果。第二、任一個 \(m\) 條邊的圖，它的拉普拉斯矩陣都可以看成 \(m\) 個 \(K_2\) 的拉普拉斯矩陣放在不同地方疊在一起。比如說 \(K_{1,3}\) 的拉普拉斯矩陣可以寫為

\[ \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix}. \]

如果我們令

\[ \begin{aligned} \bd_1 &= (1,-1,0,0)\trans, \\ \bd_2 &= (1,0,-1,0)\trans, \\ \bd_3 &= (1,0,0,-1)\trans, \\ \end{aligned} \]

則 \(K_{1,3}\) 的拉普拉斯矩陣可以寫為 \(\bd_1\bd_1\trans + \bd_2\bd_2\trans + \bd_3\bd_3\trans\)，並進一步可以表示為矩陣相乘

\[ \begin{bmatrix} \bd_1 & \bd_2 & \bd_3 \end{bmatrix} \begin{bmatrix} \bd_1\trans \\ \bd_2\trans \\ \bd_3\trans \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 & 0 \\ 1 & 0 & -1 & 0 \\ 1 & 0 & 0 & -1 \\ \end{bmatrix}. \]

最後這兩個矩陣相乘 \(NN\trans\) 其中的 \(N\) 就被稱為 \(K_{1,3}\) 的相鄰矩陣。

我們正式定義相鄰矩陣。令 \(G\) 為一個 \(n\) 個點 \(m\) 條邊的圖，則 \(G\) 的一個 相鄰矩陣（incidence matrix） \(N\) 指的是一個 \(n\times m\) 的矩陣，其每列對應到一個點、每行對應到一條邊；將 \(G\) 的點編號為 \(1,\ldots, n\)、\(G\) 的邊編號為 \(e_1, \ldots, e_m\)，若 \(e_j = \{u,v\}\)，則定義 \(N\) 的第 \(j\) 行是

\[ (0, \ldots, 0, 1, 0, \ldots, 0, -1, 0, \ldots, 0), \]

其中 \(1\) 和 \(-1\) 分別發生在 \(u\) 和 \(v\) 的位置。由於對 \(e_j\) 來說，\(u\) 和 \(v\) 的角色可以對調，所以在點邊編號都固定的情況下，\(N\) 有 \(2^m\) 種選擇。

性質 1

令 \(G\) 為一個圖，\(L\) 為其拉普拉斯矩陣，而 \(N\) 為其中一個相鄰矩陣。則有以下性質：

\(L = NN\trans\)。
\(N\trans\bx = \bzero\) 發生時，\(\bx\) 在 \(G\) 上同一個連通區塊的值都一樣。
\(\dim(\ker(N\trans))\) 等於 \(G\) 的連通區塊的個數，其中 \(\ker(N\trans) = \{\bx: N\trans\bx = \bzero\}\)。

接下來的部份，我們想要探討相連矩陣的子矩陣行列式值。我們沿用子矩陣的一些符號，\(A[\alpha,\beta]\) 表示 \(A\) 中取出列在 \(\alpha\) 內、行在 \(\beta\) 內的子矩陣，而 \(A(\alpha,\beta)\) 表示 \(A\) 中列在 \(\alpha\) 外、行在 \(\beta\) 外的子矩陣，其它符號如 \(A(\alpha,\beta]\) 及 \(A[\alpha,\beta)\) 都以類似的方式定義。我們用符號 \(:\) 代表包含全部可能元素的宇集。若 \(\alpha = \{r\}\) 只有一個元素，則我們寫 \(A(r,\beta) = A(\{r\},\beta)\) 等等來簡化符號。

令 \(G\) 為一個圖，\(N\) 為其一相連矩陣。回顧一下，\(N\) 的列與 \(V(G)\) 相對應，而其行與 \(E(G)\) 相對應。考慮一個圖 \(G\) 其點集為 \(V = \{1,2,3,4,5\}\)，其邊集為 \(\{e_1,e_2,e_3,e_4,e_5\}\) 且 \(e_1 = \{1,3\}\), \(e_2 = \{2,3\}\), \(e_3 = \{3,4\}\), \(e_4 = \{4,5\}\), \(e_5 = \{3,5\}\)。其相鄰矩陣 \(N\) 配合點邊編號可以寫成下表，這邊相連矩陣有很多選擇，我們擇一：

\[ \begin{array}{c|ccccc} ~ & e_1 & e_2 & e_3 & e_4 & e_5 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & -1 & 0 & 0 & 0 \\ 3 & -1 & 1 & -1 & 0 & -1 \\ 4 & 0 & 0 & 1 & 1 & 0 \\ 5 & 0 & 0 & 0 & -1 & 1 \\ \end{array} \]

這裡我們發現幾件事：

由於 \(\{e_3, e_4, e_5\}\) 形成一個圈，所以這三行可以各自配上係數 \(-1,1,1\) 讓其線性組合為 \(\bzero\)，所以這三行為線性相依。
由於 \(\{e_1, e_2, e_3, e_5\}\) 形成一個樹，我們可以幫點邊重新排序並得到一個上三角矩陣。排序的方法及重排後的矩陣如下：
- 任選一點 \(r = 1\) 當開頭。
- 把 \(r\) 當作樹的根部，每次加一條邊，讓它慢慢長成我們要的樹，在這個例子裡我們可以依照 \(e_1, e_3, e_2, e_5\) 的順序。
- 依照邊生長的順序，每次也會加入一個點，所以從根 \(r = 1\) 開始，依序長出 \(3, 4, 2, 5\) 等點。

\[ \begin{array}{c|ccccc} ~ & e_1 & e_3 & e_2 & e_5 \\ \hline r = 1 & 1 & 0 & 0 & 0 \\ 3 & -1 & -1 & 1 & -1 \\ 4 & 0 & 1 & 0 & 0 \\ 2 & 0 & 0 & -1 & 0 \\ 5 & 0 & 0 & 0 & 1 \\ \end{array} \]

而這些現象在一般的狀況下也是正確的，因而矩陣 \(N(r,\beta]\) 的行列式值，依照有圈或無圈有以下兩種結果。

引理 2

令 \(G\) 為一圖、而 \(N\) 為其一相連矩陣。若 \(\beta \subseteq E(G)\) 包含一個圈，則 \(N[:,\beta]\) 的行向量線性相依。若進一步有 \(r \in V(G)\) 及 \(\vert{}\beta\vert{} = \vert{}V(G)\vert{} - 1\)，則 \(N(r,\beta]\) 是一個方陣，且 \(\det(N(r,\beta]) = 0\)。

引理 3

令 \(G\) 為一圖、而 \(N\) 為其一相連矩陣。若 \(\beta \subseteq E(G)\) 形成一個 \(V(G)\) 上的樹且 \(r \in V(G)\)，則 \(N(r,\beta]\) 可透過行重排及列重排得到一個上三角矩陣，其對角線項均為 \(\pm 1\)，因此 \(\det(N(r,\beta]) = \pm 1\)。

想想以下問題：

令 \(\bx_1, \ldots, \bx_m\in\mathbb{R}^a\) 且 \(\by_1, \ldots, \by_m\in\mathbb{R}^b\)，說明以下矩陣乘法成立，等號左右均為 \(a\times b\) 矩陣，並將其與向量內積相對照：
\[ \begin{bmatrix} \bx_1 & \cdots & \bx_m \end{bmatrix} \begin{bmatrix} \by_1\trans \\ \vdots \\ \by_m\trans \end{bmatrix} = \bx_1\by_1\trans + \cdots + \bx_m\by_m\trans. \]
證明性質 1，並與拉普拉斯矩陣性質 1 相對照。
任選一個圖，來觀察引理 2 及引理 3 的敘述。
證明引理 2。
證明引理 3。