Matrizenmultiplikation

Grundidee und Berechnung

Die Matrizenmultiplikation verknüpft zwei Matrizen A und B zu einer Produktmatrix C = A·B, oft kurz AB geschrieben. Sie ist nur möglich, wenn die Spaltenzahl der ersten Matrix gleich der Zeilenzahl der zweiten ist. Für A ∈ R^(m×n) und B ∈ R^(n×p) gilt daher

C = A·B ∈ R^(m×p).

Die Ergebnismatrix besitzt also so viele Zeilen wie A und so viele Spalten wie B. Ihr Eintrag in der i-ten Zeile und k-ten Spalte lautet

cᵢₖ = ∑ⱼ₌₁ⁿ aᵢⱼ·bⱼₖ.

Man multipliziert somit die Einträge der i-ten Zeile von A komponentenweise mit den Einträgen der k-ten Spalte von B und addiert die Produkte. Dieses Verfahren heißt „Zeile mal Spalte“. Jeder Ergebniseintrag kann als Skalarprodukt einer Zeile von A mit einer Spalte von B verstanden werden. „A von links mit B multiplizieren“ bezeichnet B·A, während „A von rechts mit B multiplizieren“ A·B bedeutet.

Rechenbeispiel

Für

A = ((3, 2, 1), (1, 0, 2)) ∈ ℝ^(2×3)

und

B = ((1, 2), (0, 1), (4, 0)) ∈ ℝ^(3×2)

ist A·B definiert, weil A drei Spalten und B drei Zeilen besitzt. Das Ergebnis hat zwei Zeilen und zwei Spalten. Die vier Einträge werden einzeln nach dem Schema „Zeile mal Spalte“ berechnet:

c₁₁ = 3·1 + 2·0 + 1·4 = 7, c₁₂ = 3·2 + 2·1 + 1·0 = 8, c₂₁ = 1·1 + 0·0 + 2·4 = 9, c₂₂ = 1·2 + 0·1 + 2·0 = 2.

Damit ist

A·B = ((7, 8), (9, 2)).

Als optische Hilfestellung für diese Berechnung kann das falksche Schema verwendet werden.

Sonderformen des Produkts

Wichtige Sonderfälle ergeben sich aus den Formen der beteiligten Matrizen:

• Zeilenvektor mal Spaltenvektor: Sind xᵀ und y gleich lange reelle Vektoren, ergibt xᵀ·y eine (1×1)-Matrix beziehungsweise die reelle Zahl des Standardskalarprodukts ⟨x,y⟩ = xᵀ·y.

• Spaltenvektor mal Zeilenvektor: Für einen Spaltenvektor x der Länge m und einen Zeilenvektor yᵀ der Länge n entsteht das dyadische Produkt x⊗y = x·yᵀ, eine (m×n)-Matrix mit Einträgen cᵢⱼ = xᵢ·yⱼ. Ein allgemeines Matrizenprodukt lässt sich als Summe entsprechender dyadischer Produkte darstellen.

• Matrix mal Vektor: Für A ∈ R^(m×n) und x ∈ Rⁿ gilt A·x = y ∈ Rᵐ. Sind a₁,…,aₙ die Spalten von A, dann ist A·x = ∑ⱼ₌₁ⁿ aⱼxⱼ. Das Ergebnis ist also eine Linearkombination der Spalten von A. Diese Form wird etwa für lineare Gleichungssysteme verwendet.

• Vektor mal Matrix: Für xᵀ ∈ Rᵐ und A ∈ R^(m×n) ist xᵀ·A = yᵀ ∈ Rⁿ eine Linearkombination der Zeilen von A.

• Matrixpotenzen: Für eine quadratische Matrix gilt A² = A·A; Aⁿ bezeichnet das n-fache Produkt mit sich selbst. Eine Matrix A^(1/2) mit A = A^(1/2)·A^(1/2) heißt Quadratwurzel von A. Eine Matrix kann mehrere oder sogar unendlich viele Quadratwurzeln besitzen. Entsprechend ist A^(1/n) eine n-te Wurzel.

• Blockmatrizen: Stimmen die Blockbreiten von A mit den Blockhöhen von B überein, kann blockweise nach demselben Schema gerechnet werden. Für zwei 2×2-Blockmatrizen ist beispielsweise der linke obere Ergebnisblock A₁₁B₁₁ + A₁₂B₂₁. Die Ergebnismatrix übernimmt die Blockhöhen der ersten und die Blockbreiten der zweiten Matrix.

Gesetze und algebraische Bedeutung

Die Matrizenmultiplikation ist assoziativ: Für passende Dimensionen gilt A·(B·C) = (A·B)·C. Bei mehreren Faktoren darf daher die Klammerung verändert werden, nicht aber ihre Reihenfolge. Auch Skalare sind verträglich: a(B·C) = (aB)·C = B·(aC).

Mit der Matrizenaddition gelten beide Distributivgesetze:

(A+B)·C = A·C+B·C, C·(A+B) = C·A+C·B.

Im Allgemeinen ist die Multiplikation nicht kommutativ: A·B ≠ B·A. Bei nichtquadratischen Matrizen können die beiden Produkte bereits unterschiedliche Dimensionen besitzen. Auch bei quadratischen Matrizen können sie verschieden sein. Spezielle Matrizen können dennoch miteinander kommutieren.

Weitere Regeln sind

(A·B)ᵀ = Bᵀ·Aᵀ, (A·B)ᴴ = Bᴴ·Aᴴ, spur(A·B) = spur(B·A)

und für quadratische Matrizen über einem kommutativen Ring

det(A·B) = det(A)·det(B) = det(B·A).

