PID 上的 Smith 正规形

形式陈述

设 $R$ 是主理想整环， $A\in R^{m\times n}$ 。存在可逆矩阵 $U\in\operatorname{GL}_m(R)$ 、 $V\in\operatorname{GL}_n(R)$ ，使

UAV=D=\operatorname{diag}(d_1,\ldots,d_r,0,\ldots,0), \qquad 0\ne d_1\mid d_2\mid\cdots\mid d_r.

这里允许矩形对角矩阵， $r$ 是把标量扩到分式域后的秩。上述符号 $d_i\mid d_{i+1}$ 表示整除。非零对角元称为不变因子，每项在乘单位元的相伴意义下唯一；在 $\mathbb Z$ 上约定 $d_i>0$ 后便完全唯一。零矩阵对应 $r=0$ 。

存在性：Bézout 运算与终止

先说明可逆运算从何而来。若 $a,b$ 不全为零，由 PID 条件取 $(a,b)=(d)$ 。于是 $d$ 整除 $a,b$ ，且 $d=sa+tb$ 对某些 $s,t\in R$ 成立；任意公因子都整除这个线性组合，所以 $d$ 也是环上的最大公因子。由此得到 Bézout 块

\begin{pmatrix}s&t\\-b/d&a/d\end{pmatrix} \begin{pmatrix}a\\b\end{pmatrix} =\begin{pmatrix}d\\0\end{pmatrix}, \qquad \det\begin{pmatrix}s&t\\-b/d&a/d\end{pmatrix}=1.

矩阵中的商属于 $R$ ，所以这是环上合法的可逆换基。把这个块放到适当的两行便能做行运算，转置后也能做列运算。一般 PID 上只需保证这些块可逆，不必断言它们都能写成通常三类初等矩阵的乘积。

把一个非零条目移到左上角作为主元 $a$ 。如果首列或首行中有 $a$ 不整除的条目 $b$ ，用上述块将主元替换为 $d$ ；此时 $(a)\subsetneq(a,b)=(d)$ 。如果条目本来被 $a$ 整除，则直接减去相应倍数即可清零。交替处理首行和首列：首列清零后，清理已被主元整除的首行条目不会再次改变首列以下的零。

首行首列清零后，还必须检查右下角剩余块。若其中某项 $b$ 不被 $a$ 整除，就把该项所在行加到首行。左上角仍是 $a$ ，首行却出现了 $b$ ，于是又能用 Bézout 块严格扩大主元理想。只要这一层没有完成，就能找到这样的严格扩大。

这些扩大不可能无限持续。这是 PID 的理想升链条件：若 $(a_1)\subseteq(a_2)\subseteq\cdots$ ，其并集是理想 $(c)$ ；生成元 $c$ 属于某个 $(a_N)$ ，故整个并集已等于 $(a_N)$ ，以后不再严格增长。于是有限次主元替换之后，首行首列可清零，而且主元整除剩余块的每一项。

对剩余块归纳。后续换基只对块内条目作 $R$ -线性组合，因此这些条目始终被第一个主元整除。归纳所得下一个非零对角元也被它整除；递归重复，整除链自然成立。这证明了存在性，未使用模结构定理。

唯一性：子式生成的理想

令 $\Delta_k(A)$ 为所有 $k$ 阶子式（相应方形子矩阵的行列式）生成的理想，并令 $\Delta_0(A)=R$ 。Cauchy–Binet 公式把 $UAV$ 的每个 $k$ 阶子式写成 $A$ 的 $k$ 阶子式的 $R$ -线性组合，故 $\Delta_k(UAV)\subseteq\Delta_k(A)$ 。再对 $U^{-1},V^{-1}$ 使用同一论证，得到相等。

对于满足整除链的 $D$ ，任一非零 $k$ 阶子式都是若干对角元的乘积，必被 $d_1\cdots d_k$ 整除；前 $k$ 个对角元组成的子式恰好等于这个乘积。因此

\Delta_k(A)=(d_1\cdots d_k)\quad(1\le k\le r), \qquad \Delta_k(A)=(0)\quad(k>r).

