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\in \mathbf{R}_+^{n} \backslash \lbrace 0 \rbrace $ 且至少有一个分量为 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\in \mathbf{R}_+^{n} \backslash \lbrace 0 \rbrace $ 则 $(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$ 为非负不可约矩阵，则

$f_A(tx) = f_A(x), \forall t > 0$
$f_A(x) = \max \lbrace \rho | Ax-\rho x \geq 0 \rbrace$
设 $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$ 在 $\mathbf{R}_{+} ^n \backslash \lbrace 0 \rbrace $上可以取到最大值

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$ 上的最大值。利用对$ \forall z \in R _+ ^n \backslash \lbrace 0 \rbrace $ 和 引理 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$是非负不可约矩阵，则下面结论成立

$\rho(A)>0$ 且 $\rho(A)$ 是矩阵 $A$ 的一个单特征值
$A$ 有一个对应于 $\rho(A)$ 的正特征向量
$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 \in \mathbf{R} _+ ^n \backslash \lbrace 0 \rbrace ,f_A(x) = \rho(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 定理,$\lbrace x^k \rbrace $ 有收敛子列 $\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)$

证毕。

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

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

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

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