on
Perron-Frobenius Theorem
1 Symmetric Case #
若矩阵是对称的, 该定理变得容易了很多.
定理 #
若\(M\)是实对称, 不可约矩阵(Irreducible Matrix), 且各元素都非负, 其特征值为\(\mu_1 \geq \mu_2 \geq \dots \geq \mu_n\), 则有:
- \(\mu_1\)有一个各元素都大于 0 的特征向量
- \(\mu_1 \geq -\mu_n\)
- \(\mu_1 > \mu_2\)
证明 #
引理: 若\(M\)是实对称, 不可约矩阵, 且各元素都非负, 且\(\phi\)是一个各元素非负的特征向量, 则\(\phi\)各元素都严格大于 0
证明:
假设\(\phi\)不是严格正的, 则存在\(a\)使得\(\phi(a)=0\),
由于\(M\)是Irreducible Matrix, 所以以\(M\)为邻接矩阵的图是连通的. 则必然存在一条边\((b,c)\)使得\(\phi(b)=0, \phi( c)>0\) (否则由\(a\)开始, 其相邻的所有点\(k\)都有\(\phi(k)=0\), 继而与\(k\)相邻的所有点也是… 最终可得出\(\phi\)是 0 向量, 与其是特征向量矛盾.)
设\(\mu\)是\(\phi\)的特征值, 用下式引出矛盾:
\[0 = \mu \phi(b) = (M\phi)(b) = \sum_{(b,z) \in E} M_{b,z} \phi(z) \geq M_{b,c} \phi( c) >0\]
所以\(\phi\)是严格正的.
证明:
-
\(\mu_1\)有一个各元素都大于 0 的特征向量
由引理, 只需证明\(\mu_1\)有一个非负的特征向量.
设\(\phi_1\)是\(\mu_1\)的一个长度为 1 的特征向量, 构造向量\(x\)使得其各项都是\(\phi_{1}\)各项的绝对值: \(\forall u, x(u) = | \phi_1(u) |\)
下面说明\(x\)也是\(\mu_1\)的特征向量:
\[\mu_1 = \phi_1^T M \phi_1 = \sum_{a,b} M(a,b)\phi_1(a)\phi_2(b) \leq \sum_{a,b} M(a,b)|\phi_1(a)| |\phi_2(b)| = x^T M x\]
根据Rayleigh Quotient的性质, \(\mu_1\)已经是对任意单位向量的Rayleigh Quotient的最大值, 故上述不等号只能取等号. 且这个最大值能够取到说明\(x\)就是\(\mu_1\)的特征向量.
-
\(\mu_1 \geq -\mu_n\)
设\(\phi_n\)是\(\mu_n\)的一个长度为 1 的特征向量, 构造向量\(y\)使得其各项都是\(\phi_{n}\)各项的绝对值: \(\forall u, y(u) = | \phi_n(u) |\), 同样根据Rayleigh Quotient的性质, 有:
\[| \mu_n| = \left| \phi_n^T M \phi_n \right| = \left| \sum_{a,b} M(a,b)\phi_n(a)\phi_n(b)\right| \leq \sum_{a,b} M(a,b)y(a)y(b) = y^T M y \leq \mu_1\]
-
\(\mu_1 > \mu_2\)
即证特征值\(\mu_1\)的重数(multiplicity)为 1.
因为\(\phi_2\)与\(\phi_1\)垂直, 而\(\phi_1\)各元素都是正数(或都是负数), 故\(\phi_2\)各元素必定有正有负. 构造向量\(y\), 使得: \(\forall u, y(u) = | \phi_2(u) |\), 跟上面同理, 得到:
\[\mu_2 = \phi_2^T M \phi_2 \leq y^T M y \leq \mu_1\]
假设\(\mu_1=\mu_2\), 则说明\(y\)是\(\mu_1\)的特征向量, 且由定义, 它各项非负, 由引理得\(y\)各项严格正, 即不包含为 0 的项. 所以\(\phi_2\)不包含为 0 的项, 其各项有正有负, 且以\(M\)为邻接矩阵的图连通, 故比如存在一条边\((a,b)\)使得\(\phi_2(a) < 0 < \phi_2(b)\). 则上述不等式不可能取等号, 因为边\((a,b)\)在\(\phi_2^T M \phi_2 \)中贡献负值, 而在\(y^T M y\)中贡献正值. 与我们的假设矛盾.
故\(\mu_1 > \mu_2\)