Modultheorie/Z/Elementarteilersatz/Fakt/Beweis

Beweis

Wir schreiben . Wir führen Induktion über . Den Induktionsstart beweisen wir, um Wiederholungen zu vermeiden, bei der Rückführung des Induktionsschrittes auf die Induktionsvoraussetzung.

Es sei also beliebig und die Aussage für bewiesen. Zu zeigen: Sie gilt auch für .

Nehmen wir zunächst an. Dafür betrachten wir die folgenden Fälle:

  1. Fall: Es gibt mit oder . In diesem Fall kann durch Zeilen- oder Spaltenvertauschungen erreicht werden.
  2. Fall: Es gibt kein mit oder . Dann vertauschen wir die erste und die letzte Zeile und die erste und die letzte Spalte. Nun kann die Matrix betrachtet werden für die gilt, womit wir für bei der Induktionsvoraussetzung bezüglich sind und bei eine Nullmatrix haben, die die Aussage direkt erfüllt.

Es sei also .

Nehmen wir außerdem an, dass alle teilt, so können wir sukzessive von allen Zeilen mit das -fache der ersten Zeile und von allen Spalten mit das -fache der ersten Spalte abziehen. Dadurch enthalten die erste Zeile und die erste Spalte nur noch Nullen mit Ausnahme von . Die Induktionsvoraussetzung für kann daher auf die Matrix angewendet werden und für haben wir trivialerweise eine Diagonalmatrix mit den angegebenen Eigenschaften. Außerdem sind alle immer noch Vielfache von . Dies stellt sicher, dass alle folgenden Diagonalelemente Vielfache von sind (oder , wenn (siehe oben) irgendwann eine Nullzeile oder Nullspalte erreicht wurde).

Für den Fall, dass nicht alle Einträge der Matrix teilt, führen wir eine weitere Induktion über .

Es sei also . Dann teilt alle und wir sind im schon behandelten Fall.

Für den Induktionsschritt können wir direkt annehmen, dass nicht alle Einträge teilt. Betrachten wir zwei Fälle:

  1. Fall: Es gibt ein mit oder , das kein Vielfaches von ist. Nehmen wir o.B.d.A. an, dass . Durch Division mit Rest findet sich eine eindeutige Darstellung mit . Wir ziehen nun das -fache der ersten Spalte von der -ten Spalte ab und vertauschen die beiden Spalten. Dadurch ist das neue Element in der linken oberen Ecke und damit wegen im Bereich der Induktionsvoraussetzung (der inneren Induktion).
  2. Fall: Es findet sich nur für ein , das kein Vielfaches von ist. In diesem Fall annullieren wir die ersten Einträge der betreffenden Zeile und Spalte, indem wir von der -ten Spalte das -fache der ersten Spalte abziehen und genauso von der -ten Zeile das -fache der ersten Zeile. Danach addieren wir die -te Zeile zur ersten Zeile, wodurch in der -ten Spalte gilt . Nun kann das selbe Verfahren wie im 1. Fall angewendet werden - und mit finden und damit auf reduzieren - und die Situation daher auf die Induktionsvoraussetzung zurückgeführt werden.
  Daher gilt der Induktionsschritt zu für alle und daher die Aussage für alle .