Perron-Frobenius 理论

1907 年 O.Perron 发现正矩阵的谱有特别有趣的性质。G.Frobenius 在 1908-1912 年间将 Perron 的工作推广到不可约非负矩阵的情形，并得到了新的进一步结果。Ferron-Frobenius 理论有很多证明方式，下面介绍 H.Wielandt 的优美证明。（一步步的读下去会发现很清晰明了简单）

非负矩阵的谱半径（下面有定义）是它的一个特征值，并且这个特征值对应着非负特征向量。

两个矩阵 \(X\) 和 \(Y\) 称为置换相似的，若存在一个置换矩阵 \(P\) 满足 \(P^TXP=Y\)。设\(A\in M_n\).称\(A\)为可约的，若 \(A\) 置换相似于一个形如 \(\left( \begin{matrix} B & 0 \\ C & D \end{matrix} \right)\) 其中 \(B,D\) 是方阵，否则称 \(A\) 不可约。

\(X \geq 0\) 表示矩阵的每个元素 \(\geq 0\), （对向量，或者 \(>0\) 等情形类似定义即可）。

以下矩阵除非特别说明都是 \(n \times n\) 矩阵 \(n>1\)

引理 1 设 \(A\) 是不可约非负矩阵，$y_+^{n} $ 且至少有一个分量为 0, 则 \((I+A)y\) 的正分量的个数大于 \(y\) 的正分量个数

Proof： 设 \(y\) 恰好有 \(k\) 个正分量，\(1 \leq k \leq n-1\)。设 \(P\) 是置换矩阵，使得\(x=Py\)的前\(k\)个分量为正，其它为 0，因为 \(A\) 是非负矩阵，所以 \((I+A)y\)的零分量个数不会超过 \(n-k\)。假设这个个数等于 \(n-k\)，则有 \(y_i = 0 \Rightarrow (Ay)_i = 0\)。即 \((PAP^Tx)_i = (PAy)_i = 0,\quad i=k+1,\cdots,n\)，设 \(B=PAP^T\). 则当 \(k+1 \leq i \leq n\) 时， \[ (Bx)_i = \sum_{j=1} ^{n} b _{ij} x_j = \sum _{j=1} ^{k} b_{ij} x _j = 0 \] 但当 \(1 \leq j \leq k\) 时，\(x_j >0\)。所以 \(b_{ij}=0\), 其中 \(k+1 \leq i \leq n,1 \leq j \leq k\) 矛盾于 \(A\) 不可约，证毕。

引理 2 设 \(A\) 是 \(n\) 阶不可约非负矩阵，$y_+^{n} $ 则 \((I+A)^{n-1}y>0\)

引理 3 设 \(n>1\)，则 \(n\) 阶非负矩阵 \(A\) 不可约当且仅当 \((I+A)^{n-1}>0\)

Proof: 应用引理 2，考虑 \((I+A)^{n-1}e_j\) 即可。

若 \(A\) 不可约，考虑 \((I+A)^{n-1}e_j\) 即可知 \((I+A)\) 第 \(j\) 列每个元素都大于 \(0\)。

若 \(A\) 可约，按照定义存在置换矩阵 \(P\) 使得 \(A = P^{T} \left( \begin{matrix} B & 0 \\ C & D \end{matrix} \right) P\)，从而 \((I + A)^{n - 1} = P^{T} \left( \begin{matrix} B + I & 0 \\ C & D + I \end{matrix} \right)^{n - 1} P\)。

引理 4 一个不可约非负矩阵的非负特征向量是正特征向量

Proof：设 \(A\) 是不可约非负矩阵，\(Ax=\lambda x, x \geq 0,x \neq 0\)。显然 \(\lambda \geq 0\) 我们有 \((I+A)x = (1 + \lambda)x\) ，因此\((1+A)x\)与\(x\)有相同个数的正分量，有 引理 1 知 \(x>0\)。

Collatz-Wielandt 函数

设 \(A\) 是一个非负矩阵。\(A\) 的 Collatz－Wielandt 函数 \(f_A \colon \mathbf{R}_+ ^n \backslash \lbrace 0 \rbrace \to \mathbf{R}_+\) 定义为： \[ f_A(x) = \min _{ x_i \neq 0 } \frac{(Ax) _i }{x_i} \]

引理 5 设 \(A\) 为非负不可约矩阵，则

