对不可约矩阵判定法的探讨

这个问题是我最近在学习计算方法时遇到的。总之，我需要一种方法来快速判定一个矩阵是否是不可约的，于是我上网搜到这样一个方法：

把目标矩阵作为邻接表作出有向图，如果这个有向图是强联通的，则原矩阵不可约。

再看不可约矩阵的严谨定义：

若不存在一个置换矩阵$P$，使得 $P^{T}AP$ 可以被写成严格的分块上三角形式，即：

$$\left(\begin{array}{ll}B& C\\ 0& D\end{array}\right)$$

则原矩阵$A$不可约。

这就很有意思了，从字面上似乎完全看不出这一坨定义和“强联通”这件事有任何的联系。下面给出一个思路来建立这个联系（我不会写出严格的数学证明，如果理解了这种思路很容易写出证明）。

关于“分块上三角”

当一个矩阵具有分块上三角的结构，其实就隐含了一组单向影响：$B$块可以影响到$D$区域，但是$D$块只能影响自己，无法对$B$产生影响。

这是因为，矩阵中用$A_{ij}$表示从状态$i$影响到状态$j$，假设一个位于$B$内的元素$A_{ij}$想要影响一个$D$内的元素$A_{mn}$，它只需要从$C$中找到元素$A_{in}$作为跳板就可以。但是如果$D$中的元素想要做相同的事就不行，因为它本来要用作跳板的区域全是0，一乘就全没了。

这就大概解释了“分块上三角”和“两个独立的区域”的关系。

强联通与矩阵

其实很容易能想到强联通和“独立区域”的一层模糊关系，一个图如果是非强联通的，就也可以说它内部有若干个“独立区域”。但是，这样的说法很难和矩阵扯上关系。

如上面所说，矩阵中的每个元素都是状态转移的标志，“分块上三角”表示有一组状态永远也转移不到另一组状态。其实这里可以写得清楚一些，假设最后的分块上三角矩阵是：

$$\left(\begin{array}{llllll}{a}_{00}& a_{01}& ...& a_{0k}& ...& a_{0n}\\ a_{10}& a_{11}& ...& a_{1k}& ...& a_{1n}\\ ⋮& ⋮& & ⋮& & ⋮\\ a_{k0}& a_{k1}& ...& a_{kk}& ...& a_{kn}\\ ⋮& ⋮& & ⋮& & ⋮\\ a_{n0}& a_{n1}& ...& a_{nk}& ...& a_{nn}\end{array}\right)$$

其中左下角的k*k大小的区域全0。那么它就代表，在$[k+1,n]$中，所有的状态都无法影响到外部，即这个子集被孤立了。

既然如此，如果原矩阵中存在孤立状态，就一定可以通过一种变换把它们集中起来放到$D$的位置，而这种变换正是定义里说的$P^{T}AP$。

再想想连通图，如果一个图强联通，就说明从任意一个状态出发，都可以到达任意一个其它状态，这样一来就不可能分出一个“孤立子集”，你无论怎么变也不可能变出上三角来，所以不存在这样的置换矩阵$P$。

到此，不可约矩阵与强连通图的关系就很清晰了。