Mnożenie macierzy

Niniejszy artykuł jest częścią cyklu macierze.

Niektóre typy macierzy macierz diagonalna macierz dodatnio określona macierz elementarna macierz hermitowska macierz idempotentna macierz jednostkowa macierz klatkowa macierz nieosobliwa macierz nilpotentna macierz ortogonalna macierz osobliwa macierz rzadka macierz schodkowa macierz skalarna macierz symetryczna macierz trójkątna macierz unitarna macierz wstęgowa macierz zerowa Operacje na macierzach mnożenie przez skalar dodawanie i odejmowanie mnożenie macierzy odwracanie macierzy transpozycja macierzy sprzężenie macierzy operacje elementarne macierz dopełnień algebraicznych macierz dołączona diagonalizacja postać Jordana Inne zagadnienia wyznacznik macierzy ślad macierzy widmo macierzy minor macierzy rząd macierzy wielomian charakterystyczny

edytuj ten szablon

Mnożenie macierzy – w matematyce operacja mnożenia macierzy przez skalar lub inną macierz. Artykuł zawiera opis różnorodnych sposobów przeprowadzania ich mnożenia.

Standardowe mnożenie macierzy

Jest to najczęstszy sposób mnożenia macierzy, nazywany też mnożeniem Cauchy'ego. Działanie to zdefiniowane jest wyłącznie dla macierzy, z których pierwsza ma tyle kolumn, co druga wierszy. Jeżeli $A$ jest macierzą $n \times m$, a $B$ to macierz typu $m \times p$, to ich iloczyn, oznaczany $AB$, czasem też $A \cdot B$, jest macierzą o wymiarach $n \times p$. Jeżeli $C=AB$, a $c_{i,j}$ oznacza element $C$ na pozycji $(i,j)$, to

$c_{i,j} = \sum_{r=1}^m a_{i,r}b_{r,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \cdots + a_{i,m}b_{m,j}$

dla każdej pary $i, j$ dla której $1 \leqslant i \leqslant n$ oraz $1 \leqslant j \leqslant p$.

Obliczanie z definicji

Poniżej zilustrowany został sposób obliczania elementów $\color{Red} c_{12}$ oraz $\color{Blue} c_{33}$ macierzy wynikowej $C_{4 \times 3}$, będącej iloczynem macierzy $A_{4 \times 2}$ i $B_{2 \times 3}$.

Przykładowo, element $\color{Red} c_{12}$ powstaje z sumy iloczynów odpowiadających sobie elementów z pierwszego wiersza macierzy $A$ i drugiej kolumny macierzy $B$ (elementy macierzy składowych bierzemy zgodnie z kierunkiem strzałek). Innymi słowy, aby wyznaczyć element $\color{Red} c_{12}$, musimy wymnożyć pierwszy element z pierwszego wiersza macierzy $A$ przez pierwszy element z drugiej kolumny macierzy $B$, i do tego dodać iloczyn drugiego elementu z pierwszego wiersza macierzy $A$ i drugiego elementu z drugiej kolumny macierzy $B$. Opisane obliczenia poniżej:

$\color{Red} c_{12} \color{Black} = a_{11} \cdot b_{12} + a_{12} \cdot b_{22}$.

Każdy element iloczynu macierzy jest iloczynem skalarnym odpowiedniego wiersza pierwszej macierzy i odpowiedniej kolumny drugiej macierzy

$c_{ij}=a_{i} \cdot b_{j}^\top$

gdzie $b_{j}^\top$ oznacza transpozycję macierzy b.

Podobnie postępujemy z wyróżnionym na niebiesko elementem macierzy $C$ z trzeciego wiersza i trzeciej kolumny:

$\color{Blue} c_{33} \color{Black} = a_{31} \cdot b_{13} + a_{32} \cdot b_{23}$.

Przykładowo:

$\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} (1 \cdot 3 + 0 \cdot 2 + 2 \cdot 1) & (1 \cdot 1 + 0 \cdot 1 + 2 \cdot 0) \\ (-1 \cdot 3 + 3 \cdot 2 + 1 \cdot 1) & (-1 \cdot 1 + 3 \cdot 1 + 1 \cdot 0) \\ \end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \\ \end{bmatrix}$

