一道出现在线代课后习题的组合矩阵论入门题

题目出处：王新茂《线性代数讲义》 第二章第四节习题16
由于王老师的讲义版本更新极快，这里放上本文参考的的版本是 2023-4-23版本 （讲义和源码都是开源的，因此我在个人网站内存了一份）
最新版本的pdf和源代码均可以在王老师的个人主页上找到（需接入USTC校园网）。

题目

先给出几个定义：

• 对于任意 , 若存在置换方阵 使得 , 其中 都是阶数 的方阵, 则 称为可约的, 否则 称为不可约的.
• 若 的元素都 , 则 称为非负矩阵.
• 对于非负矩阵 , 若存在正整数 使得 的元素都 , 则 称为本原的, 否则 称为非本原的.

设 是非负矩阵. 证明:

1. 是不可约的 存在正整数 使得 的元素都是正实数
   存在正实数 使得 的元素都是正实数.
2. 存在置换方阵 使得 是准上三角方阵, 其中每个准对角块都是不可约方阵.
3. 若 是本原的, 则 是不可约的.
4. 若 是非本原且不可约的, 则存在正整数 和置换方阵 , 使得 $$P^T A P=\left(\begin{array}{cccc} O & A_1 & & \\ & O & \ddots & \\ & & \ddots & A_{m-1} \\ A_m & & & O \end{array}\right)$$ 其中每个准对角块都是零方阵, 空白处元素都是

分析

在图论研究中使用矩阵方法是常有的事，为了完成这一道题的分析，我们需要先用图论语言清晰地理解题目中的概念的涵义。

在这道题中，对于非负矩阵 其中的任意一个元素来说，我们只区分其非零与否。容易想到这样的非负矩阵 可以对应一张有向图 ，记为 ， 当且仅当 到 存在有向边。在理解 中元素的含义之后，考察 的幂。 ，因此 中的元素表示 到 是否有长度为 的路径存在，同理 中的元素表示 到 是否有长度为 的路径存在。

接下来我们需要讨论另一个重要概念可约，在其之前我们需要知道变换 的含义是什么。

我们知道一个矩阵左乘一个置换矩阵相当于将其行向量做对应的置换，而将一个矩阵右乘一个置换矩阵相当于将其列向量做对应置换的逆置换。因此实际上在这个作用当中，我们只同时改变了 中行与列的标号，也就是只是对 中点的编号做了改变，并不改变这张图 的任何性质。

这样我们就能够观察出，一个矩阵 可约当且仅当 可以被分为两个部分，这两个部分只能从一侧到另一侧而不能反过来，也就是不强联通。因此我们就知道 不可约当且仅当 强连通。

最后需要分析的是本原的含义，一个矩阵 是本原的就说明在有向图 中一定存在一个 使得任意两个点可以通过恰好 步相互到达。

证明

若 是本原的, 则 是不可约的.

只需证明若 是可约的，那么 非本原。当 可约时，

$$P^T A P=\left(\begin{array}{cc}M_{11} & M_{12} \\ O & M_{22}\end{array}\right)$$

因此

$$P^T A^m P=\left(\begin{array}{cc}M_{11} ^ {m} & \ast \\ O &M_{22} ^ {m}\end{array}\right)$$

始终不是正的，因此 非本原。

是不可约的
对于任意 ，存在正整数 ，使得 的 元素
存在正整数 使得 的元素都是正实数
存在正实数 使得 的元素都是正实数.

(a) 第一个 事实上就是 强连通的等价表述。

假如存在这样的 和 满足使得 的任意次幂中 元素均等于 ，那我们取集合 显然集合 并不包含 ，这就表明 .

对于任意点 我们有 ，否则这与 的定义矛盾。于是只需要通过 将集合 的元素排在一起，就可以说明 是可约的。

(b) 先证明第二个，当 可约时，

$$P^T A P=\left(\begin{array}{cc}M_{11} & M_{12} \\ O & M_{22}\end{array}\right)$$

因此

$$P^T (I + A + \cdots + A^{k - 1}) P=\left(\begin{array}{cc}I + M_{11} + \cdots + M_{11} ^ {k-1} & \ast \\ O & I + M_{11} + \cdots + M_{22} ^ {k-1}\end{array}\right)$$

因此这不是正矩阵，故不存在这样的 （事实上由上面的结论这是显然的）

取 ，由于 强连通，因此任意两点 存在一条长度为 的路径，不妨假设这条路径是所有路径中最短的那一条，则根据抽屉原理可知 . 因此 ，这样就证明了结论。

(c) 再证明第三个，在此之前我们需要铺垫矩阵的度量和收敛的定义。

定义矩阵 的范数为 ，再给出矩阵空间上的度量 ，由此给出矩阵收敛的定义。可以证明在这个度量下，矩阵收敛当且仅当每一个分量收敛。

我们观察到当 时， 因此此时 ，在此基础上仿照前面即可得证。

存在置换方阵 使得 是准上三角方阵, 其中每个准对角块都是不可约方阵.

本题实际上是在证明强连通分量的存在性，可以直接使用Tarjan算法构造性证明，这里不详细叙述。

若 是非本原且不可约的, 则存在正整数 和置换方阵 , 使得

$$P^T A P=\left(\begin{array}{cccc} O & A_1 & & \\ & O & \ddots & \\ & & \ddots & A_{m-1} \\ A_m & & & O \end{array}\right)$$

其中每个准对角块都是零方阵, 空白处元素都是

观察结果的形式发现，我们需要证明的就是整张图当中环的大小都是 的倍数。

设 ，也就是经过点 的所有环的大小，这个集合当中必然存在一个最小元 ，容易证明 中所有元素都是 的整数倍。

考虑图中任意两个点 由于 不可约，我们知道必然存在 满足 ，对于任意的 有 ，也就是说 . 由于这一点对任意 成立这也就给出了 ，不妨记为 .

任意两点间不同路径长度之差必然为 的整数倍，我们记 表示 到 的最短路的长度模 的值，我们容易证明 。定义等价关系 当且仅当 ，容易证明这样的等价关系的传递性，得到 个等价类 . 通过变换 将等价类排列在一起，容易证明此时得到的矩阵满足我们需要的形式。

后记

讲道理这道题完完全全就是组合矩阵论的观点，跟线性代数关系不大。
从矩阵的角度来讲，这道题介绍了矩阵在图论中应用的基本方法和一些概念，算是在介绍矩阵这个数学对象在应用层面上的价值吧。

阅读资料

• 《组合矩阵论》 - 柳柏濂
• 《线性代数讲义》 - 王新茂