Smith-Normalform

Die Smith-Normalform ist in der Mathematik eine Normalform, die für beliebige Matrizen mit Einträgen aus einem Hauptidealring definiert ist. Die Smith-Normalform einer Matrix ist eine Diagonalmatrix, die aus der Ausgangsmatrix durch Multiplikation von links und von rechts mit je einer regulären quadratischen Matrix erhalten wird. Die Einträge dieser Diagonalmatrix werden Elementarteiler oder invariante Faktoren der Ausgangsmatrix genannt. Die Smith-Normalform ist nach dem englischen Mathematiker Henry John Stephen Smith benannt.

Definition

Ist $A$ eine $(m\times n)$-Matrix über einem Hauptidealring $R$, die nicht gleich der Nullmatrix ist, dann existieren eine reguläre $(m\times m)$-Matrix $S$ und eine reguläre $(n\times n)$-Matrix $T$, sodass

$S\cdot A\cdot T={\begin{pmatrix}\alpha _{1}&0&\cdots &\cdots &\cdots &0\\0&\ddots &\ddots &&&\vdots \\\vdots &\ddots &\alpha _{r}&\ddots &&\vdots \\\vdots &&\ddots &0&\ddots &\vdots \\\vdots &&&\ddots &\ddots &0\\0&\cdots &\cdots &\cdots &0&0\end{pmatrix}}$

gilt. Für die Hauptdiagonalelemente soll dabei $\alpha _{i}\mid \alpha _{i+1}$ für $i=1,\ldots ,r-1$ gelten. Diese Darstellung wird Smith-Normalform der Matrix $A$ genannt. Die Einträge $\alpha _{i}$ sind bis auf Multiplikation mit einer Einheit eindeutig definiert und werden Elementarteiler oder invariante Faktoren der Matrix genannt. Die Elementarteiler sind dabei (bis auf Multiplikation mit einer Einheit) durch

$\alpha _{i}={\frac {d_{i}(A)}{d_{i-1}(A)}}$

gegeben, wobei $d_{i}(A)$ der größte gemeinsame Teiler aller $(i\times i)$-Minoren der Matrix $A$ ist.

Algorithmus

Der schwierige Teil bei der Ermittlung der Smith-Normalform ist die Bestimmung zweier Matrizen $S$ und $T$, sodass das Produkt $S\cdot A\cdot T$ eine Diagonalmatrix ergibt. Hierzu wird die Matrix $A$ sukzessive auf Diagonalgestalt gebracht, wobei in jedem Schritt elementare Zeilen- oder Spaltenumformungen durchgeführt werden. Parallel dazu werden die Matrizen $S$ und $T$ ausgehend von Einheitsmatrizen passender Größe sukzessive umgeformt. Dabei wird bei einer Zeilenumformung die Matrix $S$ von rechts und bei einer Spaltenumformung die Matrix $T$ von links mit einer entsprechenden Elementarmatrix multipliziert. Für die in einem Schritt modifizierten Matrizen $A',S',T'$ gilt dann die Beziehung

$A'=S'\cdot A\cdot T'$.

Dabei werden nur invertierbare Zeilen- und Spaltenoperationen durchgeführt, sodass $S$ und $T$ regulär bleiben. Ausgehend von der Diagonalgestalt von $A$ wird dann schließlich die Smith-Normalform ermittelt. Um eine Matrix in Smith-Normalform zu bringen, werden für $t=1,\ldots ,m$ konkret die folgenden Schritte durchgeführt.

Schritt 1: Wahl des Pivots

Sei $j_{t}$ der kleinste Spaltenindex derjenigen Spalten von $A$, die mindestens einen Eintrag ungleich null aufweisen, wobei die Suche für $t>1$ bei $j_{t-1}+1$ gestartet wird. Nun wird gefordert, dass für das Diagonalelement

$a_{t,j_{t}}\neq 0$

gilt. Ist dies nicht der Fall, dann gibt es nach Voraussetzung ein Element $a_{k,j_{t}}\neq 0$. Nun werden die beiden Zeilen $t$ und $k$ durch Multiplikation mit einer Permutationsmatrix vertauscht, sodass auf der Diagonale der aktuellen Spalte ein Element ungleich null zu stehen kommt. Dieses Element wird dann Pivotelement genannt.

Schritt 2: Verbesserung des Pivots

Gibt es nun einen Eintrag $a_{k,j_{t}}$ mit $a_{t,j_{t}}\nmid a_{k,j_{t}}$, dann sei

$\beta =\operatorname {ggT} \left(a_{t,j_{t}},a_{k,j_{t}}\right)$.

Der größte gemeinsame Teiler zweier Elemente eines Hauptidealrings lässt sich durch das Lemma von Bézout darstellen. Es existieren dann Elemente $\sigma ,\tau \in R$, sodass

$\beta =a_{t,j_{t}}\cdot \sigma +a_{k,j_{t}}\cdot \tau$