逐次比较相邻乘积，即可恢复每个 $d_k$ 的相伴类。这个论证处理的是矩阵的可逆行列等价；不同大小的呈示为何给出同一抽象模的不变量，要由模自身的结构另行解释。

直觉

域上的高斯消元允许除以任意非零数，最后主要留下秩。整数上的 $2$ 、 $30$ 却不是单位，不能直接除掉；它们记录了取商后仍然存在的有限周期。Smith 正规形把这些整除信息与自由方向一起保留下来。

全文采用列向量约定： $A:R^n\to R^m$ 的每一列是一条关系，目标标准基对应生成元。右乘 $V$ 重新组合关系，因为 $VR^n=R^n$ ，所以 $AVR^n=AR^n$ 。左乘 $U$ 则改变目标坐标，并以 $[x]\mapsto[Ux]$ 把 $R^m/AR^n$ 同构到 $R^m/DR^n$ 。它们的作用不同，同构方向也必须随矩阵乘法一起记录。

Smith 换基交换图：源端向下为 V 的逆，目标端向下为 U，商模间由 U 诱导同构。

可逆换基将原商群的坐标分成两个有限周期和一个自由方向。图中左方块由 $DV^{-1}=UA$ 保证交换，右方块则表示 $\Phi([x])=[Ux]$ ：先取商再用 $\Phi$ ，与先乘 $U$ 再取商得到相同结果。对角商的前两坐标分别保留模 $2$ 、模 $30$ 的余类，第三坐标保留完整整数。

例子与边界

两阶热身

对 $\begin{pmatrix}2&4\\6&8\end{pmatrix}$ ，依次作 $R_2\leftarrow R_2-3R_1$ 、 $C_2\leftarrow C_2-2C_1$ ，得到 $\operatorname{diag}(2,-4)$ ；再把第二行乘以 $-1$ ，得到 $\operatorname{diag}(2,4)$ 。所以其余核是 $\mathbb Z/2\mathbb Z\oplus\mathbb Z/4\mathbb Z$ 。

九步整数证书

现在同时保留冗余关系和自由方向，取

A=\begin{pmatrix}6&12&18\\10&30&40\\16&42&58\end{pmatrix}.

第三列等于前两列之和，但先不删除。以下每一步都只加整数倍，逆操作是减去同一倍数，因此全部在整数环上可逆。

步骤	操作	当前矩阵
1	$R_3\leftarrow R_3-R_1$	$\begin{pmatrix}6&12&18\\10&30&40\\10&30&40\end{pmatrix}$
2	$R_3\leftarrow R_3-R_2$	$\begin{pmatrix}6&12&18\\10&30&40\\0&0&0\end{pmatrix}$
3	$C_3\leftarrow C_3-C_1$	$\begin{pmatrix}6&12&12\\10&30&30\\0&0&0\end{pmatrix}$
4	$C_3\leftarrow C_3-C_2$	$\begin{pmatrix}6&12&0\\10&30&0\\0&0&0\end{pmatrix}$
5	$C_2\leftarrow C_2-2C_1$	$\begin{pmatrix}6&0&0\\10&10&0\\0&0&0\end{pmatrix}$
6	$R_2\leftarrow R_2-R_1$	$\begin{pmatrix}6&0&0\\4&10&0\\0&0&0\end{pmatrix}$
7	$R_1\leftarrow R_1-R_2$	$\begin{pmatrix}2&-10&0\\4&10&0\\0&0&0\end{pmatrix}$
8	$R_2\leftarrow R_2-2R_1$	$\begin{pmatrix}2&-10&0\\0&30&0\\0&0&0\end{pmatrix}$
9	$C_2\leftarrow C_2+5C_1$	$\begin{pmatrix}2&0&0\\0&30&0\\0&0&0\end{pmatrix}$

累计行、列变换得到

U=\begin{pmatrix}2&-1&0\\-5&3&0\\-1&-1&1\end{pmatrix}, \qquad V=\begin{pmatrix}1&3&-1\\0&1&-1\\0&0&1\end{pmatrix}, \qquad UAV=\operatorname{diag}(2,30,0).

这是一份可以直接核验的证书，不必相信消元过程本身。两矩阵的行列式均为 $1$ ，整数逆为

