有向無環圖與 (0,1) 矩陣的特徵值

本文的閱讀等級:中級

若一個矩陣 A=[a_{ij}] 的每一元 a_{ij}01,我們稱之為 (0,1) 矩陣。2003年任職 Wolfram 研究中心的韋斯坦 (Eric W. Weisstein) 在計算 n\times n 階 (0,1) 矩陣,n=1,2,\ldots, 5,的特徵值時,發現所有特徵值皆為正實數[1]的 (0,1) 矩陣總數為下列序列:

\displaystyle 1,3,25,543,29281

在圖論中,若一個有向圖無法從某個頂點出發經過若干條邊回到該點,則稱之為有向無環圖 (directed acyclic graph,簡稱DAG)。韋斯坦得到的序列恰巧與包含 n 個標記頂點的有向無環圖數的前五項相等[2]

\displaystyle 1, 3, 25, 543, 29281, 3781503,\ldots

自然地,韋斯坦猜想這兩個數列完全相同。圖一顯示 n=3 的所有標記有向無環圖。2004年麥凱 (Brendan D. McKay) 等人證明了韋斯坦猜想:包含 n 個標記頂點的有向無環圖與特徵值皆為正實數的 n\times n(0,1) 矩陣存在一對一的關係[3]。底下介紹一個精巧的證明。

DAG

圖一:有向無環圖 (n=3)

 
給定一個有向無環圖 G=(V,E),其中 V=\{1,2,\ldots,n\} 是頂點集合,E 是邊集合,令 A=[a_{ij}]Gn\times n 階鄰接矩陣 (adjacency matrix),即 a_{ij}=1(i\to j)\in E,否則 a_{ij}=0 (見“線性代數在圖論的應用 (一):鄰接矩陣”)。例如,圖二所示有向無環圖的鄰接矩陣為

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

DAG example

圖二:有向無環圖例

有向無環圖不包含迴路 (loop),故頂點存在偏序 (partial order) 關係,以有向樹表示如下:

01矩陣1

將頂點按照偏序關係重新命名使得若 ij 存在一條路徑,則 i<j。結果如下:

01矩陣2

頂點命名程序可表示為從頂點集合 V 至自身的一對一映射,稱為排列 \pi (見“特殊矩陣 (16):排列矩陣”),表示為

\displaystyle \pi=\begin{pmatrix} 1&2&3&4&5&6\\ 4&5&2&1&6&3 \end{pmatrix}

排列 \pi 對應一個排列矩陣

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

重新命名的有向無環圖的鄰接矩陣排列相似於 A (見“矩陣視覺化”),如下:

\displaystyle P^TAP=\begin{bmatrix} 0&1&1&0&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 0&0&0&0&1&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}

新的鄰接矩陣 P^TAP 為一個上三角矩陣,因為僅當 i<j 才可能存在頂點 ij 的有向邊。此外,由於有向無環圖沒有自環 (self-loop),A 的主對角元必為零,P^TAP 的主對角元也為零,稱之為嚴格上三角矩陣。令 B=I+P^TAP。顯然,B 是一個上三角 (0,1) 矩陣且主對角元等於 1,即知 B 的特徵值全都是 1。因為相似變換不改變特徵值,任一標記有向無環圖 G 唯一決定一個特徵值為正實數的 (0,1) 矩陣 PBP^T=I+A

 
接著說明相反方向的論證。令 B=[b_{ij}] 為一個 n\times n 階 (0,1) 矩陣,且特徵值 \lambda_1,\ldots,\lambda_n 都是正實數。每一 b_{ii}\le 1 推得 \hbox{trace}B=\lambda_1+\cdots+\lambda_n\le n;又因為 (0,1) 矩陣的行列式必為整數,\det B=\lambda_1\cdots\lambda_n 是正整數 (見“特徵多項式蘊藏的訊息”)。使用算術─幾何平均值不等式,

\displaystyle 1\ge\frac{1}{n}(\lambda_1+\cdots+\lambda_n)\ge(\lambda_1\cdots\lambda_n)^{1/n}\ge 1

因此,\lambda_1,\ldots,\lambda_n 的算術平均值等於幾何平均值,表明 B 的所有特徵值皆相等,即有 \lambda_i=1i=1,\ldots,n。由於 \hbox{trace}B=nB 的所有主對角元等於 1。令 A=B-I。明顯地,A 是一個 (0,1) 矩陣,且 A 的特徵值為 \lambda_i-1=0i=1,\ldots,n。設 A 是有向圖 G 的鄰接矩陣。考慮冪矩陣 A^k,其中 (A^k)_{ij} 代表從頂點 ij 長度等於 k 的漫步數。對於任一 k\ge 1

\displaystyle \sum_{i=1}^n(A^k)_{ii}=\hbox{trace}(A^k)=\sum_{i=1}^n(\lambda_i-1)^k=0

換句話說,有向圖 G 的所有長度等於 k\ge 1 的迴路數等於 0,因此是一個無環圖。所以,任一特徵值為正實數的 (0,1) 矩陣 B 唯一決定一個標記有向無環圖 G

 
註解:
[1] 一個實矩陣的特徵值皆為正數並不表示它是正定矩陣,除非該矩陣為對稱矩陣。譬如,A=\left[\!\!\begin{array}{cr}  1&-3\\  0&1  \end{array}\!\!\right] 有重複特徵值 1, 1,但 A 是未定矩陣。設 \mathbf{x}=(1,1)^T\mathbf{y}=(0,1)^T\mathbf{x}^TA\mathbf{x}\mathbf{y}^TA\mathbf{y} 有相異的正負號。
[2] 令 a_n 表示包含 n 個標記頂點的有向無環圖數。魯賓遜 (R. W. Robinson) 在1973年提出遞迴關係式 (見維基百科:Directed acyclic graph)

\displaystyle a_n=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}2^{k(n-k)}a_{n-k},~~n\ge 1,~a_0=1

證明見 Valery A. Liskovets,More on counting acyclic digraphs,arXiv:0804.2496,2008。
[3] Brendan D. McKay 等人合著 Acyclic Digraphs and Eigenvalues of (0,1)-MatricesJournal Integer Sequences,Vol. 7,Article 04.3.3,頁1-5,2004。

This entry was posted in 線性代數專欄, 圖論, 應用之道 and tagged , , , , , , , , . Bookmark the permalink.

7 則回應給 有向無環圖與 (0,1) 矩陣的特徵值

  1. 等風來 說:

    老師我是google「有向無環圖」找到您的博客,想請教您一個問題。能通俗的講解下「有向無環圖」嗎?
    剛學jiaba 看到裡面有提到jiaba算法裡面有提到「有向無環圖」看到這個有點無法理解我也google過依然不理解,想請教下老師這個問題。

    • ccjou 說:

      有向是指有向邊(directed edge),無環是說沒有迴路(loop)。你要不要具體地描述一下無法理解的部分?

  2. 宇清 說:

    老师,「有向無環圖」的临接矩阵特征值都是0,那么它有几个以0为特征值的Jordan Block是由图的什么特征决定的呢?

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s