Zum Inhalt springen

Modultheorie/Hauptidealbereich/euklidisch/Elementarteilersatz/Fakt/Beweis

Beweis

Wir schreiben M=(ai,j)1≤i≤m,1≤j≤n. Wir führen Induktion über k. Den Induktionsstart beweisen wir, um Wiederholungen zu vermeiden, bei der Rückführung des Induktionsschrittes auf die Induktionsvoraussetzung.

Es sei k0∈ℕ also beliebig und die Aussage für k<k0 bewiesen. Zu zeigen: Sie gilt auch für k=k0.

Nehmen wir zunächst a1,1=0 an. Dafür betrachten wir die folgenden Fälle:

  1. Fall: Es gibt ai,j≠0 mit i=1 oder j=1. In diesem Fall kann durch Zeilen- oder Spaltenvertauschungen a1,1≠0 erreicht werden.
  2. Fall: Es gibt kein ai,j≠0 mit i=1 oder j=1. Dann vertauschen wir die erste und die letzte Zeile und die erste und die letzte Spalte. Nun kann die Matrix (ai,j)1≤i≤m−1,1≤j≤n−1 betrachtet werden für die k<k0 gilt, womit wir für k>1 bei der Induktionsvoraussetzung bezüglich k sind und bei k=1 eine Nullmatrix haben, die die Aussage direkt erfüllt.

Es sei also a1,1≠0.

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

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

Es sei also δ(a1,1)=min⁡(δ(A)). Dann teilt a1,1 alle ai,j und wir sind im schon behandelten Fall.

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

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