Smith-Normalform

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

Ist eine -Matrix über einem Hauptidealring , die nicht gleich der Nullmatrix ist, dann existieren eine reguläre -Matrix und eine reguläre -Matrix , sodass

gilt. Für die Hauptdiagonalelemente soll dabei für gelten. Diese Darstellung wird Smith-Normalform der Matrix genannt. Die Einträge 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

gegeben, wobei der größte gemeinsame Teiler aller -Minoren der Matrix ist.

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

.

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

Schritt 1: Wahl des Pivots

[Bearbeiten | Quelltext bearbeiten]

Sei der kleinste Spaltenindex derjenigen Spalten von , die mindestens einen Eintrag ungleich null aufweisen, wobei die Suche für bei gestartet wird. Nun wird gefordert, dass für das Diagonalelement

gilt. Ist dies nicht der Fall, dann gibt es nach Voraussetzung ein Element . Nun werden die beiden Zeilen und 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

[Bearbeiten | Quelltext bearbeiten]

Gibt es nun einen Eintrag mit , dann sei

.

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

gilt. Mittels einer Zeilenumformung wird nun das -fache der Zeile zu dem -fachen der Zeile addiert. Erfüllen und obige Gleichung, dann gilt für und (diese Divisionen sind aufgrund der Definition von möglich)

.

Die Matrix

ist damit regulär mit der Inversen

.

Indem die Einträge der Matrix in die Zeilen und Spalten und einer Einheitsmatrix eingefügt werden, erhält man die Elementarmatrix . Das Produkt besitzt dann an der Stelle den Eintrag (und aufgrund der Wahl von und an der Stelle den Eintrag null, was praktisch, aber nicht wesentlich für den Algorithmus ist). Dieser neue Eintrag teilt den vorigen Eintrag . Dieser Schritt wird nun solange wiederholt, bis keine Verbesserung eintritt. Bezeichnet die Anzahl der Primfaktoren eines Elements , dann gilt nach jedem Schritt

,

daher terminiert der Prozess nach endlich vielen Schritten. Das Ergebnis ist eine Matrix mit einem Eintrag an der Stelle , der alle Einträge in der Spalte teilt.

Schritt 3: Elimination von Einträgen

[Bearbeiten | Quelltext bearbeiten]

Durch Addition entsprechender Vielfache der Zeile werden nun alle Einträge in der Spalte 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 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 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 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 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 rechts unterhalb von diagonalisiert werden. Der Algorithmus wird mit dieser Teilmatrix mit bei Schritt 1 weitergeführt.

Schritt 4: Normierung

[Bearbeiten | Quelltext bearbeiten]

Die wiederholte Anwendung der Schritte 1 bis 3 führt schließlich zu einer -Matrix, bei der nur die Einträge für mit ungleich null sind. Die Nullspalten dieser Matrix werden nun nach rechts verschoben, sodass die Einträge ungleich null genau an den Positionen für liegen. Diese Einträge seien nun durch bezeichnet.

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

gesetzt. Schließlich wird wie in Schritt 3 die Matrix wieder diagonalisiert. Nachdem der neue Eintrag an der Stelle eine Linearkombination der ursprünglichen Einträge und ist, muss er durch teilbar sein. Durch diese Operation ändert sich der Wert nicht (er entspricht dem der Determinante der oberen -Teilmatrix), allerdings verringert sich der Wert von

,

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 erreicht wurde. Nachdem alle Zeilen- und Spaltenumformungen dieses Prozesses invertierbar sind, müssen invertierbare Matrizen existieren, sodass die Smith-Normalform ergibt. Insbesondere bedeutet dies, dass die Smith-Normalform immer existiert, was in der Definition noch ohne Beweis angenommen wurde.

Als Beispiel wird die Smith-Normalform der Matrix

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

Die letzte Matrix stellt dann die Smith-Normalform von dar. Die invarianten Faktoren von sind damit , und .

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 und sind nämlich genau dann zueinander ähnlich, wenn ihre charakteristischen Matrizen und die gleiche Smith-Normalform besitzen. Beispielsweise gilt für folgende Matrizen:

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