特殊矩陣 (20)：可約矩陣

Posted on 09/05/2013 by ccjou

本文的閱讀等級：中級

令 $A$ 為一 $n\times n$ 階矩陣。如果存在一排列矩陣 (permutation matrix) $P$ 使得

$\displaystyle P^TAP=\begin{bmatrix} B&C\\ 0&D \end{bmatrix}$ ，

其中 $B$ 是 $r\times r$ 階， $r\ge 1$ ， $D$ 是 $(n-r)\times(n-r)$ 階，我們稱 $A$ 為可約矩陣 (reducible matrix)，否則稱之為不可約矩陣 (irreducible matrix)。排列矩陣滿足 $P^T=P^{-1}$ ，可知 $A$ 相似於 $P^TAP$ 。因為 $P$ 以相同方式交換 $A$ 的行與列， $P^TAP$ 也稱為 $A$ 的一個對稱排列 (symmetric permutation)。設想 $A$ 的 $(i,j)$ 元代表變數 $i$ 與變數 $j$ 的關聯性，對稱排列 $P^TAP$ 的作用即在重新命名變數 (見“矩陣視覺化”)。可約矩陣的名稱由來係因其對稱排列具有分塊上三角形式，使得線性方程的求解工作變得較為簡單。若 $\mathbf{x}$ 和 $\mathbf{b}$ 以分塊表示為 $\mathbf{x}=\begin{bmatrix} \mathbf{x}_1\\ \mathbf{x}_2 \end{bmatrix}$ 和 $\mathbf{b}=\begin{bmatrix} \mathbf{b}_1\\ \mathbf{b}_2 \end{bmatrix}$ ，則 $P^TAP\mathbf{x}=\mathbf{b}$ 可化約為兩個較小型的子系統：

$\displaystyle\begin{aligned} B\mathbf{x}_1+C\mathbf{x}_2&=\mathbf{b}_1\\ D\mathbf{x}_2&=\mathbf{b}_2 .\end{aligned}$

當線性方程是一致時，採用反向代回法，先從 $D\mathbf{x}_2=\mathbf{b}_2$ 解出 $\mathbf{x}_2$ ，再代回 $B\mathbf{x}_1=\mathbf{b}_1-C\mathbf{x}_2$ 解出 $\mathbf{x}_1$ (計算量分析見^[1])。下面我們介紹矩陣可約性在圖論的表現，以及一個簡易的可約矩陣判定法。

給定一有向圖 (directed graph)，我們可以建構一個與之對應的鄰接矩陣 (adjacency matrix，見“線性代數在圖論的應用 (一)：鄰接矩陣”)。相反的，一 $n\times n$ 階矩陣 $A=[a_{ij}]$ 也有相應的有向圖，記為 $\Gamma(A)=(V,E)$ ，其中 $V=\{v_1,\ldots,v_n\}$ 是頂點集合， $E$ 是邊集合，定義如下：若 $a_{ij}\neq 0$ ，則存在從 $v_i$ 至 $v_j$ 的有向邊。換句話說，方陣 $A$ 可以視為有向圖 $\Gamma(A)$ 的加權鄰接矩陣 (一般鄰接矩陣的非零元必為 $1$ )。圖一顯示一 $3\times 3$ 階矩陣與其有向圖。

圖一：一矩陣與其有向圖

若 $M=P^TAP$ ，其中 $P$ 是一排列矩陣，則 $\Gamma(A)$ 和 $\Gamma(M)$ 有相同的結構，除了 $\Gamma(M)$ 的頂點按照 $P$ 排列命名。排列矩陣 $P$ 是排列 $\pi$ 的等價表達 (見“特殊矩陣 (16)：排列矩陣”)。給定一排列

$\displaystyle \pi=\left(\begin{array}{cccc} 1&2&\cdots&n\\ \pi(1)&\pi(2)&\cdots&\pi(n) \end{array}\right)$ ，

傳統上我們以列排序設定 $n\times n$ 階排列矩陣

$P=\begin{bmatrix} \mathbf{e}_{\pi(1)}^T\\ \mathbf{e}_{\pi(2)}^T\\ \vdots\\ \mathbf{e}_{\pi(n)}^T \end{bmatrix}$ 。

若 $\pi(i)=k$ ，則 $P$ 的第 $i$ 列即為標準單位向量 $\mathbf{e}_k$ 的轉置 ( $\mathbf{e}_k$ 的第 $k$ 元為 $1$ ，其餘各元為 $0$ )。使用 $P^T=P^{-1}$ 推知 $A=PMP^T$ ，乘開可得

