Quelltext der Seite Matrizenmultiplikation

[[Datei:Matrix multiplication qtl1.svg|mini|Bei einer Matrizenmultiplikation muss die Spaltenzahl der ersten Matrix gleich der Zeilenzahl der zweiten Matrix sein. Die Ergebnismatrix hat dann die Zeilenzahl der ersten und die Spaltenzahl der zweiten Matrix.]]
Die '''Matrizenmultiplikation''' oder '''Matrixmultiplikation''' ist in der [[Mathematik]] eine [[Multiplikation|multiplikative]] [[Verknüpfung (Mathematik)|Verknüpfung]] von [[Matrix (Mathematik)|Matrizen]]. Um zwei Matrizen miteinander multiplizieren zu können, muss die Spaltenzahl der ersten Matrix mit der Zeilenzahl der zweiten Matrix übereinstimmen. Das Ergebnis einer Matrizenmultiplikation wird dann '''Matrizenprodukt, Matrixprodukt''' oder '''Produktmatrix''' genannt. Das Matrizenprodukt ist wieder eine Matrix, deren Einträge durch komponentenweise Multiplikation und [[Summe|Summation]] der Einträge der entsprechenden Zeile der ersten Matrix mit der entsprechenden Spalte der zweiten Matrix ermittelt werden.

Die Matrizenmultiplikation ist [[Assoziativgesetz|assoziativ]] und mit der [[Matrizenaddition]] [[Distributivgesetz|distributiv]]. Sie ist jedoch nicht [[Kommutativgesetz|kommutativ]], das heißt, die Reihenfolge der Matrizen darf bei der Produktbildung im Allgemeinen nicht vertauscht werden. Die Menge der [[Quadratische Matrix|quadratischen Matrizen]] mit Elementen aus einem [[Ring (Algebra)|Ring]] bildet zusammen mit der Matrizenaddition und der Matrizenmultiplikation den Ring der quadratischen Matrizen. Weiter bildet die Menge der [[Reguläre Matrix|regulären Matrizen]] über einem [[Unitärer Ring|unitären Ring]] mit der Matrizenmultiplikation die [[allgemeine lineare Gruppe]]. Matrizen, die durch spezielle Multiplikationen mit regulären Matrizen ineinander überführt werden können, bilden darin [[Äquivalenzklasse]]n.

Der Standardalgorithmus zur Multiplikation zweier quadratischer Matrizen weist eine [[Kubische Funktion|kubische]] Laufzeit auf. Zwar lässt sich der asymptotische Aufwand mit Hilfe spezieller Algorithmen verringern, die Ermittlung optimaler oberer und unterer [[Komplexitätstheorie|Komplexitätsschranken]] für die Matrizenmultiplikation ist jedoch noch Gegenstand aktueller Forschung.

Die Matrizenmultiplikation wird häufig in der [[Lineare Algebra|linearen Algebra]] verwendet. So wird beispielsweise die [[Faktorisierung]] einer Matrix als Produkt von Matrizen mit speziellen Eigenschaften bei der [[Numerische Mathematik|numerischen]] Lösung [[Lineares Gleichungssystem|linearer Gleichungssysteme]] oder [[Eigenwertproblem|Eigenwertproblemen]] eingesetzt. Weiterhin ist die [[Abbildungsmatrix]] der [[Komposition (Mathematik)|Hintereinanderausführung]] zweier [[Lineare Abbildung|linearer Abbildungen]] gerade das Matrizenprodukt der Abbildungsmatrizen dieser Abbildungen. Anwendungen der Matrizenmultiplikation finden sich unter anderem in der [[Informatik]], der [[Physik]] und der [[Ökonomie]].

Die Matrizenmultiplikation wurde erstmals von dem französischen Mathematiker [[Jacques Philippe Marie Binet]] im Jahr 1812 beschrieben.<ref>{{MacTutor|id=Binet|title=Jacques Philippe Marie Binet}}</ref>

[[Datei:Matrix multiplication qtl2.svg|mini|Zur Berechnung des Matrizenprodukts wird das Schema Zeile mal Spalte angewandt.]]
== Definition ==

Die Matrizenmultiplikation ist eine [[binäre Verknüpfung]] auf der Menge der [[Matrix (Mathematik)|Matrizen]] über einem Ring <math>R</math> (oft der [[Körper (Algebra)|Körper]] der [[Reelle Zahl|reellen Zahlen]]), also eine Abbildung

:<math>\cdot ~ \colon R^{m \times n} \times R^{n \times p} \to R^{m \times p}, \quad (A,B) \mapsto C = A \cdot B</math>,

die zwei Matrizen <math>A = (a_{ij})</math> und <math>B = (b_{jk})</math> eine weitere Matrix <math>C = (c_{ik})</math> zuordnet. Die Matrizenmultiplikation ist dabei nur für den Fall definiert, dass die Spaltenzahl <math>n</math> der Matrix <math>A</math> mit der Zeilenzahl der Matrix <math>B</math> übereinstimmt. Die Zeilenzahl <math>m</math> der Ergebnismatrix <math>C</math> entspricht dann derjenigen der Matrix <math>A</math> und ihre Spaltenzahl <math>p</math> derjenigen der Matrix <math>B</math>. Jeder Eintrag <math>c_{ik}</math> des Matrizenprodukts berechnet sich dabei über

:<math>c_{ik} = \sum_{j=1}^n a_{ij} \cdot b_{jk}</math>,

also durch komponentenweise Multiplikation der Einträge der <math>i</math>-ten Zeile von <math>A</math> mit der <math>k</math>-ten Spalte von <math>B</math> und durch Summation all dieser Produkte. Häufig wird bei der Notation einer Matrizenmultiplikation der [[Malpunkt]] weggelassen und man schreibt kurz <math>AB</math> statt <math>A \cdot B</math>. Soll die Reihenfolge der Faktoren betont werden, spricht man „A wird von links mit B multipliziert“ für das Produkt <math>B \cdot A</math> und „A wird von rechts mit B multipliziert“ für das Produkt <math>A \cdot B</math>.

== Beispiel ==

Gegeben seien die beiden reellen Matrizen

