随机矩阵及其特征值

随机矩阵是这样一类方阵,其元素为非负实数,且行和或列和为1。如果行和为1,则称为行随机矩阵;如果列和为1,则称为列随机矩阵;如果行和和列和都为1,则称为双随机矩阵。

前面我们介绍的谷歌矩阵HMM中的转移矩阵都属于随机矩阵,所以随机矩阵也称为概率矩阵、转移矩阵、或马尔可夫矩阵。

随机矩阵有一个性质,就是其所有特征值的绝对值小于等于1,且其最大特征值为1。下面通过两种方法证明这个结论。

首先,随机矩阵A肯定有特征值1,即

\begin{equation}A\vec 1=1\times\vec 1\end{equation}

其中的单位向量\vec 1=(\frac{1}{n},...,\frac{1}{n})^T,因为A的行和为1,所以上述等式成立。即1是A的特征值。

反证法

假设存在大于1的特征值\lambda,则有A\vec x=\lambda\vec x。令x_k\vec x中最大的元素。又因为A的元素非负,且行和为1,所以\lambda\vec x中的每个元素都是\vec x中元素的凸组合,所以\lambda\vec x中的每个元素都小于等于x_k

\begin{equation}a_{i1}x_1+a_{i2}x_2+...+a_{in}x_n=\lambda x_i\leq x_k\end{equation}

但是如果\lambda>1,则\lambda x_k>x_k,和(2)式矛盾,所以\lambda\leq 1。又因为(1)式,所以A的最大特征值为1。

常规证法

对称随机矩阵A的特征值\lambda对应的特征向量为x(为了简便,以下省略向量符号),则有Ax=\lambda x,即x^TAx=\lambda x^Tx,欲证明|\lambda|\leq 1,只需证明

\begin{equation}\lambda=\frac{<x,Ax>}{<x,x>}\leq 1\end{equation}

根据定义有:

\begin{equation}<x,Ax>=\sum_{i=1}^na_{ii}x_i^2+2\sum_{i<j,i\sim j}a_{ij}x_ix_j\end{equation}

对于i<j,i\sim j,有:

\begin{equation}a_{ij}(x_i-x_j)^2=a_{ij}x_i^2-2a_{ij}x_ix_j+a_{ij}x_j^2\end{equation}

两边求和并移项得到:

\begin{equation}\begin{array}\displaystyle{2\sum_{i<j}}a_{ij}x_ix_j & = & \displaystyle{\sum_{i<j}a_{ij}x_i^2+\sum_{i<j}a_{ij}x_j^2-\sum_{i<j}a_{ij}(x_i-x_j)^2}\\ & = & \displaystyle{\sum_{i<j}a_{ij}x_i^2+\sum_{i<j}a_{ji}x_j^2-\sum_{i<j}a_{ij}(x_i-x_j)^2}\\ & = & \displaystyle{\sum_{i<j}a_{ij}x_i^2+\sum_{i>j}a_{ij}x_i^2-\sum_{i<j}a_{ij}(x_i-x_j)^2}\\ & = & \displaystyle{\sum_i(\sum_{j\neq i}a_{ij}x_i^2)-\sum_{i<j}a_{ij}(x_i-x_j)^2}\\ & = & \displaystyle{\sum_i(x_i^2(1-a_{ii}))-\sum_{i<j}a_{ij}(x_i-x_j)^2}\end{array}\end{equation}

第2、3个等号都是因为A是对称矩阵,所以可以把a_{ij}替换为a_{ji},然后互换i,j下标。最后一个等号是因为A的行和为1。

将(6)代入(4)式得到:

\begin{equation}\begin{array}\displaystyle{<x,Ax>} & = & \displaystyle{\sum_ia_{ii}x_i^2+\sum_i(x_i^2(1-a_{ii}))-\sum_{i<j}a_{ij}(x_i-x_j)^2}\\ & = & \displaystyle{\sum_ix_i^2-\sum_{i<j}a_{ij}(x_i-x_j)^2}\end{array}\end{equation}

所以:

\begin{equation}\lambda=\frac{<x,Ax>}{<x,x>} = \frac{\sum_ix_i^2-\sum_{i<j}a_{ij}(x_i-x_j)^2}{\sum_ix_i^2} \leq 1\end{equation}

又因为(1)式,所以A的最大特征值为1。

随机矩阵的第二大特征值\lambda(A)也很有用,1-\lambda(A)被称为矩阵A的谱间隔(spectral gap),它衡量的是最大特征值和第二大特征值之间的差值。\lambda(A)在马尔可夫随机游走领域有重要作用。

\begin{equation}||A^lp-1||_2\leq \lambda^l(A)\end{equation}

上式是扩张图(Expander)领域很重要的一个引理,A为扩张图的邻接矩阵,p为在所有节点上的初始概率分布,\lambda(A)为矩阵A的第二大的特征值。因为\lambda(A)<1,所以\lambda^l(A)会快速的降到0。也就是说,在初始概率p上,随机游走l步,很快就能达到均匀分布1

Leave a Reply

Your email address will not be published. Required fields are marked *