$\displaystyle\begin{aligned} a_{ij}&=\left(PMP^T\right)_{ij}=\left(\begin{bmatrix} \mathbf{e}_{\pi(1)}^T\\ \vdots\\ \mathbf{e}_{\pi(n)}^T \end{bmatrix}M\begin{bmatrix} \mathbf{e}_{\pi(1)}&\cdots&\mathbf{e}_{\pi(n)} \end{bmatrix}\right)_{ij}\\ &=\mathbf{e}_{\pi(i)}^TM\mathbf{e}_{\pi(j)}=m_{\pi(i),\pi(j)}.\end{aligned}$

因為 $\pi$ 是一對一映射，上式表明 $\Gamma(A)$ 等同 $\Gamma(M)$ ，兩者的差異僅在於 $\Gamma(A)$ 的頂點 $v_i$ 對應 $\Gamma(M)$ 的頂點 $v_{\pi(i)}$ ， $i=1,\ldots,n$ 。

如果一有向圖的任兩頂點之間存在有向路徑 (連通兩頂點的一序列的有向邊)，則稱之為強連通 (strongly connected)。在圖一的例子中， $v_1$ 無法連通至 $v_2$ ， $\Gamma(A)$ 不是強連通。下面的定理說明一個重要的性質：矩陣可約性等價於非強連通。

定理一：若 $A$ 是一可約矩陣，則 $\Gamma(A)$ 不是強連通圖。反之，若 $A$ 是不可約矩陣，則 $\Gamma(A)$ 是強連通圖。

$(\Rightarrow)$ ：假設存在一排列矩陣 $P$ 使得 $M=P^TAP=\begin{bmatrix} B&C\\ 0&D \end{bmatrix}$ ，其中 $B$ 是 $r\times r$ 階， $D$ 是 $(n-r)\times(n-r)$ 階。分塊上三角矩陣 $M$ 的零分塊表示 $\Gamma(M)$ 不存在連通頂點集 $V_2=\{v_{r+1},v_{r+2},\ldots,v_n\}$ 至 $V_1=\{v_1,v_2,\ldots,v_{r}\}$ 的有向邊 (見圖二)。由於 $V_1$ 和 $V_2$ 不交集，可知 $\Gamma(M)$ 並非強連通，譬如，不存在 $v_{r+1}$ 至 $v_1$ 的有向路徑。因為 $\Gamma(A)$ 和 $\Gamma(M)$ 有相同的結構，故推論 $\Gamma(A)$ 也不是強連通。

圖二：可約矩陣的有向圖

$(\Leftarrow)$ ：我們證明：若 $\Gamma(A)$ 不是強連通，則 $A$ 是可約矩陣。假設 $\Gamma(A)$ 不是強連通， $v_i$ 不連通 $v_j$ ， $j\neq i$ ，即不存在 $v_i$ 至 $v_j$ 的有向路徑。將兩頂點重新命名， $\pi(i)=n$ 且 $\pi(j)=1$ 。為避免混淆，我們以 $u$ 代表新頂點。如果還有 $u_n$ (即 $v_i$ ) 無法連通的頂點 ( $u_n$ 自己除外)，將它們命名為 $u_2,u_3,\ldots,u_r$ 。令 $S=\{u_1,u_2,\ldots,u_r\}$ 表示 $u_n$ 的不可連通集， $T=\{u_{r+1},u_{r+2},\ldots,u_{n-1}\}$ 表示 $u_n$ 的可連通集。值得注意的是，不存在從頂點集 $T\cup\{u_n\}$ 至 $S$ 的有向邊，否則 $u_n$ 將可透過 $T$ 連通 $S$ 。換句話說，若 $\pi$ 是上述命名程序產生的排列，則 $\pi(i)\in\{r+1,r+2,\ldots,n\}$ 且 $\pi(j)\in\{1,2,\ldots,r\}$ 可推得 $a_{ij}=0$ 。考慮 $M=P^TAP$ ，其中 $P$ 是對應 $\pi$ 的排列矩陣。因為 $a_{ij}=m_{\pi(i),\pi(j)}$ ， $M=P^TAP$ 為一分塊上三角矩陣 $M=\begin{bmatrix} B&C\\ 0&D \end{bmatrix}$ ，其中 $0$ 是 $(n-r)\times r$ 階。

我們用圖一的例子來說明。觀察發現 $v_1$ 不能連通至 $v_2$ ，設定 $\pi(1)=3$ 且 $\pi(2)=1$ 。因為 $u_3$ 不存在其他的不可連通頂點，設 $\pi(3)=2$ ，於是得到 $S=\{u_1\}$ 且 $T=\{u_2\}$ 。對應排列 $\pi=\left(\begin{array}{ccc} 1&2&3\\ 3&1&2 \end{array}\right)$ 的排列矩陣是 $P=\begin{bmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}$ ，代入計算可得