:<math>A = \begin{pmatrix} 3 & 2 & 1 \\ 1 & 0 & 2 \end{pmatrix} \in \R^{2 \times 3}</math> &nbsp; und &nbsp; <math>B = \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ 4 & 0 \end{pmatrix} \in \R^{3 \times 2}</math>.

Da die Matrix <math>A</math> ebenso viele Spalten wie die Matrix <math>B</math> Zeilen besitzt, ist die Matrizenmultiplikation <math>A \cdot B</math> durchführbar. Nachdem <math>A</math> zwei Zeilen und <math>B</math> zwei Spalten hat, wird das Matrizenprodukt ebenfalls zwei Zeilen und Spalten aufweisen. Zur Berechnung des ersten Matrixelements der Ergebnismatrix werden die Produkte der entsprechenden Einträge der ersten Zeile von <math>A</math> und der ersten Spalte von <math>B</math> aufsummiert (die [[Sternchen (Schriftzeichen)|Sternchen]] stehen für noch nicht berechnete Elemente):

:<math>\begin{pmatrix} \color{OliveGreen} 3 & \color{OliveGreen} 2 & \color{OliveGreen} 1 \\ 1 & 0 & 2 \end{pmatrix} \cdot \begin{pmatrix} \color{BrickRed} 1 & 2 \\ \color{BrickRed} 0 & 1 \\ \color{BrickRed} 4 & 0 \end{pmatrix} = \begin{pmatrix} {\color{OliveGreen} 3} \cdot {\color{BrickRed} 1} + {\color{OliveGreen} 2} \cdot {\color{BrickRed} 0} + {\color{OliveGreen} 1} \cdot {\color{BrickRed} 4} & \ast \\ \ast & \ast \end{pmatrix} = \begin{pmatrix} {\color{Blue} 7} & \ast \\ \ast & \ast \end{pmatrix}</math>

Für das nächste Element der Ergebnismatrix in der ersten Zeile und zweiten Spalte wird entsprechend die erste Zeile von <math>A</math> und die zweite Spalte von <math>B</math> verwendet:

:<math>\begin{pmatrix} \color{OliveGreen} 3 & \color{OliveGreen} 2 & \color{OliveGreen} 1 \\ 1 & 0 & 2 \end{pmatrix} \cdot \begin{pmatrix} 1 & \color{BrickRed} 2 \\ 0 & \color{BrickRed} 1 \\ 4 & \color{BrickRed} 0 \end{pmatrix} = \begin{pmatrix} 7 & {\color{OliveGreen} 3} \cdot {\color{BrickRed} 2} + {\color{OliveGreen} 2} \cdot {\color{BrickRed} 1} + {\color{OliveGreen} 1} \cdot {\color{BrickRed} 0} \\ \ast & \ast \end{pmatrix} = \begin{pmatrix} 7 & {\color{Blue} 8} \\ \ast & \ast \end{pmatrix}</math>

Dieses Rechenschema setzt sich nun in der zweiten Zeile und ersten Spalte fort:

:<math>\begin{pmatrix} 3 & 2 & 1 \\ \color{OliveGreen} 1 & \color{OliveGreen} 0 & \color{OliveGreen} 2 \end{pmatrix} \cdot \begin{pmatrix} \color{BrickRed} 1 & 2 \\ \color{BrickRed} 0 & 1 \\ \color{BrickRed} 4 & 0 \end{pmatrix} = \begin{pmatrix} 7 & 8 \\ {\color{OliveGreen} 1} \cdot {\color{BrickRed} 1} + {\color{OliveGreen} 0} \cdot {\color{BrickRed} 0} + {\color{OliveGreen} 2} \cdot {\color{BrickRed} 4} & \ast \end{pmatrix} = \begin{pmatrix} 7 & 8 \\ {\color{Blue} 9} & \ast \end{pmatrix}</math>

Es wiederholt sich bei dem letzten Element in der zweiten Zeile und zweiten Spalte:

:<math>\begin{pmatrix} 3 & 2 & 1 \\ \color{OliveGreen} 1 & \color{OliveGreen} 0 & \color{OliveGreen} 2 \end{pmatrix} \cdot \begin{pmatrix} 1 & \color{BrickRed} 2 \\ 0 & \color{BrickRed} 1 \\ 4 & \color{BrickRed} 0 \end{pmatrix} = \begin{pmatrix} 7 & 8 \\ 9 & {\color{OliveGreen} 1} \cdot {\color{BrickRed} 2} + {\color{OliveGreen} 0} \cdot {\color{BrickRed} 1} + {\color{OliveGreen} 2} \cdot {\color{BrickRed} 0} \end{pmatrix} = \begin{pmatrix} 7 & 8 \\ 9 & {\color{Blue} 2} \end{pmatrix}</math>

Das Ergebnis ist das Matrizenprodukt <math>A \cdot B</math>. Eine optische Hilfestellung und Unterstützung zur Berechnung des Matrizenprodukts bietet das [[Falksches Schema|falksche Schema]].<ref>{{Literatur |Autor=[[Horst Stöcker]] |Titel=Taschenbuch mathematischer Formeln und moderner Verfahren |Verlag=[[Verlag Harri Deutsch]] |Ort=Frankfurt am Main |Datum=2007 |ISBN=978-3-8171-1811-3 |Seiten=371}}</ref>

[[Datei:Matrix multiplication qtl4.svg|mini|Multiplikation eines Zeilenvektors mit einem Spaltenvektor]]
== Spezialfälle ==

=== Zeilenvektor mal Spaltenvektor ===

Besteht die erste Matrix aus nur einer Zeile und die zweite Matrix aus nur einer Spalte, so ergibt das Matrizenprodukt eine <math>(1 \times 1)</math>-Matrix. Interpretiert man eine einzeilige Matrix als Zeilenvektor <math>x^\mathrm{T}</math> und eine einspaltige Matrix als Spaltenvektor <math>y</math>, so erhält man im Fall reeller Vektoren das [[Standardskalarprodukt]]

:<math>\langle x, y \rangle = x^\mathrm{T} \cdot y</math>

zweier Vektoren, wobei <math>x^\mathrm{T}</math> den zu <math>x</math> [[Transponierte Matrix|transponierten Vektor]] darstellt, beide Vektoren gleich lang sein müssen und das Ergebnis dann eine reelle Zahl ist. Jeder Eintrag eines Matrizenprodukts <math>A \cdot B</math> kann somit als Skalarprodukt eines Zeilenvektors der Matrix <math>A</math> mit einem Spaltenvektor der Matrix <math>B</math> angesehen werden.

