8.5 素矩阵

实际上，在Perron定理中可能用得最多的结果是定理(8.2.8)中的极限命题。定理(8.4.4)的证明说明，没有把引理(8.2.7)应用于不可约矩阵的仅有假设条件是谱半径为唯一的极大模特征值。因为 $A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ 是有两个极大模特征值的非负不可约矩阵的例子（并且对于它， $\lim_{m \to +\infty} A^{m}$ 不存在），所以对不可约矩阵类作进一步的限制是必要的；而最经济的办法是缺什

么就假定什么.

8.5.0 定义 非负矩阵 $A \in M_{n}$ 称为素矩阵（或本原矩阵），是指它是不可约的且只有一个极大模特征值。

素性的概念属于 Frobenius (1912). 现在, 采用与定理 (8.2.8) 相同的证明可直接由引理 (8.2.7) 得到下述极限结果.

8.5.1 定理 如果 $A \in M_{n}$ 是非负素矩阵，则

其中， $L = xy^{\prime}$ ， $Ax = \rho(A)x$ ， $\Lambda^T y = \rho(A)y$ ， $x > 0$ ， $y > 0$ 且 $x^T y = 1$ 。另外，如果 $\lambda_{n-1}$ 是 $A$ 的特征值，且对每个特征值 $\lambda \neq \rho(A)$ 有 $|\lambda| \leqslant |\lambda_{n-1}|$ ，又如果 $|\lambda_{n-1}| / \rho(A) < r < 1$ ，则存在常数 $C = C(r, A)$ ，使得 $\left\|[\rho(A)^{-1}A]^{m} - L\right\| \leqslant Cr^{m}$ 对所有 $m = 1, 2, \cdots$ 成立。

我们现在已经把Perron定理的所有结果从正矩阵类推广到非负素矩阵类。但是，实际上仍然需要解决验证一个已知非负矩阵的素性问题，从理论上讲，可能希望不直接计算特征值就能做到这一点。下面的素性特征诱导出几个有用的准则，而其特征在计算上并不是有效的检验法。

8.5.2 定理 如果 $A \in M_{n}$ 是非负的，则 $A$ 是素矩阵，当且仅当 $A^{m} > 0$ 对某个 $m \geqslant 1$ 成立。

证明：如果 $A \geqslant 0$ ，且 $\Lambda^{m} > 0$ ，则从 $A$ 的有向图 $\Gamma(A)$ 的每个结点 $P_{i}$ 到另一个结点 $P_{j}$ 一定存在一条长恰好为 $m$ 的有向道路（推论(6.2.18))．因为这是比不可约性更强的性质，所以 $A$ 一定不可约．像在(8.4.3)中那样应用Perron定理(8.2.11d，e)，则推出 $A$ 一定是素的．反之，如果 $A$ 是素矩阵，则根据定理(8.5.1)有 $\lim_{m \to \infty} [\rho(A)^{-1} A]^{m} = L > 0$ ，且对某个 $m \geqslant 1$ 必定有 $[\rho(A)^{-1} A]^{m} > 0$ . □

现在联想起不可约性的图解准则，上述特征连同已有的关于非负不可约矩阵的极大模特征值的非常强的信息给我们提供了素性的图解准则。我们知道，正整数序列 $k_{1}, k_{2}, \cdots$ 的最大公因子(g. c. d.)是使 $k$ 为所有 $k_{1}, k_{2}, \cdots$ 的因子的最大整数 $k \geqslant 1$ .

8.5.3 定理 设 $A \in M_{n}$ 是不可约非负矩阵，设 $\{P_{i}\}$ 表示有向图 $\Gamma(A)$ 的结点集。用 $L_{i} = \{k_{1}^{(i)}, k_{2}^{(i)}, \dots\}$ 表示 $\Gamma(A)$ 中起点和终点都在结点 $P_{i} (i = 1, 2, \dots, n)$ 的所有有向道路的长度集合。用 $g_{i}$ 表示 $L_{i}$ 中的所有长度的最大公因子，则 $A$ 是素矩阵，当且仅当所有 $g_{i} = 1, i = 1, 2, \dots, n$ 。

