查看“︁史密斯标准形”︁的源代码

数学中，'''史密斯标准形'''（'''SNF'''<ref>{{cite journal|last=Stanley|first=Richard P.|authorlink=Richard P. Stanley|date=2016|title=Smith normal form in combinatorics|journal=[[Journal of Combinatorial Theory]] | series=Series A |volume=144|pages=476–495|doi=10.1016/j.jcta.2016.06.013|doi-access=free|arxiv=1602.00166|s2cid=14400632}}</ref>）是适用于所有元素都位于[[主理想域]]（PID）的矩阵的[[规范形|标准形]]（不必是方阵）。史密斯标准形是[[对角矩阵]]，可以从原始矩阵左右乘[[逆元素|可逆]]方阵得到。特别地，整数构成一个PID，所以总可以计算出任何整数矩阵的史密斯标准形。史密斯标准形对于处理PID上的有限生成模，尤其是推导[[自由模]]之商的结构时非常有用。史密斯标准形得名于爱尔兰数学家Henry John Stephen Smith。

==定义==
令''A''为[[主理想域]]''R''上的非零''m''&times;''n''矩阵。存在可逆<math>m \times m</math>、<math>n \times n</math>方阵''S, T''（系数在''R''中），使得它们的积''S A T''为

<math>
\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}.
</math>

对角元素<math>\alpha_i</math>满足<math>\forall 1 \le i < r,\ \alpha_i \mid \alpha_{i+1}</math>。这就是矩阵A的史密斯标准形。元素<math>\alpha_i</math>在乘法意义上是唯一的，是[[可逆元]]，称为''基本除子''、''不变量''或''不变因子''。它们的计算公式为
: <math>\alpha_i = \frac{d_i(A)}{d_{i-1}(A)},</math>
其中<math>d_i(A)</math>（即第''i''个''行列式因子''）等于矩阵''A'' 所有<math>i\times i</math>[[子式和余子式|子式]]的行列式的[[最大公因数]]，且<math>d_0(A):=1</math>。

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

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

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

===第一步：选择主元===
择<math>j_t</math>为<math>A</math>中非零元所在的最小列数，若<math>t> 1</math>则从第<math>j_{t-1}+1</math>列开始搜索。

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

现在我们选择的主元位于<math>(t, j_t)</math>。

===第二步：改进主元===
若(''k'',''j''<sub>''t''</sub>)上有元素使<math>a_{t,j_t} \nmid a_{k,j_t}</math>，则令<math>\beta =\gcd\left(a_{t,j_t}, a_{k,j_t}\right)</math>，根据贝祖性质我们知道''R''中存在σ、τ使

:<math>
a_{t,j_t} \cdot \sigma + a_{k,j_t} \cdot \tau=\beta.
</math>

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

:<math>
\sigma\cdot \alpha + \tau \cdot \gamma=1,
</math>

那么矩阵

:<math> L_0=
\begin{pmatrix}
\sigma & \tau \\
-\gamma & \alpha \\
\end{pmatrix}
</math>

可逆，其逆为

:<math>
\begin{pmatrix}
\alpha & -\tau \\
\gamma & \sigma \\
\end{pmatrix}
.</math>

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

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

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

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

===最后一步===
将上述步骤用于结果矩阵的剩余非零列（如果有的话），最后得到<math>m \times n</math>矩阵，列为<math>j_1 < \ldots < j_r</math>，其中<math>r \le \min(m,n)</math>。矩阵非零元只有<math>(l,j_l)</math>。

现在可以把空列向右移动，这样非零元就到了位置<math>(i,i)(1 \le i\le r)</math>。简而言之，设<math>\alpha_i</math>为<math>(i,i)</math>上的元素。

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

<math>\delta(\alpha_1)+\cdots+\delta(\alpha_r)</math>的值不会因为上述操作而改变（它是上<math>r\times r</math>子阵的行列式的δ），因此操作确实（通过向右移动因子）减小了

:<math>\sum_{j=1}^r(r-j)\delta(\alpha_j).</math>
所以，这算法只能应用有限次，意味着我们已经如愿得到了<math>\alpha_1\mid\alpha_2\mid\cdots\mid\alpha_r</math>。

