Smith-Normalform

faktorisierende Normalform für Matrizen
(Weitergeleitet von Elementarteiler)

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

Bearbeiten

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.

Algorithmus

Bearbeiten

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

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

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

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

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.

Beispiel

Bearbeiten

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  .

Verwendung

Bearbeiten

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.

Siehe auch

Bearbeiten

Literatur

Bearbeiten
Bearbeiten