证明：我们知道，因为 $\pmb{\Lambda}$ 不可约，所以其长度的集合 $L_{i}$ 非空；对每个 $\pmb{i}$ 和任意 $j\neq i$ ，在 $\Gamma (A)$ 中有一条连结 $P_{i}$ 到 $P_{j}$ 的道路，同时在 $\Gamma (A)$ 中也有一条连结 $P_{j}$ 到 $P_{i}$ 的道路．如果 $\pmb{A}$ 是素矩阵，则根据定理(8.5.2)，存在某个 $m\geqslant 1$ 使得 $A^{m} > 0$ ，因而对所有 $k\geqslant m$ 有 $A^k >0$ ，另一方面，对所有 $i = 1,\dots ,n$ ，有 $m,m + 1,m + 2,\dots \in L_i$ ，因而 $g_{i} = 1$ 对所有 $i = 1,\dots ,n$ 成立.

现在假设 $A = [a_{ij}]$ 不是素矩阵。如果 $A$ 恰好有 $k > 1$ 个极大模特征值，则由推论(8.4.8)可知，对所有 $i = 1, \cdots, n$ 以及所有不是 $k$ 的倍数的 $m$ 有 $a_{n}^{(m)} \equiv 0$ 。因此 $L_{i} \subset \{k, 2k, 3k, \cdots\}$ ，因而 $g_{i} \geq k > 1$ 对所有 $i = 1, \cdots, n$ 成立。

8.5.4 附注 比定理(8.5.3)中的论断稍微进一步的结论也成立；事实上，总有 $g_{1} = g_{2} = \cdots = g_{n}$ ，而 $g_{i}$ 个项的公共值恰好是 $A$ 的极大模特征值的个数。这就是 Romanovsky 定理。

下面的结果在许多场合是有用的；特别是它证明了具有正主对角元的不可约非负矩阵一定是素矩阵。

8.5.5 引理 如果 $A \in M_{n}$ 是不可约非负矩阵，又如果 $A$ 的所有主对角元都是正的，则 $A^{n-1} > 0$ .

证明：如果 $\alpha = \min \{a_{11}, a_{22}, \dots, a_{nn}\}$ ，又如果定义

则 $B$ 是不可约非负矩阵（因为 $A$ 是不可约的），且 $A \geqslant \alpha I + B = \alpha [I + (1 / \alpha)B]$ ，因而由引理(8.4.1)可知， $A^{n-1} \geqslant \alpha^{n-1}[I + (1 / \alpha)B]^{n-1} > 0$ . □

练习 试说明，当对具有正对角元的非负方阵取升幂时，变成正元的任何元在所有各次幂中仍然是正的。

虽然不可约矩阵的幂可能是可约的，但是素矩阵的所有幂都是素矩阵。

8.5.6 引理 设 $A \in M_{n}$ 是非负素矩阵，则对所有 $k = 1,2,\dots ,A^{k}$ 是不可约非负素矩阵

证明：因为 $A$ 的所有充分大的幂是正的，所以对任意 $k$ ， $A^k$ 也是正的．假如对某个 $k$ ， $A^k$ 是可约的，则 $A^k$ 的所有幂也是可约的，因而不可能是正的．因为这与 $A$ 的所有充分大的幂是正的事实相矛盾，所以对 $A$ 的任何次幂都不可能是可约的. □

从计算上考虑，定理(8.5.2)中的特征本身不是验证素性的有效方法，因为要计算的幂没有给出其上界。如果求出 $m$ 使 $A^{m} > 0$ ，则 $A$ 是素矩阵；但是，如果我们还没有得到一个正幂，那么什么时候终止这种计算呢？下述定理给出的有限界回答了这个问题。

8.5.7 定理 设 $A \in M_{n}$ 是非负矩阵。如果 $\Lambda$ 是素矩阵，则对某个正整数 $k \leqslant (n - 1)n^{k}$ 有 $A^{k} > 0$ 。

