In der Mathematik ist Matrixmultiplikation eine binäre Operation, die ein Paar von matrices nimmt, und eine andere Matrix erzeugt. Dieser Begriff kann sich auf mehrere verschiedene Weisen beziehen, matrices zu multiplizieren, aber bezieht sich meistens auf das Matrixprodukt.

Dieser Artikel wird die folgende notational Vereinbarung verwenden. Matrices werden durch Großbuchstaben im kühnen, Vektoren im Kleinbuchstaben kühn, und Einträge von Vektoren vertreten, und matrices sind kursiv (da sie Skalare sind).

Skalarmultiplikation

Die einfachste Form der mit matrices vereinigten Multiplikation ist Skalarmultiplikation.

Allgemeine Definition

Verlassene Multiplikation:

Die Skalarmultiplikation einer Matrix A und ein Skalar λ gibt eine andere Matrix λ derselben Größe wie A. Die Einträge von λ A werden durch gegeben

:

ausführlich:

:

A_ {11} & A_ {12} & \cdots & A_ {1 M} \\

A_ {21} & A_ {22} & \cdots & A_ {2 M} \\

\vdots & \vdots & \ddots & \vdots \\

A_ {n1} & A_ {n2} & \cdots & A_ {nm} \\

\end {pmatrix} = \begin {pmatrix }\

\lambda A_ {11} & \lambda A_ {12} & \cdots & \lambda A_ {1 M} \\

\lambda A_ {21} & \lambda A_ {22} & \cdots & \lambda A_ {2 M} \\

\vdots & \vdots & \ddots & \vdots \\

\lambda A_ {n1} & \lambda A_ {n2} & \cdots & \lambda A_ {nm} \\

\end {pmatrix} </Mathematik>

Wenn wir mit matrices über einen allgemeineren Ring beschäftigt sind, dann ist die obengenannte Multiplikation die linke Multiplikation der Matrix mit dem Skalar λ.

Richtige Multiplikation:

Ähnlich wird die richtige Multiplikation definiert, um zu sein

:

Wenn der zu Grunde liegende Ring, zum Beispiel, die reelle Zahl oder das Feld der komplexen Zahl auswechselbar ist, sind die zwei Multiplikationen dasselbe. Jedoch, wenn der Ring wie der quaternions nicht auswechselbar ist, können sie nicht gleich sein.

Beispiele

Für einen echten Skalar und Matrix:

:

& \lambda = 2, \quad \mathbf = \begin {pmatrix }\

a & b \\

c & d \\

\end {pmatrix}, \\

& 2 \mathbf = 2 \begin {pmatrix }\

a & b \\c & d \\\end {pmatrix} = \begin {pmatrix }\

2a & 2b \\

2c & 2. \\

\end {pmatrix} = \begin {pmatrix }\a & b \\c & d \\

\end {pmatrix} 2 = \mathbf 2

\end {richten} </Mathematik> {aus}

Für quaternion Skalare und matrices:

:

i\begin {pmatrix}

ich & 0 \\

0 & j \\

\end {pmatrix }\

\begin {pmatrix }\

- 1 & 0 \\

0 & k \\

\end {pmatrix }\

\ne \begin {pmatrix }\

- 1 & 0 \\

0 &-k \\

\end {pmatrix }\

\begin {pmatrix }\

ich & 0 \\

0 & j \\

\end {pmatrix} ich

</Mathematik>

Matrixprodukt (zwei matrices)

Nehmen Sie an, dass zwei matrices multipliziert werden sollen (die Generalisation zu jeder Zahl wird unten besprochen). Wenn A eine n×m Matrix ist und B eine m×p Matrix ist, hat das Ergebnis AB ihrer Multiplikation ist eine n×p Matrix, nur definiert, wenn die Zahl von Säulen M in A der Zahl von Reihen M in B gleich ist.

Allgemeine Definition

Wenn

man matrices multipliziert, werden die Elemente der Reihen in der ersten Matrix mit entsprechenden Säulen in der zweiten Matrix (gezeichnet im Bildrecht) multipliziert. Man kann jeden Zugang in der dritten Matrix einer nach dem anderen schätzen.

Für zwei matrices

:

A_ {11} & A_ {12} & \cdots & A_ {1 M} \\

A_ {21} & A_ {22} & \cdots & A_ {2 M} \\

\vdots & \vdots & \ddots & \vdots \\

A_ {n1} & A_ {n2} & \cdots & A_ {nm} \\

\end {pmatrix}, \quad\mathbf {B} = \begin {pmatrix }\

B_ {11} & B_ {12} & \cdots & B_ {1p} \\

B_ {21} & B_ {22} & \cdots & B_ {2p} \\

\vdots & \vdots & \ddots & \vdots \\

B_ {m1} & B_ {m2} & \cdots & B_ {Mitglied des Parlaments} \\

\end {pmatrix} </Mathematik>

(wo notwendigerweise die Zahl von Säulen in A gleich ist, kommt die Zahl von Reihen in B m gleich) das Matrixprodukt AB wird durch definiert