[[Datei:Matrix multiplication qtl3.svg|mini|Multiplikation eines Spaltenvektors mit einem Zeilenvektor]]
=== Spaltenvektor mal Zeilenvektor ===

Besteht umgekehrt die erste Matrix aus nur einer Spalte der Länge <math>m</math> und die zweite Matrix aus nur einer Zeile der Länge <math>n</math>, so ergibt das Matrizenprodukt eine <math>(m \times n)</math>-Matrix. Wird wieder eine einspaltige Matrix als Spaltenvektor <math>x</math> und eine einzeilige Matrix als Zeilenvektor <math>y^\mathrm{T}</math> interpretiert, so wird das entstehende Produkt von Vektoren als [[dyadisches Produkt]]

:<math>x \otimes y = x \cdot y^\mathrm{T}</math>

bezeichnet. Jeder Eintrag <math>c_{ij}</math> der resultierenden Matrix ist dabei das Produkt eines Elements <math>x_i</math> des ersten Vektors mit einem Element <math>y_j</math> des zweiten Vektors. Das Matrizenprodukt <math>A \cdot B</math> kann so als Summe dyadischer Produkte der Spaltenvektoren von <math>A</math> mit den jeweiligen Zeilenvektoren von <math>B</math> geschrieben werden.

[[Datei:Matrix multiplication qtl5.svg|mini|Multiplikation einer Matrix mit einem Vektor]]
=== Matrix mal Vektor ===

Ein wichtiger Spezialfall einer Matrizenmultiplikation entsteht, wenn die zweite Matrix aus nur einer Spalte besteht. Das Ergebnis der Matrizenmultiplikation ist dann ebenfalls eine einspaltige Matrix. Wird wieder eine einspaltige Matrix als Spaltenvektor interpretiert, so erhält man das [[Matrix-Vektor-Produkt]]

:<math>A \cdot x = y</math>,

wobei <math>A \in R^{m \times n}</math>, <math>x \in R^n</math> und <math>y \in R^m</math> sind. Das Matrix-Vektor-Produkt wird beispielsweise in der Matrixschreibweise [[Lineares Gleichungssystem|linearer Gleichungssysteme]] verwendet.

Eine alternative Darstellung der Matrixmultiplikation ergibt sich durch Umschreiben der Definition. Wir schreiben <math display="inline">A = (a_1 | \dots | a_n) \in R^{m\times n}</math> sodass die <math display="inline">a_j</math> die Spalten der Matrix <math>A</math> darstellen (unten verdeutlicht durch <math>\vec a_j</math>). Ist nun <math display="inline">x \in R^n</math> dann kann man das Matrix-Vektor-Produkt auch wie folgt lesen:

<math>A \cdot x = ( \vec a_1| \dots | \vec a_n) \cdot  \vec x = \sum_{j=1}^n \vec a_j\cdot x_j  = \vec a_1 \cdot x_1 + \dots + \vec a_n \cdot x_n</math>

[[Datei:Matrix multiplication qtl7.svg|mini|Multiplikation eines Vektors mit einer Matrix]]Das Matrix-Vektor-Produkt ist also eine Linearkombination der Spalten von <math>A</math>. Diese Beobachtung lässt sich auch auf ein allgemeines Matrix-Matrix-Produkt übertragen. Ist man am [[Bild (Mathematik)|Bild]] der von der Matrix induzierten [[Lineare Abbildung|linearen Abbildung]] interessiert, ist diese Darstellung meist intuitiver für weitere Argumentation.

=== Vektor mal Matrix ===

Besteht umgekehrt die erste Matrix aus nur einer Zeile, so ergibt das Vektor-Matrix-Produkt

:<math>x^\mathrm{T} \cdot A = y^\mathrm{T}</math>

aus einem Zeilenvektor <math>x^\mathrm{T} \in R^m</math> und einer Matrix <math>A \in R^{m \times n}</math> wieder einen Zeilenvektor <math>y^\mathrm{T} \in R^n</math>. Dieses lässt sich als eine Linearkombination der Zeilen von <math>A</math> interpretieren.

=== Quadrat einer Matrix ===

Durch Multiplikation einer [[Quadratische Matrix|quadratischen Matrix]] <math>A \in R^{n \times n}</math> mit sich selbst ergibt sich wieder eine Matrix gleicher Größe, die als das ''Quadrat'' der Matrix bezeichnet wird, das heißt:

:<math>A^2 = A \cdot A</math>

Entsprechend dazu wird mit <math>A^n</math> die [[Matrixpotenz]], also das <math>n</math>-fache Produkt einer Matrix mit sich selbst, bezeichnet. Matrixpotenzen werden beispielsweise zur Definition des [[Matrixexponential]]s und des [[Matrixlogarithmus]] verwendet. Umgekehrt heißt eine quadratische Matrix <math>A^{1/2}</math>, für die

:<math>A = A^{1/2} \cdot A^{1/2}</math>

gilt, [[Quadratwurzel einer Matrix|''Quadratwurzel der Matrix'']] <math>A</math>. Eine Matrix kann mehrere, sogar unendlich viele, Quadratwurzeln besitzen. Analog wird eine Matrix, deren <math>n</math>-te Potenz die Matrix <math>A</math> ergibt, als ''<math>n</math>-te Wurzel'' <math>A^{1/n}</math> dieser Matrix bezeichnet.

[[Datei:Block matrix qtl3.svg|mini|Multiplikation zweier Blockmatrizen]]
=== Blockmatrizen ===

Weisen die beiden Matrizen <math>A</math> und <math>B</math> eine [[Blockmatrix|Blockstruktur]] auf, wobei die Blockbreiten der ersten Matrix mit den Blockhöhen der zweiten Matrix übereinstimmen müssen, so lässt sich auch das Matrizenprodukt <math>A \cdot B</math> blockweise notieren. Die Ergebnismatrix besitzt dann die Blockhöhen der ersten und die Blockbreiten der zweiten Matrix. Im Fall zweier Matrizen mit je zwei mal zwei Blöcken ergibt sich beispielsweise

