史密斯标准形

数学中，史密斯标准形（SNF^[1]）是适用于所有元素都位于主理想域（PID）的矩阵的标准形（不必是方阵）。史密斯标准形是对角矩阵，可以从原始矩阵左右乘可逆方阵得到。特别地，整数构成一个PID，所以总可以计算出任何整数矩阵的史密斯标准形。史密斯标准形对于处理PID上的有限生成模，尤其是推导自由模之商的结构时非常有用。史密斯标准形得名于爱尔兰数学家Henry John Stephen Smith。

定义编辑

令A为主理想域R上的非零m×n矩阵。存在可逆 $m\times m$ 、 $n\times n$ 方阵S, T（系数在R中），使得它们的积S A T为

${\begin{pmatrix}\alpha _{1}&0&0&&\cdots &&0\\0&\alpha _{2}&0&&\cdots &&0\\0&0&\ddots &&&&0\\\vdots &&&\alpha _{r}&&&\vdots \\&&&&0&&\\&&&&&\ddots &\\0&&&\cdots &&&0\end{pmatrix}}.$

对角元素 $\alpha _{i}$ 满足 $\forall 1\leq i<r,\ \alpha _{i}\mid \alpha _{i+1}$ 。这就是矩阵A的史密斯标准形。元素 $\alpha _{i}$ 在乘法意义上是唯一的，是可逆元，称为基本除子、不变量或不变因子。它们的计算公式为

\alpha _{i}={\frac {d_{i}(A)}{d_{i-1}(A)}},

其中 $d_{i}(A)$ （即第i个行列式因子）等于矩阵A 所有 $i\times i$ 子式的行列式的最大公因数，且 $d_{0}(A):=1$ 。

算法编辑

第一个目标是找到可逆方阵 $S$ 、 $T$ 使得 $SAT$ 为对角阵。这是算法中最难的部分。一旦实现了对角化，将矩阵转化为史密斯标准形就相对简单了。更抽象地说，我们的目标是证明 $A$ 可以视为从 $R^{n}$ （秩为 $n$ 的自由 $R$ -模）到 $R^{m}$ （秩为 $m$ 的自由 $R$ -模）的映射，且有同构 $S:R^{m}\to R^{m}$ 、 $T:R^{n}\to R^{n}$ ，使得 $S\cdot A\cdot T$ 具有对角矩阵的简单形式。 $S$ 、 $T$ 可用以下方法得到：从适当大小的单位阵开始，每次在算法中对 $A$ 进行行运算时，都将相应的列运算施于 $S$ （例如，若 $A$ 的 $i$ 行加在 $j$ 行上，则 $S$ 的 $i$ 列应减去 $j$ ，以保持乘积不变），同理，每次列运算都相应地修改 $T$ 、由于行运算是左乘，列运算是右乘，这也就保持了 $A'=S'\cdot A\cdot T'$ 不变，其中 $A',S',T'$ 表示当前值， $A$ 表示原矩阵；最终，不变式中的矩阵变为对角阵。

对于 $a\in R\setminus \{0\}$ ，记 $\delta (a)$ 为 $a$ 的素因子数（素因子存在且唯一，因为PID都是唯一分解整环）。特别地， $R$ 也是贝祖环，因此是GCD环，任意两元素的gcd满足贝祖等式。

要将矩阵转为史密斯标准形，可以重复应用下面的公式，其中 $t$ 从1到 $m$ 循环。

第一步：选择主元编辑

择 $j_{t}$ 为 $A$ 中非零元所在的最小列数，若 $t>1$ 则从第 $j_{t-1}+1$ 列开始搜索。

我们希望 $a_{t,j_{t}}\neq 0$ ；若是这种情况，这步就完成了。否则，根据假设，存在某个 $k$ ，使 $a_{k,j_{t}}\neq 0$ ，且我们可以交换 $t$ 行与 $k$ 行，得到 $a_{t,j_{t}}\neq 0$ 。