Metoda współczynniki-wektory

To mnożenie macierzy może być rozważane z nieco innego punktu widzenia: sumuje ono wektory po przemnożeniu ich uprzednio przez różne współczynniki. Jeżeli

$A = \begin{bmatrix} a_{1,1} & a_{1,2} & \dots \\ a_{2,1} & a_{2,2} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix}$ oraz $B = \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \\ b_{2,1} & b_{2,2} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 \\ B_2 \\ \vdots \end{bmatrix}$,

to

$AB = \begin{bmatrix} a_{1,1} B_1 + a_{1,2} B_2 + \cdots \\\\ a_{2,1} B_1 + a_{2,2} B_2 + \cdots \\ \vdots \end{bmatrix}$

Dla powyższych danych jest:

$\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 \begin{bmatrix} 3 & 1 \end{bmatrix} + 0 \begin{bmatrix} 2 & 1 \end{bmatrix} + 2 \begin{bmatrix} 1 & 0 \end{bmatrix} \\ -1 \begin{bmatrix} 3 & 1 \end{bmatrix} + 3 \begin{bmatrix} 2 & 1 \end{bmatrix} + 1 \begin{bmatrix} 1 & 0 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} \begin{bmatrix} 3 & 1 \end{bmatrix} + \begin{bmatrix} 0 & 0 \end{bmatrix} + \begin{bmatrix} 2 & 0 \end{bmatrix} \\ \begin{bmatrix} -3 & -1 \end{bmatrix} + \begin{bmatrix} 6 & 3 \end{bmatrix} + \begin{bmatrix} 1 & 0 \end{bmatrix} \end{bmatrix}$

$= \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix}$

Wiersze macierzy po lewej są listą współczynników. Macierz po prawej jest listą wektorów. W przykładzie pierwszy wiersz to $\begin{bmatrix}1 & 0 & 2\end{bmatrix}$, czyli bierzemy 1 raz pierwszy wektor, 0 razy drugi wektor i 2 razy trzeci wektor. Równanie można jeszcze uprościć za pomocą iloczynu zewnętrznego:

$A = \begin{bmatrix} A_1 & A_2 & \dots \end{bmatrix} \implies AB = \sum_i A_iB_i$

Elementy tej sumy są macierzami tego samego kształtu, z których każda opisuje działanie jednej kolumny z $A$ i jednego wiersza z $B$ na wynik. Kolumny $A$ mogą być postrzegane jako układ współrzędnych przekształcenia, np. dla danego wektora $x$ jest $Ax = A_1x_1+A_2x_2+\cdots$, gdzie $x_i$ są współrzędnymi wzdłuż „osi” $A_i$. Wyrazy $A_iB_i$ są analogiczne do $A_ix_i$ z tym, że $B_i$ zawiera i-tą współrzędną każdego wektora kolumnowego macierzy $B$, z której każda jest równocześnie przekształcana niezależnie od pozostałych.

Raz jeszcze stosując dane przykładowe mamy:

$\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix}1 \\ -1\end{bmatrix}\begin{bmatrix}3 & 1\end{bmatrix}+ \begin{bmatrix}0 \\ 3\end{bmatrix}\begin{bmatrix}2 & 1\end{bmatrix}+ \begin{bmatrix}2 \\ 1\end{bmatrix}\begin{bmatrix}1 & 0\end{bmatrix}$

$= \begin{bmatrix} 1 \cdot 3 & 1 \cdot 1 \\ -1 \cdot 3 & -1 \cdot 1 \end{bmatrix}+ \begin{bmatrix} 0 \cdot 2 & 0 \cdot 1 \\ 3 \cdot 2 & 3 \cdot 1 \end{bmatrix}+ \begin{bmatrix} 2 \cdot 1 & 2 \cdot 0 \\ 1 \cdot 1 & 1 \cdot 0 \end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix}$