:

(AB) _ {11} & (AB) _ {12} & \cdots & (AB) _ {1p} \\

(AB) _ {21} & (AB) _ {22} & \cdots & (AB) _ {2p} \\

\vdots & \vdots & \ddots & \vdots \\

(AB) _ {n1} & (AB) _ {n2} & \cdots & (AB) _ {np} \\

\end {pmatrix} </Mathematik>

(ohne Multiplikationszeichen oder Punkte), wo AB Einträge durch definieren ließ

:

Die Reihen und Säulen in jeder Matrix als Reihe und Spaltenvektoren beziehungsweise behandelnd, ist dieser Zugang auch ihr Vektor-Punktprodukt:

:

A_ {i1} & A_ {i2} & \cdots & A_ {in }\

\end {pmatrix }\\, \quad \mathbf {b} _j =\begin {pmatrix }\

B_ {1j} \\

B_ {2j} \\

\vdots \\

B_ {nj }\

\end {pmatrix},

\quad (AB) _ {ij} = \mathbf {ein} _i \cdot \mathbf {b} _j </Mathematik>

(Sieh unten für weitere Details). Gewöhnlich sind die Einträge Zahlen oder Ausdrücke, aber können sogar matrices selbst sein (sieh Block-Matrix). Das Matrixprodukt kann noch derselbe Weg berechnet werden.

Illustration

Die Zahl illustriert nach rechts grafisch das Produkt von zwei matrices A und B, sich zeigend, wie jede Kreuzung in der Produktmatrix einer Reihe von A und einer Säule von B. entspricht

:

\overset {4\times 2 \text {Matrix}} {\\beginnen {bmatrix }\

\color {BrickRed} a_ {11} & \color {BrickRed} a_ {12} \\

\cdot & \cdot \\

\color {BurntOrange} a_ {31} & \color {BurntOrange} a_ {32} \\

\cdot & \cdot \\

\end {bmatrix} }\

\overset {2\times 3\text {Matrix}} {\\beginnen {bmatrix }\

\cdot & \color {Fuchsie} b_ {12} & \color {Violetter} b_ {13} \\

\cdot & \color {Fuchsie} b_ {22} & \color {Violetter} b_ {23} \\

\end {bmatrix}}

\overset {4\times 3\text {Matrix}} {\\beginnen {bmatrix }\

\cdot & x_ {12} & \cdot \\

\cdot & \cdot & \cdot \\

\cdot & \cdot & x_ {33} \\

\cdot & \cdot & \cdot \\\end {bmatrix}}</Mathematik>

Die Werte an den mit Kreisen gekennzeichneten Kreuzungen sind:

:

x_ {12} &= ({\\Farbe {BrickRed} a_ {11}}, {\\Farbe {BrickRed} a_ {12}}) \cdot ({\\Farbe {Fuchsie} b_ {12}}, {\\Farbe {Fuchsie} b_ {22}}) &= {\\Farbe {BrickRed} a_ {11}} {\\Farbe {Fuchsie} b_ {12}} + {\\Farbe {BrickRed} a_ {12}} {\\Farbe {Fuchsie} b_ {22}} \\

x_ {33} &= ({\\Farbe {BurntOrange} a_ {31}}, {\\Farbe {BurntOrange} a_ {32}}) \cdot ({\\{Violetter} Farbenb_ {13}}, {\\{Violetter} Farbenb_ {23}}) &= {\\Farbe {BurntOrange} a_ {31}} {\\{Violetter} Farbenb_ {13}} + {\\Farbe {BurntOrange} a_ {32}} {\\{Violetter} Farbenb_ {23}} \\

\end {richten} </Mathematik> {aus}

Beispiele

Quadratmatrix und Spaltenvektor

:a & b \\c & d \\

\end {pmatrix}, \quad \bold {B} = \begin {pmatrix}

x\\

y \\

\end {pmatrix} </Mathematik>

ihr Matrixprodukt ist:

:a & b \\c & d \\

\end {pmatrix} \begin {pmatrix}

x\\y \\

\end {pmatrix} = \begin {pmatrix}

ein \times x + b\times y \\

c \times x + d \times y \\

\end {pmatrix} = \begin {pmatrix}

Axt + durch \\

cx + dy \\

\end {pmatrix }\

</Mathematik>

noch wird BA nicht definiert.

Das Produkt einer mit einer Säulenmatrix multiplizierten Quadratmatrix entsteht natürlich in der geradlinigen Algebra; um geradlinige Gleichungen zu lösen und geradlinige Transformationen zu vertreten. Durch die Auswahl a, b, c, d in passend, kann A eine Vielfalt von Transformationen wie Folgen vertreten, kletternd und Nachdenken, mäht einer geometrischen Gestalt im Raum.

Quadrat matrices

:

1 & 2 \\

3 & 4 \\

\end {pmatrix}, \quad \bold {B} = \begin {pmatrix}a & b \\c & d \\\end {pmatrix} </Mathematik>