:<math>
  \begin{pmatrix}
  A_{11} & A_{12} \\
  A_{21} & A_{22}
  \end{pmatrix}
\cdot
  \begin{pmatrix}
  B_{11} & B_{12} \\
  B_{21} & B_{22}
  \end{pmatrix}
= 
\begin{pmatrix}
  A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\
  A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22}
\end{pmatrix}
</math>,

womit die Ergebnismatrix auch zwei mal zwei Blöcke besitzt.

{{Siehe auch|Blockmatrix#Multiplikation von Blockmatrizen|titel1=„Multiplikation von Blockmatrizen“ im Artikel Blockmatrix}}

[[Datei:Matrix multiplication qtl6.svg|mini|Zur Berechnung eines Eintrags des Matrizenprodukts <math>A \cdot B \cdot C</math> werden alle Elemente der Matrix <math> B</math> benötigt (mittlere Zeile). Für die Bildung der hierbei benötigten Doppelsumme gibt es zwei Möglichkeiten (obere und untere Zeile).]]

== Eigenschaften ==

=== Assoziativität ===

Die Matrizenmultiplikation ist [[Assoziativgesetz|assoziativ]], das heißt, für Matrizen <math>A \in R^{m \times n}</math>, <math>B \in R^{n \times p}</math> und <math>C \in R^{p \times q}</math> gilt:

:<math>A \cdot (B \cdot C) = ( A \cdot B ) \cdot C</math>

Bei der Multiplikation mehrerer Matrizen ist es also unerheblich, in welcher Reihenfolge die Teilprodukte gebildet werden, solange die Gesamtreihung nicht verändert wird. Für den Eintrag an der Stelle <math>(i,l)</math> des resultierenden Matrizenprodukts gilt nämlich:

:<math>\sum_{j=1}^n a_{ij} \cdot \left( \sum_{k=1}^p b_{jk} \cdot c_{kl} \right) = \sum_{j=1}^n \sum_{k=1}^p a_{ij} \cdot b_{jk} \cdot c_{kl} = \sum_{k=1}^p \sum_{j=1}^n a_{ij} \cdot b_{jk} \cdot c_{kl} = \sum_{k=1}^p \left( \sum_{j=1}^n a_{ij} \cdot b_{jk} \right) \cdot c_{kl}</math>

Die Matrizenmultiplikation ist auch verträglich mit der [[Skalarmultiplikation#Matrizen|Multiplikation mit Skalaren]] <math>a \in R</math>, das heißt:

:<math>a \, (B \cdot C) = ( a \, B ) \cdot C = B \cdot ( a \, C )</math>

=== Distributivität ===

Betrachtet man neben der Matrizenmultiplikation auch noch die komponentenweise [[Matrizenaddition]] <math>A + B</math> zweier Matrizen <math>A,B \in R^{l \times m}</math>, dann sind auch die [[Distributivgesetz]]e erfüllt. Das heißt, für alle Matrizen <math>C \in R^{m \times n}</math> gilt

:<math>(A + B) \cdot C = A \cdot C + B \cdot C</math>

und für alle Matrizen <math>C \in R^{n \times l}</math> entsprechend

:<math>C \cdot (A + B) = C \cdot A + C \cdot B</math>.

Die Distributivgesetze folgen direkt aus der Distributivität der Addition mit der Multiplikation im Ring <math>R</math> über

:<math>\sum_{j=1}^m \left( a_{ij} + b_{ij} \right) \cdot c_{jk} = \sum_{j=1}^m \left( a_{ij} \cdot c_{jk} + b_{ij} \cdot c_{jk} \right) = \sum_{j=1}^m a_{ij} \cdot c_{jk} + \sum_{j=1}^m b_{ij} \cdot c_{jk}</math>

für das erste Distributivgesetz und über eine analoge Umformung auch für das zweite Distributivgesetz.

=== Nichtkommutativität ===

Das [[Kommutativgesetz]] hingegen gilt für die Matrizenmultiplikation ''nicht'', das heißt, für <math>A \in R^{m \times n}</math> und <math>B \in R^{n \times m}</math> ist im Allgemeinen

:<math>A \cdot B \neq B \cdot A</math>.

Für die beiden Matrizenprodukte gilt nämlich <math>A \cdot B \in R^{m \times m}</math> und <math>B \cdot A \in R^{n \times n}</math>, womit sie für <math>m \neq n</math> schon von den Dimensionen her nicht übereinstimmen können. Aber selbst, wenn <math>A</math> und <math>B</math> quadratisch sind, müssen die beiden Matrizenprodukte nicht gleich sein, wie das Gegenbeispiel

:<math>\begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 0 \\ 2 & 0 \end{pmatrix} = \begin{pmatrix} 4 & 0 \\ 0 & 0 \end{pmatrix} \neq \begin{pmatrix} 0 & 0 \\ 0 & 4 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 2 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix}</math>

zeigt. Die Nichtkommutativität der Matrizenmultiplikation gilt demnach sogar, wenn die Multiplikation im Ring <math>R</math> kommutativ sein sollte, wie es beispielsweise bei [[Zahl]]en der Fall ist. Für spezielle Matrizen kann die Matrizenmultiplikation dennoch kommutativ sein, siehe die nachfolgenden Abschnitte sowie den Abschnitt "Eigenvektoren kommutierender Matrizen" im Artikel [[Eigenwerte und Eigenvektoren]].

=== Weitere Rechenregeln ===

Für die [[Transponierte Matrix|Transponierte]] eines Matrizenprodukts gilt:

:<math>(A \cdot B)^\mathrm{T} = B^\mathrm{T} \cdot A^\mathrm{T}</math>.

Die Reihenfolge bei der Multiplikation wird durch die Transposition also vertauscht. Für die [[Adjungierte Matrix|Adjungierte]] des Produkts [[Komplexe Zahl|komplexer]] Matrizen gilt entsprechend

:<math>(A \cdot B)^H = B^H \cdot A^H</math>.

Die [[Spur (Mathematik)|Spur]] des Produkts zweier Matrizen <math>A \in R^{m \times n}</math> und <math>B \in R^{n \times m}</math> ist hingegen unabhängig von der Reihenfolge:

:<math>\operatorname{spur}(A \cdot B) = \operatorname{spur}(B \cdot A)</math>

Mit dem [[Determinantenproduktsatz]] gilt auch für die [[Determinante (Mathematik)|Determinante]] des Produkts zweier quadratischer Matrizen über einem kommutativen Ring:

:<math>\operatorname{det}(A \cdot B) = \operatorname{det}(A) \cdot \operatorname{det}(B) = \operatorname{det}(B) \cdot \operatorname{det}(A) = \operatorname{det}(B \cdot A)</math>

Die Determinante des Produkts zweier nicht notwendigerweise quadratischer Matrizen kann mit dem [[Satz von Binet-Cauchy]] berechnet werden.

== Algebraische Strukturen ==

=== Ring der quadratischen Matrizen ===

Die Menge der [[Quadratische Matrix|quadratischen Matrizen]] fester Größe bildet zusammen mit der Matrizenaddition und der Matrizenmultiplikation einen nichtkommutativen [[Ring (Mathematik)|Ring]], den [[Matrizenring]] <math>(R^{n \times n}, +, \cdot)</math>. Das [[Nullelement]] dieses Rings ist die [[Nullmatrix]] <math>0 \in R^{n \times n}</math>. Ist <math>R</math> ein [[unitärer Ring]], dann ist auch der zugehörige Matrizenring unitär mit der [[Einheitsmatrix]] <math>I \in R^{n \times n}</math> als [[Einselement]], wobei für alle Matrizen <math>A \in R^{n \times n}</math>

:<math>A \cdot I = I \cdot A = A</math>

gilt. Die Nullmatrix fungiert im Matrizenring in diesem Fall als [[absorbierendes Element]], das heißt, für alle Matrizen <math>A \in R^{n \times n}</math> gilt dann:

:<math>A \cdot 0 = 0 \cdot A = 0</math>

Der Ring der quadratischen Matrizen ist jedoch nicht [[nullteilerfrei]]; aus <math>A \cdot B = 0</math> folgt nicht notwendigerweise <math>A=0</math> oder <math>B=0</math>. Ein Beispiel wären zwei quadratische Matrizen
<math>A, B</math> mit je genau einem Eintrag ungleich Null an der gleichen Diagonalaußenstelle. Entsprechend darf bei Matrixgleichungen auch nicht gekürzt werden, denn aus <math>A \cdot B = A \cdot C</math> folgt nicht notwendigerweise <math>B = C</math>.
Die Menge der quadratischen Matrizen über einem Körper bildet mit der Matrizenaddition, der Skalarmultiplikation und der Matrizenmultiplikation eine [[assoziative Algebra]].

=== Gruppe der regulären Matrizen ===

Die Menge der [[Reguläre Matrix|regulären Matrizen]] <math>A \in R^{n \times n}</math> über einem unitären Ring <math>R</math> bildet mit der Matrizenmultiplikation die [[allgemeine lineare Gruppe]] <math>\operatorname{GL}(n,R)</math>. Die zur Matrix <math>A</math> [[inverse Matrix]] ist dann eindeutig über

:<math>A \cdot A^{-1} = A^{-1} \cdot A = I</math>

definiert. Für die Inverse des Produkts zweier regulärer Matrizen gilt dann:

:<math>(A \cdot B)^{-1} = B^{-1} \cdot A^{-1}</math>

Durch die Invertierung wird die Reihenfolge bei der Multiplikation demnach ebenfalls vertauscht. Ist <math>A</math> regulär, dann gilt auch die Kürzungsregel, das heißt aus <math>A \cdot B = A \cdot C</math> oder <math>B \cdot A = C \cdot A</math> folgt dann <math>B=C</math>.

=== Gruppen der orthogonalen und unitären Matrizen ===

Eine reelle quadratische Matrix <math>A \in \R^{n \times n}</math> heißt [[Orthogonale Matrix|orthogonal]], wenn

:<math>A \cdot A^\mathrm{T} = A^\mathrm{T} \cdot A = I</math>

gilt. Die orthogonalen Matrizen bilden mit der Matrizenmultiplikation die [[orthogonale Gruppe]] <math>\operatorname{O}(n)</math>, eine [[Untergruppe]] der allgemeinen linearen Gruppe <math>\operatorname{GL}(n,\R)</math>. Entsprechend dazu heißt eine komplexe quadratische Matrix <math>A \in \Complex^{n \times n}</math> [[Unitäre Matrix|unitär]], wenn

:<math>A \cdot A^H = A^H \cdot A = I</math>

gilt. Die unitären Matrizen bilden mit der Matrizenmultiplikation die [[unitäre Gruppe]] <math>\operatorname{U}(n)</math>, eine Untergruppe der allgemeinen linearen Gruppe <math>\operatorname{GL}(n,\Complex)</math>.

=== Äquivalenzklassen von Matrizen ===

Mit Hilfe der Matrizenmultiplikation werden [[Äquivalenzrelation]]en zwischen Matrizen über einem Körper definiert. Wichtige Äquivalenzrelationen sind:

* [[Äquivalenz (Matrix)|Äquivalenz]]: Zwei Matrizen <math>A</math> und <math>B</math> heißen äquivalent, wenn es zwei reguläre Matrizen <math>C</math> und <math>D</math> gibt, sodass <math>B = C^{-1} \cdot A \cdot D</math> gilt.
* [[Ähnlichkeit (Matrix)|Ähnlichkeit]]: Zwei quadratische Matrizen <math>A</math> und <math>B</math> heißen ähnlich, wenn es eine reguläre Matrix <math>C</math> gibt, sodass <math>B = C^{-1} \cdot A \cdot C</math> gilt.
* [[Kongruenz (Matrix)|Kongruenz]]: Zwei quadratische Matrizen <math>A</math> und <math>B</math> heißen kongruent, wenn es eine reguläre Matrix <math>C</math> gibt, sodass <math>B = C^\mathrm{T} \cdot A \cdot C</math> gilt.

Matrizen, die durch solche Multiplikationen mit regulären Matrizen ineinander überführt werden können, bilden demnach [[Äquivalenzklasse]]n.

== Algorithmen ==

=== Standardalgorithmus ===

In [[Pseudocode]] kann die Matrizenmultiplikation wie folgt implementiert werden:

<syntaxhighlight lang="matlab">
function matmult(A,B,l,m,n)
  C = zeroes(l,n)                         // Ergebnismatrix C mit Nullen initialisieren
  for i = 1 to l                          // Schleife über die Zeilen von C
    for k = 1 to n                        // Schleife über die Spalten von C
      for j = 1 to m                      // Schleife über die Spalten von A / Zeilen von B
        C(i,k) = C(i,k) + A(i,j) * B(j,k) // Bildung der Produktsumme
      end
    end
  end
  return C
</syntaxhighlight>

Die Reihenfolge der drei [[For-Schleife]]n kann dabei beliebig vertauscht werden, ohne das Ergebnis der Berechnung zu verändern. Da die drei Schleifen unabhängig voneinander sind, ist die Anzahl der benötigten Operationen von der [[Landau-Symbole|Ordnung]]

:<math>\mathcal{O}(l \cdot m \cdot n)</math>.

Die [[Zeitkomplexität]] des Algorithmus ist demnach für quadratische Matrizen <math>(l=m=n)</math> [[Kubische Funktion|kubisch]], also von der Ordnung

:<math>\mathcal{O}(n^3)</math>.

Bei der [[Matrix-Kettenmultiplikation]], also der Multiplikation von drei oder mehr nichtquadratischen Matrizen, kann durch eine geschickte Wahl der Reihenfolge die Gesamtzahl arithmetischer Operationen minimiert werden.

[[Datei:Bound on matrix multiplication omega over time.svg|mini|Entwicklung der oberen Komplexitäts&shy;schranke der Matrizenmultiplikation in den letzten Jahrzehnten]]
=== Algorithmen mit besserer Komplexität ===

Asymptotisch effizienter lassen sich zwei quadratische Matrizen mit dem [[Strassen-Algorithmus]] multiplizieren. Hierbei wird die Anzahl der Multiplikationen, die zur Multiplikation zweier <math>(2 \times 2)</math>-Matrizen benötigt werden, durch geschicktes Zusammenfassen von acht auf sieben reduziert, was auf Kosten zusätzlicher Additionen geschieht. Wendet man dieses Verfahren rekursiv an, ergibt sich eine Komplexitätsordnung von

:<math>\mathcal{O}\left(n^{\log_2 7}\right) \approx \mathcal{O}\left(n^{2{,}807}\right)</math>.

Allerdings lohnt sich der Strassen-Algorithmus aufgrund der in der Landau-Notation versteckten Konstanten nur für sehr große Matrizen.<ref>{{Literatur |Autor=Paolo D’Alberto, Alexandru Nicolau |Titel=Using recursion to boost ATLAS’s performance |Sammelwerk=High-Performance Computing |Reihe=Lecture Notes in Computer Science |Band=Volume 4759 |Verlag=Springer |Datum=2010 |Seiten=142–151 |DOI=10.1007/978-3-540-77704-5_12}}</ref> Der Algorithmus mit der derzeit besten Komplexität ist eine Verbesserung des [[Coppersmith–Winograd-Algorithmus]] mit einer Laufzeit der näherungsweisen Ordnung<ref>{{Literatur |Autor=Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou |Titel=New Bounds for Matrix Multiplication: from Alpha to Omega |Sammelwerk=Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |Verlag=ACM |Datum=2024 |ISBN=978-1-61197-791-2 |DOI=10.1137/1.9781611977912.134 |Seiten=3792-3835}}</ref>

:<math>\mathcal{O}\left(n^{2{,}371552}\right)</math>.

Für den praktischen Einsatz ist dieser Algorithmus jedoch nicht geeignet. Eine untere Schranke für die Komplexität der Matrizenmultiplikation ist

:<math>\Omega\left(n^2\right)</math>,

da jedes der <math>n^2</math> Elemente der Ausgabematrix erzeugt werden muss. Die Ermittlung optimaler unterer und oberer Komplexitätsschranken für die Matrizenmultiplikation ist Gegenstand aktueller Forschung.

Ist eine der beiden Matrizen konstant, so kann lineare Berechnungscodierung verwendet werden.<ref>{{Literatur |Autor=Ralf R. Müller, Bernhard Gäde, Ali Bereyhi |Datum=2021 |Titel=Linear computation coding |arXiv=2102.00398 |Online=[https://arxiv.org/pdf/2102.00398.pdf PDF] |Abruf=2021-12-16}}</ref> Ihre asymptotische Komplexität ist

:<math>\mathcal{O}\left(n^3/\log n\right)</math>,

jedoch sind die versteckten Konstanten relativ klein, so dass bereits für Matrizen mit mehr als 20 bis 30 Zeilen oder Spalten eine Verbesserung gegenüber dem Standardverfahren erreicht werden kann.

=== Programmierung ===

Das Matrizenprodukt ist in Programmiersystemen auf unterschiedliche Weise integriert, wobei insbesondere Verwechselungsgefahr mit dem komponentenweisen [[Hadamard-Produkt]] besteht. In den numerischen Softwarepaketen [[MATLAB]] und [[GNU Octave]] wird die Matrizenmultiplikation durch den [[Sternchen (Schriftzeichen)|Sternchen]]-Operator <code>*</code> realisiert, sodass <code>A * B</code> das Matrizenprodukt ergibt.<ref>{{Literatur |Autor=Christoph W. Überhuber, Stefan Katzenbeisser, Dirk Praetorius |Titel=MATLAB 7: Eine Einführung |Verlag=Springer |Datum=2007 |Seiten=81}}</ref> In anderen Programmierumgebungen, wie [[Fortran]], [[Mathematica]], [[R (Programmiersprache)|R]] oder [[SciPy]], wird jedoch durch <code>A * B</code> das Hadamard-Produkt berechnet. Die Matrixmultiplikation wird dann durch Funktionsaufrufe, wie <code>matmul(A,B)</code> in Fortran oder <code>dot(A,B)</code> in SciPy, oder durch eigene Operatoren für die Matrixmultiplikation, wie <code>.</code> in Mathematica oder <code>%*%</code> in R, umgesetzt.<ref> 
{{Internetquelle |url=https://wiki.scipy.org/NumPy_for_Matlab_Users |titel=NumPy for Matlab Users |hrsg=SciPy.org |datum=2014-02-22 |abruf=2015-01-03}}</ref>

Die [[objektorientierte Modellierung]] ermöglicht es in C++ die arithmetischen und funktionalen Standardoperatoren auch für Matrizenoperationen zu überladen und durch entsprechende Klassenmethoden ihre typische Verwendung auf Tensoren und Matrizen höherer Stufe zu übertragen.<ref>{{Literatur |Autor=Udo F. Meißner |Titel=Tensorkalkül mit objektorientierten Matrizen  für Numerische Methoden in Mechanik und Ingenieurwissenschaften - Eine Grundlage für Tensor-/Matrix-Algorithmen der Finite-Elemente-Methode |Verlag=Springer Vieweg |Datum=2022|DOI=10.1007/978-3-658-39881-1}}</ref>

[[Datei:Singular-Value-Decomposition.svg|mini|Durch eine Singulärwertzerlegung kann eine Scherung als Produkt einer Drehung, einer Skalierung und einer weiteren Drehung dargestellt werden.]]

== Verwendung ==
=== Faktorisierungen ===

In gewisser Weise ist die Umkehrung der Matrizenmultiplikation die [[Faktorisierung]] einer gegebenen Matrix <math>A</math> als Produkt zweier Matrizen <math>B</math> und <math>C</math>, das heißt die Ermittlung einer Darstellung der Form

:<math>A = B \cdot C</math>.

Eine solche Faktorisierung ist nicht eindeutig, daher werden an die Matrizen <math>B</math> und <math>C</math> zusätzliche Anforderungen gestellt, wie [[Orthogonale Matrix|Orthogonalität]], [[Symmetrische Matrix|Symmetrie]] oder eine bestimmte Besetzungsstruktur. Wichtige Zerlegungen reeller oder komplexer Matrizen dieser Art sind:

* die [[LR-Zerlegung]] einer quadratischen Matrix in eine untere und eine obere [[Dreiecksmatrix]]
* die [[Cholesky-Zerlegung]], eine spezielle LR-Zerlegung einer symmetrisch [[positiv definit]]en Matrix
* die [[ILU-Zerlegung]], eine Art unvollständige LR-Zerlegung speziell für [[Dünnbesetzte Matrix|dünnbesetzte Matrizen]]
* die [[QR-Zerlegung]] einer Matrix in eine orthogonale Matrix und eine obere Dreiecksmatrix
* die [[Schur-Zerlegung]] einer quadratischen Matrix in drei Matrizen: eine unitäre Matrix, eine obere Dreiecksmatrix und die Inverse der ersten Matrix
* die [[Singulärwertzerlegung]] einer Matrix in drei Matrizen: eine [[unitäre Matrix]], eine Diagonalmatrix bestehend aus den [[Singulärwert]]en und die Adjungierte einer unitären Matrix

Solche Zerlegungen von Matrizen werden häufig in der [[Numerische lineare Algebra|numerischen linearen Algebra]] etwa zur Lösung [[Lineares Gleichungssystem|linearer Gleichungssysteme]] oder [[Eigenwertproblem]]e eingesetzt. So lassen sich beispielsweise die Zeilen- und Spaltenumformungen im [[Gaußsches Eliminationsverfahren|gaußschen Eliminationsverfahren]] als Produkt von [[Elementarmatrix|Elementarmatrizen]] angeben.

[[Datei:Diagram for transformation matrix of composition.svg|mini|Hintereinanderausführung zweier linearer Abbildungen als Matrizenmultiplikation]]
=== Lineare Abbildungen ===

Sind allgemein <math>V</math> und <math>W</math> zwei endlichdimensionale [[Vektorraum|Vektorräume]] über dem gleichen Körper, dann kann jede [[lineare Abbildung]] <math>f \colon V \to W</math> nach Wahl je einer [[Basis (Vektorraum)|Basis]] in den beiden Vektorräumen über ihre [[Abbildungsmatrix]] <math>M_f</math> dargestellt werden. Das [[Bild (Mathematik)|Bild]] <math>y</math> eines Vektors <math>x</math> unter der Abbildung <math>f</math> in den jeweiligen Basen kann dann über das Matrix-Vektor-Produkt

:<math>y = M_f \cdot x</math>

ermittelt werden. In der [[Geometrie]] lässt sich beispielsweise auf diese Weise jede [[Drehung]] um den [[Koordinatenursprung|Ursprung]] und jede [[Spiegelung (Geometrie)|Spiegelung]] an einer [[Ursprungsebene]] durch ein solches Matrix-Vektor-Produkt ausführen. Ist nun <math>U</math> ein weiterer Vektorraum und <math>g \colon W \to U</math> eine weitere lineare Abbildung, dann gilt für die Abbildungsmatrix der [[Komposition (Mathematik)|Hintereinanderausführung]] <math>g \circ f</math> dieser beiden Abbildungen:

:<math>M_{g \circ f} = M_g \cdot M_f</math>

Die Abbildungsmatrix einer Hintereinanderausführung zweier linearer Abbildungen ist also das Matrizenprodukt der beiden zugehörigen Abbildungsmatrizen. Auf diese Weise lässt sich beispielsweise jede [[Drehspiegelung]] als Produkt einer [[Drehmatrix]] und einer [[Spiegelungsmatrix]] darstellen. Alternativ kann eine lineare Abbildung auch durch Vektor-Matrix-Multiplikation eines Zeilenvektors mit der transponierten Abbildungsmatrix durchgeführt werden. Die Hintereinanderausführung von Abbildungen entspricht dann einer Matrizenmultiplikation von rechts statt von links.

=== Anwendungen ===

Anwendungen der Matrizenmultiplikation finden sich unter anderem:
* in der [[Analysis]] bei der Komposition [[Differenzierbare Funktion|differenzierbarer Funktionen]] mehrerer Variablen nach der [[Mehrdimensionale Kettenregel|mehrdimensionalen Kettenregel]],
* in der [[Computergrafik]] bei der Durchführung von [[Koordinatentransformation]]en in einer [[Grafikpipeline]],
* in der [[Optik]] bei der Berechnung von [[Licht]]strahlen durch [[Optisches Bauelement|optische Bauelemente]] mittels der [[Matrizenoptik]],
* in der [[Ökonomie]] bei der [[Input-Output-Analyse]] einer [[Produktion]] sowie bei der innerbetrieblichen [[Materialverflechtung]],<ref>{{Literatur |Autor=Christoph Mayer,David Francas,Carsten Weber |Titel=Lineare Algebra für Wirtschaftswissenschaftler |Auflage=3. |Verlag=GBV Fachverlage |Ort=Wiesbaden |Datum=2007 |ISBN=978-3-8349-9529-2 |Seiten=75 f.}}</ref>
* in der [[Robotik]] bei der Beschreibung [[Kinematische Kette|kinematischer Ketten]] mittels der [[Denavit-Hartenberg-Transformation]],
* in der [[Elektrotechnik]] bei der [[Zweitor]]theorie elektrischer [[Netzwerk (Elektrotechnik)|Netzwerke]],
* in der [[Quantenmechanik]] im Rahmen der [[Matrizenmechanik]], hier auch für „unendlich große“ Matrizen.
* als [[Benchmark (Computer)|Benchmark (Leistungstest)]], insbesondere für [[Mehrprozessorsystem|Multiprozessorsysteme]]

{{Siehe auch|Matrixpotenz#Anwendungen|titel1=„Anwendungen“ im Artikel Matrixpotenz}}

== Verallgemeinerungen ==

=== Matrizen über Halbringen ===

Allgemeiner können Matrizen über einem [[Halbring (Algebraische Struktur)|Halbring]] <math>R</math> betrachtet werden, wobei die wichtigsten Eigenschaften der Matrizenmultiplikation, wie Assoziativität und Distributivität, erhalten bleiben. Entsprechend bildet dann <math>(R^{n \times n}, +, \cdot)</math> den Halbring der quadratischen Matrizen über <math>R</math>. Die Nullmatrix ist im Matrizenhalbring wieder das Nullelement und auch absorbierend, wenn das Nullelement im zugrunde liegenden Halbring absorbierend ist. Ist der zugrunde liegende Halbring unitär, dann bildet auch die Einheitsmatrix wieder das Einselement im Matrizenhalbring.

Wichtige Beispiele für Halbringe sind [[Distributiver Verband|distributive Verbände]], wie beispielsweise [[Boolesche Algebra|boolesche Algebren]]. Fasst man die Elemente eines solchen Verbands als [[Wahrheitswert]]e auf, so sind Matrizen über einem Verband zweistellige [[Relation (Mathematik)|Relationen]]. Die Matrizenmultiplikation entspricht in diesem Fall der [[Relation (Mathematik)#Verkettung von Relationen|Komposition von Relationen]].

=== Matrizenkategorien ===

Algebraische Strukturen wie Ringe und Gruppen, deren Elemente Matrizen sind, sind auf quadratische Matrizen fester Größe beschränkt. Die Matrizenmultiplikation ist dagegen nicht derartig eingeschränkt. Eine Möglichkeit, diese Einschränkung aufzuheben, ist es, stattdessen [[Kategorie (Mathematik)|Kategorien]] von Matrizen, jeweils über einem festen unitären Ring oder Halbring, zu betrachten. Die Objekte sind natürliche Zahlen, und ein [[Pfeil (Kategorientheorie)|Pfeil]] <math>n \to m</math> ist eine <math>(n\times m)</math>-Matrix. Die Komposition von Pfeilen ist durch die Matrizenmultiplikation gegeben. Sollen Matrizen auch addiert werden können, handelt es sich um eine [[präadditive Kategorie]]. Wenn Matrizen aller endlichen Größen vorkommen, erhält man eine [[abelsche Kategorie]]. Wenn nur invertierbare Matrizen vorkommen, handelt es sich um ein [[Gruppoid (Kategorientheorie)|Gruppoid]]. In diesem Fall kann es interessant sein, anstelle der natürlichen Zahlen beliebige endliche Mengen als Objekte zuzulassen.

== Verwandte Produkte ==

Neben dem Matrizenprodukt existieren noch eine Reihe weiterer Produkte von Matrizen:

* Das [[Hadamard-Produkt]] zweier Matrizen ergibt eine Matrix, deren Einträge einfach durch komponentenweise Multiplikation der Einträge der Ausgangsmatrizen ermittelt werden. Im Vergleich zum Matrizenprodukt ist es jedoch weit weniger bedeutend.
* Das [[Kronecker-Produkt]] zweier Matrizen ergibt eine große Matrix, die durch Betrachtung aller möglichen Produkte von Einträgen der beiden Ausgangsmatrizen entsteht.
* Das [[Frobenius-Skalarprodukt]] zweier reeller oder komplexer Matrizen ergibt eine Zahl, die sich durch komponentenweise Multiplikation der Einträge der Ausgangsmatrizen und nachfolgende Summation all dieser Produkte berechnet. Im komplexen Fall wird dabei immer ein Eintrag [[Komplexe Konjugation|komplex konjugiert]].

== Literatur ==

* {{Literatur
   |Autor=Tilo Arens, Frank Hettlich, Christian Karpfinger, Ulrich Kockelkorn, Klaus Lichtenegger, [[Hellmuth Stachel]]
   |Titel=Mathematik
   |Auflage=2.
   |Verlag=Spektrum Akademischer Verlag
   |Datum=2011
   |ISBN=3-8274-2347-3}}
* {{Literatur
   |Autor=[[Michael Artin]]
   |Titel=Algebra
   |Verlag=Springer
   |Datum=1998
   |ISBN=3-7643-5938-2}}
* {{Literatur
   |Autor=[[Gene Golub]], Charles van Loan
   |Titel=Matrix Computations
   |Verlag=JHU Press
   |Datum=2012
   |ISBN=1-4214-0794-9}}
* {{Literatur
   |Autor=[[Charles Leiserson]], [[Ronald L. Rivest]], Clifford Stein
   |Titel=Algorithmen – eine Einführung
   |Verlag=Oldenbourg
   |Datum=2010
   |ISBN=3-486-59002-2}}

== Weblinks ==
* {{MathWorld|title=Matrix Multiplication|id=MatrixMultiplication}}
* {{PlanetMath|author=djao|title=Matrix operations|id=matrixoperations}}
* [https://matrixcalc.org/de/ Matrixmultiplikation Online Rechner]

== Einzelnachweise ==
<references />

[[Kategorie:Ringtheorie]]
[[Kategorie:Lineare Algebra]]