证明：因为 $A$ 是不可约的，则在 $\Gamma(A)$ 中存在从结点 $P_{1}$ 回到结点 $P_{1}$ 的有向道路；这样的最短道路有长 $k_{1} \leqslant n$ 。因此矩阵 $A^{k_{1}}$ 在它的 1，1 位置有正元，并且 $A^{k_{1}}$ 的任意幂也将有正 1，1 元。因为 $A$ 是素的，由引理(8.5.6)可知 $A^{k_{1}}$ 一定不可约，因而在 $\Gamma(A^{k_{1}})$ 中一定存在从结点 $P_{2}$ 回到结点 $P_{2}$ 的有向道路；这样的最短道路有长 $k_{2} \leqslant n$ 。因此矩阵 $(A^{k_{1}})^{k_{2}} = A^{k_{1}k_{2}}$ 有正 1，1 元和正 2，2 元。这个过程可沿主对角线继续进行下去直到得到矩阵 $A^{k_{1}k_{2}\cdots k_{n}}$ （其中每个 $k_{i} \leqslant n$ ）为止，这个矩阵是不可约的且有正对角元，因而由引理(8.5.5)可知 $[A^{k_{1}k_{2}\cdots k_{n}}]^{n-1} > 0$ 。因为

所以证毕.

如果 $A$ 是给定的素矩阵，使 $A^k > 0$ 的最小 $k$ 称为 $A$ 的本原指标，通常记作 $\gamma(A)$ 。我们已经看到，如果 $A$ 有正对角元，则 $\gamma(A) \leqslant n - 1$ ，而在一般情形下有 $\gamma(A) \leqslant n^{n-1}(n - 1)$ ，后一个界可以得到显著改进。

8.5.8 定理 设 $A \in M_{n}$ 是非负素矩阵，且假定 $\Gamma(A)$ 中的最短简单有向回路有长 $s$ 。则 $A^{n - (n - 2)} > 0$ ，即 $\gamma(A) \leqslant n + s(n - 2)$ 。

证明：因为 $A$ 是不可约的，所以 $\Gamma(A)$ 的每个结点落在一条回路上，且从任一结点回到自身的最短回路将是长度至多为 $n$ 的简单回路。经过一个置换，可以假定，在这条最短回路中的结点是 $P_{1}, P_{2}, \cdots, P_{s}$ 。注意到 $n + s(n - 2) = n - s + s(n - 1)$ 且考虑 $A^{n - s - s(n - 1)} = A^{n - s}(A^{s})^{n - 1}$ ，把 $A^{n - s}$ 写成分块形式

其中 $X_{11} \in M_s$ 和 $X_{22} \in M_n$ ，因为结点 $P_1, \cdots, P_s$ 组成 $\Gamma(A)$ 中的一条回路，所以 $X_{11}$ 在每一行至少有一个非零元，因而从图 $\Gamma(A^n)$ 中的每个结点 $P_i$ 到 $\Gamma(A_n)$ 中的某个结点 $P_j$ （或许 $P_i = P_j$ ）存在某条弧；如果 $1 \leqslant i, j \leqslant s$ ，这是成立的。因为从不在上述回路中的每个结点 $P_{i-1}, \cdots, P_n$ ，到该回路中的某个结点，在 $\Gamma(A)$ 中一定有一条长不超过 $n-s$ （它们是不在该回路中的结点数）的有向道路，所以在 $X_{21}$ 的每一行中至少有一个非零元。当绕着回路走了足够多的附加步数时，从不在该回路中的每个结点到该回路的某个结点，显然在 $\Gamma(A)$ 中恰好有一条长恰好为 $n-s$ 的有向道路。

现在把 $(A^{\prime})^{n - 1}$ 写成如下的分块形式

其中， $Y_{11} \in M_1$ ，而 $Y_{22} \in M_n$ 。因为 $P_1, \cdots, P_s$ 组成 $\Gamma(A)$ 中的一条回路，所以在 $\Gamma(A^s)$ 中的每个结点 $P_1, \cdots, P_s$ 有一个圈。因为 $A$ 是素矩阵，所以 $A^s$ 也是素矩阵，因而是不可约的。从 $\Gamma(A^s)$ 的每个结点 $P_1, \cdots, P_s$ 到任意其他结点，在 $\Gamma(A^s)$ 中有一条长至多为 $n - 1$ 的道路。首先绕着起点的圈走足够多次，便可以构造这样一条长恰好为 $n - 1$ 的道路。这说明 $Y_{11} > 0$ 和 $Y_{12} > 0$ 。