ihre Matrixprodukte sind:

:1 & 2 \\3 & 4 \\\end {pmatrix} \begin {pmatrix}a & b \\c & d \\\end {pmatrix} = \begin {pmatrix}

1 \times + 2\times c & 1\times b + 2\times d \\

3 \times + 4 \times c & 3 \times b + 4\times d \\

\end {pmatrix} = \begin {pmatrix}

+ 2c & b + 2. \\

3a + 4c & 3b + 4d \\

\end {pmatrix }\</Mathematik>

und

:a & b \\c & d \\\end {pmatrix} \begin {pmatrix}1 & 2 \\3 & 4 \\\end {pmatrix} = \begin {pmatrix}

ein \times 1 + b\times 3 & ein \times 2 + b \times 4 \\

c \times 1 + d \times 3 & c \times 2 + d \times 4 \\

\end {pmatrix} = \begin {pmatrix}

+ 3b & 2a + 4b \\

c + 3. & 2c + 4d \\

\end {pmatrix }\</Mathematik>

Der Multiplying Square matrices, die geradlinige Transformationen vertreten, entspricht der zerlegbaren Transformation (sieh unten für Details).

Eigenschaften der Matrixmultiplikation

Allgemein

Analog Zahlen (Elemente eines Feldes) befriedigen matrices die folgenden allgemeinen Eigenschaften. Obwohl es eine Subtilität wegen der Natur der Matrixmultiplikation gibt.

Der ganze matrices

:

weil AB und BA gleichzeitig nicht definiert werden dürfen, selbst wenn sie sind, können sie noch immer nicht gleich sein. Das ist gegen die gewöhnliche Multiplikation von Zahlen. So lange die Einträge der Matrix aus einem Ring kommen, der eine Identität und n> 1 hat, gibt es ein Paar von n×n, der matrices über den Ring nichtpendelt. </li>

: </li>

: </li>

: und

wo λ ein Skalar ist. Wenn λ dem Zentrum des Rings von Einträgen der Matrix gehört, dann sind alle vier Mengen, weil λX = Xλ für den ganzen matrices X gleich. Diese Bedingung ist automatisch zufrieden, ob die Zahlen in den Einträgen aus einem Ersatzring, zum Beispiel, einem Feld kommen. </li>

:

wo T das Umstellen, den Austausch der Reihe i mit der Spalte i in einer Matrix anzeigt. Diese Identität hält für jeden matrices über einen Ersatzring, aber nicht für alle Ringe im Allgemeinen. </li>

Wenn A und B komplizierte Einträge, dann haben

:

wo Hermitian anzeigt, der einer Matrix (Komplex verbunden ist, verbunden und umgestellt). </li>

Die Spur eines Produktes AB ist der Ordnung von A und B unabhängig:

: </li></ol>

Quadrat matrices nur

Wenn A eine Quadratmatrix, dann ist

:

wo ich die Identitätsmatrix derselben Ordnung bin. </li>

Wenn A eine Quadratmatrix ist, kann es eine umgekehrte Matrix von Einem solchem dass geben

:

Wenn dieses Eigentum dann A hält, ist eine invertible Matrix, wenn nicht A ist eine einzigartige Matrix. </li>

Die Determinante eines Produktes AB ist das Produkt der Determinanten von A und B:

:

Während die Produkte von matrices AB und BA selbst nicht immer pendeln, tun die Determinanten der Produkte immer, da sie Zahlen sind. </li>

</ol>

Geradlinige Transformationen

Matrices bieten eine kurze Weise an, geradlinige Transformationen zwischen Vektorräumen zu vertreten, und Matrixmultiplikation entspricht der Zusammensetzung von geradlinigen Transformationen. Das Matrixprodukt von zwei matrices kann definiert werden, wenn ihre Einträge demselben Ring gehören, und folglich hinzugefügt und multipliziert werden können.

Lassen Sie U, V, und W Vektorräume über dasselbe Feld mit gegebenen Basen, S sein: V  W und T: U  V, geradlinige Transformationen und ST sein: U  W, ihre Zusammensetzung sein.

Nehmen Sie an, dass A, B, und C der matrices das Darstellen der Transformationen T, S, und ST in Bezug auf die gegebenen Basen sind.

Dann ist AB = C, d. h. die Matrix der Zusammensetzung (oder das Produkt) geradliniger Transformationen das Produkt ihres matrices in Bezug auf die gegebenen Basen.

Matrixprodukt (jede Zahl)

Kettenmultiplikation

Matrixmultiplikation kann zum Fall von mehr als zwei matrices erweitert werden, vorausgesetzt, dass für jedes folgende Paar ihre Dimensionen zusammenpassen.

Allgemeine Definition

Das Produkt von N matrices A, A..., mit Größen n×n, n×n..., n×n, ist die n×n Matrix:

:

Dieselben Eigenschaften werden halten, so lange die Einrichtung von matrices nicht geändert wird.

Beispiele

