12 非负矩阵与 Perron–Frobenius 理论

1. 两种“正”不要混淆

本章的

$$A\ge 0$$

表示每个元素 $a_{ij}\ge 0$；$A>0$ 表示每个元素严格为正。这与 $A⪰0$（Hermite 半正定）是完全不同的概念。

元素非负矩阵描述了不会相互抵消的传递过程：人口迁移、网页链接、Markov 链和投入产出模型都属于这一类。

2. 正矩阵的 Perron 定理

若 $A>0$，则：

1. $\rho (A)>0$ 是 $A$ 的特征值。
2. 存在严格正的右特征向量 $x>0$，使 $Ax=\rho (A)x$。
3. $\rho (A)$ 的代数重数为 $1$。
4. 其他特征值 $\lambda$ 满足 $|\lambda |<\rho (A)$。

所以反复作用 $A$ 后，只要初始向量在 Perron 方向上分量非零，归一化迭代通常会趋向该正特征向量。

3. 非负矩阵与不可约性

非负矩阵可能因分块结构而没有严格正的唯一主方向。矩阵 $A\ge 0$ 不可约，当且仅当其有向图强连通；也等价于

$$(I+A{)}^{n-1}>0.$$

对不可约非负矩阵，Perron–Frobenius 定理保证：

• $\rho (A)>0$ 是单特征值；
• 存在严格正的左右 Perron 特征向量；
• 圆周 $|z|=\rho (A)$ 上可能仍有其他特征值，它们反映周期性。

若进一步为本原矩阵，则外围特征值只剩 $\rho (A)$，归一化幂迭代具有真正的收敛性。

4. 单调性与行列和界

若 $0\le B\le A$，则

$$\rho (B)\le \rho (A).$$

对 $A\ge 0$，取全一向量即可得到粗界

$$\underset{i}{min}\sum _j{a}_{ij}\le \rho (A)\le \underset{i}{max}\sum _j{a}_{ij}.$$

列和也有同样的界。若每行和都等于 $1$，则 $A\mathbf{1}=\mathbf{1}$，所以 $1$ 是特征值且 $\rho (A)=1$。

5. Collatz–Wielandt 公式

若 $A\ge 0$ 不可约，则

$$\rho (A)=\underset{x>0}{max}\underset{i}{min}\frac{(Ax{)}_i}{x_i}=\underset{x>0}{min}\underset{i}{max}\frac{(Ax{)}_i}{x_i}.$$

它把谱半径写成一个极大极小问题：任取正向量 $x$，各分量增长率 $(Ax{)}_i/x_i$ 的最小值给下界，最大值给上界；最优时二者在 Perron 向量上同时等于 $\rho (A)$。

6. 随机矩阵

行随机矩阵满足 $A\mathbf{1}=\mathbf{1}$；列随机矩阵满足 ${\mathbf{1}}^{T}A={\mathbf{1}}^T$；双随机矩阵同时满足两者。

对不可约且非周期的随机矩阵，Markov 链会收敛到唯一平稳分布。谱上对应：$1$ 是简单主特征值，其余特征值模严格小于 $1$。

Birkhoff–von Neumann 定理指出，双随机矩阵构成的凸集的极点正是置换矩阵；因此每个双随机矩阵都是置换矩阵的凸组合。

7. Perron 正特征向量的存在性

令标准单纯形

$$\mathrm{\Delta }=\{x\ge 0:{\mathbf{1}}^{T}x=1\}.$$

当 $A>0$ 时，映射

$$F(x)=\frac{Ax}{{\mathbf{1}}^{T}Ax}$$

把 $\mathrm{\Delta }$ 连续地映入其内部。Brouwer 不动点定理保证存在 $x\in \mathrm{\Delta }$ 使 $F(x)=x$，于是

$$Ax=({\mathbf{1}}^{T}Ax)x,$$

得到严格正的特征向量。再比较任意复特征向量 $z$ 的模：

$$|Az|\le A|z|,$$

并利用 $A>0$ 的严格性，可证明其他特征值的模严格小于 Perron 根。存在性来自单纯形上的不动点，支配性来自正性消除了相位抵消。

8. 不可约不等于本原

三循环置换矩阵

$$P=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right)$$

的有向图强连通，所以 $P$ 不可约；但 $P^3=I$，任何幂都不会逐项为正。其特征值为

$$1,\omega ,{\omega }^2,\omega =e^{2\pi i/3},$$

全部位于单位圆上。幂迭代不会收敛，而是在三个状态间循环。

加入自环后

$$M=\frac{1}{2}(I+P)$$

仍是随机矩阵，并且 $M^2>0$，所以它本原。此时外围谱只剩简单特征值 $1$，Markov 链才会收敛到唯一平稳分布。周期性正是“不可约仍可能不收敛”的缺失条件。

9. 双随机矩阵的最小分解例子

每个 $2\times 2$ 双随机矩阵都有形式

$$D=\left(\begin{array}{cc}a& 1-a\\ 1-a& a\end{array}\right),0\le a\le 1.$$

它可写成

$$D=a\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)+(1-a)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$$

这就是 Birkhoff–von Neumann 定理在二维的完整图景：双随机矩阵是置换矩阵的凸组合，置换矩阵则是这个凸集无法再分解的极点。

10. 自检

• [ ] 不混淆 $A>0$ 与 $A\succ 0$。
• [ ] 能用有向图解释不可约性。
• [ ] 能用行和快速夹住谱半径。
• [ ] 能解释 Collatz–Wielandt 公式为何在 Perron 向量处取等号。
• [ ] 能把随机矩阵的稳态与主特征向量联系起来。
• [ ] 能用三循环矩阵解释不可约与本原的区别。
• [ ] 能把 $2\times 2$ 双随机矩阵分解为两个置换矩阵的凸组合。

回到课程总览，或进入期末速查与自检。