Smith normal form: Difference between revisions

Revision as of 09:53, 13 February 2014

Latest revision as of 20:13, 30 April 2025

(53 intermediate revisions by 43 users not shown)

Line 1:

{{Short description|Matrix normal form}}

In [[mathematics]], the '''Smith normal form''' (sometimes abbreviated '''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>) is a [[Canonical form|normal form]] that can be defined for any [[matrix (mathematics)|matrix]] (not necessarily [[square matrix|square]]) with entries in a [[principal ideal ___domain]] (PID). The Smith normal form of a matrix is [[Diagonaldiagonal matrix|diagonal]], and can be obtained from the original matrix by multiplying on the left and right by [[invertible matrix|invertible]] square matrices. In particular, the [[Integer#Algebraic properties|integers]] are a PID, so one can always calculate the Smith normal form of an [[integer matrix]]. The Smith normal form is very useful for working with [[finitely generated modulesmodule|finitely generated]] [[module (mathematics)|module]]s over a PID, and in particular for deducing the structure of a [[quotient module|quotient]] of a [[free module]]. It is named after the Irish mathematician [[Henry John Stephen Smith]].<ref>Lazebnik, F. (1996). On systems of linear diophantine equations. Mathematics Magazine, 69(4), 261-266.</ref><ref>Smith, H. J. S. (1861). Xv. on systems of linear indeterminate equations and congruences. Philosophical transactions of the royal society of london, (151), 293-326.</ref>

==Definition==

Let ''<math>A''</math> be a nonzero ''<math>m''& \times;'' n''</math> matrix over a [[principal ideal ___domain]] ''<math>R''</math>. There exist invertible <math>m \times m</math> and <math>n \times n</math>-matrices ''<math>S, T''</math> (with entries in <math>R</math>) sosuch that the product ''S A T''<math>SAT</math> is

:<math>\begin{pmatrix}

0\alpha_1 & 0 & 0 & \cdots & 0 & \cdots & 0 \\

\begin{pmatrix}

\alpha_10 & 0\alpha_2 & 0 & & \cdots & & 0 \\

0 & \alpha_20 & 0\ddots & & \cdotsvdots & & 0 \vdots\\

0\vdots & 0& & \ddots &alpha_r & & & 0\\

\vdots &0 & & \alpha_rcdots & & 0 & \vdotscdots & 0 \\

\vdots & & & & 0\vdots & & \vdots \\

0 & & \cdots & & 0 & \ddotscdots & \\0

\beginend{pmatrix}.</math>

0 & & & \cdots & & & 0

\end{pmatrix}.

</math>

and the diagonal elements <math>\alpha_i</math> satisfy <math>\alpha_i \mid \alpha_{i+1}\;\forall\;</math> for all <math>1 \le i < r</math>. This is the Smith normal form of the matrix ''<math>A''</math>. The elements <math>\alpha_i</math> are unique [[up to]] multiplication by a [[Unitunit (ring theory)|unit]] and are called the ''elementary divisors'', ''invariants'', or ''invariant factors''. They can be computed (up to multiplication by a unit) as

: <math>\alpha_i = \frac{d_i(A)}{d_{i-1}(A)},</math>

where <math>d_i(A)</math> (called ''i''-th ''determinant divisor'') equals the [[greatest common divisor]] of the determinants of all <math>i\times i</math> [[Minorminor (linear algebra)|minorsminor]]s of the matrix ''<math>A''</math> and <math>d_0(A):=1</math>.

'''Example :''' For a <math>2\times2</math> matrix, <math>{\rm SNF}{a~~b\choose c~~d}

= {\rm diag}(d_1, d_2/d_1)</math> with <math>d_1 = \gcd(a,b,c,d)</math> and <math>d_2 = |ad-bc|</math>.

== Algorithm ==

OurThe first goal will beis to find invertible square matrices ''<math>S''</math> and ''<math>T''</math> such that the product ''<math>S A T''</math> is diagonal. This is the hardest part of the algorithm. andOnce oncediagonality we haveis achieved diagonality, it becomes relatively easy to put the matrix ininto Smith normal form. Phrased more abstractly, the goal is to show that, thinking of ''<math>A''</math> as a map from <math>R^n</math> (the free ''<math>R''</math>-[[Module (mathematics)|module]] of rank ''<math>n''</math>) to <math>R^m</math> (the free ''<math>R''</math>-[[Module (mathematics)|module]] of rank ''<math>m''</math>), there are isomorphisms[[isomorphism]]s <math>S:R^m \to R^m</math> and <math>T:R^n \to R^n</math> such that <math>S \cdot A \cdot T</math> has the simple form of a [[diagonal matrix]]. The matrices ''<math>S''</math> and ''<math>T''</math> can be found by starting out with identity matrices of the appropriate size, and modifying ''<math>S''</math> each time a row operation is performed on ''<math>A''</math> in the algorithm by the samecorresponding rowcolumn operation (for example, if row <math>i</math> is added to row <math>j</math> of <math>A</math>, then column <math>j</math> should be subtracted from column <math>i</math> of <math>S</math> to retain the product invariant), and similarly modifying ''<math>T''</math> for each column operation performed. Since row operations are left-multiplications and column operations are right-multiplications, this preserves the invariant <math>A'=S'\cdot A\cdot T'</math> where <math>A',S',T'</math> denote current values and ''<math>A''</math> denotes the original matrix; eventually the matrices in this invariant become diagonal. Only invertible row and column operations are performed, which ensures that ''<math>S''</math> and ''<math>T''</math> remain invertible matrices.

For ''<math>a'' \in ''R'' \setminus \{0\}</math>, write δ<math>\delta(''a'')</math> for the number of prime factors of ''<math>a''</math> (these exist and are unique since any PID is also a [[unique factorization ___domain]]). In particular, ''<math>R''</math> is also a [[Bézout ___domain]], so it is a [[gcd ___domain]] and the gcd of any two elements satisfies a [[Bézout's identity]].

To put a matrix into Smith normal form, one can repeatedly apply the following, where ''<math>t''</math> loops from 1 to ''<math>m''</math>.

===Step I: Choosing a pivot===

Choose ''j''<submath>''t''j_t</submath> to be the smallest column index of ''<math>A''</math> with a non-zero entry, starting the search at column index ''j''<submath>''j_{t''-1}+1</submath>+1 if ''<math>t'' &gt;> 1</math>.

We wish to have <math>a_{t,j_t}\neq0</math>; if this is the case this step is complete, otherwise there is by assumption some ''<math>k''</math> with <math>a_{k,j_t} \neq 0</math>, and we can exchange rows <math>t</math> and ''<math>k''</math>, thereby obtaining <math>a_{t,j_t}\neq0</math>.

Our chosen pivot is now at position <math>(''t'', ''j''<sub>''t''j_t)</submath>).

===Step II: Improving the pivot===

Line 42 ⟶ 44:

</math>

By left-multiplication with an appropriate invertible matrix ''L'', it can be achieved that row ''t'' of the matrix product is the sum of σ times the original row ''t'' and τ times the original row ''k'', that row ''k'' of the product is another [[linear combination]] of those original rows, and that all other rows are unchanged. Explicitly, if σ and τ satisfy the above equation, then for <math>\alpha=a_{t,j_t}/\beta</math> and <math>\gamma=a_{k,j_t}/\beta</math> (which divisions are possible by the definition of β) one has

:<math>

Line 66 ⟶ 68:

.</math>

Now ''L'' can be obtained by fitting <math>L_0</math> into rows and columns ''t'' and ''k'' of the [[identity matrix]]. By construction the matrix obtained after left-multiplying by ''L'' has entry β at position (''t'',''j''_''t'') (and due to our choice of α and γ it also has an entry 0 at position (''k'',''j''_''t''), which is useful though not essential for the algorithm). This new entry β divides the entry <math>a_{t,j_t}</math> that was there before, and so in particular <math>\delta(\beta) < \delta(a_{t,j_t})</math>; therefore repeating these steps must eventually terminate. One ends up with a matrix having an entry at position (''t'',''j''_''t'') that divides all entries in column ''j''_''t''.

===Step III: Eliminating entries===

Finally, adding appropriate multiples of row ''t'', it can be achieved that all entries in column ''j''_''t'' except for that at position (''t'',''j''_''t'') are zero. This can be achieved by left-multiplication with an appropriate matrix. However, to make the matrix fully diagonal we need to eliminate nonzero entries on the row of position (''t'',''j''_''t'') as well. This can be achieved by repeating the steps in Step II for columns instead of rows, and using multiplication on the right by the [[transpose]] of the obtained matrix ''L''. In general this will result in the zero entries from the prior application of Step III becoming nonzero again.

However, notice that each application of Step II for either rows or columns must continue to reduce the value of <math>\delta(a_{t,j_t})</math>, and so the process must eventually stop after some number of iterations, leading to a matrix where the entry at position (''t'',''j''_''t'') is the only non-zero entry in both its row and column.

However, notice that the [[ideal (ring theory)|ideals]] generated by the elements at position (''t'',''j''_''t'') form an [[ascending chain condition|ascending chain]], because entries from a later step always divide entries from a previous step. Therefore, since ''R'' is a [[Noetherian ring]] (it is a [[principal ideal ___domain|PID]]), the ideals eventually become stationary and do not change. This means that at some stage after Step II has been applied, the entry at (''t'',''j''_''t'') will divide all nonzero row or column entries before applying any more steps in Step II. Then we can eliminate entries in the row or column with nonzero entries while preserving the zeros in the already-zero row or column. At this point, only the block of ''A'' to the lower right of (''t'',''j''_''t'') needs to be diagonalized, and conceptually the algorithm can be applied recursively, treating this block as a separate matrix. In other words, we can increment ''t'' by one and go back to Step I.

At this point, only the block of ''A'' to the lower right of (''t'',''j''_''t'') needs to be diagonalized, and conceptually the algorithm can be applied recursively, treating this block as a separate matrix. In other words, we can increment ''t'' by one and go back to Step I.

===Final step===

Line 88 ⟶ 92:

== Applications ==

The Smith normal form is useful for computing the [[homology (mathematics)|homology]] of a [[chain complex]] when the chain modules of the chain complex are [[Finitely generated module|finitely generated]]. For instance, in [[topology]], it can be used to compute the homology of a finite [[simplicial complex]] or [[CW complex]] over the integers, because the boundary maps in such a complex are just integer matrices. It can also be used to provedetermine the well[[invariant knownfactor]]s that occur in the [[structure theorem for finitely generated modules over a principal ideal ___domain]], which includes the [[fundamental theorem of finitely generated abelian groups]].

The Smith normal form is also used in [[control theory]] to compute [[transmission and blocking zeros]] of a [[transfer function matrix]].<ref>{{Cite book|title=Multivariable feedback design|last=Maciejowski|first=Jan M.|date=1989|publisher=Addison-Wesley|isbn=0201182432|___location=Wokingham, England|oclc=19456124}}</ref>

== Example ==

Line 97 ⟶ 103:

2 & 4 & 4 \\

-6 & 6 & 12 \\

10 & -4 & -16

\end{pmatrix}

</math>

Line 108 ⟶ 114:

2 & 0 & 0 \\

-6 & 18 & 24 \\

10 & -2416 & -364

\end{pmatrix}

\to

Line 114 ⟶ 120:

2 & 0 & 0 \\

0 & 18 & 24 \\

0 & -2416 & -364

\end{pmatrix}

</math>

Line 122 ⟶ 128:

\begin{pmatrix}

2 & 0 & 0 \\

0 & 182 & 2420 \\

0 & -616 & -124

\end{pmatrix}

\to

\begin{pmatrix}

2 & 0 & 0 \\

0 & 62 & 1220 \\

0 & 180 & 24156

\end{pmatrix}

</math>

Line 137 ⟶ 143:

\begin{pmatrix}

2 & 0 & 0 \\

0 & 62 & 120 \\

0 & 0 & -12156

\end{pmatrix}

\to

\begin{pmatrix}

2 & 0 & 0 \\

0 & 6 & 0 \\

0 & 0 & 12

\end{pmatrix}

</math>

Line 153:

\begin{pmatrix}

2 & 0 & 0 \\

0 & 62 & 0 \\

0 & 0 & 12156

\end{pmatrix}

</math>

and the invariant factors are 2, 62 and 12156.

== Run-time complexity ==

The Smith Normal Form of an ''N''-by-''N'' matrix ''A'' can be computed in time <math>O(\|A\| \log \|A\| N^4\log N)</math>.<ref>{{Cite web |title=Computation time of Smith normal form in Maple |url=https://mathoverflow.net/a/208106/34461 |access-date=2024-04-05 |website=MathOverflow |language=en}}</ref> If the matrix is [[Sparse matrix|sparse]], the computation is typically much faster.

== Similarity ==

The Smith normal form can be used to determine whether or not matrices with entries over a common [[field (mathematics)|field]] <math>K</math> are [[similar (linear algebra)|similar]]. Specifically two matrices ''A'' and ''B'' are similar [[if and only if]] the [[characteristic matrix|characteristic matrices]] <math>xI-A</math> and <math>xI-B</math> have the same Smith normal form (working in the PID <math>K[x]</math>).

For example, with

:<math>\begin{align}

\begin{align}

A & {} =\begin{bmatrix}

1 & 2 \\

Line 187 ⟶ 189:

0 & (x-1)(x-2)

\end{bmatrix}.

\end{align}</math>

</math>

''A'' and ''B'' are similar because the Smith normal form of their characteristic matrices match, but are not similar to ''C'' because the Smith normal form of the characteristic matrices do not match.

Line 194 ⟶ 195:

== See also ==

* [[Canonical form]]

* [[Diophantine equation]]

* [[Elementary divisors]]

* [[FrobeniusInvariant normal formfactors]]

* [[Hermite normal form]]

* [[Invariant factor]]

* [[Henry John Stephen Smith]] (1826–1883), [[eponym]] of the Smith normal form

* [[Structure theorem for finitely generated modules over a principal ideal ___domain]]

* [[Frobenius normal form]] (also called rational canonical form)

* [[Hermite normal form]]

* [[Singular value decomposition]]

== External links ==

* [http://huisman.perso.math.cnrs.fr/ens/m/s7/groupes_et_anneaux/smith.gif An animated example of computation of Smith normal form].

* [http://www.numbertheory.org/php/smith.html NumberTheory.org]

* {{WolframAlpha |id=SmithDecomposition|title=SmithDecomposition}}<ref>{{cite web|author=Wolfram Research|title=SmithDecomposition|year=2015|url=https://reference.wolfram.com/language/ref/SmithDecomposition.html|access-date={{date|06- March-2025}}|quote=<code>SmithDecomposition[''m'']</code> gives the Smith normal form decomposition of an integer matrix ''m''.}}</ref>

==References==

{{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 |urljstor=http://www.jstor.org/stable/108738 |doi=10.1098/rstl.1861.0016 |s2cid=110730515 }} Reprinted (pp. [httphttps://archive.org/stream/collectedmathema01smituoft#page/366/mode/2up 367–409]) in [httphttps://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.

* K. R. Matthews, [http://www.numbertheory.org/courses/MP274/smith.pdf Smith normal form]. MP274: Linear Algebra, Lecture Notes, University of Queensland, 1991.

* {{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]. MP274: Linear Algebra, Lecture Notes, University of Queensland, 1991.

[[Category:Matrix theory]]