Formel für Matrix ^ m per Induktion beweisen

01.06.2012, 01:29

Kiwiatmb

Formel für Matrix ^ m per Induktion beweisen

Hallo

Folgende Aufgabe:

Sei K ein Körper und A aus M(nxn,K) gegeben durch
$\begin{eqnarray*} \begin{pmatrix} \lambda & 1 & 0 & 0 & ... & 0 \\ 0 & \lambda & 1 & 0 & ... & 0 \\ 0 & 0 &\lambda & 1 & ... & 0 \\ ... & ... & ... & ... & ... & ... \\ ... & ... & ... & ... & ... & 1 \\ 0 & ... & ... & ... & 0 & \lambda \end{pmatrix} \end{eqnarray*}$

Berechnen Sie die Potenzen A^m für m>=1.

Durch ein bisschen rumprobieren bin ich schon auf Folgendes gekommen:

$\begin{eqnarray*} (A^m)_{i j} = \begin{cases} 0 & \text{für }i<j\\ \binom{m}{|i-j|}\cdot x^{m-|i-j|} & \text{für }i\geq j \end{cases} \end{eqnarray*}$

Zur Veranschaulichung für euch mal für m=5 und Dimension n=5 (was euch hoffentlich von der Richtigkeit meiner obigen Behauptung überzeugt):
$\begin{eqnarray*} \begin{pmatrix} \lambda ^5 & 5 \lambda ^4 & 10 \lambda ^3 & 10 \lambda ^2 & 5 \lambda \\ 0 & \lambda ^5 & 5 \lambda ^4 & 10 \lambda ^3 & 10 \lambda ^2 \\ 0 & 0 & \lambda ^5 & 5 \lambda ^4 & 10 \lambda ^3 \\ 0 & 0 & 0 & \lambda ^5 & 5 \lambda ^4 \\ 0 & 0 & 0 & 0 & \lambda ^5 \\ \end{pmatrix} \end{eqnarray*}$

So, ich würde das ganze gern per vollst. Induktion beweisen.

Induktionsanfang: m=1

$\begin{eqnarray*} (A^1)_{i j}=\begin{cases} 0 & \text{für }i<j\\ \binom{1}{|i-j|}\cdot x^{1-|i-j|} & \text{für }i\geq j \end{cases}=\begin{cases} 0 & \text{für }i<j\\ \lambda & \text{für }i=j\\ 1 & \text{für }i = j+1\\ 0 & \text{für }i > j+1 \end{cases} \end{eqnarray*}$
Passt. (Ja, ist nicht glasklar, aber ausreichend denke ich mal...)

Induktionsschritt: m -> m+1

Hier sehe ich mir jetzt mal den Fall i>=j an, die 0en kommen dann schon hin... (Muss dann natürlich noch irgendwie aufgeschrieben werden.)
Hier nehme ich mir mal die etwas einfacherere Def. der Binomialkoeffizienten.

Also:
$\begin{eqnarray*} (A^{m+1})_{i j}= \binom{m+1}{|i-j|}\cdot x^{m+1-|i-j|}= \frac{(m+1)!}{(|i-j|)! \cdot (m+1-|i-j|)!} \cdot x^{m+1-|i-j|} = \frac{m!}{(|i-j|)! \cdot (m-|i-j|)!} \cdot x^{m-|i-j|} \cdot \frac{m+1}{m+1-|i-j|} \cdot x = \binom{m}{|i-j|} \cdot x^{m-|i-j|} \cdot \frac{m+1}{m+1-|i-j|} \cdot x = \text{ nutze Ind.vor.:} (A^m)_{i j} \cdot \frac{m+1}{m+1-|i-j|} \cdot x = ? \end{eqnarray*}$

So. Soweit bin ich. Eigentlich müsste ich jetzt ja mehr oder weniger fertig sein. Allerdings weiß ich gar nicht genau, was dieser Rest da rechts vom A^m jetzt eigentlich sein sollte, damit ich glücklich bin. Eigentlich ja A, aber das ist es irgendwie nicht...

Ist das überhaupt der(/ein) richtige Weg? (Wir haben gerade mit Jordanzerlegung angefangen. Sieht hier auch ein wenig danach aus, aber eigentlich muss das doch auch so mit Induktion gehen - mit Jordan bin ich noch nicht ganz fit.)

Wäre sehr froh, wenn ihr mir hier ein wenig die Augen öffnen könntet.

Danke schon jetzt !

Grüße,
~

P.S.: Ich sehe gerade, die Beträge könnte ich dann im IS weglassen, wenn ich i>=j betrachte. Aber nun gut, ändert ja nichts wesentliches.

01.06.2012, 10:58

Leopold

Auf diesen Beitrag antworten »

Es wäre zu überlegen, die Matrix folgendermaßen zu zerlegen:

$\begin{eqnarray*} A = \lambda E + U \end{eqnarray*}$

wobei $\begin{eqnarray*} E \end{eqnarray*}$ die Einheitsmatrix sei und $\begin{eqnarray*} U \end{eqnarray*}$ die Matrix mit Einsen in der ersten Nebendiagonalen und Nullen sonst. Da $\begin{eqnarray*} E \end{eqnarray*}$ mit allen Matrizen vertauschbar ist, darf man kommutativ rechnen und erhält nach dem binomischen Lehrsatz sofort:

$\begin{eqnarray*} A^m = \left( \lambda E + U \right)^m = \sum_{k=0}^m {m \choose k} \lambda^{m-k} U^k \end{eqnarray*}$

Und jetzt läuft alles auf die Berechnung von $\begin{eqnarray*} U^k \end{eqnarray*}$ hinaus. Da beobachtet man aber schnell, wie die Einsen bei jedem Schritt um 1 nach rechts wandern.

