史密斯標準形

數學中，史密斯標準形（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}$ 的線性組合，所以可以被β除。