由于所有行列运算都可逆，这就表明存在可逆方阵<math>m \times m</math>、<math>n \times n</math>''S, T''使乘积''S A T''满足史密斯标准形的定义。特别地，这表明史密斯标准形一定存在，无需证明。

== 应用 ==
[[链复形]]的链模为[[有限生成模]]时，史密斯标准形对计算[[链复形]]的[[同调]]将十分有用。例如，[[拓扑学]]中，可用于计算整数上有限[[单纯复形]]或[[CW复形]]的同调，因为这种复形的边界映射的整数矩阵；还可用于确定[[主理想域]]上有限生成模结构定理中出现的不变因子，其中包括了[[有限生成阿贝尔群基本定理]]。

[[控制论]]中，史密斯标准形还用于计算[[传递函数矩阵]]的零点。<ref>{{Cite book|title=Multivariable feedback design|url=https://archive.org/details/multivariablefee0000maci|last=Maciejowski|first=Jan M.|date=1989|publisher=Addison-Wesley|isbn=0201182432|location=Wokingham, England|oclc=19456124}}</ref>

== 例子 ==
求下列整数矩阵的史密斯标准形：

:<math>
\begin{pmatrix}
2 & 4 & 4 \\
-6 & 6 & 12 \\
10 & 4 & 16
\end{pmatrix}
</math>

下面的矩阵是算法应用于上述矩阵的中间步骤。

:<math>
\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}
</math>

:<math>
\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}
</math>

:<math>
\to
\begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 156
\end{pmatrix}
</math>

所求史密斯标准形为

:<math>
\begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 156
\end{pmatrix}
</math>

不变因子为2、2、156。

== 矩阵相似 ==
史密斯标准形可用于判定元素属于同一域的两个矩阵是否[[相似矩阵|相似]]。具体来说，当且仅当特征矩阵<math>xI-A</math>、<math>xI-B</math>有相同的史密斯标准形时，''A、B''相似。

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

''A、B''相似是因为它们特征矩阵的史密斯标准形相同，而与''C''不相似，因为它们特征矩阵的史密斯标准形不同。

== 另见 ==
* [[规范形]]
* [[丢番图方程]]
* [[弗罗贝尼乌斯标准形]]（也称为有理规范形）
* [[埃尔米特标准形]]
* [[奇异值分解]]

== 注释 ==
{{Reflist}}

== 参考文献 ==
* {{cite journal |last=Smith |first=Henry J. Stephen |authorlink=Henry John Stephen Smith |year=1861 |title=On systems of linear indeterminate equations and congruences |journal=[[Philosophical Transactions of the Royal Society of London|Phil. Trans. R. Soc. Lond.]] |volume=151 |issue=1 |pages=293–326 |jstor=108738 |doi=10.1098/rstl.1861.0016 |s2cid=110730515 }} Reprinted (pp. [https://archive.org/stream/collectedmathema01smituoft#page/366/mode/2up 367–409]) in [https://archive.org/details/collectedmathema01smituoft ''The Collected Mathematical Papers of Henry John Stephen Smith'', Vol. I], edited by [[James Whitbread Lee Glaisher|J. W. L. Glaisher]]. Oxford: Clarendon Press (1894), ''xcv''+603 pp.
* {{PlanetMath |urlname=GausssAlgorithmForPrincipalIdealDomains |title=Smith normal form}}
* {{PlanetMath |urlname=ExampleOfSmithNormalForm |title=Example of Smith normal form}}
* K. R. Matthews, [http://www.numbertheory.org/courses/MP274/smith.pdf Smith normal form] {{Wayback|url=http://www.numbertheory.org/courses/MP274/smith.pdf |date=20210506154254 }}. MP274: Linear Algebra, Lecture Notes, University of Queensland, 1991.

== 外部链接 ==
* [http://huisman.perso.math.cnrs.fr/ens/m/s7/groupes_et_anneaux/smith.gif An animated example of computation of Smith normal form] {{Wayback|url=http://huisman.perso.math.cnrs.fr/ens/m/s7/groupes_et_anneaux/smith.gif |date=20210414171135 }}.

[[Category:矩阵论]]