Assoziativitaet der Matrixmultiplikation

20.12.2013, 21:43

Joefish

Assoziativitaet der Matrixmultiplikation

$\begin{eqnarray*} &&\textsf{Sei}~ A^{m,n}, B^{n,o}, C^{o,p} ~\textsf{mit}~ m,n,o,p \in \mathbb{N}_0 \textsf{.} \left[d_{ij} \right] \textsf{sei Element der Matrix}~ \left(A \cdot B \right) \cdot C ~\textsf{an der Stelle}~ i,j \textsf{.} &&\textsf{Zeige dass}~ \left(A \cdot B \right) \cdot C = A \left(B \cdot C \right) ~ \textsf{gilt.} \\ &&\begin{array}{l c l c l} \left(A \cdot B \right) \cdot C &=& \sum\limits_{s=1}^o \left(\sum\limits_{k=1}^n a_{ik} \cdot b_{ks} \right) \cdot c_{sj} \\ &=& \sum\limits_{s=1}^o \sum\limits_{k=1}^n a_{ik} \cdot b_{ks} \cdot c_{sj} & \quad & \left(\textsf{Ausklammern von}~ \sum\limits_{k=1}^n a_{ik} \cdot b_{ks} \right) \\ &=& \left(\sum\limits_{k=1}^n a_{ik} \cdot b_{ks} \right) \cdot \sum\limits_{s=1}^o c_{sj} \\ &=& \sum\limits_{k=1}^n \sum\limits_{s=1}^o a_{ik} \cdot b_{ks} \cdot c_{sj} \\ &=& \sum\limits_{k=1}^n a_{ik} \left(\sum\limits_{s=1}^o b_{ks} \cdot c_{sj} \right) &=& A \cdot \left( B \cdot C \right)\\ \end{array} \\ &&\textsf{Assoziativitaetsbeweise zur Matrixmultiplikation habe ich viele gefunden, jedoch nicht wirklich ausfuerhlich, da es wohl zu trivial ist?} \\ &&\textsf{Jedenfalls, mein Problem ist das Ausklammern der Summe aus einer Summe mit einem Element (hier}~ b_{ks} ~\textsf{), dessen Index abhaenging von beiden Summen ist.} \\ &&\textsf{Wenn ich, wie oben, das }~ b_{ks} ~\textsf{einfach mit ausklammere, habe ich das Problem, dass es ausserhalb der abhaengigen Summe ist und somit nicht berechtnet werden kann.} \\ &&\textsf{Kann man dies vielleicht eleganter machen, durch die Allgemeingueltigkeit der Kommutativitaet der Multiplikation in reellen Zahlen, ohne sich um den Index der Zahlen zu kuemmern?} \end{eqnarray*}$

21.12.2013, 12:54

Elvis

Auf diesen Beitrag antworten »

Was du machst, sieht nicht so richtig nach einem Beweis aus. Ich verstehe nicht, wieso du "ausklammern" kannst.
Der entscheidende Beweisschritt dürfte in der Vertauschung der beiden Summenzeichen, also in der Vertauschung der Reihenfolge der Summation bei endlichen Summen, liegen.

Vielleicht ist das genau gesehen auch nichts anderes als dein Beweis ?
Nachtrag: Nein ist es nicht, dein "Beweis" ist falsch.

21.12.2013, 15:52

Joefish

Auf diesen Beitrag antworten »

Danke fuer deine Antwort.
Es soll ja gezeigt werden, dass $\begin{eqnarray*} \left(A \cdot B\right) \cdot C = \sum\limits_{s=1}^o \left(\sum\limits_{k=1}^n a_{ik}b_{ks}\right) \cdot c_{sj} ~=~ \sum\limits_{k=1}^n a_{ik} \left(\sum\limits_{s=1}^o b_{ks}c_{sj} \right) = A \cdot \left(B \cdot C \right) \end{eqnarray*}$

Das heisst, wir muessten nur zeigen, dass die Reihenfolge der Summenzeichen kommutativ ist.
Meine Idee war nun die innere Summe auszuklammern, was eigentlich kein Problem sein sollte,
denn die innere Summe wird in jedem Iterationsschritt der aeusseren Summe zu dessen Argument(nicht sicher ob richtige Bezeichnung..) multipliziert.

$\begin{eqnarray*} \sum\limits_{s=1}^o \left(\sum\limits_{k=1}^n a_{ik}b_{ks}\right) \cdot c_{sj} = \left(\sum\limits_{k=1}^n a_{ik}b_{ks}\right) \sum\limits_{s=1}^o c_{sj} = \sum\limits_{k=1}^n \sum\limits_{s=1}^o a_{ik}b_{ks}c_{sj} \end{eqnarray*}$

