MathB.in - Share Mathematics with LaTeX and Markdown

Sei 
$$M=\begin{pmatrix}0&1&0&0&\ldots&0\\
0&0&1&0&\ldots&0\\
0&0&0&1&\ldots&0\\
0&0&0&0&\ldots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&0&\ldots&1\\
0&0&0&0&\ldots&0\\
\end{pmatrix}$$
eine $n\times n$-Matrix.
Für $M$ gilt: $M_{i,j}=1$ genau dann, wenn $j-i=1$, sonst 0.

Nun gilt Folgendes: $M^k_{i,j}=1$ genau dann, wenn $j-i=k$, sonst 0.

Wir beweisen dies mit vollständiger Induktion nach $k$.

Induktionsanfang: Der Fall $k=0$ und $k=1$ sind klar.

Sei nun $k$ eine beliebige feste natürliche Zahl.

Induktionsannahme:  $M^{k-1}_{i,j}=1$ genau dann, wenn $j-i=k-1$, sonst 0.

Wir zeigen damit: $M^k_{i,j}=1$ genau dann, wenn $j-i=k$, sonst 0.

Wegen $M^k=M\cdot M^{k-1}$ berechnet sich ein Zelleintrag mit $M^k[i,j]=\sum_{r=1}^n M[i,r]\cdot M^{k-1}[r,j]$.
Da in jeder Zeile bzw. Spalte von $M$ bzw. $M^{k-1}$ höchstens einmal 1 steht, sind auch die Zelleneinträge von $M^k$ höchstens 1. 
Die Produkte $M[i,r]\cdot M^{k-1}[r,j]$ sind genau dann 1, wenn  beide Zahlen $M[i,r]$ und $M^{k-1}[r,j]$ gleich 1 sind. 
Aus der Induktionsannahme folgt, dass diese Bedingung genau dann gilt, wenn $r-i=1$ und $j-r=k-1$. Also gilt $r=1+i=j-k+1$ und damit $j-i=k$.

Mithilfe dieses Ergebnisses ist auch klar, dass $M^{m-1}\neq0$ (es gibt einen 1 in der letzten Position der ersten Zeile), aber $M^m=0$.  Dies gilt auch für größere Potenzen.

Wed, 09 May 2018 08:02 GMT