# 藉由有向圖理解矩陣運算
> 資料整理: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv), [jouae](https://github.com/jouae)

## 圖解數學
矩陣的概念常讓人困惑，但若換個視角，或許能有不同的體會。在學習數學的過程，我們不免因其難度與抽象而感到挫折；然而，有時只要轉換思考方式，就可找到簡單且直觀的解法。

舉例來說，平方公式 (a + b + c)²
$$
(a + b + c)^2 \\
= (a + b + c) \cdot (a + b + c) = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc
$$

除了代數推導或機械地記憶上方公式，我們可藉由下圖，從幾何角度來理解這平方公式。
> [出處](https://x.com/Matematickcom/status/1828404892462924284)

> 有意思的是，這個代數問題也可以組合的角度去思考，詳見[多項式定理](https://en.wikipedia.org/wiki/Multinomial_theorem)。

## 矩陣與有向圖的等價性

前述的幾何對應，可推廣到矩陣的解讀，也就是，非負矩陣可等價地轉換成對應的有向圖，同時該非負矩陣也被稱為鄰接矩陣(adjacency matrix)。

如下圖所示，左邊的 3×3 矩陣可等價地表示為右邊包含三個節點 $v1$, $v2$, $v3$ 的有向圖。該表示法對於理解矩陣和圖論都有幫助。

本文的圖例來自數學家 [Tivadar Danka](https://x.com/TivadarDanka/status/1612415042766663680)，他致力於讓每個人都能理解數學 (make math accessible for everyone)。


如上圖所示，若我們將矩陣的每一行視為一個節點，則每個元素就可表示為一條加權的有向邊。當然，值為 0 的元素可忽略不計。若元素位於第 $i$ 行第 $j$ 列，則對應於從節點 $i$ 到節點 $j$ 的有向邊。

乍看之下，這種表示方式似乎較複雜，但我們可從單個節點開始理解。

例如，對於這個 3×3 的矩陣，第 1 行對應於圖中最頂部的節點 (稱為 1 號節點)，該節點包含 3 個元素，但其中一個為 0，因此只延伸出二條邊。黃色的邊表示矩陣中 $(1,1)$ 位置的元素 0.5，因此它是一條指向自身且權重為 0.5 的有向邊。同樣，藍色的邊則指向 2 號節點，權重為 1。

由此，我們可分析出，矩陣的第 $i$ 列對應於所有指向 $i$ 號節點的邊。

## 等價表示有何用？

非負矩陣與有向圖之間的等價性不僅能幫助我們理解矩陣及其運算，還能簡化某些計算過程；反過來說，這也讓我們能從新的角度理解圖論。

例如，矩陣的冪運算可對應到圖論中的遊走 (walk)。

如上圖所示，對於 $n \times n$ 的方形矩陣 $A$ 的 $k$ 次冪，其每個元素的求和過程都會包含所有可能的 $k$ 步遊走路徑。

假設我們要計算上述 3×3 矩陣的平方:
$$
\begin{bmatrix}
0.5 & 1 & 0 \\
0.2 & 0 & 2.2 \\
1.8 & 2 & 0
\end{bmatrix}^2
$$

利用矩陣乘法，我們需要進行如下計算：

對於結果矩陣的 $a_{11}$，我們可得到結果為 $0.5 \times 0.5 + 1 \times 0.2 + 0 \times 1.8 = 0.45$。最終該平方矩陣表示如下：
$$
\begin{bmatrix}
0.45 & 0.5 & 2.2\\
4.06 & 4.6 & 0\\
1.3 & 1.8 & 4.4
\end{bmatrix}
$$

若利用圖遊走的方法，我們可藉由計算符合 $a_{1,l} \to a_{l,1}$ 的所有 2 步遊走路徑來得到結果。這種方式特別適用於描述馬可夫鏈的狀態，當中轉移機率矩陣的平方本質上表示該鏈在 2 步之後達到某個狀態的機率。

改以另一個角度來思考矩陣乘法與圖的關係，方陣 $A \times A$ 的第一個行向量可寫成一線性組合如下：
$$
a_{11}
\begin{bmatrix}
a_{11} \\
a_{21} \\
a_{31}
\end{bmatrix}
+a_{21}
\begin{bmatrix}
a_{12} \\
a_{22} \\
a_{32}
\end{bmatrix}
+a_{31}
\begin{bmatrix}
a_{13} \\
a_{23} \\
a_{33}
\end{bmatrix}
$$

從鄰接矩陣的定義可以得知，行向量 $[a_{11}, a_{21}, a_{31}]^T$ 依照順序解釋為： $v_1$ 至 $v_1$ 的權重為 $a_{11}$；$v_2$ 至 $v_1$ 的權重為 $a_{21}$；$v_3$ 至 $v_1$ 的權重為 $a_{31}$。

則一路徑長度為 $2$ 的遊走如 $v_1v_1v_1$ 表示為 $a_{11}a_{11}$；$v_1v_2v_1$ 為 $a_{12}a_{21}$；$v_1v_3v_1$ 為 $a_{13}a_{31}$。顯而易見的將該等權重總和則表示**以 $v_1$ 為起點及 $v_1$ 為終點路徑長度為 2 的權重。**
$$
\begin{bmatrix}
a_{11}a_{11}+a_{12}a_{21}+a_{13}a_{31} \\
a_{21}a_{11}+a_{22}a_{21}+a_{23}a_{31} \\
a_{31}a_{11}+a_{32}a_{21}+a_{33}a_{31}
\end{bmatrix}
$$

則上述線性組合後行向量第一個元素代表以 $v_1$ 為起點及 $v_1$ 為終點路徑長度為 2 的權重；第二個元素代表以 $v_2$ 為起點及 $v_1$ 為終點路徑長度為 2 的權重；第三個元素代表以 $v_3$ 為起點及 $v_1$ 為終點路徑長度為 2 的權重。

矩陣結構之美，在於單單一個矩陣乘法就可計算自某一起點至另一終點的圖路徑組合。

此外，將矩陣表示為有向圖，還能讓我們深入了解非負矩陣的結構。為此，Tivadar Danka 指出，我們該先有「強連通分量」([strongly connected components](https://en.wikipedia.org/wiki/Strongly_connected_component)) 的概念。

## 強連通分量

在一個有向圖中，若能從任意一個節點到達圖中的所有其它節點，我們就說這個圖是強連通的，圖示如下：

強連通分量則是指圖中能夠實現強連通的部分或子圖。如下圖所示，左右各有一個強連通分量，而中間的白色邊不屬於任何強連通分量。

下圖則展示了另一個例子，其中黃色部分是強連通分量：

對應於強連通圖的矩陣是不可約矩陣，而非負矩陣中的所有其他矩陣都是可約矩陣 ([reducible matrix](https://planetmath.org/ReducibleMatrix))。

Tivadar Danka 藉由一個例子解釋這點：當我們將一個包含強連通分量但本身並不強連通的圖轉寫成矩陣形式時，這個矩陣就是可約的。在主對角線上的子矩陣分別表示兩個強連通分量，而其它部分則表示分量之間的連接情況。

下面將這個包含強連通分量、但本身並不強連通的圖轉寫成對應的矩陣形式：

而這個矩陣是可約矩陣。

可看到，在主對角線上的兩個子矩陣分別表示兩個強連通分量，而右上方的子矩陣表示從第 1 個強連通分量指向第 2 個強連通分量的邊，左下方的則表示從第 2 個強連通分量指向第 1 個強連通分量的邊（因為沒有這樣的邊，所以全為 0）。

這種表示矩陣的方法稱為 [Frobenius normal form](https://en.wikipedia.org/wiki/Frobenius_normal_form)。

我們可將任何非負矩陣轉換成 [Frobenius normal form](https://en.wikipedia.org/wiki/Frobenius_normal_form) 矩陣，這可藉由為非負矩陣構建對應的有向圖，然後找到其中的強連通分量，並重新標記各個節點來達成。

## 用圖來得到 [Frobenius normal form](https://en.wikipedia.org/wiki/Frobenius_normal_form)

為了說明這一過程，我們可將各個強連通分量融合成單個物件，視其為一個黑箱，然後在新圖中找到只有出邊而沒有入邊的分量，並對其進行編號。

然後，在這個新圖中，我們需要找到只有出邊而沒有入邊的分量。本例只有一個，我們將其標記為 0 號：

下一步是對每個分量進行編號，使得每個分量的編號都是離 0 號最遠的距離。

可見，0 號到中間的分量有二條路徑，那麼選擇離 0 最遠的那條路徑對其進行編號。最終得到：

這定義的是分量的順序。接下來標記各個分量的內部節點：

若該圖本身來自一個矩陣，則上述重新標註過程就能得到 [Frobenius normal form](https://en.wikipedia.org/wiki/Frobenius_normal_form) 矩陣。

這個重新標記的過程是使用一個置換矩陣 $P$ 對原矩陣進行變換，而該置換矩陣由多個轉置矩陣的積構成。

當然，用圖來表示矩陣的用途遠不止於此，例如我們尚可用矩陣的特徵值來定義圖的特徵值，而該想法催生譜圖論 ([spectral graph theory](https://en.wikipedia.org/wiki/Spectral_graph_theory)) 的發展。

## 結語

顯然，矩陣與圖之間的這種等價關係不僅能推動圖論的研究，還能為線性代數的計算和分析提供全新的視角。這種等價關係在實際應用中也極為重要，例如 DNA 資料經常以矩陣或圖的形式表示。此外，矩陣運算在大語言模型和知識圖譜極其重要。

上述內容摘自 Tivadar Danka 正在撰寫的《[Mathematics of Machine Learning](https://tivadardanka.com/mathematics-of-machine-learning-preview/)》一書。這本書將由淺入深地介紹與機器學習相關的數學知識，讓讀者真正知其然也知其所以然。