U^{-1}=\begin{pmatrix}3&1&0\\5&2&0\\8&3&1\end{pmatrix}, \qquad V^{-1}=\begin{pmatrix}1&-3&-2\\0&1&1\\0&0&1\end{pmatrix}.

另用原矩阵的子式作独立校验：全部条目的 gcd 为 $2$ 。按行对、列对都依次取 $(1,2),(1,3),(2,3)$ ，九个二阶子式为

60,60,-60,\quad60,60,-60,\quad-60,-60,60.

它们的 gcd 为 $60$ ，三阶行列式为零。因此秩为 $2$ ， $d_1=2$ 、 $d_2=60/2=30$ ，与证书一致。矩阵的一个零列记录关系之间的依赖，一个零行则在余核中留下自由方向；二者不能混为同一生成元。

假设与计算成本

对角形本身还不够： $\operatorname{diag}(6,10)$ 不满足整除链，其 Smith 形是 $\operatorname{diag}(2,30)$ 。在 $k[x,y]$ 上，矩阵 $(x\ y)$ 不可能变成 $(d\ 0)$ ，因为条目生成的理想 $(x,y)$ 不是主理想。Smith 形也不同于奇异值分解：这里保留环上的整除关系，并不要求换基正交。例如整数矩阵 $\operatorname{diag}(2,3)$ 的 Smith 形为 $\operatorname{diag}(1,6)$ ，而视为实矩阵时，其奇异值是 $3,2$ 。前者记录整数商中的周期，后者记录 Euclidean 长度的伸缩。

存在性证明说明上述主元处理会终止，却没有控制中间整数的位数。若输入条目的最大位长为 $B$ ，位复杂度还须计入矩阵尺寸、主元更新次数和中间位长，不能由“类似消元”推断通用的 $O(n^3)$ 位成本。枚举子式适合本例的独立校验，并不是大矩阵求 Smith 形的默认算法。Kannan–Bachem 的多项式算法采用另外的位长控制；它的结论不能直接套到任意教学消元流程上。

推论与应用

若 $A:R^n\to R^m$ 有 $r$ 个非零不变因子，则余核满足

R^m/AR^n\cong R/(d_1)\oplus\cdots\oplus R/(d_r)\oplus R^{m-r}.

单位因子给出零模，应删去；目标端未被关系占用的坐标给出自由副本。本例由此得到 $\mathbb Z/2\mathbb Z\oplus\mathbb Z/30\mathbb Z\oplus\mathbb Z$ 。有限生成阿贝尔群结构定理中的同一算例继续把 $U$ 翻译成原生成元的像和同构的逆，完成从对角矩阵到具体群元素的计算。

另一方面， $D$ 的第三个源坐标无约束，所以 $\ker_{\mathbb Z}A=\mathbb Z(-1,-1,1)$ ，生成元是 $V$ 的第三列。它表示第三条关系等于前两条关系之和，属于源端；余核的自由生成元属于目标端。

矩阵正规形还提供PID 上有限生成模结构定理的存在性工具。该页先证明有限生成模具有有限关系矩阵，再从模内部恢复唯一不变量，补齐矩阵计算之外的两步。

参考资料

Sanjana Das、Jakin Ng，MIT Algebra II, Lecture 20，2022，§20.3–20.4：列关系呈示与商模换基。
同课程 Lecture 21，Theorem 21.4、Lemma 21.6、Note 21.5：Euclidean 整环上的证明及一般 PID 的可逆换基区别。本文用理想升链补足一般 PID 的终止论证。
H. J. S. Smith，On Systems of Linear Indeterminate Equations and Congruences，1861，Arts. 12–14，印刷页 311–317：子式公因子与整数单位变换的历史来源。
R. Kannan、A. Bachem，Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix，SIAM J. Comput. 8(4)，1979，499–507，§3：带位长控制的算法；此处仅作进阶来源，不主张本文流程具有该复杂度。

形式陈述 ​

存在性：Bézout 运算与终止 ​

唯一性：子式生成的理想 ​

两阶热身 ​

九步整数证书 ​

假设与计算成本 ​

反向链接