Wenn A, B, C, und D beziehungsweise m×p, p×q, q×r, und r×n matrices sind, dann gibt es 5 Weisen, sie zu gruppieren, ohne ihre Ordnung und zu ändern

:

ist eine m×n Matrix.

Mächte von matrices

Quadrat matrices kann mit sich wiederholt ebenso als gewöhnliche Zahlen multipliziert werden, weil sie immer dieselbe Zahl von Reihen und Säulen haben. Diese wiederholte Multiplikation kann als eine Macht der Matrix, ein spezieller Fall des gewöhnlichen Matrixproduktes beschrieben werden. Im Gegenteil - haben rechteckige matrices dieselbe Zahl von Reihen und Säulen nicht, so können sie zu einer Macht nie erhoben werden. Für eine n×n Matrix Ein rasied eine positive ganze Zahl k wird es als definiert

:

und die folgende Identität hält, wo λ ein Skalar ist:

Nullmacht:

:

wo ich die Identitätsmatrix bin. Das ist zur zeroth Macht jeder Zahl parallel, die Einheit gleichkommt.

Skalarmultiplikation:

:

Determinante:

:

Die naive Berechnung von Matrixmächten soll k Zeiten die Matrix zum Ergebnis multiplizieren, mit der Identitätsmatrix gerade wie der Skalarfall anfangend. Das kann mit der binären Darstellung von k, eine für Skalare allgemein verwendete Methode verbessert werden. Eine noch bessere Methode ist, die eigenvalue Zergliederung von A zu verwenden.

Das Rechnen hoher Mächte von matrices kann sehr zeitraubend sein, aber die Kompliziertheit der Berechnung kann durch das Verwenden des Lehrsatzes von Cayley-Hamilton drastisch vermindert werden, der eine Identität ausnutzt, hat das Verwenden des charakteristischen Polynoms der matrice gefunden und gibt eine wirksamere Gleichung für A, der stattdessen einen Skalar zur erforderlichen Macht, aber nicht eine komplette Matrix erhebt.

Mächte von Diagonalmatrizen

Ein spezieller Fall ist die Macht einer Diagonalmatrix A.

Da sich das Produkt von Diagonalmatrizen auf das einfache Multiplizieren entsprechender diagonaler Elemente zusammen beläuft, wird die Macht k einer Diagonalmatrix A Einträge zur Macht erheben lassen. Ausführlich;

:

\mathbf {Ein} ^k = \begin {pmatrix}

A_ {11} & 0 & \cdots & 0 \\

0 & A_ {22} & \cdots & 0 \\

\vdots & \vdots & \ddots & \vdots \\

0 & 0 & \cdots & A_ {nn }\

\end {pmatrix} ^k =

\begin {pmatrix}

A_ {11} ^k & 0 & \cdots & 0 \\

0 & A_ {22} ^k & \cdots & 0 \\

\vdots & \vdots & \ddots & \vdots \\

0 & 0 & \cdots & A_ {nn} ^k

\end {pmatrix }\</Mathematik>

die Bedeutung seines leichten, eine Diagonalmatrix zu einer Macht zu erheben. Wenn man eine willkürliche Matrix (nicht notwendigerweise eine Diagonalmatrix) zu einer Macht erhebt, ist es häufig nützlich, dieses Eigentum durch diagonalizing die Matrix zuerst auszunutzen.

Die inneren und Außenprodukte

In Anbetracht zwei Spaltenvektoren sind a und b, das Euklidische Skalarprodukt und Außenprodukt die einfachsten speziellen Fälle des Matrixproduktes, durch das Umstellen der Spaltenvektoren in Zeilenvektoren.

Das Skalarprodukt:

ist ein Spaltenvektor multipliziert links mit einem Zeilenvektoren:

:

Ausführlicher,

:

\begin {pmatrix} a_1 & a_2 & \cdots & a_n\end {pmatrix }\

\begin {pmatrix} b_1 \\b_2 \\\vdots \\b_n\end {pmatrix }\

a_1b_1+a_2b_2 +\cdots+a_nb_n

\sum_ {i=1} ^n a_ib_i

</Mathematik>

Das Außenprodukt:

ist ein Zeilenvektor multipliziert links mit einem Spaltenvektor:

:

wo

:

\begin {pmatrix} b_1 & b_2 & \cdots & b_n\end {pmatrix }\

\begin {pmatrix }\

a_1 b_1 & a_1 b_2 & \cdots & a_1 b_n \\

a_2 b_1 & a_2 b_2 & \cdots & a_2 b_n \\

\vdots & \vdots & \ddots & \vdots \\

a_n b_1 & a_n b_2 & \cdots & a_n b_n \\

\end {pmatrix}.

</Mathematik>

Matrixprodukt (in Bezug auf das Skalarprodukt)

Nehmen Sie an, dass die erste n×m Matrix A in seine Zeilenvektoren a, und die zweite m×p Matrix B in seine Spaltenvektoren b zersetzt wird:

:

\begin {pmatrix }\

