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$ 时,

但当 $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$ 即可。

引理 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}_+$ 定义为:

引理 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$ 的最大行和。

记$\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$ 在 $z^0$ 上取到它在 $\Omega_n$ 上的最大值。利用对$ \forall z \in R _+ ^n \backslash \lbrace 0 \rbrace $ 和 引理 6.1

可见 $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$ 的 伴随矩阵。我们有

$X(i|j)$ 表示矩阵去掉第 $i$ 行和第 $j$ 列所剩下的矩阵

记 $B(r)=adj(rI-A)$ 则 $\phi’(r) = tr B(r)$

因为 $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$ 因此

注意到当 $i \to \infty$ 时, $A _{k_i} \to A , \rho(A _{k _i}) \to \rho(A)$ 从而得到 $Ax = \rho(A)x$,证毕。

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

定理 10 设 $A$ 是非负矩阵,则

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

Proof:设 $x$ 是 $A^T$ 的一个 Perron 向量(对应于谱半径的非负特征向量)。因为 $\rho(A^T)=\rho(A)$, 从而 $A^Tx=\rho(A)x$ 得到

将这些等式相加得到 $\rho(A) \sum_{i=1}^n x_i =\sum_{k=1}^n r_k x_k$ 即

证毕。

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

Proof:设$Bx=\lambda x$ 则 $|B||x| \geq |\lambda||x|$,但是 $|B| \leq A$,所以 $|\lambda| |x| \leq |B||x| \leq A |x|$,由 引理 5.2引理 8

证毕。

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

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

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

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