1. \(f_A(tx) = f_A(x), \forall t > 0\)
2. \(f_A(x) = \max \lbrace \rho | Ax-\rho x \geq 0 \rbrace\)
3. 设 \(x \in \mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace\)，记 \(y = (I+A)^{n-1} x\) ,则 \(f_A(y) \geq f_A(x)\)。

Proof：(1),(2)显然。下证明(3)： 我们有\(Ax- f_A(x)x \geq 0\)，在等式两边左乘以\((I+A)^{n-1}\)并利用\(A\)和\((I+A)^{n-1}\)乘法可交换的性质，得到\(A(I+A)^{n-1}x - f_A(x)(I+A)^{n-1}x \geq 0\) 即 \(Ay - f_A(x)y\geq 0\) 再由（2）证毕。

容易证明：\(f_A\) 是有界函数，实际上，\(f_A\) 非负且不超过 \(A\) 的最大行和（考虑每一个 \(f_A(e_j)\) 即可)。

记\(\Omega _n = \lbrace x \in \mathbf{R}_+ ^n | \sum _{i=1} ^n = 1 \rbrace\) 引理 5.1 说明，我们只需要在 \(\Omega_n\) 上研究 \(f_A\) 即可。显然\(\Omega_n\)是一个紧集，但是 \(f_A\) 可能在 \(\Omega_n\) 的边界不连续。

但是我们仍然有下面 引理 6。

引理 6 设 \(A\) 是非负不可约矩阵，则 \(f_A\) 在 $_{+} ^n $上可以取到最大值

Proof: 记\(\Delta = (I+A)^{n-1} \Omega _n = \lbrace y \mid y=(I+A)^{n-1} x ,x \in \Omega_n \rbrace\) 则 \(\Delta\) 是一个紧集， 且有 引理 2 知 \(\Delta\) 中向量都是正向量，因此 \(f_A\) 在 \(\Delta\) 上连续，由 Weierstrass 定理，\(f_A\) 在某一点 \(y^0 \in \Delta\) 取得 \(f_A\) 在 \(\Delta\) 上的最大值。记 \(z^0 = y^0/ \sum_{i=1} ^n y_i ^0 \in \Omega_ n\)。\(\forall x \in \Omega_n\)，记 \(y=(I+A)^{n-1}x\) 利用 引理 5 可知 \[ f_A(x) \leq f_A(y) \leq f_A(y^0) = f_A(z^0) \] 这就证明了 \(f_A\) 在 \(z^0\) 上取到它在 \(\Omega_n\) 上的最大值。利用对$ z R_+ ^n $ 和 引理 6.1 有 \[ f_A(z) = f_A(\frac{z}{\sum_{i=1}^n z_i}) \leq f_A(z^0) \] 可见 \(f_A\) 在 \(z^0\) 处取到它在 \(R _+ ^n \backslash \lbrace 0 \rbrace\) 上的最大值。

Perron-Frobenius 定理

矩阵 \(A\) 的谱半径 \(\rho(A)\) 定义成矩阵 \(A\) 的所有特征值的绝对值的最大值。

现在万事俱备了，下面开始介绍著名的 Perron-Frobenius 定理

定理 7(Perron-Frobenius) 设\(A\)是非负不可约矩阵，则下面结论成立

1. \(\rho(A)>0\) 且 \(\rho(A)\) 是矩阵 \(A\) 的一个单特征值
2. \(A\) 有一个对应于 \(\rho(A)\) 的正特征向量
3. \(A\) 的每个非负特征向量都对应于特征值 \(\rho(A)\)

Proof：由 引理 6 存在 \(x^0 \in R _+ ^n \backslash \lbrace 0 \rbrace\) 满足 \(f_A(x^0) \geq f_A(x), \forall x \in \mathbf{R}_+ ^n \backslash \lbrace 0 \rbrace\) 记 \(r=f_A(x^0)\)，取 \(u=(1,\cdots,1)^T\)。因为 \(A\) 不可约，没有零行，所以 \(r \geq f_A(u) = \min \sum_{i=1} ^n a_{ij} > 0\)

