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

本文的閱讀等級:中級

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

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

其中 Br\times r 階,r\ge 1D(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_iv_j 的有向邊。換句話說,方陣 A 可以視為有向圖 \Gamma(A) 的加權鄰接矩陣 (一般鄰接矩陣的非零元必為 1)。圖一顯示一 3\times 3 階矩陣與其有向圖。

A matrix and its directed graph

圖一:一矩陣與其有向圖

 
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},其中 Br\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_1V_2 不交集,可知 \Gamma(M) 並非強連通,譬如,不存在 v_{r+1}v_1 的有向路徑。因為 \Gamma(A)\Gamma(M) 有相同的結構,故推論 \Gamma(A) 也不是強連通。

Directed graph of a reducible matrix

圖二:可約矩陣的有向圖

 
(\Leftarrow):我們證明:若 \Gamma(A) 不是強連通,則 A 是可約矩陣。假設 \Gamma(A) 不是強連通,v_i 不連通 v_jj\neq i,即不存在 v_iv_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

 
定理二:若 An\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_iv_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}_2B\mathbf{x}_1=\mathbf{b}_1-C\mathbf{x}_2 則耗用了 n^3/12+n^2/4 個乘法運算。

廣告
本篇發表於 特殊矩陣, 線性代數專欄 並標籤為 , , , , , , 。將永久鏈結加入書籤。

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

  1. 張盛東 說道:

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

    • ccjou 說道:

      對,可約矩陣和permutation matrix,以及doubly stochastic matrix有關,改天再介紹。

      • 張盛東 說道:

        老師,不好意思,我還有一個問題。Markov Chain還有一個性質就是週期性。如果是離散Markov Chain,是否有定理檢測Markov矩陣的週期性?

        • ccjou 說道:

          你最近在學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矩陣。

          • 張盛東 說道:

            謝謝老師答疑。
            其實我最近在上Information Theory,教科書的第二章提到Stochastic Process的熵,令我想起這兩個在我心中一直存在的疑問,剛好看到老師的這篇大作,就忍不住問老師了。

  2. ccjou 說道:

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

    http://www.americanscientist.org/libraries/documents/201321152149545-2013-03Hayes.pdf

    • 張盛東 說道:

      老師說得對。基本上工程上用到的數學的骨架就是線代。
      很後悔undergrad的時候太注重calculus和analysis方面,忽視了線代,現在上grad school才開始惡補。幸虧有老師的blog。

    • Watt Lin 說道:

      插播一則輕鬆話題:
      我在高中時期,數學第六冊,有介紹「馬克夫鏈」(Markov Chains),
      學校教這段課程的期間,恰好有一天我看「五燈獎」電視節目,
      有人演唱「馬車夫之戀」,我想起數學課本的「馬克夫鏈」。
      經過好幾年,我偶然聽到「馬車夫之戀」歌曲,
      腦子裡又想到Markov Chains。
      ————————————-
      假設有某位老師,講「馬克夫鏈」課程時,用一點空檔時間,
      播放「馬車夫之戀」給同學們聽,會不會提升學習效果?

  3. 張盛東 說道:

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

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s