# Modultheorie/Hauptidealbereich/euklidisch/Elementarteilersatz/Fakt/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:
* 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.
* 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:
* 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).
* 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.
$k=k_{0}$
$\delta (a_{1,1})$
$k$