下面证明 \(r\) 是 \(A\) 的一个特征值，我们有: \(Ax^0 - rx^0 \geq 0\)，假设 \(Ax^0 - rx^0 \neq 0\)。由 引理 5.2 知 \((I+A)^{n-1}(Ax^0 - rx^0) > 0\) 即 \(Ay^0 - ry^0> 0\) 其中，\(y_0 = (I+A)^{n-1}x^0 >0\)。因此存在 \(\epsilon > 0\) 使得 \(Ay^0 - (r+\epsilon)y^0> 0\). 由引理 5.2，\(f_A(y^0) \geq r+\epsilon > r\) 这就与 \(r=f_A(x^0)\) 的最大性矛盾。所以 \(Ax^0=rx^0\)。从而\(r\)是\(A\)的一个特征值，\(x^0\) 是 \(A\) 的一个特征向量。有 引理 4 知，\(x^0\) 是正向量。 设 \(\lambda\) 是 \(A\) 的任何一个特征向量：\(Ax=\lambda x\) 则 \(|\lambda||x| \leq A|x|\)，于是 \(|\lambda| \leq f_ A(|x|) \leq r\) 这表明 \(r = \rho(A)\)。

以下关于证明 \(\rho(A)\) 是单特征值的部分可以不看

---

现证明 \(\rho(A)\) 是单特征值，我们先证明 \(\rho(A)\) 的几何重数是 1，设 \(Ay = \rho(A) y,0 \neq y \in \mathbf{C}^n\) 则 \(A|y| \geq \rho(A)|y|\) 上面证明过程表明上式是等式（细品，走一遍没毛病）且 \(|y|>0\)。可见 \(A\) 的对应于 \(\rho(A)\) 的特征向量不含零分量。设 \(y\) 和 \(z\) 是对应 \(\rho(A)\) 的特征向量。则 \(|y|>0,|z|>0.z_1 y-y_ 1 z\) 属于 \(\rho(A)\) 的特征子空间，但 \(z_1 y-y_ 1 z\) 的第一个分量为 0，所以它不可能是 \(\rho(A)\) 的特征值，因此，\(z_1 y-y_ 1 z＝0\)，\(y\) 和 \(z\) 线性相关，所以 \(\rho(A)\) 的几何重数为 1.