Wektory $\begin{bmatrix}3 & 2 & 1\end{bmatrix}^\top$ oraz $\begin{bmatrix}1 & 1 & 0\end{bmatrix}^\top$ zostały równocześnie przekształcone na $\begin{bmatrix}5 & 4\end{bmatrix}^\top$ oraz $\begin{bmatrix}1 & 2\end{bmatrix}^\top$. Można je również przekształcić po kolei czyniąc te same kroki:

$\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix}1 \\ -1\end{bmatrix}3+ \begin{bmatrix}0 \\ 3\end{bmatrix}2+ \begin{bmatrix}2 \\ 1\end{bmatrix}1 = \begin{bmatrix} 1\cdot 3 \\ -1\cdot 3\end{bmatrix}+ \begin{bmatrix} 0\cdot 2 \\ 3\cdot 2\end{bmatrix}+ \begin{bmatrix} 2\cdot 1 \\ 1\cdot 1\end{bmatrix} = \begin{bmatrix} 5 \\ 4 \end{bmatrix}$

Metoda list wektorowych

O zwykłym iloczynie macierzy można myśleć jak o iloczynie skalarnym listy kolumnowej wektorów przez listę wierszową wektorów. Jeżeli

$A = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \dots \\ a_{2,1} & a_{2,2} & a_{2,3} & \dots \\ a_{3,1} & a_{3,2} & a_{3,3} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ \vdots \end{bmatrix}$ oraz $B = \begin{bmatrix} b_{1,1} & b_{1,2} & b_{1,3} & \dots \\ b_{2,1} & b_{2,2} & b_{2,3} & \dots \\ b_{3,1} & b_{3,2} & b_{3,3} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 & B_2 & B_3 & \dots \end{bmatrix}$,

gdzie

$A_1$ to wektor wierszowy wszystkich elementów postaci $a_{1,x}$, $A_2$ to wektor wierszowy wszystkich elementów postaci $a_{2,x}$ itd.,

a $B_1$ jest wektorem kolumnowym wszystkich elementów postaci $b_{x,1}$, $B_2$ wektorem kolumnowym wszystkich elementów postaci $b_{x,2}$ itd.,

to wtedy

$AB = \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ \vdots \end{bmatrix} * \begin{bmatrix} B_1 & B_2 & B_3 & \dots \end{bmatrix} = \begin{bmatrix} (A_1 \cdot B_1) & (A_1 \cdot B_2) & (A_1 \cdot B_3) & \dots \\ (A_2 \cdot B_1) & (A_2 \cdot B_2) & (A_2 \cdot B_3) & \dots \\ (A_3 \cdot B_1) & (A_3 \cdot B_2) & (A_3 \cdot B_3) & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}.$

Własności

Mnożenie macierzy nie jest w ogólności przemienne, tj. $AB \ne BA$. Można zaobserwować to następująco: nie można spodziewać się, iż zmiana proporcji wektorów da ten sam wynik. Innym sposobem jest też zwrócenie uwagi na kolejność czynników – liczba kolumn w macierzy proporcji musi być równa liczbie wierszy w macierzy wektorów: muszą one reprezentować tę samą liczbę wektorów. Przypadkiem szczególnym jest np. mnożenie macierzy diagonalnych równego stopnia, które jest przemienne.

Choć mnożenie macierzy nie jest przemienne, to wyznaczniki $AB$ oraz $BA$ są zawsze równe (jeżeli $A$ i $B$ są macierzami kwadratowymi tego samego stopnia), co wyjaśnione jest w w artykule o wyznaczniku.

Mnożenie Cauchy'ego jest istotne, ponieważ jeśli macierze $A$ i $B$ reprezentują przekształcenia liniowe (co powszechnie się czyni), to ich iloczyn $AB$ odpowiada złożeniu tych przekształceń, w którym odwzorowanie $B$ wykonywane jest w pierwszej kolejności.

Dodatkowo wszystkie sposoby mnożenia opisane w tym artykule dzielą zestaw wspólnych własności opisanych niżej.

Algorytmy

Naiwny algorytm standardowego mnożenia macierzy typu $x \times y$ przez macierz typu $y \times z$ wymaga $xyz$ mnożeń. Dla macierzy kwadratowych daje to algorytm o złożoności $\Theta(n^3)$.

