對角化不只是矩陣的分類;它把重複的或連續的線性演化化為純量問題。若 , 為對角矩陣,則每個冪 以及由 構成的任何表達式,都可由 的對角元算出。本單元把這個想法應用於三種標準情形:離散動力系統 與馬爾可夫(Markov)鏈、線性遞歸關係,以及線性微分方程組 。它用到特徵值與特徵向量(5.1)、對角化與相似(5.2)以及 5.3 的對角化判別。
可對角化矩陣的冪
定理 5.5.1
(沿特徵向量基計算冪)
設 ,其中 , 的縱列是特徵向量 ,滿足 。則對每個整數 ,
若 ,則以 為初始向量的 的解為
證明
(相鄰因子相消)
在乘積 中,每個相鄰的 都相消,剩下 。第二個結論:對 歸納得 ,再由線性即得公式。
係數 是 在特徵向量基下的座標,即 的解。
馬爾可夫鏈
定義 5.5.2
(縱列隨機矩陣)
若方陣 的所有元素非負且每條縱列之和為 ,稱 為縱列隨機矩陣(column-stochastic,縱列和為 1)。若 是描述時刻 各狀態分佈的概率向量(元素非負且和為 ),而 是一步內由狀態 轉到狀態 的概率,則 。
定理 5.5.3
(縱列隨機矩陣的特徵值)
設 為 的縱列隨機矩陣。則 是 的特徵值,並且 的每個特徵值 (實或複)都滿足 。此外 ( 為全 向量),故 :總概率守恆。
證明
(轉置矩陣特徵向量的最大分量)
各縱列和為 即 ,所以 是 的特徵值。由 , 與 有相同的特徵值。設 ,(可為複向量),取 使 最大。 的第 橫行的元素非負且和為 ,故
所以 。
證明透視
非負性與「和為一」用在何處
證明有兩個關鍵步驟。第一, 與 有相同的特徵值,所以只需研究 ;它的每條橫行(而非縱列)之和為 ,這把縱列條件轉化為關於平均值的陳述。第二,取使 最大的下標 。 的第 橫行是一組非負且和為 的權,所以 是 各分量的加權平均,其模不會超過最大的模,由此得 ,而 才容許約去。非負性用在 一步。若沒有非負性,結論不成立: 的兩條縱列之和都是 ,特徵值卻是 與 。
定義 5.5.4
(穩態分佈)
若概率向量 (元素非負且和為 )滿足 ,便稱 為縱列隨機矩陣 的穩態分佈。
定理 5.5.5
(收斂到穩態分佈)
設 為縱列隨機矩陣,在 上可對角化,特徵值 的重數為一,其餘特徵值都滿足 。則存在滿足 且元素之和為 的向量 ,並且對每個初始向量 ,
證明
(特徵向量基展開與總概率守恆)
令 ,展開 。則 ,因為 。由守恆,對所有 有 ,取極限得 。取 可知 ,故 的元素之和為 ,且 。
反例模式
若其他特徵值的模不嚴格小於一,迭代未必收斂
斷言:若 為縱列隨機矩陣,在 上可對角化,且 是單特徵值,則對每個概率向量 , 都收斂。當另有特徵值的模為 時,這是錯的。取對調矩陣 :它的各縱列之和為 ,特徵值為 (特徵向量 )與 (特徵向量 ),所以可對角化,且 是單特徵值。取 ,則 、,如此類推:序列來回振盪,沒有極限。在展開式 中,項 並不趨於 。補救辦法是要求其餘每個特徵值 都滿足 。
線性遞歸與微分方程組
遞歸關係 可化為 的一階方程組:
特徵值是 的根;當兩根相異時,由冪的公式得 的閉式。
對微分方程組 ,,設 ,令 。則 ,解耦為純量方程 ,解為 。
定理 5.5.6
(沿特徵向量基解線性方程組)
若 有特徵向量基 ,且 ,則 , 的唯一解為
證明
(直接求導與唯一性)
求導得 ,且 。唯一性:任一解 給出 ,滿足 ,而 ,故解由 決定。
以上關於冪、收斂與微分方程組的結論都假設存在完整的特徵向量基。若特徵值有重複,應先用 5.3 與 5.4 的對角化判別。
例題
例題 5.5.7
(馬爾可夫鏈的閉式軌道)
設 (每條縱列之和為 )。跡為 ,行列式為 ,故 給出 與 。: 給出 ,故 。: 給出 。由 出發,解 :、 給出 、。因此
驗算 :公式給出 ,直接計算 。穩態分佈為 。
例題 5.5.8
(由特徵向量基得出斐波那契(Fibonacci)數)
設 ,,。令 ,則 ,。特徵值為 與 ( 的根),特徵向量為 與 。寫 :、 給出 。 的第二個分量為
驗算 :,故 。
例題 5.5.9
(解耦的微分方程組)
設 ,。特徵值為 ()與 ()。因 ,由特徵向量基的解公式,
驗算:,而 。
常見錯誤與細節
常見錯誤
(橫行隨機的約定會令特徵向量反轉)
若轉移矩陣是每條橫行(而非每條縱列)之和為 ,概率行向量的演化為 ,穩態向量是左特徵向量。以 (第一個例題的矩陣轉置)為例, 的右特徵向量是 ,它並不是分佈;穩態行向量是 :確實 。
常見錯誤
(特徵向量還不是分佈)
第一個例題中,消元得到 的 ,但它的元素之和是 而不是 。任何非零倍數都是特徵向量,所以穩態分佈是元素之和為 的那個倍數,即 。
常見錯誤
(離散的冪與連續的指數)
對 ,特徵值 貢獻 ,衰減需要 ;對 ,它貢獻 ,衰減需要 。例如 給出 ,永不衰減,但 ; 在離散系統中給出 ,在連續系統中 卻增長。
練習
快速檢查
(求縱列隨機矩陣 的穩態分佈及另一個特徵值。)
解答 · 引導解答
跡為 ,行列式為 ,故 ,特徵值為 與 。: 給出 ;除以和 歸一化,得穩態分佈 。驗算:。
快速檢查
(解 ,,。)
解答 · 引導解答
特徵方程為 ,根為 與 ,故 。條件 、 給出 ,。因此 。驗算:,而 。
快速檢查
(對 ,解 ,。)
解答 · 引導解答
為下三角矩陣,特徵值為 與 。: 給出 。: 給出 。解 :,。故 。驗算:,。
快速檢查
(證明縱列隨機矩陣 的特徵值為 與 ,並說明當 時,何時對每個 都有 收斂。)
解答 · 引導解答
各縱列和為 ,故 是特徵值;跡為 ,所以另一個特徵值為 。當 時 ,且 當且僅當 。此時矩陣有兩個相異特徵值,可對角化,由收斂定理,對每個 都收斂。當 時矩陣是 , 平凡地收斂,但極限依賴於 ,不存在唯一的穩態分佈。當 時矩陣是對調矩陣 ,除非 的兩個分量相等,否則 振盪。因此對每個 都有 收斂當且僅當 ;而收斂到 乘以唯一的穩態分佈當且僅當 。
快速檢查
(設 ,求 的公式。)
解答 · 引導解答
特徵值 的特徵向量為 與 ,故 ,。於是