为了证明 \(r=\rho(A)\) 是特征多项式 \(\phi(\lambda) = det(\lambda I - A)\) 的单根，只需证明，导数 \(\phi'(r) \neq 0\)

用 \(adj(X)\) 表示矩阵 \(X\) 的 伴随矩阵。我们有 \[ \phi'(\lambda) = \sum_{i=1}^n det[(\lambda I - A)(i|i)] =tr[adj(\lambda I - A)] \] > \(X(i|j)\) 表示矩阵去掉第 \(i\) 行和第 \(j\) 列所剩下的矩阵

记 \(B(r)=adj(rI-A)\) 则 \(\phi'(r) = tr B(r)\) \[ (rI-A)B(r) = det(rI-A)I \] 因为 \(r\) 的几何重数为 1，所以 \(rank(rI-A)=n-1\)，于是 \(B(r) \neq 0\)。设 \(b\) 是\(B(r)\)的任意一个非零列，则\((rI-A)b=0\),因此 \(b\) 是 \(A\) 的对应于 \(r\) 的特征向量，但是 \(A\) 有一个对应于 \(r\) 的特征向量 \(x^0\)，且因为 \(r\) 的几何重数为 1，因此 \(b\) 是 \(x^0\) 的一个常数倍，从而 \(b>0\) 或者 \(b<0\)。这就证明了 \(B(r)\) 的每一列要么是零列，要么是正向量，要么是负向量。考虑 \([B(r)]^T = adj(rI-A^T),r=\rho(A)=\rho(A^T)\)。上面结论应用于 \([B(r)]^T\) 的列，所以 \(B(r)>0\) 或者 \(B(r)<0\)，从而 \(\phi'(r)=tr[B(r)] \neq 0\)，这就证明了 \(\rho(A)\) 是单特征值。

---

我们已经证明了(1),(2)。现在来证明(3)。设 \(y>0\) 是 \(A^T\) 对应于 \(\rho(A)\) 的特征向量，设 \(x\) 是 \(A\) 的任意一个非负特征向量：\(Ax = \mu x\)。则 \(\mu y^T x = y^T Ax = \rho(A)y^Tx\), 因为 \(y^Tx>0\), 我们有 \(\mu = \rho(A)\)，证毕。

由引理 4，\(A\) 的非负特征向量实际上都是正向量，因此结论 3 可叙述成：在\(A\) 的所有特征向量中，只有 \(\rho(A)\) 有非负特征向量。上述证明还确定了以下结果：

定理 8. 设 \(A\) 是不可约非负矩阵，则 \(\rho(A) = \max \lbrace f_A(x)|x\in \mathbf{R}_+ ^n \backslash \lbrace 0 \rbrace \rbrace > 0\) , 若$ x _+ ^n ,f_A(x) = (A)$ 则\(x>0\) 是对应于\(\rho(A)\)的一个特征向量

定理 9. 设 \(A\) 是一个非负矩阵，则 \(\rho(A)\) 是 \(A\) 的特征值，且 \(A\) 有一个对应于\(\rho(A)\)的非负特征向量

Proof：设\(A\)的阶数为\(n\)，定理对\(n=1\)是平凡地成立。下面设\(n=2\)，用\(J\)表示元素全为 1 的矩阵。 对于正整数 \(k\)，记 \(A_k = A + \frac{1}{k} J\) 是一个正矩阵，由 Perron-Frobenius 定理，\(A_k\) 在 \(\Omega _n = \lbrace x \in \mathbf{R}_+ ^n | \sum _{i=1} ^n = 1 \rbrace\) 中有唯一一个对应于 \(\rho(A_k)\) 的特征向量 \(x^k\)。

因为向量序列 \(\lbrace x^k \rbrace\) 有界因此，由 Bolzano-Weierstrass 定理,$x^k $ 有收敛子列 \(\lbrace x^{k_i} \rbrace: \lim_{i \to \infty } x^{k_i} = x\)。显然 \(x \in \Omega_n\) 因此 \[ A _{k_i}x^{k _i} = \rho(A_{k _i}) x^{k_i} \] 注意到当 \(i \to \infty\) 时， \(A _{k_i} \to A , \rho(A _{k_i}) \to \rho(A)\) 从而得到 \(Ax = \rho(A)x\)，证毕。

至此，Prron-Frobenius 定理介绍完毕。下面介绍一个非负矩阵特征值的界。

定理 10 设 \(A\) 是非负矩阵，则

\[ \min_{1 \leq i \leq n} r_i \leq \rho(A) \leq \max_{1 \leq i \leq n} r_i \]

\[ \min_{1 \leq i \leq n} c_i \leq \rho(A) \leq \max_{1 \leq i \leq n} c_i \]

其中 \(r_i, c_i\) 分别为 \(A\) 的第 \(i\) 行之和以及第 \(i\) 列之和。

Proof：设 \(x\) 是 \(A^T\) 的一个 Perron 向量(对应于谱半径的非负特征向量)。因为 \(\rho(A^T)=\rho(A)\)， 从而 \(A^Tx=\rho(A)x\) 得到 \[ \rho(A)x_i = \sum_{k=1}^n a_{ki}x_k \qquad i = 1,\cdots,n. \] 将这些等式相加得到 \(\rho(A) \sum_{i=1}^n x_i =\sum_{k=1}^n r_k x_k\) 即 \[ \rho(A)= \frac{\sum_{k=1}^n r_k x_k }{\sum_{i=1}^n x_i} \] 证毕。

定理 11(Wielandt) 设\(A\)是不可约非负矩阵，且\(|B| \leq A\) 则对于 \(B\) 的任何特征值 \(\lambda\)有

\[ |\lambda| \leq \rho(A) \]

Proof：设\(Bx=\lambda x\) 则 \(|B||x| \geq |\lambda||x|\)，但是 \(|B| \leq A\)，所以 \(|\lambda| |x| \leq |B||x| \leq A |x|\)，由 引理 5.2 和 引理 8 知 \[ |\lambda| \leq f_A(|x|) \leq \rho(A) \] 证毕。

根据谱半径的连续性，我们马上有如下推论

1. 若矩阵 \(A\) 非负，且\(|B| \leq A\)，则 \(\rho(B) \leq \rho(A)\)
2. 对任意矩阵\(A\)，\(\rho(A) \leq \rho(|A|)\).(这个直接证明也可以)

本文源自詹兴致所著的《矩阵论》第六章。

定理虽然很长但是整个过程十分优美，思路十分清晰，仔细分析每一步还是很容易看懂的，并且在证明的过程中就能体会为什么一开始要提出“非负不可约矩阵”的概念了，然后应用连续性把一些结果推广到非负矩阵。