为了完成证明，算出

因为在后一个表示式中的 $X$ 子块的每一行至少含有一个非零元，又因为在后一个表示式中的每个 $Y$ 子块都是正的，所以整个分块矩阵是正的，且 $A^{n} \cdot (A^{s})^{n-1} > 0$ .

(8.5.8)的一个推论是 $\mathbf{H} \cdot \mathbf{W}$ Ielandt的著名结果，它给出了一般的素矩阵的本原指标的准确上界.

8.5.9 推论 如果 $A \in M_{n}$ 是非负矩阵，则 $A$ 是素矩阵，当且仅当 $A^{n^2} = 0$ .

证明：如果 $A$ 的任意幂是正的，则 $A$ 是素矩阵，所以，我们只要考虑逆命题。如果 $n = 1$ ，结论是显然的，因此假定 $n > 1$ 。如果 $A$ 是素矩阵，则 $A$ 是不可约的，且在 $\Gamma(A)$ 中有若干条回路。如果 $\Gamma(A)$ 中最短的回路有长 $n$ ，则 $\Gamma(A)$ 中的每条回路的长是 $n$ 的倍数，因而由定理(8.5.3)可知， $A$ 不能是素矩阵。于是 $\Gamma(A)$ 中最短回路的长是 $n - 1$ 或者更小，因此根据定理(8.5.8)有

Wielandt给出的一个例子(本节末习题4)说明，界 $\gamma (A)\leqslant n^{2} - 2n + 2$ 是所有对角元全为0的矩阵的最佳界．我们知道，如果所有主对角元是正的，则 $A$ 是素矩阵，当且仅当 $A^n >0$ 如果某些主对角元为正，可能不是全部主对角元为正，则Holladay和Varga的下述结果利用定理(8.5.8)中所采用的证明思想给出了关于本原指标的一个界.

8.5.10 定理 设 $A \in M_{n}$ 是不可约非负矩阵，且假定 $A$ 有 $d$ 个正主对角元， $1 \leqslant d \leqslant n$ 。则 $A^{2n - d - 1} > 0$ ；即 $\gamma(A) \leqslant 2n - d - 1$ 。

证明：在所述假设下， $A$ 一定是素矩阵，且在 $\Gamma(A)$ 中极小长回路有长1，实际上有 $d$ 条这样的回路。通过置换，可以假定 $P_{1},\dots,P_{d}$ 是 $\Gamma(A)$ 中的具有圈的结点。考虑 $A^{2n - d} = A^{n - d}(A^{1})^{n - 1}$ ，且记

其中， $X_{11},Y_{11}\in M_d$ ，而 $X_{22},Y_{22}\in M_{n_d}$ 采用在定理(8.5.8)证明中的相同证法来处理 $A^n$ 和 $(A^{\prime})^{n - 1}$ 的对应位置的子块便可证明，子块 $X_{11}$ 和 $X_{21}$ 的每一行至少含有一个非零元，且子块 $Y_{11}$ 和 $Y_{12}$ 是正的．由定理(8.5.8)中所运用的相同推理可知，乘积 $A^n\cdot A^{n - 1}$ 是正矩阵. □

练习 证明矩阵 $A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$ 是素矩阵。它的特征值是什么？计算由(8.5.9)和(8.5.10)给出的关于 $\gamma(A)$ 的界。 $\gamma(A)$ 的精确值是什么？

