8.7 随机矩阵和双随机矩阵

如果非负矩阵 $A \in M_{n}$ 的所有行和是 1, 则具有这一性质的矩阵称为 (行) 随机矩阵, 这是因为每一行可以看成有 $n$ 个点的样本空间上的离散概率分布. 列随机矩阵是行随机矩阵的转置; 这样的矩阵常常出现在 (8.0) 节中所讨论的城市间的人口流动模型中. 随机矩阵还出现在 Markov 链的研究中以及象经济学和运筹学这类领域的各种各样的数学模型问题中.

$M_{n}$ 中的随机矩阵的集合是紧凸集，并且具有简单而又重要的性质。如果用 $e \in \mathbb{R}^{n}$ 表示所有分量为 +1 的向量，非负矩阵 $A \in M_{n}$ 是随机矩阵，当且仅当 $A e = e$ 。所以， $M_{n}$ 中的随机矩阵构成一个容易识别的非负矩阵族，且它们有一个特殊的正的公共特征向量。有正特征向量的非负矩阵具有许多特殊性质[例如，(8.1.30)，(8.1.31)和(8.1.33)]，因此所有随机矩阵具有这些性质。

如果随机矩阵 $A \in M_{n}$ 的转置 $A^{T}$ 也是随机矩阵，就称 $A$ 是双随机矩阵；所有行和与列和都是 +1。双随机矩阵的集合也是 $M_{n}$ 中的紧凸集，显然，非负矩阵 $A \in M_{n}$ 是双随机矩阵，当且仅当 $Ae = e$ 且 $e^{\prime}A = e^{T}$ 。在 (6.3.5) 中已经遇到过一种双随机矩阵形式，即正交随机矩阵 $A = \left[ \begin{array}{lll} |u_{ij}| & \end{array} \right]$ ，其中 $U = [u_{ij}] \in M_{n}$ 是酉矩阵。 $A$ 的行和与列和都是 +1 可从 $U$ 的行与列都是 Euclid 单位向量的事实推出。

双随机矩阵的另一个例子是置换矩阵组成的集合(群). 由Birkhoff定理可知, 任一双随机矩阵是有限多个置换矩阵的凸组合, 因而置换矩阵实际上是基本的和标准的双随机矩阵. 我们

给出的关于Birkhoff定理的证明依赖于以下事实(见附录B)：紧凸集 $S$ 中的每个点是 $S$ 的诸端点的凸组合，我们将证明，双随机矩阵的集合的端点恰好是置换矩阵.

8.7.1 定理（Birkhoff）矩阵 $A \in M_{n}$ 是双随机矩阵，当且仅当对某个 $N < \infty$ ，存在置换矩阵 $P_{1}, \cdots, P_{N} \in M_{n}$ 和正纯量 $\alpha_{1}, \cdots, \alpha_{N} \in \mathbb{R}$ ，使得 $\alpha_{1} + \cdots + \alpha_{N} = 1$ 且 $A = \alpha_{1}P_{1} + \cdots + \alpha_{N}P_{N}$ .

证明：条件的充分性是显然的；我们只需证明其必要性。设 $A = [a_{ij}] \in M_n$ 是给定的双随机矩阵。如果 $A$ 是置换矩阵，则在它的每一行和每一列恰好有一个元素 $+1$ ，而所有其他元均为 0。如果可以记 $A = \alpha_1 B + \alpha_2 C$ ，其中， $0 < \alpha_1, \alpha_2 < 1, \alpha_1 + \alpha_2 = 1$ ，且 $B, C$ 是双随机矩阵，则因为 $\alpha_1$ 和 $\alpha_2$ 都是非零元且 $b_{ij}, c_{ij}$ 是非负元，所以与 $A$ 的 0 元 $a_{ij} = 0$ 相对应的 $B$ 和 $C$ 的每个元一定适合 $0 = a_{ij} = \alpha_1 b_{ij} \mid \alpha_2 c_{ij}$ ，因而 $b_{ij} = c_{ij} = 0$ 。由于 $B$ 和 $C$ 是双随机矩阵，所以它们的各个行和是 $+1$ ，因而各非零元一定都是 $+1$ ，且与 $A$ 的各非零元处在相同的位置；即 $A = B = C$ 。这就证明了每个置换矩阵是双随机矩阵集合的端点。

