隨機矩陣（stochastic matrix）

最近一個月來一直在看Google排序的核心算法---PageRank排序算法[1][2]，在多篇論文中涉及到圖論、馬爾可夫鏈的相關性質說明與應用[3][4][5]，而最為關鍵，一直讓我迷惑的一句話是"A stochastic matrix has principal/primary eigenvalue 1"[3][4][5][6][7][8]。可能對于系統學習過矩陣理論的人，它很平淡，不值得單獨拿出來討論或者說明。而我在此不得不承認自己的無知。盡管在高等代數中學習過關于矩陣性質的一些討論，但從來沒有接觸過所謂的隨機矩陣(Stochastic Matrix)，更不要說其性質了。于是，我從網上努力的尋找相關文獻，但結果不是特別理想，并沒有關于隨機矩陣的詳細介紹以及相關性質的證明。我想也許一方面是我搜索技術還不成熟，或者是搜索的關鍵詞不準確，亦或者是網上關于它的資料本就很缺乏。在這里我想將最近搜集的相關資料拿出來整理一下思路，以備將來之用，也是對自己學習的一個真實記錄和督促。

隨機矩陣實際上是非負矩陣(Nonnegative matrix)的一類，而非負矩陣是指矩陣元素都是非負(Nonnegative)的，當然非負要與正矩陣（Positive matrix）進行細微的區分。非負矩陣在計算數學、圖論、線性規劃、自動控制等領域有著廣泛的應用，對其特征值，尤其是最大特征值（注意這里的最大是從模的角度或者說是絕對值概念上的最大）特征值，也就是矩陣的主特征值（principal/primary eigenvalue）的估計有很重要的意義[9]。

隨機矩陣說來如此之重要，那么到底什么樣的矩陣才是隨機矩陣呢？假如隨便給你一個非負矩陣，該如何判定它是否屬于隨機矩陣呢？

隨機矩陣實際上應當分成行隨機矩陣（Row stochastic matrix）和列隨機矩陣（Column stochastic matrix）。行隨機矩陣是指方陣的行和等于1；而列隨機矩陣就是其列和等于1的非負矩陣。那么同時滿足行和列和都是1的非負矩陣就是雙隨機矩陣（Double stochastic matrix），單位矩陣就是一種雙隨機矩陣。從研究的角度，其實只要研究行矩陣的性質即可，畢竟列隨機矩陣只是行隨機矩陣的轉置矩陣。因此以下的討論完全從行隨機矩陣出發。

既然隨機矩陣A行和為1，那么假設e=（1,1,...,1），則e的轉置向量e'，即是矩陣的一個特征向量，對應于A的特征值1。這樣對于證明隨機矩陣的主特征值是1還有一定的距離。假設A的n個特征值為λ(i)，其中i=1,2,...,n；若要證明性質成立，則必須證明|λ(i)|<=1。現今有一個特征值是1，只要證明其余各特征值的絕對值都小于等于1即可。

于是我又查找了相關資料，并在“數學博士論壇”發帖請教，得到的回復是要證明它，粗略地講利用圓盤定理即可，若要精細的證明還要利用Perron-Frobenius Theorm[9][10][11][12]。一個個新的概念和方法出現在面前，看來需要系統的學習數值方法、數值計算理論。查找到的資料[10]表明任何矩陣的譜半徑都不大于該矩陣任意誘導矩陣范數，而隨機矩陣的L1-Norm值是1，那么譜半徑（是主特征值的等價說法）不大于1，而由于1是A的一個特征值，那么就不可能出現絕對值大于1的特征值了：1確實是隨機矩陣A的主特征值。

那么對上述性質的證明就等價于證明資料[10]中的結論了。

其實，“任意復數域上的矩陣的譜半徑不大于其任意一種誘導范數”只是矩陣的一個基本的性質。其具體證明見下圖：

根據以上的證明結果可知，對任意的行隨機矩陣，其譜半徑是1，即最大特征值是1得證。

由此可知，其實矩陣的一個小小的性質對于沒有系統學習過矩陣理論的人有時確實是一個難題。要入行，就當懂行規，要入門，就當精通門路。

隨機矩陣的主特征值以及second largest eigenvalue的比值是冪法收斂速度的一個基本的衡量標準。PageRank的計算有多種方式，而對此的研究也是不計其數，當然最傳統的還是利用冪法來確定抓取入庫的各網頁的PageRank值。由于web網頁的數量巨大，針對冪法收斂速度的考慮就不是多余無用的分析。而兩特征值的“譜隙”（Eigengap）主要用來衡量利用冪法求解得到的PR值的穩定性的。由此看來，特征值分析對于理解PageRank算法起到關鍵作用。

相關推薦：

php版螺旋矩陣（由里到外）

PHP實現N*M的字符矩陣90度旋轉

以上就是隨機矩陣（ stochastic matrix）的詳細內容，更多請關注php中文網其它相關文章！