Quadratische Matrizen fester Größe bilden mit Addition und Multiplikation den im Allgemeinen nichtkommutativen Matrizenring (R^(n×n),+,·). Die Einheitsmatrix I erfüllt A·I = I·A = A, die Nullmatrix 0 erfüllt A·0 = 0·A = 0. Der Matrizenring ist nicht nullteilerfrei: Aus A·B = 0 folgt nicht zwingend A = 0 oder B = 0. Daher darf allgemein auch nicht aus A·B = A·C auf B = C geschlossen werden.

Die regulären, also invertierbaren Matrizen bilden die allgemeine lineare Gruppe GL(n,R). Für sie gilt A·A⁻¹ = A⁻¹·A = I sowie (A·B)⁻¹ = B⁻¹·A⁻¹. Bei regulärem A ist Kürzen zulässig. Reelle orthogonale Matrizen erfüllen A·Aᵀ = Aᵀ·A = I und bilden O(n); komplexe unitäre Matrizen erfüllen A·Aᴴ = Aᴴ·A = I und bilden U(n).

Multiplikation mit regulären Matrizen definiert außerdem Beziehungen zwischen Matrizen: Äquivalenz liegt bei B = C⁻¹·A·D vor, Ähnlichkeit bei B = C⁻¹·A·C und Kongruenz bei B = Cᵀ·A·C. Entsprechend zusammenhängende Matrizen bilden Äquivalenzklassen.

Algorithmen und Umsetzung

Der Standardalgorithmus berechnet jeden Eintrag durch drei ineinanderliegende Schleifen. Für A ∈ R^(l×m) und B ∈ R^(m×n) benötigt er O(l·m·n) Operationen; bei quadratischen n×n-Matrizen beträgt die Laufzeit O(n³). Die Reihenfolge der drei Schleifen verändert das Ergebnis nicht. Bei einer Kette aus mindestens drei nichtquadratischen Matrizen kann eine geeignete Klammerung die Zahl der arithmetischen Operationen verringern.

Der Strassen-Algorithmus reduziert bei 2×2-Matrizen die nötigen Multiplikationen von acht auf sieben und erreicht rekursiv

O(n^(log₂7)) ≈ O(n^2,807).

Wegen versteckter Konstanten lohnt er sich nur für sehr große Matrizen. Eine Verbesserung des Coppersmith–Winograd-Algorithmus erreicht näherungsweise O(n^2,371552), ist aber für die Praxis ungeeignet. Die untere Schranke beträgt Ω(n²), weil alle n² Einträge der Ausgabematrix erzeugt werden müssen. Optimale obere und untere Schranken sind weiterhin Gegenstand der Forschung. Ist eine Matrix konstant, erreicht lineare Berechnungscodierung O(n³/log n) und kann laut Artikel bereits ab mehr als 20 bis 30 Zeilen oder Spalten günstiger als das Standardverfahren sein.

In Programmen muss das Matrizenprodukt vom komponentenweisen Hadamard-Produkt unterschieden werden. MATLAB und GNU Octave verwenden A * B für das Matrizenprodukt. In Fortran, Mathematica, R oder SciPy steht A * B dagegen für das Hadamard-Produkt; die Matrizenmultiplikation erfolgt dort etwa mit matmul(A,B), dot(A,B), dem Operator . beziehungsweise %*%.

Zerlegungen, Abbildungen und Erweiterungen

Bei einer Faktorisierung wird eine Matrix als A = B·C dargestellt. Weil dies nicht eindeutig ist, fordert man zusätzliche Eigenschaften wie Orthogonalität, Symmetrie oder eine bestimmte Besetzungsstruktur. Wichtige Verfahren sind LR-, Cholesky-, ILU-, QR-, Schur- und Singulärwertzerlegung. Sie dienen in der numerischen linearen Algebra besonders zur Lösung linearer Gleichungssysteme und von Eigenwertproblemen. Bei der Singulärwertzerlegung kann beispielsweise eine Scherung als Produkt einer Drehung, einer Skalierung und einer weiteren Drehung dargestellt werden.

Eine lineare Abbildung f: V→W zwischen endlichdimensionalen Vektorräumen lässt sich nach Wahl von Basen durch eine Abbildungsmatrix M_f darstellen. Das Bild eines Vektors ist y = M_f·x. Für eine weitere Abbildung g: W→U gilt bei der Hintereinanderausführung

M_(g∘f) = M_g·M_f.

Das erklärt, warum die Reihenfolge der Faktoren wichtig ist. Drehungen, Spiegelungen und Drehspiegelungen können so durch Matrixprodukte beschrieben werden.

Weitere Anwendungen liegen in der mehrdimensionalen Kettenregel, in Koordinatentransformationen der Computergrafik, der Matrizenoptik, der ökonomischen Input-Output-Analyse, kinematischen Ketten der Robotik, der Zweitortheorie elektrischer Netzwerke, der Quantenmechanik und in Leistungstests besonders für Multiprozessorsysteme.

Die Konstruktion lässt sich von Ringen auf Halbringe verallgemeinern; Assoziativität und Distributivität bleiben erhalten. Bei booleschen Algebren können Matrizen zweistellige Relationen darstellen, wobei ihre Multiplikation der Komposition von Relationen entspricht. In Matrizenkategorien sind natürliche Zahlen die Objekte und eine (n×m)-Matrix ist ein Pfeil n→m; die Pfeilkomposition ist die Matrizenmultiplikation.

Verwandte, aber andere Produkte sind das komponentenweise Hadamard-Produkt, das Kronecker-Produkt, das aus allen möglichen Produkten von Einträgen eine größere Matrix bildet, und das Frobenius-Skalarprodukt. Letzteres liefert durch komponentenweise Multiplikation und anschließende Summation eine Zahl; bei komplexen Matrizen wird dabei jeweils ein Eintrag komplex konjugiert.