随机矩阵（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；若要证明性质成立，则必须证明

关键词：随机矩阵（ stochastic matrix）