gilt. Mittels einer Zeilenumformung wird nun das $\sigma$-fache der Zeile $t$ zu dem $\tau$-fachen der Zeile $k$ addiert. Erfüllen $\sigma$ und $\tau$ obige Gleichung, dann gilt für $\alpha =a_{t,j_{t}}/\beta$ und $\gamma =a_{k,j_{t}}/\beta$ (diese Divisionen sind aufgrund der Definition von $\beta$ möglich)

$\sigma \cdot \alpha +\tau \cdot \gamma =1$.

Die Matrix

$L_{0}={\begin{pmatrix}\sigma &\tau \\-\gamma &\alpha \\\end{pmatrix}}$

ist damit regulär mit der Inversen

$L_{0}^{-1}={\begin{pmatrix}\alpha &-\tau \\\gamma &\sigma \\\end{pmatrix}}$.

Indem die Einträge der Matrix $L_{0}$ in die Zeilen und Spalten $t$ und $k$ einer Einheitsmatrix eingefügt werden, erhält man die Elementarmatrix $L$. Das Produkt $L\cdot A$ besitzt dann an der Stelle $(t,j_{t})$ den Eintrag $\beta$ (und aufgrund der Wahl von $\alpha$ und $\gamma$ an der Stelle $(k,j_{t})$ den Eintrag null, was praktisch, aber nicht wesentlich für den Algorithmus ist). Dieser neue Eintrag $\beta$ teilt den vorigen Eintrag $a_{t,j_{t}}$. Dieser Schritt wird nun solange wiederholt, bis keine Verbesserung eintritt. Bezeichnet $\delta (a)$ die Anzahl der Primfaktoren eines Elements $a$, dann gilt nach jedem Schritt

$\delta (\beta )<\delta (a_{t,j_{t}})$,

daher terminiert der Prozess nach endlich vielen Schritten. Das Ergebnis ist eine Matrix mit einem Eintrag an der Stelle $(t,j_{t})$, der alle Einträge in der Spalte $j_{t}$ teilt.

Schritt 3: Elimination von Einträgen

Durch Addition entsprechender Vielfache der Zeile $t$ werden nun alle Einträge in der Spalte $j_{t}$ außerhalb der Diagonale zu null gesetzt. Dies kann ebenfalls durch Linksmultiplikation mit entsprechenden Elementarmatrizen erreicht werden. Um die Matrix jedoch auf volle Diagonalgestalt zu bringen, müssen auch die Einträge ungleich Null in der Zeile $t$ eliminiert werden. Dies kann durch Wiederholung von Schritt 2 für die Spalten der Matrix in Kombination mit Rechtsmultiplikationen erreicht werden. Allerdings kann dies dazu führen, dass Nulleinträge, die in einer vorhergegangenen Anwendung von Schritt 3 erzeugt wurden, wieder ungleich null werden.

Die Ideale, die durch die Elemente an der Position $(t,j_{t})$ gebildet werden, erzeugen jedoch eine aufsteigende Kette, da die Einträge aus einem späteren Schritt immer die Einträge aus einem früheren Schritt teilen. Nachdem $R$ noethersch ist, werden die Ideale ab einem gewissen Schritt stationär und ändern sich nicht mehr. Das bedeutet, dass schließlich der Eintrag an der Stelle $(t,j_{t})$ nach einer Anwendung von Schritt 2 alle Einträge ungleich null in der gleichen Spalte und Zeile teilt. Dann können diese Einträge eliminiert werden, wobei die bereits erzeugten Nulleinträge erhalten bleiben. Nun muss nur noch der Block von $A$ rechts unterhalb von $(t,j_{t})$ diagonalisiert werden. Der Algorithmus wird mit dieser Teilmatrix mit $t+1$ bei Schritt 1 weitergeführt.

Schritt 4: Normierung

Die wiederholte Anwendung der Schritte 1 bis 3 führt schließlich zu einer $(m\times n)$-Matrix, bei der nur die Einträge $(l,j_{l})$ für $j_{1}<\ldots <j_{r}$ mit $r\leq \min(m,n)$ ungleich null sind. Die Nullspalten dieser Matrix werden nun nach rechts verschoben, sodass die Einträge ungleich null genau an den Positionen $(i,i)$ für $i=1,\ldots ,r$ liegen. Diese Einträge seien nun durch $\alpha _{i}$ bezeichnet.

Die Teilbarkeitsforderung der Smith-Normalform an die Diagonalelemente ist jedoch möglicherweise noch nicht erfüllt. Gilt $\alpha _{i}\nmid \alpha _{i+1}$ für einen Index $i$, dann kann dies durch Zeilen- und Spaltenumformungen folgendermaßen behoben werden. Zunächst wird die Spalte $i+1$ zur Spalte $i$ addiert, sodass ein Eintrag $\alpha _{i+1}$ in der Spalte $i$ entsteht, ohne dass der Diagonaleintrag $\alpha _{i}$ an der Position $(i,i)$ verändert wird. Nun wird wie in Schritt 2 mit einer Zeilenumformung der Eintrag an der Stelle $(i,i)$ gleich

$\beta =\operatorname {ggT} (\alpha _{i},\alpha _{i+1})$