A_ {1 1} & A_ {1 2} & \cdots & A_ {1 M} \\

A_ {2 1} & A_ {2 2} & \cdots & A_ {2 M} \\

\vdots & \vdots & \ddots & \vdots \\

A_ {n 1} & A_ {n 2} & \cdots & A_ {n M }\

\end {pmatrix} = \begin {pmatrix }\

\mathbf {ein} _1 \\\mathbf {ein} _2 \\\vdots \\\mathbf {ein} _n

\end {pmatrix}, \quad \mathbf {B} = \begin {pmatrix }\

B_ {1 1} & B_ {1 2} & \cdots & B_ {1 p} \\

B_ {2 1} & B_ {2 2} & \cdots & B_ {2 p} \\

\vdots & \vdots & \ddots & \vdots \\

B_ {M 1} & B_ {M 2} & \cdots & B_ {M p }\

\end {pmatrix }\\begin {pmatrix }\

\mathbf {b} _1 & \mathbf {b} _2 & \cdots & \mathbf {b} _p

\end {pmatrix }\</Mathematik>wo:

Durch die Einträge in der Einführung wurde gegeben:

:

\mathbf {AB} =

\begin {pmatrix }\

\mathbf {ein} _1 \\

\mathbf {ein} _2 \\

\vdots \\

\mathbf {ein} _n

\end {pmatrix} \begin {pmatrix} \mathbf {b} _1 & \mathbf {b} _2 & \dots & \mathbf {b} _p

\end {pmatrix} = \begin {pmatrix }\

(\mathbf _1 \cdot \mathbf {b} _1) & (\mathbf _1 \cdot \mathbf {b} _2) & \dots & (\mathbf _1 \cdot \mathbf {b} _p) \\

(\mathbf _2 \cdot \mathbf {b} _1) & (\mathbf _2 \cdot \mathbf {b} _2) & \dots & (\mathbf _2 \cdot \mathbf {b} _p) \\

\vdots & \vdots & \ddots & \vdots \\

(\mathbf {ein} _n \cdot \mathbf {b} _1) & (\mathbf {ein} _n \cdot \mathbf {b} _2) & \dots & (\mathbf {ein} _n \cdot \mathbf {b} _p)

\end {pmatrix }\</Mathematik>

Es ist auch möglich, ein Matrixprodukt in Bezug auf Verkettungen von Produkten von matrices und Reihe oder Spaltenvektoren auszudrücken:

:\mathbf {AB} =\begin {pmatrix }\\mathbf {ein} _1 \\\mathbf {ein} _2 \\\vdots \\\mathbf {ein} _n\end {pmatrix} \begin {pmatrix} \mathbf {b} _1 & \mathbf {b} _2 & \dots & \mathbf {b} _p\end {pmatrix} = \begin {pmatrix }\

\mathbf {Ein }\\mathbf {b} _1 & \mathbf {Ein }\\mathbf {b} _2 & \dots & \mathbf {Ein }\\mathbf {b} _p

\end {pmatrix} = \begin {pmatrix }\

\mathbf {ein} _1\mathbf {B} \\

\mathbf {ein} _2\mathbf {B }\\\

\vdots \\

\mathbf {ein} _n\mathbf {B }\

\end {pmatrix }\</Mathematik>

Diese Zergliederungen sind für matrices besonders nützlich, die als Verkettungen von besonderen Typen von Zeilenvektoren oder Spaltenvektoren, z.B orthogonaler matrices vorgesehen werden (dessen Reihen und Säulen Einheitsvektoren sind, die zu einander orthogonal sind), und Markov matrices (dessen Reihen oder Säulen zu 1 resümieren).

Matrixprodukt (in Bezug auf das Außenprodukt)

Eine alternative Methode resultiert, wenn die Zergliederung der andere Weg ringsherum getan wird, d. h. die erste Matrix A in Spaltenvektoren und die zweite Matrix B in Zeilenvektoren zersetzt wird:

:

\mathbf {AB} =

