不可约矩阵

概述

非负矩阵 $A \in \mathbb{R}^{n \times n}{\geq 0}$ 称为不可约（irreducible），若不存在非空真子集 $S \subsetneq {1,\ldots,n}$ 使得 $a{ij} = 0$ 对所有 $i \in S, j \notin S$。等价地，$A$ 的关联有向图（节点 $i \to j$ 当 $a_{ij} > 0$）是强连通的——任意节点可沿有向边到达其他任意节点。不可约性是格奥尔格·弗罗贝尼乌斯 1912年引入的核心概念（原文称"unzerlegbar"），是Perron-Frobenius定理对非负矩阵成立的必要条件。

关键内容

等价定义

$A \in \mathbb{R}^{n \times n}_{\geq 0}$ 不可约 $\iff$ 以下任一等价条件成立：

代数定义：不存在置换矩阵 $P$ 使 $PAP^T = \begin{pmatrix} B & C \ 0 & D \end{pmatrix}$（分块上三角）
图论定义：$A$ 的关联有向图强连通
幂次定义：对任意 $i, j$，存在 $k \geq 0$ 使 $(A^k)_{ij} > 0$（即通过若干步可从 $i$ 到达 $j$）
等价于：$(I + A)^{n-1}$ 的所有元素严格为正

可约性分类

可约矩阵可通过行列置换化为分块上三角形式：

$$PAP^T = \begin{pmatrix} A_{11} & A_{12} & \cdots \ 0 & A_{22} & \cdots \ \vdots & & \ddots \end{pmatrix}$$

其中对角块 $A_{11}, A_{22}, \ldots$ 均为不可约子矩阵（或 $1 \times 1$ 零块）。这一分解揭示了可约矩阵的层级结构，为分析一般非负矩阵提供了统一框架。

不可约矩阵的谱性质

对不可约非负矩阵 $A$： - Perron根存在：谱半径 $r = \rho(A) > 0$ 是简单特征值 - 正特征向量：$r$ 对应的左右特征向量均严格正 - 周期性（Frobenius）：若有向图中所有闭回路长度的最大公因数为 $h$，则模等于 $r$ 的特征值恰好有 $h$ 个，均匀分布于圆周

本原矩阵（Primitive Matrix）

不可约矩阵的一个重要子类：

定义：不可约非负矩阵 $A$ 称为本原（primitive / primitive），若其周期 $h = 1$，即有向图中所有闭回路长度的最大公因数为1。

等价条件：$\exists m$ 使 $A^m$ 的所有元素严格为正。

与正矩阵的关系：正矩阵（$a_{ij} > 0$）$\Rightarrow$ 本原矩阵 $\Rightarrow$ 不可约矩阵，但反向不成立。

Wielandt上界：本原矩阵 $A$（$n \times n$）使 $A^m$ 全正的最小 $m$ 满足 $m \leq n^2 - 2n + 2$。

周期指数 $h$ 的计算

对不可约矩阵，周期 $h$ 等于关联有向图的周期——图中所有有向闭回路长度的最大公因数。

矩阵特征	周期 $h$	谱结构
正矩阵	1（本原）	$r$ 唯一最大特征值
不可约，$h=1$	本原	$r$ 唯一最大特征值
不可约，$h=2$	二周期	${r, -r}$ 为最大模特征值
不可约，$h=k$	$k$ 周期	$h$ 个特征值在圆周等距分布

应用意义

Markov链：不可约矩阵 ↔ 不可约Markov链（任意状态可到达任意状态）；本原矩阵 ↔ 遍历（aperiodic）Markov链，收敛到唯一平稳分布。

PageRank：Google 矩阵须为不可约本原矩阵，才能保证Perron特征向量的唯一性（引入阻尼因子 $\alpha$ 的目的之一）。

正系统稳定性：不可约正系统的稳定性条件（$\rho(A) < 1$）可精确刻画，可约情形则需逐块分析。

谱聚类：图的Laplacian矩阵不可约当且仅当图连通，这决定了谱聚类方法能否正确分离社区结构。

来源

raw/books/矩阵分析/10_frobenius_nonnegative_matrices_1912.md