gesetzt. Schließlich wird wie in Schritt 3 die Matrix wieder diagonalisiert. Nachdem der neue Eintrag an der Stelle $(i+1,i+1)$ eine Linearkombination der ursprünglichen Einträge $\alpha _{i}$ und $\alpha _{i+1}$ ist, muss er durch $\beta$ teilbar sein. Durch diese Operation ändert sich der Wert $\delta (\alpha _{1})+\cdots +\delta (\alpha _{r})$ nicht (er entspricht dem $\delta$ der Determinante der oberen $(r\times r)$-Teilmatrix), allerdings verringert sich der Wert von

$\sum _{j=1}^{r}(r-j)\delta (\alpha _{j})$,

dadurch dass die Primfaktoren nach rechts verschoben werden. Daher sind nach endlich vielen Anwendungen keine weiteren Operationen möglich, was bedeutet, dass wie gewünscht $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ erreicht wurde. Nachdem alle Zeilen- und Spaltenumformungen dieses Prozesses invertierbar sind, müssen invertierbare Matrizen $S,T$ existieren, sodass $S\cdot A\cdot T$ die Smith-Normalform ergibt. Insbesondere bedeutet dies, dass die Smith-Normalform immer existiert, was in der Definition noch ohne Beweis angenommen wurde.

Beispiel

Als Beispiel wird die Smith-Normalform der Matrix

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

berechnet. Die folgenden Matrizen sind die Zwischenschritte des Smith-Algorithmus angewandt auf diese Matrix:

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

$\to {\begin{pmatrix}2&0&0\\0&6&12\\0&18&24\end{pmatrix}}\to {\begin{pmatrix}2&0&0\\0&6&12\\0&0&-12\end{pmatrix}}\to {\begin{pmatrix}2&0&0\\0&6&0\\0&0&12\end{pmatrix}}$

Die letzte Matrix stellt dann die Smith-Normalform von $A$ dar. Die invarianten Faktoren von $A$ sind damit $2$, $6$ und $12$.

Verwendung

Die Smith-Normalform ist nützlich für die Berechnung der Homologie eines Kettenkomplexes, wenn seine Moduln endlich erzeugt sind. In der Topologie kann die Smith-Normalform beispielsweise eingesetzt werden, um die Homologie eines Simplizialkomplexes oder eines Zellkomplexes über den ganzen Zahlen zu berechnen, da die Randoperatoren solcher Komplexe gerade durch ganzzahlige Matrizen dargestellt werden. Sie kann auch verwendet werden, um den Struktursatz für endlich erzeugte Moduln über einem Hauptidealring zu beweisen.

Die Smith-Normalform kann auch verwendet werden, um zu ermitteln ob zwei Matrizen über dem gleichen Körper zueinander ähnlich sind. Zwei Matrizen $A$ und $B$ sind nämlich genau dann zueinander ähnlich, wenn ihre charakteristischen Matrizen $xI-A$ und $xI-B$ die gleiche Smith-Normalform besitzen. Beispielsweise gilt für folgende Matrizen:

${\begin{aligned}A&{}={\begin{pmatrix}1&2\\0&1\end{pmatrix}},&&{\mbox{SNF}}(xI-A)={\begin{pmatrix}1&0\\0&(x-1)^{2}\end{pmatrix}}\\B&{}={\begin{pmatrix}3&-4\\1&-1\end{pmatrix}},&&{\mbox{SNF}}(xI-B)={\begin{pmatrix}1&0\\0&(x-1)^{2}\end{pmatrix}}\\C&{}={\begin{pmatrix}1&0\\1&2\end{pmatrix}},&&{\mbox{SNF}}(xI-C)={\begin{pmatrix}1&0\\0&(x-1)(x-2)\end{pmatrix}}\end{aligned}}$

Daher sind $A$ und $B$ zueinander ähnlich, da die Smith-Normalformen ihrer charakteristischen Matrizen gleich sind, sie sind aber nicht ähnlich zu $C$, da die charakteristischen Matrizen unterschiedlich sind.

Siehe auch

• Frobenius-Normalform
• Jordansche Normalform
• Singulärwertzerlegung

Literatur

• Henry J. Stephen Smith: On systems of linear indeterminate equations and congruences. In: Phil. Trans. R. Soc. Lond.. 151, Nr. 1, 1861, S. 293–326. . Reprinted. J. W. L. Glaisher (Hrsg.): The Collected Mathematical Papers of Henry John Stephen Smith, Vol. I. Clarendon Press, Oxford 1894, S. 367–409, Textarchiv – Internet Archive
• K. R. Matthews: Smith normal form. (PDF; 143 kB) In: MP274: Linear Algebra, Lecture Notes, University of Queensland, 1991.
• G. Kemper, F. Reimers: Kapitel 7: Normalformen. In: Lineare Algebra, Springer Spektrum Berlin, Heidelberg, 2022.

Weblinks

• Smith normal form. In: PlanetMath. (englisch)
• Example of Smith normal form. In: PlanetMath. (englisch)