另一方面，如果 $A$ 不是置换矩阵，则至少有 $A$ 的一行，例如第 $i$ 行，它至少含两个非零元。在该行中选取任一非零元 $a_{i_1i_2}$ ，因为在第 $i$ 行中至少有两个非零元且该行中的所有（非负）元之和是 $+1$ ，所以 $a_{i_1i_2}$ 一定适合 $0 < a_{i_1i_2} < 1$ 。由于 $0 < a_{i_1i_2} < 1$ ，且第 $i_2$ 列的所有（非零）元之和是 $+1$ ，所以在 $a_{i_1i_2}$ 所在的同一列，一定有另一个非零元 $a_{i_3i_2}$ ， $i_3 \neq i_1$ ，且 $0 < a_{i_3i_2} < 1$ 。根据同样的推理，在 $a_{i_3i_2}$ 所在的同一行，另有一个非零元 $a_{i_3i_4}$ ， $i_4 \neq i_2$ ，且 $0 < a_{i_3i_4} < 1$ 。如果把这个过程继续下去，且对用这种方式依次选出的各元加上标号，则经有限多步，原来选定的元素 $a_{ij}$ 会首次再被选到。从第一次出现元素 $a_{ij}$ 直到第二次再出现 $a_{ij}$ 的过程中，诸元素组成的序列（包括第一次出现的元 $a_{ij}$ ，但不包括第二次出现的元 $a_{ij}$ ）是 $A$ 的元素的有限有序序列，且其中每对相邻元在同一行或同一列交替出现；设 $a_{ij}$ 是这个序列中的最小（正）元。设 $B \in M_n$ 是这样一个矩阵，在 $B$ 中， $+1$ 出现在与序列的第一个元 $a_{ij}$ 相对应的位置， $-1$ 出现在与序列的第二个元相对应的位置， $+1$ 出现在与序列的第三个元相对应的位置，依此类推，交替地选取 $\pm 1$ 。 $B$ 的所有其他元是 0。注意， $B$ 的所有行和与列和是 0。设 $A_i = A + a_{i_j}B$ 及 $A_j = A - a_{i_j}B$ 。注意， $A_i$ 与 $A$ 都是非负矩阵（因为 $a_{i_j}$ 的极小性），且它的行和与列和是 $+1$ （因为 $B$ 的行和与列和是 0），所以 $A_i$ 和 $A$ 是双随机矩阵。由于 $A = \frac{1}{2} A_1 + \frac{1}{2} A$ ，且 $A_i \neq A$ ，我们得出 $A$ 不是双随机矩阵集合的端点。

刚才给出的证明说明，一个给定的矩阵是双随机矩阵的紧凸集的端点，当且仅当它是置换矩阵。从紧凸集的每个点是诸端点的凸组合的事实可知定理成立。

因为在 $M_{n}$ 中恰好有 $n!$ 个互不相同的置换矩阵，Birkhoff定理保证，任意双随机矩阵可以表示成至多 $N = n!$ 个置换矩阵的凸组合。更细致的分析说明，所需置换矩阵不超过 $N - n^{2} - 2n + 2$ 个。

习题

1. 设 $A \in M_n$ 是非零非负矩阵，且有正特征向量 $x = [x_i]$ ，又设 $D = \operatorname{diag}(x_1, \cdots, x_n)$ ，证明 $\rho = \rho(A) > 0$ ，由(8.1.30)可知 $Ax = \rho x$ ，且 $ADe = \rho De$ ，其中 $e \in \mathbb{R}^n$ 的所有元是 $+1$ ，由此得出， $A$ （经具有正主对角元的对角相似矩阵）相似于随机矩阵的正倍数[即 $\rho(A)$ ]。这个论断使我

们把许多有关具有正特征向量的非负矩阵的问题化简成有关随机矩阵的问题.

1. 证明 $M_{n}$ 中的随机矩阵的集合与双随机矩阵的集合是紧凸集.

2. 证明 $M_{n}$ 中随机矩阵的集合与双随机矩阵的集合各自在矩阵乘法下构成一个半群；即如果 $A, B \in M_{n}$ 是（双）随机矩阵，则 $AB$ 是（双）随机矩阵。

3. 证明，非负矩阵 $A \in M_{n}$ 是随机矩阵，当且仅当 $Ae = e$

4. 证明 $2 \times 2$ 双随机矩阵是有相同主对角元的对称矩阵。

5. (a) 试用(8.7.1)的证明中所采用的想法但不用附录B的结果，给出(8.7.1)的另一个直接证明，(b)然后给出一个算法，把一个双随机矩阵分解为置换矩阵的一个凸组合。提示：如果A不是置换矩阵，利用证明中所表述的诸元素组成的序列作一个置换矩阵，从A减去这个置换矩阵的正数倍就得到一个有相同行和与列和的非负矩阵，且它至少有一个非零元。于是，在这个矩阵上重复上述过程且继续做下去。

6. 证明(8.7.1)中的分解是不唯一的。

7. 如果双随机矩阵 $A$ 是可约的，证明 $A$ 实际上置换相似于形如 $\left[ \begin{array}{cc}A_2 & 0\\ 0 & A_1 \end{array} \right]$ 的矩阵．关于 $A_{1}$ 和 $A_{2}$ 能说些什么？

进一步阅读 定理(8.7.1)的证明思想取自B. Saunders and H. Schneider, “Applications of the Gordon-Stiemke Theorem in Combinatorial Matrix Theory,” SIAM Rev. 21(1979), 528-541, 从中可找到有关的事实。每个双随机矩阵 $A \in M_{n}$ 至少是 $n^{2} - 2n + 2$ 置换矩阵的一个凸组合，该结果的讨论可参看M. Marcus and R. Ree, “Diagonals of Doubly Stochastic Matrices,” Quart. J. Math Oxford, Ser. 2, 10(1959), 295-302.