Modultheorie/Hauptidealbereich/euklidisch/Elementarteilersatz/Fakt/Beweis

Beweis

Wir schreiben ${}M=(a_{i,j})_{1\leq i\leq m,1\leq j\leq 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 ${}k_{0}\in \mathbb {N}$ also beliebig und die Aussage für ${}k<k_{0}$ bewiesen. Zu zeigen: Sie gilt auch für ${}k=k_{0}$.

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

1. Fall: Es gibt ${}a_{i,j}\neq 0$ mit ${}i=1$ oder ${}j=1$. In diesem Fall kann durch Zeilen- oder Spaltenvertauschungen ${}a_{1,1}\neq 0$ erreicht werden.
2. Fall: Es gibt kein ${}a_{i,j}\neq 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 ${}(a_{i,j})_{1\leq i\leq m-1,1\leq j\leq n-1}$ betrachtet werden für die ${}k<k_{0}$ 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 ${}a_{1,1}\neq 0$.

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

Für den Fall, dass ${}a_{1,1}$ nicht alle Einträge der Matrix teilt, führen wir eine weitere Induktion über ${}\delta (a_{1,1})$.

Es sei also ${}\delta (a_{1,1})=\operatorname {min} (\delta (A))$. Dann teilt ${}a_{1,1}$ alle ${}a_{i,j}$ und wir sind im schon behandelten Fall.

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

1. Fall: Es gibt ein ${}a_{i,j}$ mit ${}i=1$ oder ${}j=1$, das kein Vielfaches von ${}b:=a_{1,1}$ ist. Nehmen wir o.B.d.A. an, dass ${}i=1$. Durch Division mit Rest findet sich eine eindeutige Darstellung ${}a_{1,j}=cb+r$ mit ${}\delta (r)<\delta (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 ${}(a_{1,1}=r)$ und damit wegen ${}\delta (r)<\delta (b)$ im Bereich der Induktionsvoraussetzung (der inneren Induktion).
2. Fall: Es findet sich nur für ${}i,j\geq 2$ ein ${}a_{i,j}$, das kein Vielfaches von ${}a_{1,1}$ ist. In diesem Fall annullieren wir die ersten Einträge der betreffenden Zeile und Spalte, indem wir von der ${}j$-ten Spalte das ${}{\frac {a_{1,j}}{a_{1,1}}}$-fache der ersten Spalte abziehen und genauso von der ${}i$-ten Zeile das ${}{\frac {a_{i,1}}{a_{1,1}}}$-fache der ersten Zeile. Danach addieren wir die ${}i$-te Zeile zur ersten Zeile, wodurch in der ${}j$-ten Spalte gilt ${}a_{1,j}=a_{i,j}$. Nun kann das selbe Verfahren wie im 1. Fall angewendet werden - ${}q$ und ${}r$ mit ${}a_{1,j}=qa_{1,1}+r$ finden und damit ${}a_{1,1}$ auf ${}r$ reduzieren - und die Situation daher auf die Induktionsvoraussetzung zurückgeführt werden.

  Daher gilt der Induktionsschritt zu ${}k=k_{0}$ für alle ${}\delta (a_{1,1})$ und daher die Aussage für alle ${}k$.

Zur bewiesenen Aussage