$\displaystyle P^TAP=\left[\!\!\begin{array}{ccrr} 3&\vline&1&-1\\ \hline 0&\vline&0&5\\ 0&\vline&-4&2 \end{array}\!\!\right]$ 。

給定一方陣 $A$ ，如何判斷 $A$ 是否為可約矩陣，或者說，有向圖 $\Gamma(A)$ 是否非強連通？下面我介紹一個簡單的算法。對於 $n\times n$ 階實矩陣 $A=[a_{ij}]$ ，若每一 $a_{ij}>0$ ，我們稱 $A$ 是正矩陣 (positive matrix)，記為 $A>0$ (見“特殊矩陣 (18)：正矩陣”)。若每一 $a_{ij}\ge 0$ ，則稱之為非負矩陣 (nonnegative matrix)，記為 $A\ge 0$ 。對於實矩陣 $A$ ，令 $\vert A\vert$ 表示絕對值矩陣 (這裡 $\vert A\vert$ 不代表行列式)，即 $(\vert A\vert)_{ij}=\vert a_{ij}\vert$ 。明顯地， $\vert A\vert\ge 0$ 。

定理二：若 $A$ 是 $n\times n$ 階不可約矩陣，則 $(I+\vert A\vert)^{n-1}>0$ 。反之亦然。

根據二項式定理，

$\displaystyle \left((I+\vert A\vert)^{n-1}\right)_{ij}=\left(\sum_{k=0}^{n-1}\binom{n-1}{k}\vert A\vert^k\right)_{ij}=\sum_{k=0}^{n-1}\binom{n-1}{k}\left(\vert A\vert\right)^k_{ij}$ 。

我們要證明：若 $A$ 是不可約矩陣，則每一 $(i,j)$ 皆有 $0\le k\le n-1$ 使得 $\left(\vert A\vert^k\right)_{ij}>0$ 。寫出

$\displaystyle \left(\vert A\vert^k\right)_{ij}=\sum_{q_1,\ldots,q_{k-1}}\vert a_{iq_1}\vert\vert a_{q_1q_2}\vert\cdots\vert a_{q_{k-1}j}\vert$ 。

若存在指標序列 $q_1,q_2,\ldots,q_{k-1}$ 使得 $a_{iq_1}, a_{q_1q_2},\ldots,a_{q_{k-1}j}$ 全部不等於零，則 $\left(\vert A\vert^k\right)_{ij}>0$ 。換句話說，如果頂點 $v_i$ 至 $v_j$ 可連通，即存在長度等於 $k$ ( $0\le k<n$ ) 的有向路徑

$\displaystyle v_i\to v_{q_1}\to v_{q_2}\to\cdots\to v_{q_{k-1}}\to v_j$ ，

必然有 $\left(\vert A\vert^k\right)_{ij}>0$ 。根據定理一， $A$ 是不可約矩陣等價於 $\Gamma(A)$ 是強連通圖，即任兩頂點均可連通，故證明 $(I+\vert A\vert)^{n-1}$ 是正矩陣。相反方向的論述也成立。

最後我們以圖一的例子展示可約矩陣的判定過程：

$\displaystyle \vert A\vert=\begin{bmatrix} 2&0&4\\ 1&3&1\\ 5&0&0 \end{bmatrix},~~~(I+\vert A\vert)^2=\left[\!\!\begin{array}{rrr} 29&0&16\\ 12&16&9\\ 20&0&21 \end{array}\!\!\right]$ 。

因為 $(I+\vert A\vert)^2$ 包含零元，故不為正矩陣，推知 $\Gamma(A)$ 不是強連通，也就是說， $A$ 是可約矩陣。

註解：
[1] 設 $A=\begin{bmatrix} B&C\\ 0&D \end{bmatrix}$ 為一 $n\times n$ 階矩陣，其中 $B, C, D$ 都是 $n/2$ 階方陣。利用高斯消去法解 $A\mathbf{x}=\mathbf{b}$ 需要 $n^3/3$ 個乘法運算，可約系統 $D\mathbf{x}_2=\mathbf{b}_2$ 和 $B\mathbf{x}_1=\mathbf{b}_1-C\mathbf{x}_2$ 則耗用了 $n^3/12+n^2/4$ 個乘法運算。

This entry was posted in 特殊矩陣, 線性代數專欄 and tagged 特殊矩陣, 鄰接矩陣, 可約矩陣, 圖論, 強連通, 有向圖, 不可約矩陣. Bookmark the permalink.

12 Responses to 特殊矩陣 (20)：可約矩陣

張盛東 says:

11/05/2013 at 11:36 am

