OI-wiki 线性代数指南Jordan 标准型与 Jordan 分解的完整推导【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文是 OI-wiki 线性代数专题中关于Jordan若尔当标准型与Jordan 分解的深度指南。核心内容包括三条主线把任意线性变换分解为「可对角化部分 幂零部分」的 Jordan 分解、把矩阵化为近似对角的标准形Jordan 标准型所需的 λ 矩阵与 Smith 标准型工具以及贯穿其中的初等因子、不变因子与最小多项式判据。读完本文你将掌握 Jordan 分解的存在性、唯一性证明思路能够用初等变换求解 λ 矩阵的 Smith 标准型并能从初等因子出发写出任意矩阵的 Jordan 标准型、判断矩阵可否对角化。本文内容以 jordan.md 为骨架并援引 OI-wiki 线性代数分类下的 对角化、特征多项式、初等变换 等篇目作为前置与佐证。前置知识从特征理论到幂零结构Jordan 理论并不是孤立出现的它建立在 OI-wiki 特征理论与对角化篇目char-poly.md、diagonalization.md的完整概念链条之上特征矩阵与特征多项式对 $n$ 阶矩阵 $A$矩阵 $\lambda I-A$ 称为 $A$ 的特征矩阵其行列式 $f(\lambda)|\lambda I-A|$ 是 $n$ 次首一多项式根恰为 $A$ 的全部特征值最小多项式能零化 $A$ 的次数最低的首一多项式 $m_A(\lambda)$它整除一切零化多项式含特征多项式且与特征多项式在不计重数时根相同准素分解若最小多项式分解为 $m_A(\lambda){(\lambda-\lambda_1)}^{r_1}{(\lambda-\lambda_2)}^{r_2}\cdots{(\lambda-\lambda_k)}^{r_k}$则空间可分解为不变子空间的直和 $VV_1\oplus V_2\oplus\cdots\oplus V_k$其中 $V_iN\left({(A-\lambda_i I)}^{r_i}\right)$幂零变换与循环子空间满足 $T^r0$ 的变换称为幂零变换由某个向量 $\xi_0$ 及其像链 $\xi_0,T(\xi_0),\cdots,T^{r-1}(\xi_0)$ 张成的子空间称为 $T$ 循环子空间任一幂零变换的循环子空间关于倒序循环基的矩阵恰为一个幂零 Jordan 块。直观地说可对角化要求「几何重数 代数重数」即特征向量足够多到张成全空间而 Jordan 标准型放宽了这一要求——当特征向量不足 $n$ 个时用「主对角线为特征值、上方斜线为 $1$」的 Jordan 块来捕获幂零方向的细节。这也是为什么 Jordan 理论总与幂零矩阵的标准形式绑定出现。Jordan 分解任意线性变换 可对角化部分 幂零部分由射影变换构造分解设 $T$ 是 $n$ 维空间 $V$ 上的一个线性变换其最小多项式为$$ m_A(\lambda){(\lambda-\lambda_1)}^{r_1}{(\lambda-\lambda_2)}^{r_2}\cdots{(\lambda-\lambda_k)}^{r_k} $$由准素分解空间 $V$ 可以分解为子空间的直和$$ VV_1\oplus V_2\oplus\cdots\oplus V_k $$其中 $V_iN\left({(A-\lambda_i I)}^{r_i}\right)$式中 $A$ 为 $T$ 对应的矩阵这些子空间都在 $T$ 作用下不变。令变换 $T_i$ 为 $V$ 在子空间 $V_i$ 上的射影投影即构造多项式 $u_i(T)$ 使得$T_iu_i(T)\dfrac{m_A(T)}{{(T-\lambda_i T_e)}^{r_i}}$$T_1T_2\cdotsT_kT_e$式中 $T_e$ 表示空间 $V$ 的恒等变换。于是射影 $T_i$ 具有如下两条关键性质变换 $T_i$ 在空间 $V_i$ 上的限制 ${T_i|}_{V_i}$ 为空间 $V_i$ 的恒等变换如果 $i$ 与 $j$ 不相等变换 $T_i$ 在空间 $V_j$ 上的限制 ${T_i|}_{V_j}$ 为空间 $V_j$ 的零变换。于是变换 $T_i$ 将空间 $V$ 的每一个向量 $\xi$ 映射为它在空间 $V_i$ 中的分量 $\xi_i$。这组射影是后续一切构造的地基。可对角化部分与幂零部分构造变换$$ T_D\lambda_1 T_1\lambda_2 T_2\cdots\lambda_k T_k $$由于每一个变换 $T_i$ 都是变换 $T$ 的一个多项式所以变换 $T_D$ 也是变换 $T$ 的一个多项式于是每一个子空间 $V_i$ 在变换 $T_D$ 下不变。由上述等式可知变换 $T_D$ 在子空间 $V_i$ 上的限制 ${T_D|}_{V_i}$ 是子空间 $V_i$ 的一个位似数乘位似系数为 $\lambda_i$。因此变换 $T_D$ 可以对角化——它在每个 $V_i$ 上都只是按特征值 $\lambda_i$ 缩放。再构造$$ T_NT-T_D $$于是变换 $T_N$ 也是变换 $T$ 的一个多项式所以每一个子空间 $V_i$ 在变换 $T_N$ 下不变。对于子空间 $V_i$ 中的任意向量 $\xi_i$有$$ {T_N}^{r_i}(\xi_i){T-T_D}^{r_i}(\xi_i){T-\lambda_i T_i}^{r_i}(\xi_i)0 $$令 $r$ 为全体 $r_i$ 的最大值那么对于空间 $V$ 中的任意向量 $\xi$变换 $T_N$ 的 $r$ 次方将向量 $\xi$ 映射至零向量。因此变换 $T_N$ 是一个幂零变换。分解的存在性与唯一性这样空间 $V$ 的每一个变换 $T$ 都可以写成$$ TT_DT_N $$其中 $T_D$ 可以对角化而 $T_N$ 是一个幂零变换。因为 $T_D$ 和 $T_N$ 都是变换 $T$ 的多项式所以它们的乘积可交换$$ T_DT_NT_NT_D $$这里用到两个关键定理定理可交换的可对角化变换可同时对角化设 $T_1$ 和 $T_2$ 是空间 $V$ 的两个可对角化变换且 $T_1T_2T_2T_1$那么存在一个基使得 $T_1$ 和 $T_2$ 关于这同一个基的矩阵是对角形式。定理Jordan 分解设 $T$ 是 $n$ 维空间 $V$ 上的一个线性变换那么存在一个可对角化变换 $T_D$ 和一个幂零变换 $T_N$使得$TT_DT_N$$T_DT_NT_NT_D$它们都是变换 $T$ 的多项式并且它们由变换 $T$ 唯一确定。该定理给出关于变换 $T$ 的分解称为 $T$ 的若尔当Jordan分解$T_D$ 叫做 $T$ 的可对角化部分$T_N$ 叫做 $T$ 的幂零部分。同样地有矩阵的 Jordan 分解定理矩阵的 Jordan 分解设 $A$ 是一个 $n$ 阶矩阵那么存在一个可对角化矩阵 $D$ 和一个幂零矩阵 $N$使得$ADN$$DNND$它们都是矩阵 $A$ 的多项式并且它们由矩阵 $A$ 唯一确定。该定理给出关于矩阵 $A$ 的分解称为 $A$ 的若尔当Jordan分解$D$ 叫做 $A$ 的可对角化部分$N$ 叫做 $A$ 的幂零部分。关于幂零变换的循环子空间分解与幂零 Jordan 块以及「$V$ 分解为 $T$ 循环子空间的方法由 $T$ 唯一确定按维数降序 $r_1\geq\cdots\geq r_S$」等前置结论可进一步阅读 diagonalization.md 的幂零矩阵一节。λ 矩阵把矩阵放进多项式环要显式地求出 Jordan 标准型仅靠线性变换层面的存在性论证还不够需要一套能把矩阵「加工」成标准形的代数工具。为此引入含有变元参量 $\lambda$ 的更广义的矩阵——它不仅仅是一个数表讨论范围相较单纯由数构成的矩阵更加广泛。对于 λ 矩阵对应空间相应的域变为含有一个变元 $\lambda$ 的有理式域。以 $\lambda$ 的多项式为元素的矩阵称为 λ 矩阵记为 $A(\lambda)$。由于多项式域包含数域数字矩阵是特殊的 λ 矩阵数字矩阵 $A$ 的特征矩阵 $\lambda I-A$ 是一种 λ 矩阵——这正是 λ 矩阵理论与矩阵相似理论之间的桥梁。λ 矩阵的初等变换对于 λ 矩阵同样可以定义加减法、乘法、初等变换、秩。对于 λ 方阵同样可以定义行列式、余子式、代数余子式。对于 λ 矩阵初等变换与数阵大多相同仅将倍加变换改为这里以行变换为例用 $\lambda$ 的多项式 $\varphi(\lambda)$ 乘某行并加到另一行上。注意倍乘变换不进行修改。这是因为倍加变换不改变行列式而倍乘变换改变行列式。为了保持多项式域的秩的性质行列式只能在数域上进行改变即倍乘只允许乘非零常数不允许乘非常数的多项式。相应的初等矩阵也一并进行修改。易见三种初等阵的行列式均为非零常数因此均为满秩。所以它们左乘或右乘不改变 λ 矩阵的秩。若 $A(\lambda)$ 经过有限次初等变换变为 $B(\lambda)$则称 $A(\lambda)$ 和 $B(\lambda)$等价。对于 λ 矩阵如果等价则秩相同反之则不然这与数字矩阵有区别数字矩阵同秩即等价λ 矩阵则需要更强条件。数字矩阵上的初等矩阵、初等变换与行列式性质可对照 elementary-operations.md 复习。Smith 标准型与不变因子标准型的形状定理设 λ 矩阵的秩是 $r$则 $A(\lambda)$ 一定等价于分块形$$ \begin{pmatrix} D(\lambda) 0\ 0 0\ \end{pmatrix} $$其中$$ D(\lambda)\begin{pmatrix} d_1(\lambda) \ \ddots \ d_r(\lambda)\ \end{pmatrix} $$每一个 $d_i(\lambda)$ 是一个首 $1$ 多项式并且相邻两个多项式有整除关系 $d_i(\lambda)|d_{i1}(\lambda)$。称此标准型为Smith 标准型称 $d_i(\lambda)$ 为不变因子。求解方法具体求解 Smith 标准型的办法是从左上角到右下角进行消元每次左上角的元素是右下方剩余的全体多项式的最大公因式并借助左上角的元素将该行该列全部消为 $0$。定理条件 $A(\lambda)$ 和 $B(\lambda)$ 等价等价于条件 $A(\lambda)$ 和 $B(\lambda)$ 拥有完全一样的不变因子。也就是说不变因子完全刻画了 λ 矩阵的等价类是 λ 矩阵的「完全不变量」。初等因子把不变因子打散由代数基本定理设 $A(\lambda)$ 的不变因子 $d_1(\lambda),d_2(\lambda),\cdots,d_m(\lambda)$ 的分解为$$ d_i(\lambda){(\lambda-\lambda_1)}^{e_{i1}}{(\lambda-\lambda_2)}^{e_{i2}}\cdots{(\lambda-\lambda_S)}^{e_{iS}} $$其中 $\lambda_1,\cdots,\lambda_S$ 互不相同。由于 $d_i(\lambda)|d_{i1}(\lambda)$因此指数 $e_{1j},e_{2j},\cdots,e_{mj}$ 递增并且最后一项 $d_m(\lambda)$ 的各项指数均非零。上式中指数大于零的全部因子统称为 $A(\lambda)$ 的初等因子。注意初等因子计重数如果对于某个 $j$指数 $e_{ij}$ 出现了若干次则对应的初等因子 ${(\lambda-\lambda_j)}^{e_{ij}}$ 也应当出现相应次数。之前的定理说明$A(\lambda)$ 与 $B(\lambda)$ 等价等价于它们拥有完全一致的不变因子。不变因子完全相同自然初等因子也完全相同但是反之则不然。事实上定理$A(\lambda)$ 与 $B(\lambda)$ 不变因子完全相同等价于初等因子和秩均完全相同。于是「初等因子和秩均完全相同」也成为判断 λ 矩阵等价性的条件。在初等变换的时候也可以先将 $A(\lambda)$ 变换为对角阵再求出初等因子和秩再求出不变因子得到标准型。有结论定理设 $A(\lambda)$ 等价于对角阵$$ \operatorname{diag}{f_1(\lambda),f_2(\lambda),\cdots,f_r(\lambda),0,\cdots,0} $$那么 $f_1(\lambda),f_2(\lambda),\cdots,f_r(\lambda)$ 的全体一次因子的幂 ${(\lambda-\lambda_j)}^{e_{ij}}$构成 $A(\lambda)$ 的初等因子。由初等因子和秩构造不变因子的具体方法为先将初等因子按照因式分类排成表格把同类因式进行降幂排列放到同一行各类因式的最高次幂放到一列把列数用 $1$ 补齐至秩 $r$那么每一列的乘积构成一个不变因子。这是一条非常实用的手工演算流程。在特征矩阵中的应用如果 $A$ 与 $B$ 是数阵那么它们的特征矩阵是 λ 矩阵。有结论定理条件数阵 $A$ 与 $B$ 相似等价于条件特征矩阵 $\lambda I-A$ 和 $\lambda I-B$ 等价。由于特征矩阵 $\lambda I-A$ 只在主对角线含有 $n$ 个 $\lambda$所以秩为 $n$。由上述推理同型的数阵的特征矩阵的秩始终相等于是有等价性数阵 $A$ 与 $B$ 相似等价于特征矩阵 $\lambda I-A$ 和 $\lambda I-B$ 有完全相同的初等因子。对于特征矩阵 $\lambda I-A$初等变换保持等价性所以不改变秩。观察三种初等变换由于唯一被改写的倍加变换不改变行列式事实上三种初等变换仅对行列式的结果多项式改变常数倍因此不改变行列式的结果多项式的因式分解与次数。因此特征矩阵 $\lambda I-A$ 的行列式为 $n$ 次多项式初等变换化为 Smith 标准型后由于秩为 $n$行列式就是主对角线全体不变因子的乘积也等于全体初等因子的乘积。因此特征矩阵 $\lambda I-A$ 的全体初等因子的次数之和等于 $n$。Jordan 标准型近似对角化的终极标准形Jordan 块与 Jordan 标准型的定义矩阵$$ \begin{pmatrix} \lambda 1 0 \cdots 0 0\ 0 \lambda 1 \cdots 0 0\ 0 0 \lambda \cdots 0 0\ \vdots \vdots \vdots \vdots \vdots\ 0 0 0 \cdots \lambda 1\ 0 0 0 \cdots 0 \lambda\ \end{pmatrix} $$主对角线上的元素都是 $\lambda$紧邻主对角线上方的元素都是 $1$其余位置都是 $0$叫做属于 $\lambda$ 的一个 Jordan 矩阵或称 Jordan 块。显然幂零 Jordan 矩阵是 Jordan 矩阵的特例即 $\lambda$ 为 $0$ 的情形——这也与 Jordan 分解中「幂零部分」的构造一一对应。形如$$ \begin{pmatrix} J_1 0\ J_2 \ \ddots \ 0 J_m\ \end{pmatrix} $$的 $n$ 阶矩阵其中每一个 $J_i$ 都是一个 Jordan 块叫做一个Jordan 标准型。存在性定理定理设 $T$ 是 $n$ 维空间 $V$ 的一个变换$\lambda_1,\cdots,\lambda_k$ 是 $T$ 的一切互不相同的特征值那么存在一个基使得 $T$ 关于这个基的矩阵有形状$$ \begin{pmatrix} B_1 0\ B_2 \ \ddots \ 0 B_k\ \end{pmatrix} $$其中$$ B_i\begin{pmatrix} J_{i1} 0\ J_{i2} \ \ddots \ 0 J_{is_i}\ \end{pmatrix} $$其中 $J_{i1},\cdots,J_{is_i}$ 都是属于 $\lambda_i$ 的 Jordan 块。证明思路这也是全文最具启发性的部分逐层拼接如下准素分解。根据最小多项式 $m_A(\lambda){(\lambda-\lambda_1)}^{r_1}\cdots{(\lambda-\lambda_k)}^{r_k}$ 有准素分解 $VV_1\oplus V_2\oplus\cdots\oplus V_k$其中 $V_iN\left({(A-\lambda_i I)}^{r_i}\right)$$A$ 为 $T$ 对应的矩阵。逐子空间处理。令变换 $S_i$ 为 $T$ 在 $V_i$ 上的限制 ${T|}{V_i}$接下来对每一个 $S_i$ 进行 Jordan 分解。记 $T_e$ 为 $V$ 上的恒等变换记 $T_i$ 为 $S_i$ 的 Jordan 分解中的幂零部分$S_i\lambda_i T_eT_i$。于是 $T_i$ 为子空间 $V_i$ 的一个幂零变换事实上也是 $T-\lambda_i T_e$ 在 $V_i$ 上的限制 ${(T-\lambda_i T_e)|}{V_i}$。幂零变换的循环分解。子空间 $V_i$ 可以分解为幂零变换 $T_i$ 循环子空间的直和 $$ V_iW_{i1}\oplus W_{i2}\oplus\cdots\oplus W_{is_i} $$取循环基并倒序排列。在每一个循环子空间 $W_{ij}$ 里取一个循环基并倒序排列凑成 $V_i$ 的一个基于是 $T_i$ 关于这个基的矩阵有形状 $$ N_i\begin{pmatrix} N_{i1} 0\ N_{i2} \ \ddots \ 0 N_{is_i}\ \end{pmatrix} $$ 全体 $N_{ij}$ 均为幂零 Jordan 块。叠加可对角化部分。于是对于 $V_i$ 上述选取的基$S_i$ 对应的矩阵是 $$ B_i\begin{pmatrix} \lambda_i 0\ \lambda_i \ \ddots \ 0 \lambda_i\ \end{pmatrix}\begin{pmatrix} N_{i1} 0\ N_{i2} \ \ddots \ 0 N_{is_i}\ \end{pmatrix}\begin{pmatrix} J_{i1} 0\ J_{i2} \ \ddots \ 0 J_{is_i}\ \end{pmatrix} $$ 这里 $J_{i1},J_{i2},\cdots,J_{is_i}$ 都是属于 $\lambda_i$ 的 Jordan 块。拼合全空间基。对于每一个子空间 $V_i$按照以上方式选取一个基凑起来成为 $V$ 的基那么 $T$ 关于这个基的矩阵即构成定理规定的形式。定理Jordan 标准型的存在唯一性每一个 $n$ 阶矩阵 $A$ 都与一个 Jordan 标准型相似。除了各个 Jordan 块排列的次序以外与 $A$ 相似的 Jordan 标准型是由 $A$ 唯一确定的。注意在上述构造的矩阵 $B_i$ 中第一项是一个单位阵的若干倍自然可以和第二项交换。因此第一项就是 $B_i$ 的 Jordan 分解的可对角化部分第二项就是 $B_i$ 的 Jordan 分解的幂零部分。在一个矩阵对应的 Jordan 标准型里面主对角线上的元素构成的对角阵是这个矩阵对应的 Jordan 标准型的可对角化部分把主对角线上的元素换成 $0$ 就得到这个矩阵对应的 Jordan 标准型的幂零部分。这为 Jordan 分解提供了一种显式读法。初等因子 ↔ Jordan 块写标准型的钥匙定理对于矩阵 $A$ 的 Jordan 标准型中每一个 Jordan 块$$ J_i\begin{pmatrix} \lambda_i 1 \ \lambda_i 1 \ \ddots \ddots \ \ddots 1\ \lambda_i\ \end{pmatrix} $$对应于特征矩阵 $\lambda I-A$ 的一个初等因子 ${(\lambda-\lambda_i)}^{n_i}$特征矩阵 $\lambda I-A$ 的全体初等因子对应于矩阵 $A$ 的 Jordan 标准型中的全体 Jordan 块。这是因为矩阵 $A$ 相似于它的 Jordan 标准型因此两者的特征矩阵也等价将 Jordan 标准型的特征矩阵化为 Smith 标准型即可看出。于是借助特征矩阵 $\lambda I-A$ 的初等因子可以直接写出矩阵 $A$ 的 Jordan 标准型——每个初等因子 ${(\lambda-\lambda_i)}^{n_i}$ 对应一个 $n_i$ 阶、特征值为 $\lambda_i$ 的 Jordan 块初等因子计重数所以 Jordan 块也计重数。一个直接的推论是推论矩阵 $A$ 可对角化等价于特征矩阵 $\lambda I-A$ 的初等因子均为一次的。这与「代数重数 几何重数」的可对角化判据见 diagonalization.md相互印证一旦某个初等因子的次数大于 $1$对应的特征值就出现「亏格」必须以带 $1$ 的 Jordan 块来补足。弗罗贝尼乌斯Frobenius定理最小多项式的最终定位上文指出$n$ 阶特征矩阵的 Smith 标准形的秩为 $n$。定理Frobenius设矩阵 $A$ 的特征矩阵 $\lambda I-A$ 的 Smith 标准形为$$ \operatorname{diag}{d_1(\lambda),d_2(\lambda),\cdots,d_n(\lambda)} $$则最后一个不变因子 $d_n(\lambda)$ 恰好为矩阵 $A$ 的最小多项式 $m_A(\lambda)$。由此得到矩阵 $A$ 可对角化的一组等价条件推论矩阵 $A$ 可对角化的等价条件为最小多项式 $m_A(\lambda)$ 无重根特征矩阵 $\lambda I-A$ 的不变因子无重根特征矩阵 $\lambda I-A$ 的初等因子均为一次的。原文档将该定理署名写作 Forbenious规范拼写为 Frobenius即弗罗贝尼乌斯。至此从 Smith 标准型 → 不变因子 → 初等因子 → Jordan 块 → 最小多项式整条逻辑链完全闭合初等因子是「最细」的不变量不变因子是「排序后」的不变量最小多项式则恰为最后一个不变因子。在 OI 与算法中的关联与应用Jordan 理论与 λ 矩阵工具在 OI 中并非纯粹的理论装饰OI-wiki 的 整式递推篇目 shift.md 中即明确写道为了更系统地描述上述几道例题中构造矩阵的过程我们引入 λ 矩阵 的概念。在该篇目中求解整式递推的远处系数例如 $n\le 6\times 10^8$、对 $998244353$ 取模的模板题时需要维护一对 $m$ 维向量之间的线性变换即 $m\times m$ 的矩阵而矩阵的每一项对应于某个多项式的一个点值。此时把矩阵看作以 $\lambda$ 的多项式为元素的 λ 矩阵把「点值之间的倍数关系」抽象为 λ 矩阵的构造正是本文所述 λ 矩阵视角在竞赛算法中的直接应用。这体现了特征理论、λ 矩阵与多项式算法三个板块在 OI-wiki 中的相互打通。此外特征矩阵的 Smith 标准型、不变因子与最小多项式也是推导线性递推加速、矩阵快速幂优化等问题时理解「矩阵幂的周期性结构」的理论背景相关前置可参考 特征多项式篇目 char-poly.md 中的 Hessenberg 算法与 Cayley–Hamilton 定理部分。阅读路径建议若对特征值、特征多项式、最小多项式还不熟悉先读 char-poly.md若对特征子空间、几何重数、准素分解、幂零矩阵与循环子空间需要补课读 diagonalization.md若对初等矩阵、初等变换与行列式的关系需要复习读 elementary-operations.md线性代数体系的总览可参考 线性代数简介 index.md。本文的核心结论可总结为一句话任何矩阵都唯一地分解为「可对角化部分 幂零部分」且相似意义下的标准形——Jordan 标准型——完全由特征矩阵的初等因子决定而最后一个不变因子即最小多项式无重根与否正是矩阵可否对角化的分水岭。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考