现在我们选择的主元位于 $(t,j_{t})$ 。

第二步：改进主元编辑

若(k,j_t)上有元素使 $a_{t,j_{t}}\nmid a_{k,j_{t}}$ ，则令 $\beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}}\right)$ ，根据贝祖性质我们知道R中存在σ、τ使

a_{t,j_{t}}\cdot \sigma +a_{k,j_{t}}\cdot \tau =\beta .

与适当的可逆阵L左乘，矩阵乘积的第t行是原矩阵第t行的σ倍与第k行的τ倍的和，乘积的第k行则是这些行的另一个线性组合，其他行则保持不变。若σ、τ满足上市，则对于 $\alpha =a_{t,j_{t}}/\beta$ 和 $\gamma =a_{k,j_{t}}/\beta$ （根据β的定义，这样作商是可能的），可以得到

\sigma \cdot \alpha +\tau \cdot \gamma =1,

那么矩阵

L_{0}={\begin{pmatrix}\sigma &\tau \\-\gamma &\alpha \\\end{pmatrix}}

可逆，其逆为

{\begin{pmatrix}\alpha &-\tau \\\gamma &\sigma \\\end{pmatrix}}.

现在L可以通过将 $L_{0}$ 放入单位阵的t~k行列来得到。根据构造，L左乘后得到的矩阵在(t,j_t)的位置上有元素β（由于我们选择了α、γ，(k,j_t)上也有元素0，虽然这对算法并不重要，但很有用）。这个新元素β除了原元素 $a_{t,j_{t}}$ ，因此 $\delta (\beta )<\delta (a_{t,j_{t}})$ ；因此重复这些步骤最后必须终止。最终得到的矩阵的(t,j_t)元素除以了j_t列的所有元素。

第三步：消除元素编辑

最后，加上第t行的适当倍数，可以使j_t列中除(t,j_t)外的所有元素都变为零。这也可以通过左乘适当的矩阵来实现。不过，为使矩阵完全对角，还需消除(t,j_t)所在行上的非零元素，这可以通过对列重复第二步中的算法来实现，并与得到的矩阵L的转置右乘。一般来说，这会导致之前应用第三步时消除的元素再次变为非零。

注意，对行列每次应用第二步的算法都必须减少 $\delta (a_{t,j_{t}})$ 的值，因此这一过程须在一定迭代次数后终止，使矩阵中(t,j_t)元素是所在行列中的唯一非零元。

这时，只需对(t,j_t)右下方的A块进行对角化，从概念上讲这个算法可以递归应用，将块视为单独的矩阵。换句话说，可以将t增加1，然后回到第一步。

最后一步编辑

将上述步骤用于结果矩阵的剩余非零列（如果有的话），最后得到 $m\times n$ 矩阵，列为 $j_{1}<\ldots <j_{r}$ ，其中 $r\leq \min(m,n)$ 。矩阵非零元只有 $(l,j_{l})$ 。

现在可以把空列向右移动，这样非零元就到了位置 $(i,i)(1\leq i\leq r)$ 。简而言之，设 $\alpha _{i}$ 为 $(i,i)$ 上的元素。

对角元的可除性条件可能不能满足。 $\forall i<r$ 使 $\alpha _{i}\nmid \alpha _{i+1}$ ，可以只对 $i$ 、 $i+1$ 行列进行操作来弥补这一缺陷：首先将第 $i+1$ 列加到 $i$ 列，以在第i列得到 $\alpha _{i+1}$ 元素而不影响 $(i,i)$ 位置上的元素 $\alpha _{i}$ ，然后应用行运算使 $(i,i)$ 元素等于 $\beta =\gcd(\alpha _{i},\alpha _{i+1})$ ，如第二步所述；最后按第三步方法，使矩阵再次对角化。由于 $(i+1,i+1)$ 的新条目是原 $\alpha _{i},\alpha _{i+1}$ 的线性组合，所以可以被β除。