Wo mache ich hier einen Fehler? Fuer mich sieht das schluessig aus, wenn ich mein Problem mit dem Index von b ignoriere ^^ ( $\begin{eqnarray*} *^1 \end{eqnarray*}$ )
Im Prinzip zaehle ich durch Vertauschen der Summenzeichen die Summen nur 'anders zusammen'.
So wie ich die Flaeche eines Rechtecks Laenge * Breite oder Breite * Laenge berechnen kann. Ich zaehle die Bausteine nur in einer anderen Reihenfolge, welche durch Kommutativitaet aequivalent sind.

Auf Wikipedia wurde ich auch nicht wirklich schlauer

Zitat:

Dabei gilt die Regel: $\begin{eqnarray*} \sum_{i,j=1}^n a_{ij} = \sum_{j,i=1}^n a_{ij} \end{eqnarray*}$

Was waere denn der 'richtige' Weg dies zu beweisen?

Edit: Weil ich immer mein Problem mit b ansprech... Ich muss es ja nicht mit Ausklammern (falls das denn ueberhaupt moeglich ist),
sondern nur $\begin{eqnarray*} \sum\limits_{k=1}^n a_{ik} \end{eqnarray*}$ und koennte so gleich auf die gewuenschte Form $\begin{eqnarray*} \sum\limits_{k=1}^n a_{ik} \left(\sum\limits_{s=1}^o b_{ks}c_{sj} \right) \end{eqnarray*}$ kommen.

21.12.2013, 18:29

Elvis

Auf diesen Beitrag antworten »

In der Mitte liegt ein Problem vor, denn $\begin{eqnarray*} \sum_{s=1}^o c_{sj} \end{eqnarray*}$ wird bei der korrekten Matrizenmultiplikation nicht gebildet. Es müssen immer Produkte aus a und b, b und c, oder aus a und b und c auftreten.
Wikipedia sagt (genau wie ich) , dass man die Reihenfolge der endlichen Doppelsumme vertauschen darf, es ist also egal, ob man zuerst über s und dann über k oder zuerst über k und dann über s summiert.

Richtig ist dann $\begin{eqnarray*} (AB)C=\sum_s(\sum_k a_{ik} b_{ks} )c_{sj}=\sum_s(\sum_k a_{ik} b_{ks} c_{sj})=\sum_k (\sum_s a_{ik} b_{ks} c_{sj})=\sum_k a_{ik} (\sum_s b_{ks}c_{sj})=A(BC) \end{eqnarray*}$ . Die $\begin{eqnarray*} c_{sj} \end{eqnarray*}$ kann man unter die k-Summe ziehen, weil sie von k unabhängig sind, die $\begin{eqnarray*} a_{ik} \end{eqnarray*}$ kann man aus der s-Summe herausziehen, weil sie von s unabhängig sind. ABER $\begin{eqnarray*} a_{ik}b_{ks} \end{eqnarray*}$ ist von s abhängig, kann also nicht aus der s-Summe herausgezogen werden.

21.12.2013, 20:29

Joefish

Auf diesen Beitrag antworten »

Stimmt, das habe ich nicht beachtet, dass das nicht passt..
Jedoch, ist das Vertauschen der Doppelsummen ein Axiom oder kann man das auch beweisen?
Ich denke graphisch kann man sich gut veranschaulichen, indem man diese Multiplikation an einem Wuerfel betrachtet.
Aber das geht wohl kaum als Beweis durch..
Das Ausklammern schien mir eine gute Moeglichkeit, um die Iterations-Indices der Summen zu vertauschen..

22.12.2013, 11:52

Elvis

Auf diesen Beitrag antworten »

Dass die Summation bei Doppelsummen von der Reihenfolge der Summation unabhängig ist, folgt sofort aus der Kommutativität der Addition. Bei einem Rechteck von Zahlen ist es gleich, ob du die Spaltensummen oder die Zeilensummen addierst. Mehr steckt nicht dahinter, erst bei unendlichen Reihen wird es ein bißchen interessanter.

23.12.2013, 16:56

Joefish

Auf diesen Beitrag antworten »

Okay. Ich dachte es koennte Probleme mit $\begin{eqnarray*} b_{ks} \end{eqnarray*}$ geben, da der Index beider Summen in ihm vorkommen.
Aber gibt es auch einen formalen Beweis fuer diese 'Umordnung'?
Obwohl.. die Kommutativitaet der Addition reicht wirklich, da ausser der Reihenfolge sich wirklich nichts veraendert..

Alles klar, dann vielen Dank fuer deine Hilfe smile

24.12.2013, 10:52

Elvis

Auf diesen Beitrag antworten »

Zum formalen Beweis gehört natürlich, dass man die "allgemeine Kommutativität" durch vollständige Induktion nach der Anzahl der Summanden beweist. Dieser Beweis ist so trivial, dass wir ihn voraussetzen können. Augenzwinkern

Neue Frage »

Antworten »

Assoziativitaet der Matrixmultiplikation

Verwandte Themen