Istnieją wydajniejsze algorytmy rozwiązywania tego zadania. Pierwszy z takich algorytmów podał w 1969 r. Volker Strassen - złożoność tego algorytmu to około $O(n^{2,807})$. Nie jest on jednak zwykle używany w praktyce z powodu braku numerycznej stabilności. Najlepszy obecnie znany algorytm mnożenia macierzy, podany przez Dona Coppersmitha i Shmuela Winograda, ma złożoność rzędu ok. $O(n^{2,376})$. Dolne oszacowanie złożoności mnożenia macierzy, wynikające z konieczności obliczenia $n^2$ wartości, to $\Omega(n^2)$.

Jeśli to możliwe, należy skorzystać z algorytmów wykorzystujących szczególne własności macierzy, np. istnieje prosty algorytm mnożenia macierzy diagonalnych klasy $\Theta(n)$.

Potęgowanie macierzy

Definiujemy potęgę macierzy kwadratowej $A$ rekurencyjnie za pomocą wzorów:

$A^0=I_k\,$ gdzie $k$ jest wymiarem macierzy $A$,

$A^{n+1}=A \cdot A^{n}$ dla całkowitego nieujemnego $n$.

A zatem

$A^1 = A \,$,

$A^2 = A \cdot A$,

$A^3 = A \cdot A \cdot A$,

itd.

Operacja potęgowania macierzy ma następujące własności:

• $A^{n+m} = A^n \cdot A^m$
• $(A^n)^m = A^{nm}$

Naiwny algorytm obliczenia potęgi $A^n$ wymaga $\Theta(n)$ mnożeń.

Za pomocą algorytmu szybkiego potęgowania potęgę $A^n$ możemy obliczyć w czasie $\Theta(\log n)$.

Możliwe jest również potęgowanie za pomocą diagonalizacji – wymaga to podniesienia macierzy diagonalnej do $n$-tej potęgi (zob. złożoność obliczeniowa iloczynu macierzy); jeżeli macierz $A$ ma współczynniki całkowite, to macierz diagonalna nie musi zachować tej właściwości, co może spowodować błędy zaokrągleń, dlatego jest to metoda mniej ogólna.

Mnożenie przez skalar

Mnożenie macierzy $A = (a_{ij})$ przez skalar $r$ daje w wyniku iloczyn $rA$ będący macierzą tego samego typu co $A$. Jej współczynniki dane są wzorem

$(rA)_{ij} = r \cdot a_{ij}$.

Na przykład, jeśli

$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$,

to

$7 A = \begin{bmatrix} 7 \cdot 1 & 7 \cdot 2 \\ 7 \cdot 3 & 7 \cdot 4 \end{bmatrix} = \begin{bmatrix} 7 & 14 \\ 21 & 28 \end{bmatrix}$.

Jeżeli jesteśmy zainteresowani macierzami nad pierścieniem, to powyższe mnożenie nazywa się czasem mnożeniem lewostronnym, podczas gdy mnożenie prawostronne definiowane jest jako

$(Ar)_{ij} = a_{ij} \cdot r$.

Jeżeli pierścień jest przemienny, np. ciało liczb rzeczywistych lub zespolonych, to powyższe mnożenia są tożsame. Jednakże, jeśli pierścień nie jest przemienny, jak np. kwaterniony, mogą się one różnić. Przykładowo

$i\begin{bmatrix} i & 0 \\ 0 & j \\ \end{bmatrix} = \begin{bmatrix} -1 & 0 \\ 0 & k \\ \end{bmatrix} \ne \begin{bmatrix} -1 & 0 \\ 0 & -k \\ \end{bmatrix} = \begin{bmatrix} i & 0 \\ 0 & j \\ \end{bmatrix}i.$

Iloczyn Hadamarda

Dla dwóch macierzy tego samego typu definiuje się iloczyn Hadamarda, znany także jako iloczyn Schura lub iloczyn po współrzędnych. Może być on uogólniony także na operatory. Iloczyn Hadamarda dwóch macierzy $A, B$ typu $m \times n$ oznaczany przez $A \bullet B$ jest również macierzą typu $m \times n$ daną wzorem

$(A \bullet B)_{ij} = a_{ij} b_{ij}$.