\begin {pmatrix} \mathbf {\\Bar a\_1 & \mathbf {\\Bar a\_2 & \cdots & \mathbf {\\Bar a\_m \end {pmatrix }\

\begin {pmatrix} \mathbf {\\Bar b\_1 \\\mathbf {\\Bar b\_2 \\\vdots \\\mathbf {\\Bar b\_m \end {pmatrix }\

\mathbf {\\Bar a\_1 \otimes \mathbf {\\Bar b\_1 + \mathbf {\\Bar a\_2 \otimes \mathbf {\\Bar b\_2 + \cdots + \mathbf {\\Bar a\_m \otimes \mathbf {\\Bar b\_m

\sum_ {i=1} ^m \mathbf {\\Bar a\_i \otimes \mathbf {\\Bar b\_i

</Mathematik>

wo dieses Mal

:

Diese Methode betont die Wirkung von individuellen Paaren der Säule/Reihe auf dem Ergebnis, das ein nützlicher Gesichtspunkt mit z.B der Kovarianz matrices ist, wo jedes solches Paar der Wirkung eines einzelnen Beispielpunkts entspricht.

Beispiele

Nehmen Sie an

:

\mathbf = \begin {pmatrix }\

1 & 2 & 3 \\

4 & 5 & 6 \\

7 & 8 & 9 \\

\end {pmatrix}, \quad \mathbf {B} = \begin {pmatrix }\

a & d \\

b & e \\

c & f \\

\end {pmatrix} </Mathematik>

das Verwenden der Skalarprodukt-Annäherung:

:\begin {pmatrix }\

{\\Farbe {BrickRed} 1\& {\\Farbe {BurntOrange} 2\& {\\Farbe {Violett} 3\\\

{\\Farbe {BrickRed} 4\& {\\Farbe {BurntOrange} 5\& {\\Farbe {Violett} 6\\\

{\\Farbe {BrickRed} 7\& {\\Farbe {BurntOrange} 8\& {\\Farbe {Violett} 9\\\

\end {pmatrix }\\begin {pmatrix }\

{\\Farbe {BrickRed} a\& {\\Farbe {BrickRed} d\\\

{\\Farbe {BurntOrange} b\& {\\Farbe {BurntOrange} e\\\

{\\Farbe {Violett} c\& {\\Farbe {Violett} f\\\

\end {pmatrix }\\begin {pmatrix }\

{\\Farbe {BrickRed} 1a} + {\\Farbe {BurntOrange} 2b} + {\\Farbe {Violett} 3c} & {\\Farbe {BrickRed} 1d} + {\\Farbe {BurntOrange} 2e} + {\\Farbe {Violett} 3f} \\

{\\Farbe {BrickRed} 4a} + {\\Farbe {BurntOrange} 5b} + {\\Farbe {Violett} 6c} & {\\Farbe {BrickRed} 4d} + {\\Farbe {BurntOrange} 5e} + {\\Farbe {Violett} 6f} \\

{\\Farbe {BrickRed} 7a} + {\\Farbe {BurntOrange} 8b} + {\\Farbe {Violett} 9c} & {\\Farbe {BrickRed} 7d} + {\\Farbe {BurntOrange} 8e} + {\\Farbe {Violett} 9f} \\

\end {pmatrix }\</Mathematik>

während die Außenproduktannäherung gibt:

:\begin {pmatrix }\{\\Farbe {BrickRed} 1\& {\\Farbe {BurntOrange} 2\& {\\Farbe {Violett} 3\\\{\\Farbe {BrickRed} 4\& {\\Farbe {BurntOrange} 5\& {\\Farbe {Violett} 6\\\{\\Farbe {BrickRed} 7\& {\\Farbe {BurntOrange} 8\& {\\Farbe {Violett} 9\\\\end {pmatrix }\\begin {pmatrix }\{\\Farbe {BrickRed} a\& {\\Farbe {BrickRed} d\\\{\\Farbe {BurntOrange} b\& {\\Farbe {BurntOrange} e\\\{\\Farbe {Violett} c\& {\\Farbe {Violett} f\\\\end {pmatrix }\\begin {pmatrix }\

{\\Farbe {BrickRed} 1a} & {\\Farbe {BrickRed} 1d} \\

{\\Farbe {BrickRed} 4a} & {\\Farbe {BrickRed} 4d} \\

{\\Farbe {BrickRed} 7a} & {\\Farbe {BrickRed} 7d} \\

\end {pmatrix} +

\begin {pmatrix }\

{\\Farbe {BurntOrange} 2b} & {\\Farbe {BurntOrange} 2e} \\

{\\Farbe {BurntOrange} 5b} & {\\Farbe {BurntOrange} 5e} \\

{\\Farbe {BurntOrange} 8b} & {\\Farbe {BurntOrange} 8e} \\

\end {pmatrix} +\begin {pmatrix }\

{\\Farbe {Violett} 3c} & {\\Farbe {Violett} 3f} \\

{\\Farbe {Violett} 6c} & {\\Farbe {Violett} 6f} \\

{\\Farbe {Violett} 9c} & {\\Farbe {Violett} 9f} \\

\end {pmatrix }\</Mathematik>

Algorithmen für die effiziente Matrixmultiplikation

Die Laufzeit der Quadratmatrixmultiplikation, wenn ausgeführt, naiv, ist. Die Laufzeit, um rechteckigen matrices (eine M×p-Matrix mit einer P×n-Matrix) zu multiplizieren, ist O (mnp) jedoch, effizientere Algorithmen bestehen wie der Algorithmus von Strassen, der von Volker Strassen 1969 ausgedacht ist und häufig als "schnelle Matrixmultiplikation" gekennzeichnet ist. Es basiert auf einer Weise, zwei 2×2-matrices zu multiplizieren, der nur 7 Multiplikationen verlangt (statt des üblichen 8), auf Kosten von mehrerer zusätzlicher Hinzufügung und Subtraktionsoperationen. Verwendung davon gibt rekursiv einen Algorithmus mit multiplicative Kosten dessen. Der Algorithmus von Strassen ist im Vergleich zum naiven Algorithmus komplizierter, und es hat an numerischer Stabilität Mangel. Dennoch erscheint es in mehreren Bibliotheken wie BLAS, wo es für matrices mit Dimensionen n> 100 bedeutsam effizienter ist, und für großen matrices über genaue Gebiete wie begrenzte Felder sehr nützlich ist, wo numerische Stabilität nicht ein Problem ist.

Der aktuelle Algorithmus mit der niedrigsten bekannten Hochzahl k ist eine Generalisation des Algorithmus des Kupferschmieds-Winograd, der eine asymptotische Kompliziertheit von O (n) wegen Vassilevska Williams hat. Dieser Algorithmus und der Algorithmus des Kupferschmieds-Winograd, auf dem es basiert, sind dem Algorithmus von Strassen ähnlich: Ein Weg wird ausgedacht, um zwei k×k-matrices mit weniger zu multiplizieren, als k Multiplikationen, und diese Technik wird rekursiv angewandt. Jedoch ist der unveränderliche durch die Große O Notation verborgene Koeffizient so groß, dass diese Algorithmen nur für matrices lohnend sind, die zu groß sind, um auf heutigen Computern zu behandeln.

Da jeder Algorithmus, um zwei n×n-matrices zu multiplizieren, alle 2×n-Einträge bearbeiten muss, gibt es einen Operationen tiefer gebundenen asymptotischen. Raz (2002) beweist einen niedrigeren, der für begrenzte mitwirkende Arithmetik-Stromkreise über die reellen Zahlen oder komplexen Zahlen gebunden ist.

Cohn u. a. (2003, 2005) gestellte Methoden wie die Algorithmen des Strassens und Kupferschmieds-Winograd in einem völlig verschiedenen gruppentheoretischen Zusammenhang, durch das Verwenden verdreifacht sich Teilmengen von begrenzten Gruppen, die befriedigen, hat ein Zusammenhangloskeitseigentum das dreifache Produkteigentum (TPP) genannt. Sie zeigen, dass, wenn Familien von Kranz-Produkten von Gruppen von Abelian mit symmetrischen Gruppen begreifen, sich Familien der Teilmenge mit einer gleichzeitigen Version des TPP verdreifachen, dann gibt es Matrixmultiplikationsalgorithmen mit der im Wesentlichen quadratischen Kompliziertheit. Die meisten Forscher glauben, dass das tatsächlich der Fall - ein langer Versuch des Beweises ist, dass das vom verstorbenen Jim Eve übernommen wurde. Jedoch haben Alon, Shpilka und Umans kürzlich gezeigt, dass einige dieser Vermutungen, die schnelle Matrixmultiplikation einbeziehen, mit einer anderen plausiblen Vermutung, der Sonnenblume-Vermutung unvereinbar sind.

Wegen der Natur von Matrixoperationen und des Lay-Outs von matrices im Gedächtnis ist es normalerweise möglich, wesentliche Leistungszunahmen durch den Gebrauch von parallelization und vectorization zu gewinnen. Es sollte deshalb bemerkt werden, dass einige niedrigere Zeitkompliziertheitsalgorithmen auf Papier indirekte Zeitkompliziertheitskosten auf echten Maschinen haben können.

Andere Formen der Multiplikation

Es gibt andere Weisen, zwei matrices zu multiplizieren, die tatsächlich einfacher sind als die Definition oben.

Produkt von Hadamard

Für zwei matrices derselben Dimensionen gibt es das Produkt von Hadamard, auch bekannt als das entrywise Produkt und das Produkt von Schur. Für zwei matrices A und B derselben Dimensionen das Produkt von Hadamard ist Ein  B eine Matrix derselben Dimensionen, die Elemente hat

:ausführlich:: A_ {21} & A_ {22} & \cdots & A_ {2 M} \\\vdots & \vdots & \ddots & \vdots \\ A_ {n1} & A_ {n2} & \cdots & A_ {nm} \\

\end {pmatrix }\\circ\begin {pmatrix }\

B_ {11} & B_ {12} & \cdots & B_ {1 M} \\

B_ {21} & B_ {22} & \cdots & B_ {2 M} \\

\vdots & \vdots & \ddots & \vdots \\

B_ {n1} & B_ {n2} & \cdots & B_ {nm} \\

\end {pmatrix} = \begin {pmatrix }\

A_ {11} B_ {11} & A_ {12} B_ {12} & \cdots & A_ {1-M-}-B_ {1 M} \\

A_ {21} B_ {21} & A_ {22} B_ {22} & \cdots & A_ {2-M-}-B_ {2 M} \\

\vdots & \vdots & \ddots & \vdots \\

A_ {n1} B_ {n1} & A_ {n2} B_ {n2} & \cdots & A_ {nm} B_ {nm} \\

\end {pmatrix} </Mathematik>

Wegen der Eigenschaft entrywise Verfahren ist diese Operation zu vielen multiplizierenden gewöhnlichen Zahlen (mn von ihnen) plötzlich - folglich identisch das Produkt von Hadamard ist auswechselbar, assoziativ und über die Hinzufügung verteilend, und ist eine Hauptsubmatrix des Produktes von Kronecker. Es erscheint in lossy Kompressionsalgorithmen wie JPEG.

Das Frobenius Skalarprodukt, manchmal angezeigter A: B ist das teilkluge Skalarprodukt von zwei matrices, als ob sie Vektoren sind. Es ist auch die Summe der Einträge des Produktes von Hadamard. Ausführlich,

:

wo "tr" die Spur einer Matrix anzeigt. Dieses Skalarprodukt veranlasst die Norm von Frobenius.

Produkt von Kronecker

Für zwei matrices A und B irgendwelcher verschiedenen Dimensionen m×n und p×q beziehungsweise (kein contraints auf den Dimensionen jeder Matrix) hat das Produkt von Kronecker angezeigt, dass Ein  B eine Matrix mit Dimensionen mp×nq ist, der Elemente hat

:ausführlich::

A_ {11 }\\mathbf {B} & A_ {12 }\\mathbf {B} & \cdots & A_ {1n }\\mathbf {B} \\

A_ {21 }\\mathbf {B} & A_ {22 }\\mathbf {B} & \cdots & A_ {2n }\\mathbf {B} \\

\vdots & \vdots & \ddots & \vdots \\

A_ {m1 }\\mathbf {B} & A_ {m2 }\\mathbf {B} & \cdots & A_ {mn }\\mathbf {B} \\

\end {pmatrix} </Mathematik>

Das ist die Anwendung des allgemeineren auf matrices angewandten Tensor-Produktes.

Siehe auch

• Matrixhinzufügung
• Matrixinversion
• Logische Matrix
• Zusammensetzung von Beziehungen
• Cracovian
• Algorithmus von Strassen
• Algorithmus des Kupferschmieds-Winograd
• Grundlegende geradlinige Algebra-Unterprogramme

Zeichen

• Henry Cohn, Robert Kleinberg, Balazs Szegedy und Chris Umans. Gruppentheoretische Algorithmen für die Matrixmultiplikation.. Verhandlungen des 46. Jährlichen Symposiums auf Fundamenten von Informatik, am 23-25 Oktober 2005, Pittsburgh, Pennsylvanien, IEEE Computergesellschaft, Seiten 379-388.
• Henry Cohn, Chris Umans. Eine Gruppentheoretische Annäherung an die Schnelle Matrixmultiplikation.. Verhandlungen des 44. Jährlichen IEEE Symposiums auf Fundamenten von Informatik, am 11-14 Oktober 2003, Cambridge, Massachusetts, IEEE Computergesellschaft, Seiten 438-449.
• Kupferschmied, D., Winograd S., Matrixmultiplikation über arithmetische Fortschritte, J. Symbolischer Comput. 9, p. 251-280, 1990.
• Vorabend, James. Auf O (loggen n^2 n), Algorithmen für n x n Matrixoperationen. Technischer Bericht Nr. 1169, Schule der Computerwissenschaft der Wissenschaft, Universität Newcastles auf Tyne, August 2009. PDF
• Knuth, D.E. Die Kunst des Computerprogrammierbands 2: Halbnumerische Algorithmen. Addison-Wesley Professional; 3 Ausgabe (am 14. November 1997). Internationale Standardbuchnummer 978-0-201-89684-8. Seiten 501.
• .

Hat

• Raz geführt. Auf der Kompliziertheit des Matrixproduktes. In Verhandlungen des vierunddreißigsten jährlichen ACM Symposiums auf der Theorie der Computerwissenschaft. ACM Presse, 2002..
• Robinson, Sara, Zu einem Optimalen Algorithmus für die Matrixmultiplikation, SIAM Nachrichten 38 (9), November 2005. PDF
• Strassen, Volker, ist Gaussian Beseitigung, Numer nicht Optimal. Mathematik. 13, p. 354-356, 1969.
• Vassilevska Williams, Virginia, die Barriere des Kupferschmieds-Winograd, das Manuskript, November 2011 Brechend. PDF

Außenverbindungen

• Das gleichzeitige dreifache Produkteigentum und die gruppentheoretischen Ergebnisse für die Hochzahl der Matrixmultiplikation
• WIMS Online-Matrixvermehrer
• Matrixmultiplikationsprobleme
• Blockieren Sie Matrixmultiplikationsprobleme
• Matrixmultiplikation in C
• Geradlinige Algebra: Matrixoperationen Multiplizieren oder fügen matrices eines Typs hinzu, und mit Koeffizienten wählen Sie und sehen, wie das Ergebnis geschätzt wurde.
• Sehmatrixmultiplikation Ein interaktiver app, um Matrixmultiplikation zu erfahren.
• Online-Matrixrechenmaschine
• Matrixmultiplikation in Java - Dr P. Viry