Smith-Normalform

Grundidee und Definition

Die Smith-Normalform ist eine Normalform für beliebige Matrizen über einem Hauptidealring R. Sie ist eine Diagonalmatrix, die aus einer Ausgangsmatrix A durch Multiplikation von links und rechts mit regulären, also invertierbaren, quadratischen Matrizen entsteht. Die Diagonaleinträge heißen Elementarteiler oder invariante Faktoren.

Für eine von der Nullmatrix verschiedene (m×n)-Matrix A existieren reguläre Matrizen S der Größe m×m und T der Größe n×n mit

S·A·T = diag(α₁, …, αᵣ, 0, …, 0).

Dabei gilt für die Hauptdiagonalelemente die Teilbarkeitsbedingung αᵢ | αᵢ₊₁ für i = 1, …, r−1. Die Elementarteiler sind bis auf Multiplikation mit einer Einheit eindeutig bestimmt. Sie lassen sich aus den größten gemeinsamen Teilern der Minoren berechnen: αᵢ = dᵢ(A) / dᵢ₋₁(A). Dabei ist dᵢ(A) der größte gemeinsame Teiler aller i×i-Minoren von A.

Ausgangslage und Pivotwahl

Der zentrale Teil des Smith-Algorithmus besteht darin, S und T so zu bestimmen, dass S·A·T eine Diagonalmatrix wird. Dazu wird A schrittweise durch elementare, invertierbare Zeilen- und Spaltenumformungen verändert. Gleichzeitig werden S und T ausgehend von passenden Einheitsmatrizen aufgebaut. Bei einer Zeilenumformung wird S von rechts, bei einer Spaltenumformung T von links mit der entsprechenden Elementarmatrix multipliziert. Für die jeweils veränderten Matrizen gilt A′ = S′·A·T′. Weil nur invertierbare Operationen verwendet werden, bleiben S und T regulär.

Für t = 1, …, m wird zunächst der kleinste Spaltenindex jₜ gesucht, dessen Spalte mindestens einen von null verschiedenen Eintrag enthält. Für t > 1 beginnt die Suche bei jₜ₋₁ + 1. Der Diagonaleintrag aₜ,ⱼₜ soll ungleich null sein. Falls dort eine Null steht, wird eine Zeile k mit aₖ,ⱼₜ ≠ 0 ausgewählt und durch eine Permutationsmatrix mit Zeile t vertauscht. Der von null verschiedene Eintrag auf der Diagonale der aktuellen Spalte ist das Pivotelement.

Verbesserung des Pivots

Teilt das Pivotelement aₜ,ⱼₜ einen anderen Eintrag aₖ,ⱼₜ nicht, wird es durch einen kleineren gemeinsamen Teiler ersetzt. Es sei

β = ggT(aₜ,ⱼₜ, aₖ,ⱼₜ).

Nach dem Lemma von Bézout gibt es σ, τ ∈ R mit β = aₜ,ⱼₜ·σ + aₖ,ⱼₜ·τ. Setzt man α = aₜ,ⱼₜ/β und γ = aₖ,ⱼₜ/β, gilt σ·α + τ·γ = 1. Deshalb ist die Matrix

L₀ = [[σ, τ], [−γ, α]]

regulär und besitzt die Inverse L₀⁻¹ = [[α, −τ], [γ, σ]]. Wird L₀ in die Zeilen und Spalten t und k einer Einheitsmatrix eingesetzt, erhält man eine Elementarmatrix L. Das Produkt L·A enthält dann an der Stelle (t, jₜ) den Eintrag β; an der Stelle (k, jₜ) steht aufgrund der Konstruktion eine Null.

Dieser Vorgang wird wiederholt, solange sich das Pivotelement verbessern lässt. Bezeichnet δ(a) die Anzahl der Primfaktoren eines Elements a, so gilt nach jedem Verbesserungsschritt δ(β) < δ(aₜ,ⱼₜ). Daher endet der Prozess nach endlich vielen Schritten. Danach teilt das Pivotelement alle Einträge in seiner Spalte.

Elimination der Einträge

Zuerst werden durch geeignete Vielfache der Zeile t alle Einträge außerhalb des Diagonaleintrags in der Spalte jₜ zu null gemacht. Anschließend müssen auch die von null verschiedenen Einträge in Zeile t beseitigt werden. Dazu wird Schritt 2 auf die betreffenden Spalten angewandt, verbunden mit Rechtsmultiplikationen.