周老師，請問一下這裡關於矩陣的可約性是否和Markov Chain中的可約性是一回事？

Reply
- ccjou says:
  
  11/05/2013 at 11:41 am
  
  對，可約矩陣和permutation matrix，以及doubly stochastic matrix有關，改天再介紹。
  
  Reply
  - 張盛東 says:
    
    11/13/2013 at 9:13 am
    
    老師，不好意思，我還有一個問題。Markov Chain還有一個性質就是週期性。如果是離散Markov Chain，是否有定理檢測Markov矩陣的週期性？
    
    Reply
    - ccjou says:
      
      11/13/2013 at 9:47 am
      
      你最近在學Markov chain是吧？改日我再解釋來龍去脈，這裡長話短說。
      Nonnegative (如Markov matrix) irreducible matrices 可以分為兩大類：
      (1) Primitive matrix：若僅有一個特徵值位在spectral circle，即 $\lambda=\rho(A)=\max_{\mu\in\sigma(A)}\vert\mu\vert$ ，這裡 $\sigma(A)$ 是spectrum。
      (2) Imprimitive matrix：若存在 $r>1$ 個特徵值位在spectral circle。
      
      事實：設P為Markov chain的transition matrix。
      P是Imprimitive=>Irreducible Markov chain有週期性
      P是Primitive=>Irreducible Markov chain無週期性
      
      檢測：
      (1) 若 $P$ 是imprimitive，則 $\hbox{trace}(P)=0$ 。即若 $P$ 的一主對角元是正數，則 $P$ 是primitive。
      (2) Frobenius’s test
      $P$ 是primitive iff $P^k>0$ 存在某個 $k>0$ 。這裡 $P^k>0$ 表示 $P^k$ 是正矩陣，即所有元都是正數。舉例來說，
      $P=\begin{bmatrix} 0&1&0\\ 1/2&0&1/2\\ 0&1&0 \end{bmatrix}$ 的週期是2。計算可知不存在 $k>0$ 使得 $P^k>0$ ，故 $P$ 是imprimitive矩陣。
      
      Reply
      - 張盛東 says:
        
        11/13/2013 at 10:08 am
        
        謝謝老師答疑。
        其實我最近在上Information Theory，教科書的第二章提到Stochastic Process的熵，令我想起這兩個在我心中一直存在的疑問，剛好看到老師的這篇大作，就忍不住問老師了。
        
        Reply
ccjou says:

11/13/2013 at 10:52 am

每次聽到有人問(或抱怨)學線性代數有甚麼用總會令我想起Markov chain和它的誕生故事。Markov很喜愛詩，原本Markov chain是為了分析普希金的韻文小說Eugene Onegin的母音與子音分布。Markov以為Markov chain沒有別的用途，可誰又能預見後來的發展呢？

Click to access 201321152149545-2013-03Hayes.pdf

Reply
- 張盛東 says:
  
  11/13/2013 at 11:01 am
  
  老師說得對。基本上工程上用到的數學的骨架就是線代。
  很後悔undergrad的時候太注重calculus和analysis方面，忽視了線代，現在上grad school才開始惡補。幸虧有老師的blog。
  
  Reply
- Watt Lin says:
  
  11/13/2013 at 6:39 pm
  
  插播一則輕鬆話題：
  我在高中時期，數學第六冊，有介紹「馬克夫鏈」(Markov Chains)，
  學校教這段課程的期間，恰好有一天我看「五燈獎」電視節目，
  有人演唱「馬車夫之戀」，我想起數學課本的「馬克夫鏈」。
  經過好幾年，我偶然聽到「馬車夫之戀」歌曲，
  腦子裡又想到Markov Chains。
  ————————————-
  假設有某位老師，講「馬克夫鏈」課程時，用一點空檔時間，
  播放「馬車夫之戀」給同學們聽，會不會提升學習效果？
  
  Reply
張盛東 says:

02/13/2015 at 3:52 pm

老師，請教一下能否從線性代數的角度理解Markov Chain中time reversibility裡的detained balance條件呢？為何該條件滿足都保證有stationary distribution？是否該條件保證了特徵值1的代數重數為1？

Reply
- 張盛東 says:
  
  02/13/2015 at 4:03 pm
  
  對不起，應該是detailed balance條件。
  
  Reply
- ccjou says:
  
  02/13/2015 at 8:19 pm
  
  這麼深奧的問題！等我整理好思路了，再寫幾篇序列文討論這個主題好吧。最近渾渾噩噩，估計要等到過年後。
  
  Reply
  - 張盛東 says:
    
    02/14/2015 at 5:42 am
    
    不好意思，麻煩老師您了。期待老師的大作。
    
    Reply

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