作为最后一个附注，我们指出，如果想证明一个给定的非负矩阵是素的，则可以验证该矩阵是不可约的且满足Wielandt条件(8.5.9)。在实际中出现的矩阵常常有特殊的结构，使我们容易看出相应的有向图是不是强连接的。另外，如果任一主对角元是正的，则该矩阵一定是素的。但是，如果矩阵很大，且没有特殊的结构或者其元素没有什么对称性，或者如果所有主对角元是零，则可能需要利用定理(8.4.1)或推论(8.5.9)来验证不可约性或素性。在这两种情形下，如果将所述矩阵反复平方若干次直到所得到的幂超过临界值（分别为 $n - 1$ 或 $n^2 - 2n + 2$ ）为止，则矩阵乘法所需要的次数将大大缩小。例如，如果 $n = 10$ ，则计算 $(I + A)^2$ ， $(I + A)^1$ ， $(I + A)^3$ 和 $(I + A)^{16}$ 足以验证不可约性；这是4次矩阵乘法而不是直接应用引理(8.4.1)所需要的8次乘法。类似的，如果 $A$ 是非负的，则计算 $A^2$ ， $A^4$ ， $A^8$ ， $A^{16}$ ， $A^{32}$ ， $A^{64}$ 和 $A^{128}$ 足以验证素性；这是7次矩阵乘法而不是81次乘法。注意在这些讨论中我们未指明利用了习题3。

习题

1. 写出定理(8.5.1)的证明.

2. 若 $A \in M_{n}$ 是非负素矩阵，证明对所有 $i$ ， $j = 1, \cdots, n$ 有 $\lim_{m \to \infty} [a_{ij}^{(m)}]^{1/m} = \rho(A)$ ，试把这个结果与推论(5.6.14)作一比较。可以省略掉有关素性假设的那一部分吗？

3. 证明，如果 $A \geqslant 0$ 和 $A^k > 0$ ，则 $A^m > 0$ 对所有 $m \geqslant k$ 成立。如果 $A$ 是素矩阵，则对任意正整数 $k$ ， $A^k$ 是素矩阵。但是，如果 $A$ 和 $B$ 都是素矩阵，则可能 $AB$ 不是素矩阵。提示：考虑 $\left[ \begin{array}{ll}1 & 1 \\ 1 & 0 \end{array} \right]$ 和 $\left[ \begin{array}{ll}0 & 1 \\ 1 & 1 \end{array} \right]$ 。

4. 试用 $\Gamma(A)$ 证明，对 $n \geqslant 3$ ，Wielandt 矩阵

是不可约素矩阵，然后证明 $A^{n^2 - 2n + 1}$ 的(1，1)元是零而 $A^{n^2 - 2n - 2} > 0$ ，提示：把 $A$ 看成作用在标准基 $\{e_1, \dots, e_n\}$ 上的线性变换．那么 $A: e_i \rightarrow ? A^{n-1}: e_i \rightarrow ? A^{(n-1)(n-1)}: e_1 \rightarrow ?$

1. 设 $A \in M_{n}$ 是不可约非负矩阵。证明，如果至少有一个主对角元是正的，则 $A$ 是素矩阵。证明这个充分条件对 $n = 2$ 是必要条件而对 $n \geqslant 3$ 则不是。

2. 设 $A = [a_{\eta}] \in M_n$ 是非负的，且假定 $a_{kk} > 0$ 对某个 $k = 1, 2, \dots, n$ 成立。证明 $\Lambda$ 的每个幂的 $k, k$ 元也是正的。如果 $a_{kk} = 0$ 而 $\Lambda^2$ 的 $k, k$ 元是正的， $A^3$ 的 $k, k$ 元是正的吗？

3. 详细验证本节未提出的简便算法.

4. 如果 $\Lambda$ 是任意幂等矩阵，则 $A = \lim_{m\to \infty}A^{m}$ 。证明，如果 $A$ 是非负的，不可约的和幂等的，则 $A$ 是秩1的正矩阵。

5. 给出例子说明，即使 $A \geqslant 0$ 不是素矩阵， $\lim_{m \to \infty} [\rho(A)^{-1} A]^{m}$ 仍可能存在。实际上， $A$ 可能是可约的，还可能有极大模重特征值。

6. 证明定理(8.5.1)的下述部分逆命题：如果 $A \in M_{n}$ 是非负矩阵和不可约矩阵，又如果 $\lim_{m \to \infty} [\rho(A)^{-1} A]^{m}$ 存在，则 $A$ 是素矩阵。提示：如果 $|\mu| = \rho(A)$ ， $\mu \neq \rho(A)$ ，且 $\Lambda z = \mu z$ ， $z \neq 0$ ，则 $[\rho(A)^{-1} A]^{m} z \rightarrow ?$

