Smith标准形存在性

下文算法中 $\mathbf{A}(\lambda )$ 指 $n$ 阶 $\lambda$-矩阵.

算法1. 若 $a_{11}\ne 0$, 且 $\mathbf{A}(\lambda )$ 的第 $1$ 行或第 $1$ 列中存在元素无法被 $a_{11}$ 整除, 通过有限次初等变换使第 $1$ 行第 $1$ 列中所有元素都能被 $a_{11}$ 整除, 且 $(1,1)$ 位置的元素次数变低.

Step 1. 从 $a_{21}$ 向下检查第 $1$ 列, 若遇到 $a_{i1}$ 不能被 $a_{11}$ 整除, 设 $a_{i1}$ 可以唯一地表示为

$a_{i1}=a_{11}p+r$

其中 $\mathrm{deg}(r)<\mathrm{deg}(a_{i1})$.

将第 $1$ 行乘以 $p$ 加到第 $i$ 行, 并交换第 $i$ 行和第 $1$ 行, 此时 $(1,1)$ 位置的元素是 $r$.

Step 2. 重复 Step 1, 直至第 $1$ 行第 $1$ 列的元素可以整除第一列元素退出. 这个步骤的执行次数至多是有限的, 因为每次执行完后 $(1,1)$ 位置的元素次数都比上次降低至少 $1$, 若无限进行下去, $r$ 的次数将会是负数, 矛盾.

Step 3. 此时再对矩阵进行转置, 重复 Step 1~2.

Step 4. 将矩阵再次进行转置, 输出, 此时第 $1$ 行和第 $1$ 列的元素都可以被 $(1,1)$ 位置的元素整除, 且 $(1,1)$ 位置的元素次数变低.

算法2. 若 $a_{11}\ne 0$, 且 $\mathbf{A}(\lambda )$ 中存在元素无法被 $a_{11}$ 整除, 通过有限次初等变换将其变换为 ${\mathbf{A}}^{\prime }(\lambda )$, 其中 $a_{11}^{\prime }\ne 0$, $\mathrm{deg}(a_{11})<\mathrm{deg}(a_{11})$ 且 $a_{11}^{\prime }$ 整除${\mathbf{A}}^{\prime }(\lambda )$所有元素.

Step 1. 如果第 $1$ 行或第 $1$ 列中有元素不能被 $a_{11}$ 位置的元素整除, 则采用算法1对矩阵进行处理.

Step 2. 若仍有 $a_{ij}$ 不能被 $a_{11}$ 整除, 设可以唯一地表示为 $a_{i1}=a_{11}p$, 则将第 $1$ 行乘以 $-p$ 加到第 $i$ 行，$(i,1)$ 位置为 $0$, $(i,j)$ 位置为 $a_{ij}-p{a}_{1j}$, 将第 $i$ 行加到第 $1$ 行, 此时 $(1,1)$ 位置仍为 $a_{1,1}$, $(1,j)$ 位置变为 $a_{1j}(1-p)+a_{ij}$, 不能被 $a_{11}$ 整除, 调用算法1对矩阵进行处理.

Step 3. 重复调用步骤2, 必然在有限步内得到满足要求的矩阵. 显然每次处理完后 $(1,1)$ 位置元素的次数都降低至少 $1$, 因此若无限进行下去, 次数将为负, 矛盾.

算法3. 将矩阵 $\mathbf{A}(\lambda )$ 经过有限次初等变换化为Smith标准形.

Step 1. 若 $a_{11}$ 不能整除所有元素, 则调用算法2对矩阵进行处理.

Step 2. 消去第 $1$ 行第 $1$ 列除 $(1,1)$ 位置外的所有元素.

Step 3. 对于除去第1行第1列的子矩阵, 重复Step 1 ~ 2的处理流程. 对于除去第 $1$ ~ $2$ 行第 $1$ ~ $2$ 列的子矩阵, 重复Step 1 ~ 2的处理流程… 最终将会得到一个对角阵 d i a g { d 11 , . . . , d n n } \mathrm{diag}\{d_{11},..., d_{nn}\} diag{d11​,...,dnn​}, 由构造过程可知, 这个对角阵的对角元素满足$d_{ii}|d_{i+1,i+1}$, $i=1,2,...,n-1$, 最后再对对角阵的每个对角元素乘以常数, 使其最高次项系数为 $1$, 显然这个对角阵就是一个Smith标准形.

$\mathbf{A}(\lambda )$ 代入算法3可得到其Smith标准形, 因此 $\mathbf{A}(\lambda )$ 的 Smith标准形必然存在.