Dabei können bereits erzeugte Nulleinträge vorübergehend wieder von null verschieden werden. Die von den jeweiligen Pivoteinträgen erzeugten Ideale bilden jedoch eine aufsteigende Kette, weil spätere Einträge die früheren teilen. Da R noethersch ist, werden diese Ideale nach endlich vielen Schritten stationär. Schließlich teilt das Pivotelement alle von null verschiedenen Einträge in seiner Zeile und Spalte. Diese Einträge können dann eliminiert werden, ohne die bereits erzeugten Nullen zu verlieren.

Danach wird nur noch der rechts unterhalb des aktuellen Pivots liegende Block bearbeitet. Der Algorithmus wird für diese Teilmatrix mit t + 1 erneut bei der Pivotwahl begonnen.

Normierung zur Smith-Normalform

Durch die wiederholte Anwendung der ersten drei Schritte entsteht eine (m×n)-Matrix, deren einzige von null verschiedenen Einträge an Positionen (l, jₗ) mit j₁ < … < jᵣ liegen, wobei r ≤ min(m,n) gilt. Nullspalten werden nach rechts verschoben. Die von null verschiedenen Einträge liegen dann an den Positionen (i,i) für i = 1, …, r und werden mit αᵢ bezeichnet.

Möglicherweise erfüllen sie noch nicht α₁ | α₂ | … | αᵣ. Falls αᵢ den Eintrag αᵢ₊₁ nicht teilt, wird zunächst Spalte i+1 zu Spalte i addiert. Dadurch entsteht in Spalte i zusätzlich der Eintrag αᵢ₊₁, während αᵢ an Position (i,i) unverändert bleibt. Wie in Schritt 2 wird anschließend der Eintrag an dieser Position auf β = ggT(αᵢ, αᵢ₊₁) gebracht. Mit Schritt 3 wird die Matrix wieder diagonalisiert.

Der neue Eintrag an Position (i+1,i+1) ist eine Linearkombination der ursprünglichen Einträge αᵢ und αᵢ₊₁ und daher durch β teilbar. Die Summe δ(α₁) + … + δ(αᵣ) bleibt unverändert; sie entspricht dem δ der Determinante der oberen r×r-Teilmatrix. Gleichzeitig sinkt die Größe Σⱼ₌₁ʳ (r−j)δ(αⱼ), weil Primfaktoren nach rechts verschoben werden. Deshalb endet auch dieser Prozess nach endlich vielen Schritten und die Teilbarkeitskette wird erreicht. Da alle Umformungen invertierbar sind, existieren schließlich reguläre S und T mit S·A·T in Smith-Normalform. Damit ist die Existenz der Smith-Normalform gezeigt.

Beispiel und Anwendungen

Über dem Ring R = ℤ wird die Matrix

A = [[2, 4, 4], [−6, 6, 12], [10, −4, −16]]

bearbeitet. Die angegebenen Zwischenschritte führen schließlich zu

[[2, 0, 0], [0, 6, 0], [0, 0, 12]].

Diese letzte Matrix ist die Smith-Normalform von A über ℤ. Die invarianten Faktoren sind 2, 6 und 12; sie erfüllen 2 | 6 und 6 | 12.

Die Smith-Normalform wird unter anderem zur Berechnung der Homologie eines Kettenkomplexes mit endlich erzeugten Moduln verwendet. In der Topologie lassen sich damit beispielsweise Homologien von Simplizialkomplexen oder Zellkomplexen über den ganzen Zahlen berechnen, weil deren Randoperatoren durch ganzzahlige Matrizen dargestellt werden. Außerdem kann sie zum Beweis des Struktursatzes für endlich erzeugte Moduln über einem Hauptidealring dienen.

Weiterhin entscheidet sie, ob zwei Matrizen über demselben Körper ähnlich sind. Matrizen A und B sind genau dann ähnlich, wenn ihre charakteristischen Matrizen xI−A und xI−B dieselbe Smith-Normalform besitzen. Für

A = [[1, 2], [0, 1]] und B = [[3, −4], [1, −1]]

gilt jeweils SNF(xI−A) = SNF(xI−B) = diag(1, (x−1)²). Daher sind A und B ähnlich. Für C = [[1, 0], [1, 2]] gilt dagegen SNF(xI−C) = diag(1, (x−1)(x−2)); C ist somit nicht ähnlich zu A oder B.