7. 证明. $A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ 是不可约的，但 $A^2$ 是可约的。这与(8.5.6)矛盾吗？

8. 给出一个不可约非负矩阵 $A \in M_{n}$ ，使得 $\lim_{m \to \infty} [\rho(A)^{-1} A]^{m}$ 不存在。

9. 如果 $\varepsilon > 0$ ，又如果 $A \in M_n$ 是非负不可约矩阵，证明 $A + \varepsilon I$ 是素矩阵。

10. 非负矩阵 $A = [a_{n}]$ 称为组合对称的，是指 $a_{n} > 0$ 当且仅当 $a_{p} > 0$ 对所有 $i, j = 1, \cdots, n$ 成立。证明，如果 $A$ 是组合对称的素矩阵，则 $A^{2n-2} > 0$ 。提示：考虑 $A^2$ 且利用（8.5.6）和（8.5.10）。你能给出关于 $\Gamma(A)$ 的回路结构的更多的信息来改进 $\gamma(A)$ 的界吗？提示：利用（8.5.8）。

11. 证明，如果 $A \in M_n$ 是非负的，不可约的和非奇异的，且 $n$ 是素数，则或者 (a) $A$ 是素矩阵，或者 (b) $A$ 的所有特征值有极大模且 $A$ 相似于 $x^n - \rho(A)^n = 0$ 的友矩阵。

12. 一种计算非负矩阵 $A \in M_{n}$ 的 Perron 向量和谱半径的方法是幂法：

$x^{(0)}$ 是任意正向量， $\sum_{i = 1}^{n}x_{i}^{(0)} = 1;$

$y^{(m + 1)} = Ax^{(m)}$ 对所有 $m = 0,1,2,\dots$ 成立；

522

如果 $A$ 是素矩阵，证明，向量 $x^{(m)}$ 的序列收敛于 $A$ 的（右）Perron 向量，而数 $\sum_{i=1}^{n} y_i^{(m+1)}$ 的序列收敛于 $A$ 的 Perron 根。其收敛速度如何？关于素性的假设是必要的吗？

1. 如果 $A \in M_{n}$ 是非负的，证明 $A$ 的素性只与零元的位置有关而与非零元的大小无关。

2. 如果 $A \in M_{n}$ 是非负的、不可约的和对称的，证明 $A$ 是素矩阵当且仅当 $A + \rho(A)I$ 是非奇异矩阵。特别是，如果 $A$ 是半正定矩阵，这个条件被满足。以0和1为元素的对称非负矩阵常常作为无向图的邻接矩阵而出现。

3. 如果 $A \in M_{n}$ 是素矩阵且 $k \geqslant \gamma(A)$ ，证明 $A^{k} > 0$

4. 给出定理(8.5.10)的证明细节.

5. 计算下列各矩阵的特征值和特征向量，并且按本章的基本概念（非负矩阵、不可约矩阵、素矩阵、正矩阵等）进行归类： $\left[ \begin{array}{ll}1 & 1\\ 1 & 1 \end{array} \right],\left[ \begin{array}{ll}0 & 1\\ 1 & 1 \end{array} \right],\left[ \begin{array}{ll}1 & 0\\ 1 & 1 \end{array} \right],\left[ \begin{array}{ll}1 & 0\\ 0 & 1 \end{array} \right],\left[ \begin{array}{ll}1 & 0\\ 0 & 0 \end{array} \right],\left[ \begin{array}{ll}0 & 1\\ 0 & 0 \end{array} \right],$ $\left[ \begin{array}{ll}0 & 0\\ 0 & 0 \end{array} \right]$ 这些矩阵为可能出现的各种可能性提供了好的实例.

6. 在定理(8.5.8)的证明中，证明 $X_{11}$ 和 $X_{12}$ 的每一列至少含有一个非零元。证明 $Y_{21} > 0$

进一步阅读 关于(8.5.4)中提到的Romanovsky定理的证明可参看V．Romanovsky,“Recherches sur les Chaines de Markoff，"Acta Math. 66(1936)，147-251.