Dla przykładu:

$\begin{bmatrix} 1 & 2 \\ 3 & 1 \\ \end{bmatrix} \bullet \begin{bmatrix} 0 & 3 \\ 2 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1\cdot 0 & 2\cdot 3 \\ 3\cdot 2 & 1\cdot 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 6 \\ 6 & 1 \\ \end{bmatrix}$.

Zauważmy, że iloczyn Hadamarda jest podmacierzą iloczynu Kroneckera (zob. niżej). Iloczyn Hadamarda badany jest w teorii macierzy i pojawia się w algorytmach kompresji stratnej takiej jak JPEG, jednak właściwie nie pojawia się w algebrze liniowej. Dyskusja na ten temat zawarta jest w Horn & Johnson, 1994, rozdz. 5.

Iloczyn Kroneckera

Dla dowolnych dwóch macierzy $A$ oraz $B$ definiuje się iloczyn prosty lub iloczyn Kroneckera (od nazwiska Leopolda Kroneckera) jako

$A \otimes B = \begin{bmatrix} a_{11}B & a_{12}B & \cdots & a_{1n}B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{bmatrix}$.

Zauważmy, że jeśli $A$ jest macierzą typu $m \times n$, zaś $B$ macierzą typu $p \times r$, to $A \otimes B$ jest macierzą typu $mp \times nr$. To mnożenie również nie jest przemienne.

Na przykład

$\begin{bmatrix} 1 & 2 \\ 3 & 1 \\ \end{bmatrix} \otimes \begin{bmatrix} 0 & 3 \\ 2 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1\cdot 0 & 1\cdot 3 & 2\cdot 0 & 2\cdot 3 \\ 1\cdot 2 & 1\cdot 1 & 2\cdot 2 & 2\cdot 1 \\ 3\cdot 0 & 3\cdot 3 & 1\cdot 0 & 1\cdot 3 \\ 3\cdot 2 & 3\cdot 1 & 1\cdot 2 & 1\cdot 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \end{bmatrix}$.

Jeżeli $A$ i $B$ reprezentują przekształcenia liniowe, odpowiednio $V_1 \to W_1$ oraz $V_2 \to W_2$, to $A \otimes B$ reprezentuje iloczyn tensorowy dwóch odwzorowań, $V_1 \otimes V_2 \to W_1 \otimes W_2$.

Wspólne własności

Wszystkie rodzaje mnożenia macierzy są łączne:

$A (B C) = (A B) C$,

rozdzielne względem dodawania:

$A (B + C) = A B + A C$

oraz

$(A + B) C = A C + B C$

i zgodne z mnożeniem przez skalar:

$c (A B) = (c A) B$

$(A c) B = A (c B)$

$(A B) c = A (B c)$

Należy wspomnieć, że w powyższe trzy wyrażenia będą sobie tożsame, jeśli mnożenie i dodawanie w ciele skalarów będzie przemienne, np. będzie ono pierścieniem przemiennym. Zobacz sekcję mnożenie przez skalar wyżej, aby zobaczyć kontrprzykład dla ciała skalarów kwaternionów.

Iloczyn wewnętrzny Frobeniusa

Iloczyn Frobeniusa, oznaczany czasem $A:B$, jest iloczynem wewnętrznym po składowych dwóch macierzy traktowanych jako wektory. Innymi słowy jest to suma elementów iloczynu Hadamarda, czyli

$A:B = \sum_i\sum_j A_{ij} B_{ij} = \operatorname{tr}(A^\top B) = \operatorname{tr}(A B^\top)$.

Ten iloczyn skalarny indukuje normę Frobeniusa.

Zobacz też

• krakowian (kolejny iloczyn macierzy)
• algorytm Strassena (1969)
• algorytm Winograda (1980)
• algorytm Coppersmitha–Winograda (1990)
• macierz logiczna
• eksponenta macierzy
• problem nawiasowania ciągu macierzy
• macierz odwrotna
• złożenie relacji
• Basic Linear Algebra Subprograms
• dodawanie macierzy
• iloczyn skalarny

Linki zewnętrzne

• Ilustracja graficzna mnożenia macierzy