01.06.2012, 11:13

DP1996

Auf diesen Beitrag antworten »

RE: Formel für Matrix ^ m per Induktion beweisen

Zitat:

Original von Kiwiatmb
$\begin{eqnarray*} (A^m)_{i j} = \begin{cases} 0 & \text{für }i<j\\ \binom{m}{|i-j|}\cdot x^{m-|i-j|} & \text{für }i\geq j \end{cases} \end{eqnarray*}$

Das erscheint plausibel. Zwei Anmerkungen:
1. Deine Variable ist natürlich lambda
2. i bezeichnet normalerweise die Zeilennummer und j die Spaltennummer, d.h. i<j bezieht sich auf die obere Matrix-"hälfte" und i>j auf die untere. Deine Fallunterscheidung ist also grad falschrum.

Der Induktionsanfang passt soweit (eben abgesehen von Anmerkung 2)

Den Induktionsschritt finde ich hingegen unnötig kompliziert. Ich würde das Matrizenprodukt betrachten:

$\begin{eqnarray*} (A^{m+1})_{i;j}=\sum_{k=1}^n (A^m)_{i;k}(A)_{k;j} \end{eqnarray*}$

In letzterer Summe sind die meisten Einträge Null, da viele Einträge aus A Null sind. Lediglich zwei Summanden überleben, für die kannst du dann deine Induktionsvoraussetzung einsetzen, etwas umformen und bist fertig.

Edit: Oh sorry, lange nicht mehr die Vorschau funktion benutzt.

02.06.2012, 16:19

Kiwiatmb

Auf diesen Beitrag antworten »

Ich glaube, ich würde es gerne mit Induktion versuchen, auch wenn die andere Methode etwas einfacher aussieht. Jetzt hab' ich damit angefangen, jetzt mach' ich das auch. Bleibt mir die andere Methode ja immer noch als Rückfalllösung.

Also:
$\begin{eqnarray*} (A^{m+1})_{i;j}=\sum_{k=1}^n (A^m)_{i;k}(A)_{k;j} = \begin{cases} 0 & \text{für }j<i\\ \binom{m}{|j-i|-1} \lambda ^{m+1-|i-j|} + \binom{m}{|j-i|} \lambda ^{m-|i-j|} & \text{für }j \geq i \end{cases} \end{eqnarray*}$
So, und nun ? Hier kann ich natürlich die I.V. einsetzen, aber fertig bin ich irgendwie immer noch nicht. Hab' mal probiert, meine etwas eingerosteten Binomialkoeffizientenskills auszupacken:

$\begin{eqnarray*} \binom{m}{|j-i|-1} \lambda ^{m+1-|i-j|} + \binom{m}{|j-i|} \lambda ^{m-|i-j|} &= \left( \binom{m+1}{|j-i|} - \binom{m}{|j-i|} \right)\lambda ^{m+1-|j-i|} + \binom{m}{|j-i|} \lambda ^{m-|j-i|} &= \binom{m+1}{|j-i|} \lambda ^{m+1-|j-i|} - \binom{m}{|j-i|} \lambda ^{m+1-|j-i|} + \binom{m}{|j-i|} \lambda ^{m-|j-i|} &= \binom{m+1}{|j-i|} \lambda ^{m+1-|j-i|} - \binom{m}{|j-i|} \lambda ^{m-|j-i|} \cdot \lambda + \binom{m}{|j-i|} \lambda ^{m-|j-i|} &= (A^{m+1})_{i j} - \lambda (A^m)_{i j} + (A^m)_{i j} \end{eqnarray*}$

Sieht sehr schön aus. Aber ob das stimmt und wie das hilft, seh' ich gerade wirklich nicht...

03.06.2012, 10:00

soundso

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} (A^{m+1})_{i;j}=%5Csum_{k=1}^n%20(A^m)_{i;k}(A)_{k;j}%20=%20%5Cbegin{cases}%3Cbr%20/%3E%20%20%3Cbr%20/%3E0%20%20&%20%5Ctext{f%FCr%20}j%3Ci%5C%5C%3Cbr%20/%3E%20%3Cbr%20/%3E%5Cbinom{m}{|j-i|-1}%20%5Clambda%20^{m+1-|i-j|}%20+%20%5Cbinom{m}{|j-i|}%20%5Clambda%20^{m-|i-j|}%20&%20%5Ctext{f%FCr%20}j%20%5Cgeq%20i%3Cbr%20/%3E%3Cbr%20/%3E%5Cend{cases} \end{eqnarray*}$

A ist doch nur für $\begin{eqnarray*} (A)_{j;j} , (A)_{j-1,j} \end{eqnarray*}$ ungleich null
Wenn ich das bei j>=i für k einsetze und für die A die Werte 1 oder x komm ich auf
$\begin{eqnarray*} %5Cbinom{m}{|j-i|-1}%20%5Clambda%20^{m+1-|i-j|}+%5Cbinom{m}{|j-i|}%20%5Clambda%20^{m+1-|i-j|} \end{eqnarray*}$
und dann auch aufs richtige Ergebnis Freude

(ich glaub wir sind im gleichen Kurs smile

)

03.06.2012, 17:13

Kiwiatmb

Auf diesen Beitrag antworten »

Jop, ich seh' grad, ich hab' dasselbe in meiner Beispielmatrix stehen. Jetzt ist alles gut. (:

Zitat:

(ich glaub wir sind im gleichen Kurs smile

)

Vielen, vielen Dank an euch 3 !

Neue Frage »

Antworten »

Formel für Matrix ^ m per Induktion beweisen

Verwandte Themen