第 17 章 非负矩阵与 Perron-Frobenius 理论¶
前置：特征值 (Ch06) · 矩阵分析 (Ch14) · 图论基础 (Ch27)
本章脉络：非负矩阵的动机（概率、人口、金钱） \(\to\) 矩阵的不可约性 (Irreducibility) \(\to\) 原初矩阵 (Primitive Matrices) \(\to\) Perron 定理（正矩阵） \(\to\) Frobenius 定理（不可约非负矩阵） \(\to\) 谱半径 \(\rho(A)\) 的代数与几何支配性 \(\to\) Perron 向量（稳定状态） \(\to\) Collatz-Wielandt 公式 \(\to\) 应用：Google PageRank 算法、Leontief 经济平衡、Leslie 种群模型
延伸：Perron-Frobenius 理论是描述“正反馈”与“稳定流向”的终极工具；它揭示了只要系统是强连通的且非负，其长期演化必然收敛于一个具有物理意义的正稳定态，是离散动力系统分析的核心
在物理、生物和经济模型中，大多数变量（如人口、概率、价格）在逻辑上必须是非负的。Perron-Frobenius 理论是研究这类系统演化规律的皇冠明珠。它打破了特征值可能是虚数或负数的常规，证明了在非负约束下，矩阵必然存在一个“统治级”的正特征值及其对应的正特征向量。本章将确立这一连接拓扑连通性与代数稳定性的深刻框架。
17.1 不可约性与图论准则¶
定义 17.1 (非负矩阵与正矩阵)
- 非负矩阵 \(A \ge 0\)：所有元素 \(a_{ij} \ge 0\)。
- 正矩阵 \(A > 0\)：所有元素 \(a_{ij} > 0\)。
定义 17.2 (不可约矩阵)
非负矩阵 \(A\) 称为不可约的（Irreducible），如果不存在置换矩阵 \(P\) 使得 \(P^T A P\) 呈现分块上三角形式。 图论等价：矩阵关联的有向图是强连通的（即任意两点间均有路径）。
17.2 Perron-Frobenius 定理¶
定理 17.1 (不可约非负矩阵定理)
设 \(A \ge 0\) 且不可约，设 \(r = \rho(A)\) 为其谱半径。则： 1. 实正性：\(r\) 是 \(A\) 的一个特征值，且 \(r > 0\)。 2. 简单性：\(r\) 是特征方程的单根（代数重数为 1）。 3. 正特征向量：对应于 \(r\) 的特征向量 \(\mathbf{v}\) 可以选为全正的（\(v_i > 0\)）。 4. 单调性：\(r\) 随矩阵元素的增加而严格增大。
定理 17.2 (原初矩阵的支配性)
若 \(A\) 是原初的（即存在 \(k\) 使得 \(A^k > 0\)），则对任何其他特征值 \(\lambda\)，均有 \(|\lambda| < r\)。 物理意义：这意味着系统无论从什么初始状态出发，长期演化都会被 \(r\) 及其对应的正向量（平稳分布）所统治。
17.3 随机矩阵与计算¶
技术：Collatz-Wielandt 公式
谱半径 \(r\) 可以通过以下极值问题求得： $\(r = \max_{\mathbf{x} > 0} \min_{i} \frac{(A\mathbf{x})_i}{x_i}\)$ 这为无需精确求解特征方程即可估算主特征值提供了数值路径。
练习题¶
1. [基础] 判定 \(A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\) 是否为正矩阵、非负矩阵以及是否不可约。
参考答案
判定： 1. 非负性：元素均为 0 或 1，故是非负矩阵。 2. 正性：含有 0，故不是正矩阵。 3. 不可约性：关联图为 \(1 \leftrightarrow 2\)，是强连通的。或者观察 \(A^2 = I\)， \(A+A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} > 0\)。故是不可约矩阵。
2. [特征值] 求上题中 \(A\) 的特征值，并验证 Perron-Frobenius 结论。
参考答案
计算： 特征方程 \(\lambda^2 - 1 = 0 \implies \lambda = \pm 1\)。 1. 谱半径 \(r = \rho(A) = 1\)。 2. \(r=1\) 确实是特征值，且是实数。 3. 对应 \(r=1\) 的特征向量为 \((1, 1)^T\)，是全正的。 注意：由于该矩阵不是原初的（是周期的），存在另一个特征值 \(-1\) 满足模长等于 \(r\)。
3. [不可约性] 判定 \(A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\) 是否不可约。
参考答案
图论观察： 1. 顶点 1 到自身有环，顶点 1 到顶点 2 有边。 2. 但顶点 2 无法到达顶点 1（\(a_{21}=0\)）。 3. 关联图不是强连通的。 结论：是可约矩阵。它已经是一个分块上三角矩阵。
4. [随机矩阵] 证明：行随机矩阵（行和为 1）的谱半径必为 1。
参考答案
证明： 1. 令 \(\mathbf{1} = (1, 1, \ldots, 1)^T\)。 2. \(A\mathbf{1}\) 的第 \(i\) 个分量等于 \(A\) 的第 \(i\) 行元素之和。 3. 由定义，\(A\mathbf{1} = 1 \cdot \mathbf{1}\)。 4. 因此 1 是 \(A\) 的特征值，故 \(\rho(A) \ge 1\)。 5. 又因为 \(\|A\|_\infty = \max (\text{行和}) = 1\)，由 \(\rho(A) \le \|A\|\) 知 \(\rho(A) \le 1\)。 结论：\(\rho(A) = 1\)。
5. [原初矩阵] 举出一个不可约但非原初的矩阵例子。
参考答案
例子：置换矩阵 \(P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\)。 分析：它是不可约的（强连通），但它的幂 \(P, I, P, I \ldots\) 永远包含 0 元素，无法变得全正。此类矩阵称为周期矩阵。
6. [Perron向量] 在 PageRank 算法中，为什么要在原始链接矩阵上加一个全正扰动（阻尼因子）？
参考答案
代数解释： 1. 原始互联网链接图可能不是强连通的（可约），或者具有周期性（非原初）。 2. 这会导致主特征值 1 不唯一，或者幂法迭代不收敛。 3. 加入全正扰动（谷歌矩阵）保证了矩阵是原初正矩阵。 4. 根据 Perron 定理，此时主特征值 1 是唯一的且具有绝对支配性，保证了算法对任何初始排名都能收敛到唯一解。
7. [性质] 证明：若 \(A \ge 0\) 是不可约的，则 \((I + A)^{n-1} > 0\)。
参考答案
证明思路： 1. \((I+A)^{n-1} = \sum \binom{n-1}{k} A^k\)。 2. 在图中，\(A^k\) 的 \((i,j)\) 元素非零代表存在长度为 \(k\) 的路径。 3. 不可约意味着任意两点间存在长度小于等于 \(n-1\) 的路径。 4. 每一对 \((i,j)\) 在求和式中至少有一项 \(A^k\) 是正的。 结论：该矩阵幂和是全正的，这证明了不可约矩阵通过自反馈可以转化为原初结构。
8. [比较] 若 \(0 \le A \le B\)（逐分量），证明 \(\rho(A) \le \rho(B)\)。
参考答案
推导： 1. 利用 Collatz-Wielandt 公式：\(\rho(A) = \inf_{\mathbf{x} > 0} \max_i \frac{(A\mathbf{x})_i}{x_i}\)。 2. 由于 \(A \le B\) 且 \(\mathbf{x} > 0\)，有 \(A\mathbf{x} \le B\mathbf{x}\)。 3. 对任何 \(\mathbf{x}\)，其 \(A\) 的增长比率均小于等于 \(B\) 的增长比率。 结论：非负矩阵的谱半径是其元素的单调非减函数。
9. [应用] 什么是经济学中的 Leontief 生产方程的平稳态？
参考答案
解释： 在封闭模型中，\(Ax = x\)，产出恰好等于投入消耗。这对应的正是消耗矩阵 \(A\) 的 Perron 特征向量。Perron-Frobenius 理论保证了这种平衡下的产出向量 \(\mathbf{x}\) 每一个分量都是正的，具有实际经济意义。
10. [极限] 设 \(A > 0\) 为正矩阵，且 \(\rho(A) = 1\)。证明 \(\lim_{k \to \infty} A^k = \mathbf{v}\mathbf{w}^T\)。
参考答案
证明： 1. 由于 \(A\) 是正矩阵，它是原初的，1 是唯一的模最大特征值。 2. 将 \(A\) 写成 Jordan 分解：\(A = \mathbf{v}\mathbf{w}^T + \sum_{j \ge 2} \lambda_j J_j\)。 3. 计算幂：\(A^k = (\mathbf{v}\mathbf{w}^T)^k + \sum \lambda_j^k J_j^k = \mathbf{v}\mathbf{w}^T + \sum \lambda_j^k J_j^k\)。 4. 由于 \(|\lambda_j| < 1\)，当 \(k \to \infty\) 时，其余项均趋于 0。 结论：矩阵幂最终坍缩为一个秩 1 矩阵，由主特征向量的外积构成。
本章小结¶
非负矩阵理论建立了物理规律与代数结构之间的和谐共振：
- 正性的保全：Perron-Frobenius 定理确立了主特征向量的正性，这为概率分布、资源分配等现实问题提供了唯一合法的稳态解。
- 结构的连通性：不可约性将矩阵的代数性质与图的拓扑结构绑定，证明了“全空间流通”是系统趋于唯一稳定状态的先决条件。
- 计算的收敛性：原初性确保了系统的长期行为不具有震荡性，揭示了复杂网络（如互联网、神经网络）中信息流动的最终指向。