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

本文的閱讀等級：中級

若一個矩陣 $A=[a_{ij}]$ 的每一元 $a_{ij}$ 為 $0$ 或 $1$ ，我們稱之為 (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]。底下介紹一個精巧的證明。

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

給定一個有向無環圖 $G=(V,E)$ ，其中 $V=\{1,2,\ldots,n\}$ 是頂點集合， $E$ 是邊集合，令 $A=[a_{ij}]$ 為 $G$ 的 $n\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}$ 。

圖二：有向無環圖例

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

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

頂點命名程序可表示為從頂點集合 $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$ 才可能存在頂點 $i$ 至 $j$ 的有向邊。此外，由於有向無環圖沒有自環 (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=1$ ， $i=1,\ldots,n$ 。由於 $\hbox{trace}B=n$ ， $B$ 的所有主對角元等於 $1$ 。令 $A=B-I$ 。明顯地， $A$ 是一個 (0,1) 矩陣，且 $A$ 的特徵值為 $\lambda_i-1=0$ ， $i=1,\ldots,n$ 。設 $A$ 是有向圖 $G$ 的鄰接矩陣。考慮冪矩陣 $A^k$ ，其中 $(A^k)_{ij}$ 代表從頂點 $i$ 至 $j$ 長度等於 $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)-Matrices，Journal Integer Sequences，Vol. 7，Article 04.3.3，頁1-5，2004。

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

等風來 says:

12/17/2015 at 3:31 pm

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

- ccjou says:
  
  12/17/2015 at 6:37 pm
  
  有向是指有向邊(directed edge)，無環是說沒有迴路(loop)。你要不要具體地描述一下無法理解的部分？
  
宇清 says:

12/20/2016 at 4:15 am

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

- ccjou says:
  
  12/20/2016 at 8:10 am
  
  Jordan block 對應有向樹的一條偏序，譬如
  
  $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}$ 的Jordan form 是
  $J=\begin{bmatrix} 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0 \end{bmatrix}$ 。
  
  - 宇清 says:
    
    12/20/2016 at 10:48 am
    
    请问老师，图的一条偏序是什么意思？
    
    - ccjou says:
      
      12/20/2016 at 12:23 pm
      
      從 $P^TAP$ 可知7個有向邊
      $1\to 2$ , $1\to 3$ , $2\to 3$ , $2\to 5$ , $3\to 4$ , $3\to 6$ , $4\to 5$ .
      
      最長的一條路徑描述一條偏序關係
      $1\to 2\to 3\to 4\to 5$
      此即最大的5×5階Jordan block。
      刪除路徑上的頂點1,2,3,4,5，再找剩下的路徑(偏序)，得到頂點6，1×1階Jordan block。
      
      你自己再舉些例子。
      
      - 宇清 says:
        
        12/20/2016 at 12:50 pm
        
        多谢老师！

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