史密斯標準形

數學中，史密斯標準形（SNF）是適用於所有元素都位於主理想域（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 \\ <pre> & & & & 0 & & \\ & & & & & \ddots & \\ </pre> 0 & & & \cdots & & & 0 \end{pmatrix}.$$

對角元素$\alpha_i$滿足$\forall 1 \le 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$使得$S A T$為對角陣。這是演算法中最難的部分。一旦實現了對角化，將矩陣轉化為史密斯標準形就相對簡單了。更抽象地說，我們的目標是證明$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}\neq0$；若是這種情況，這步就完成了。否則，根據假設，存在某個$k$，使$a_{k,j_t} \neq 0$，且我們可以交換$t$行與$k$行，得到$a_{t,j_t}\neq0$。

現在我們選擇的主元位於$(t, j_t)$。

### 第二步：改進主元

若(k,jt)上有元素使$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,jt)的位置上有元素β（由於我們選擇了α、γ，(k,jt)上也有元素0，雖然這對演算法並不重要，但很有用）。這個新元素β除了原元素$a_{t,j_t}$，因此$\delta(\beta) < \delta(a_{t,j_t})$；因此重複這些步驟最後必須終止。最終得到的矩陣的(t,jt)元素除以了jt列的所有元素。

### 第三步：消除元素

最後，加上第t行的適當倍數，可以使jt列中除(t,jt)外的所有元素都變為零。這也可以通過左乘適當的矩陣來實現。不過，為使矩陣完全對角，還需消除(t,jt)所在行上的非零元素，這可以通過對列重複第二步中的演算法來實現，並與得到的矩陣L的轉置右乘。一般來說，這會導致之前應用第三步時消除的元素再次變為非零。

注意，對行列每次應用第二步的演算法都必須減少$\delta(a_{t,j_t})$的值，因此這一過程須在一定迭代次數後終止，使矩陣中(t,jt)元素是所在行列中的唯一非零元。

這時，只需對(t,jt)右下方的A塊進行對角化，從概念上講這個演算法可以遞歸應用，將塊視為單獨的矩陣。換句話說，可以將t增加1，然後回到第一步。

### 最後一步

將上述步驟用於結果矩陣的剩餘非零列（如果有的話），最後得到$m \times n$矩陣，列為$j_1 < \ldots < j_r$，其中$r \le \min(m,n)$。矩陣非零元只有$(l,j_l)$。

現在可以把空列向右移動，這樣非零元就到了位置$(i,i)(1 \le i\le 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}$的線性組合，所以可以被β除。

$\delta(\alpha_1)+\cdots+\delta(\alpha_r)$的值不會因為上述操作而改變（它是上$r\times r$子陣的行列式的δ），因此操作確實（通過向右移動因子）減小了

$$\sum_{j=1}^r(r-j)\delta(\alpha_j).$$

所以，這演算法只能應用有限次，意味著我們已經如願得到了$\alpha_1\mid\alpha_2\mid\cdots\mid\alpha_r$。

由於所有行列運算都可逆，這就表明存在可逆方陣$m \times m$、$n \times n$S, T使乘積S A T滿足史密斯標準形的定義。特別地，這表明史密斯標準形一定存在，無需證明。

## 應用

鏈復形的鏈模為有限生成模時，史密斯標準形對計算鏈復形的同調將十分有用。例如，拓撲學中，可用於計算整數上有限單純復形或CW復形的同調，因為這種復形的邊界映射的整數矩陣；還可用於確定主理想域上有限生成模結構定理中出現的不變因子，其中包括了有限生成阿貝爾群基本定理。

控制論中，史密斯標準形還用於計算傳遞函數矩陣的零點。

## 例子

求下列整數矩陣的史密斯標準形：

$$\begin{pmatrix} 2 & 4 & 4 \\ -6 & 6 & 12 \\ 10 & 4 & 16 \end{pmatrix}$$

下面的矩陣是演算法應用於上述矩陣的中間步驟。

$$\to \begin{pmatrix} 2 & 0 & 0 \\ -6 & 18 & 24 \\ 10 & -16 & -4 \end{pmatrix} \to \begin{pmatrix} 2 & 0 & 0 \\ 0 & 18 & 24 \\ 0 & -16 & -4 \end{pmatrix}$$

$$\to \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 20 \\ 0 & -16 & -4 \end{pmatrix} \to \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 20 \\ 0 & 0 & 156 \end{pmatrix}$$

$$\to \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 156 \end{pmatrix}$$

所求史密斯標準形為

$$\begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 156 \end{pmatrix}$$

不變因子為2、2、156。

## 矩陣相似

史密斯標準形可用於判定元素屬於同一域的兩個矩陣是否相似。具體來說，若且唯若特徵矩陣$xI-A$、$xI-B$有相同的史密斯標準形時，A、B相似。

例如

$$\begin{align} A & {} =\begin{bmatrix} <pre> 1 & 2 \\ 0 & 1 </pre> \end{bmatrix}, & & \mbox{SNF}(xI-A) =\begin{bmatrix} <pre> 1 & 0 \\ 0 & (x-1)^2 </pre> \end{bmatrix} \\ B & {} =\begin{bmatrix} <pre> 3 & -4 \\ 1 & -1 </pre> \end{bmatrix}, & & \mbox{SNF}(xI-B) =\begin{bmatrix} <pre> 1 & 0 \\ 0 & (x-1)^2 </pre> \end{bmatrix} \\ C & {} =\begin{bmatrix} <pre> 1 & 0 \\ 1 & 2 </pre> \end{bmatrix}, & & \mbox{SNF}(xI-C) =\begin{bmatrix} <pre> 1 & 0 \\ 0 & (x-1)(x-2) </pre> \end{bmatrix}. \end{align}$$

A、B相似是因為它們特徵矩陣的史密斯標準形相同，而與C不相似，因為它們特徵矩陣的史密斯標準形不同。

## 外部連結

- An animated example of computation of Smith normal form .