爲什麼學線代時不知道：矩陣與圖竟然存在等價關係

機器之心報道

編輯：佳琪

在學習數學時，我們常因所學知識的難度和抽象而受挫；但有些時候，只需換個角度，我們就能爲問題的解答找到一個簡單又直觀的解法。舉個例子，小時候在學習和的平方 (a+b)² 公式時，我們可能並不理解爲什麼它等於 a²+2ab+b²，只知道書上這麼寫，老師讓這麼記；直到某天我們看見了這張動圖：

登時恍然大悟，原來我們可以從幾何角度來理解它！

現在，這種恍然大悟之感又出現了：非負矩陣可以等價地轉換成對應的有向圖！

如下圖所示，左側的 3×3 矩陣其實可以等價地表示成右側的包含三個節點的有向圖，並且這種表示方式對矩陣和圖論都大有幫助。

這個例子來自致力於讓每個人都能看懂數學（make math accessible for everyone）的數學家 Tivadar Danka。這位自稱「混亂善良（Chaotic good）」的數學家通過一系列推文和博客文章生動地介紹了矩陣和圖的這種等價性及其用途。截至目前，這些推文已被閱讀了超過 200 萬次，收穫了超過 3200 次轉發和 9100 次收藏。

矩陣與有向圖的對價性

如上圖的例子所示，如果我們將其中每一行都視爲一個節點，則每一個元素都可表示成一條有向且加權的邊。當然，0 元素可以忽略不計。如果該元素位於第 i 行第 j 列，則對應於從節點 i 到節點 j 邊。

乍一看，這似乎很複雜，但我們可以先看其中一個節點。

如圖所示，對於這個 3×3 的矩陣，第 1 行對應於最頂部的節點（我們這裡稱之爲 1 號節點），其包含 3 個元素但其中一個爲 0，因此該節點延伸出了兩條邊。其中黃色邊表示的是 (1,1) 處的元素 0.5，因此它是指向自身且權重爲 0.5 的有向邊。同理，藍色邊是指向 2 號節點且權重爲 1 的邊。

這樣一來，我們便能分析出，矩陣的第 i 列便對應於指向 i 號節點的所有邊。

這種等價表示有什麼用？

非負矩陣與有向圖之間的這種等價性既能幫助我們更好地理解矩陣及其運算，也能幫助簡化一些計算過程；反過來，這也能幫助我們從新的視角理解圖。

舉個例子，矩陣的冪就對應於圖中的遊走。

如上圖所示，對於 n×n 的方形矩陣 A 的 k 次冪，其中每個元素的求和過程都會納入所有可能的 k 步遊走。

舉個例子，假設我們要計算上述 3×3 矩陣的平方。

如果使用矩陣乘法，則我們需要這樣計算：

對於運算結果的第一個元素，我們可以得到結果 = 0.5×0.5+1×0.2+0×1.8 = 0.45。最終，我們可以得到完整的結果爲：

但如果藉助上述的圖遊走方法，則可以通過遊走路徑來得到結果。同樣，對於結果矩陣的第一個元素，就需要對符合 a_{1,l}→a_{l,1} 的所有 2 步遊走路徑求和。

但是，如果這個有向圖表示的是馬爾科夫鏈的狀態，其轉移概率矩陣的平方本質上就表示該鏈 2 步之後達到某個狀態的概率。

不僅如此，用圖表示矩陣還能讓我們深入瞭解非負矩陣的結構。爲此，Danka 表示我們需要先了解「強連通分量（strongly connected components）」這一概念。

強連通分量

什麼是強連通分量？對於一個有向圖，如果能從該圖中的每個節點到達其它每個節點時，我們就說該圖是強連通的。如下圖所示。

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

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

對應於強連通圖的矩陣是不可約矩陣，而非負矩陣中的所有其它矩陣都是可約矩陣。

Danka 通過一個例子給出瞭解釋。（爲了說明簡單，例子中的所有權重均爲單元權重，但實踐中這些權重值可以是任意非負值。）

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

而這個矩陣是可約矩陣。

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

這種書寫分塊矩陣的形式被稱爲弗羅貝尼烏斯標準形（Frobenius normal form）。

那麼，我們很自然就會問：我們能將任意非負矩陣都轉換成弗羅貝尼烏斯標準形矩陣嗎？

通過使用有向圖來表示非負矩陣，我們可以輕鬆地看出答案是肯定的，因爲任何表示非負矩陣的有向圖都可以表示成互相連接的強連通分量。這個過程非常簡單：

如此便大功告成了！

用圖來得到弗羅貝尼烏斯標準形

那麼，這個更好的方式是什麼呢？

以上述的例子爲基礎，我們來看看這個過程。

首先，將各個強連通分量融合成單個對象，如下圖所示。這時候我們可以將每個強連通分量視爲一個黑箱 —— 我們不關心其內部結構，只看其外部連接。

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

接下來一步較爲麻煩：對每個分量進行編號，使得每個分量的編號都是離 0 號最遠的距離。如下示例能更清晰地說明這一點：

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

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

如果該圖本身來自一個矩陣，則這樣的重新標註過程就能得到一個弗羅貝尼烏斯標準形矩陣！

實際上，這個重新標註的過程就是使用一個置換矩陣 P 對原矩陣執行變換，而該置換矩陣由多個轉置矩陣的積構成。

以下爲該定理的完整形式：

當然，用圖表示矩陣的用途遠不止於此，比如我們還可以使用矩陣的特徵值來定義圖的特徵值。事實上，這一思路催生了譜圖理論（spectral graph theory）這一研究領域。

結語

很顯然，矩陣和圖之間的這種等價關係既有助於圖論研究，也能爲線性代數的計算和分析提供一個新視角。其也有一些重要的實際用途，比如 DNA 數據就常被表示成矩陣或圖的形式。

另外，我們都知道矩陣運算對於當前的大模型 AI 的重要性，而以知識圖譜爲代表的圖也正通過檢索增強式搜索等技術成爲當前 AI 的重要助力。將這兩者關聯起來，或許能在 AI 可解釋性以及圖人工智能方面帶來一些新的突破。至少，這能幫助我們更好地學習線性代數。

實際上，上述內容正是提煉自 Tivadar Danka 正在編寫的《Mathematics of Machine Learning》一書。這本書將由淺入深地介紹與機器學習相關的數學知識，讓讀者真正知其然也知其所以然，並且 Danka 自信地宣稱這會是「學習機器學習的最佳資源」。目前他已經在網上發佈了兩章預覽，感興趣的讀者可訪問：https://tivadardanka.com/mathematics-of-machine-learning-preview/