Tekst źródłowy strony Mnożenie macierzy

{{dopracować|źródła=2021-02}}
'''Mnożenie macierzy''' – operacja mnożenia [[macierz]]y przez [[Skalar (matematyka)|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 dwuargumentowe|Działanie]] to zdefiniowane jest wyłącznie dla macierzy, z których pierwsza ma tyle kolumn, co druga wierszy. Jeżeli <math>A</math> jest macierzą <math>n \times m,</math> a <math>B</math> macierzą typu <math>m \times p,</math> to ich '''iloczyn''', oznaczany <math>AB,</math> czasem też <math>A \cdot B,</math> jest macierzą o wymiarach <math>n \times p.</math> Jeżeli <math>C=AB,</math> a <math>c_{i,j}</math> oznacza element <math>C</math> na pozycji <math>(i,j),</math> to<ref name="epwn">{{Encyklopedia PWN | id = 3942407 | tytuł = mnożenie macierzy | data dostępu = 2024-09-24 }}</ref>:
: <math>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} + \ldots + a_{i,m}b_{m,j}</math>

dla każdej pary <math>i, j</math> dla której <math>1 \leqslant i \leqslant n</math> oraz <math>1 \leqslant j \leqslant p.</math>

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

[[Plik:Matrix multiplication diagram.svg|left]]
Przykładowo, element <math>\color{Red} c_{12}</math> powstaje z sumy iloczynów odpowiadających sobie elementów z ''pierwszego wiersza'' macierzy <math>A</math> i ''drugiej kolumny'' macierzy <math>B</math> (elementy macierzy składowych bierzemy zgodnie z kierunkiem strzałek). Innymi słowy, aby wyznaczyć element <math>\color{Red} c_{12},</math> musimy wymnożyć pierwszy element z ''pierwszego wiersza'' macierzy <math>A</math> przez pierwszy element z ''drugiej kolumny'' macierzy <math>B,</math> i do tego dodać iloczyn drugiego elementu z ''pierwszego wiersza'' macierzy <math>A</math> i drugiego elementu z ''drugiej kolumny'' macierzy <math>B.</math> Opisane obliczenia poniżej:
: <math>\color{Red} c_{12} \color{Black} = a_{11} \cdot b_{12} + a_{12} \cdot b_{22}.</math>

Każdy element iloczynu macierzy jest iloczynem skalarnym odpowiedniego wiersza pierwszej macierzy i odpowiedniej kolumny drugiej macierzy
: <math>c_{ij}=a_i \cdot b_j^\top,</math>

gdzie <math>b_j^\top</math> oznacza [[macierz transponowana|transpozycję]] macierzy b.

Podobnie postępujemy z wyróżnionym na niebiesko elementem macierzy <math>C</math> z trzeciego wiersza i trzeciej kolumny:
: <math>\color{Blue} c_{33} \color{Black} = a_{31} \cdot b_{13} + a_{32} \cdot b_{23}.</math>

Przykładowo:
: <math>\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}.</math>

=== Metoda współczynniki-wektory ===
To mnożenie macierzy może być rozważane z nieco innego punktu widzenia: sumuje ono [[wektor]]y po przemnożeniu ich uprzednio przez różne współczynniki. Jeżeli
: <math>A = \begin{bmatrix}
   a_{1,1} & a_{1,2} & \ldots \\
   a_{2,1} & a_{2,2} & \ldots \\
   \vdots & \vdots & \ddots
\end{bmatrix}</math> &ensp; oraz &ensp; <math>B = \begin{bmatrix}
   b_{1,1} & b_{1,2} & \ldots \\
   b_{2,1} & b_{2,2} & \ldots \\
   \vdots & \vdots & \ddots
\end{bmatrix} = \begin{bmatrix}
   B_1 \\
   B_2 \\
   \vdots
\end{bmatrix},</math>

to
: <math>AB = \begin{bmatrix}
   a_{1,1} B_1 + a_{1,2} B_2 + \ldots \\\\
   a_{2,1} B_1 + a_{2,2} B_2 + \ldots \\
   \vdots
\end{bmatrix}.</math>

Dla powyższych danych jest:
: <math>\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}</math>
: <math>= \begin{bmatrix}
   5 & 1 \\
   4 & 2
\end{bmatrix}.</math>

Wiersze macierzy po lewej są listą współczynników. Macierz po prawej jest listą wektorów. W przykładzie pierwszy wiersz to <math>\begin{bmatrix}1 & 0 & 2\end{bmatrix},</math> czyli bierzemy 1 raz pierwszy wektor, 0 razy drugi wektor i 2 razy trzeci wektor. Równanie można jeszcze uprościć za pomocą [[Iloczyn mieszany|iloczynu zewnętrznego]]:
: <math>A = \begin{bmatrix}
   A_1 & A_2 & \ldots
\end{bmatrix} \implies AB = \sum_i A_iB_i.</math>

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

Raz jeszcze stosując dane przykładowe, mamy:
: <math>
\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}
</math>
: <math>
= \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}.
</math>

Wektory <math>\begin{bmatrix}3 & 2 & 1\end{bmatrix}^\top</math> oraz <math>\begin{bmatrix}1 & 1 & 0\end{bmatrix}^\top</math> zostały równocześnie przekształcone na <math>\begin{bmatrix}5 & 4\end{bmatrix}^\top</math> oraz <math>\begin{bmatrix}1 & 2\end{bmatrix}^\top.</math> Można je również przekształcić po kolei, czyniąc te same kroki:
: <math>
\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}.
</math>

=== Metoda list wektorowych ===
O zwykłym iloczynie macierzy można myśleć jak o [[iloczyn skalarny|iloczynie skalarnym]] [[Przestrzeń współrzędnych#Macierze|listy kolumnowej]] wektorów przez [[Przestrzeń współrzędnych#Macierze|listę wierszową]] wektorów. Jeżeli
: <math>A = \begin{bmatrix}
   a_{1,1} & a_{1,2} & a_{1,3} & \ldots \\
   a_{2,1} & a_{2,2} & a_{2,3} & \ldots \\
   a_{3,1} & a_{3,2} & a_{3,3} & \ldots \\
   \vdots & \vdots & \vdots & \ddots
\end{bmatrix} = \begin{bmatrix}
   A_1 \\
   A_2 \\
   A_3 \\
   \vdots
\end{bmatrix}</math> &ensp; oraz &ensp; <math>B = \begin{bmatrix}
   b_{1,1} & b_{1,2} & b_{1,3} & \ldots \\
   b_{2,1} & b_{2,2} & b_{2,3} & \ldots \\
   b_{3,1} & b_{3,2} & b_{3,3} & \ldots \\
   \vdots & \vdots & \vdots & \ddots
\end{bmatrix} = \begin{bmatrix}
   B_1 & B_2 & B_3 & \ldots
\end{bmatrix},</math>

gdzie:
: <math>A_1</math> to wektor wierszowy wszystkich elementów postaci <math>a_{1,x},</math> <math>A_2</math> to wektor wierszowy wszystkich elementów postaci <math>a_{2,x}</math> itd.,
: a <math>B_1</math> jest wektorem kolumnowym wszystkich elementów postaci <math>b_{x,1},</math> <math>B_2</math> wektorem kolumnowym wszystkich elementów postaci <math>b_{x,2}</math> itd.,

to wtedy
: <math>AB = \begin{bmatrix}
   A_1 \\
   A_2 \\
   A_3 \\
   \vdots
\end{bmatrix}
* \begin{bmatrix}
   B_1 & B_2 & B_3 & \ldots
\end{bmatrix} = \begin{bmatrix}
   (A_1 \cdot B_1) & (A_1 \cdot B_2) & (A_1 \cdot B_3) & \ldots \\
   (A_2 \cdot B_1) & (A_2 \cdot B_2) & (A_2 \cdot B_3) & \ldots \\
   (A_3 \cdot B_1) & (A_3 \cdot B_2) & (A_3 \cdot B_3) & \ldots \\
   \vdots & \vdots & \vdots & \ddots
\end{bmatrix}.</math>

=== Własności ===
Mnożenie macierzy nie jest w ogólności [[przemienność|przemienne]], tj. <math>AB \ne BA.</math> 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 [[Macierz diagonalna|macierzy diagonalnych]] równego stopnia, które jest przemienne.

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

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

Dodatkowo wszystkie sposoby mnożenia opisane w tym artykule dzielą zestaw [[Mnożenie macierzy#Wspólne własności|wspólnych własności]] opisanych niżej.

=== Algorytmy ===
Naiwny [[algorytm]] standardowego mnożenia macierzy typu <math>x \times y</math> przez macierz typu <math>y \times z</math> wymaga <math>xyz</math> mnożeń. Dla macierzy kwadratowych daje to algorytm o [[złożoność obliczeniowa|złożoności]] <math>\Theta(n^3).</math>

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 <math>O(n^{2{,}807}).</math> Nie jest on jednak zwykle używany w praktyce z powodu braku [[Algorytm numerycznie stabilny|numerycznej stabilności]]. Najlepszy obecnie znany algorytm mnożenia macierzy, podany przez [[Don Coppersmith|Dona Coppersmitha]] i [[Shmuel Winograd|Shmuela Winograda]], ma złożoność rzędu ok. <math>O(n^{2{,}376}).</math> Dolne oszacowanie złożoności mnożenia macierzy, wynikające z konieczności obliczenia <math>n^2</math> wartości, to <math>\Omega(n^2).</math>

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 [[macierz diagonalna|macierzy diagonalnych]] klasy <math>\Theta(n).</math>

=== Potęgowanie macierzy ===
Definiujemy potęgę [[Macierz#Wprowadzenie i oznaczenia|macierzy kwadratowej]] <math>A</math> [[Rekurencja|rekurencyjnie]] za pomocą wzorów:
: <math>A^0=I_k</math> gdzie <math>k</math> jest wymiarem macierzy <math>A,</math>
: <math>A^{n+1}=A \cdot A^n</math> dla całkowitego nieujemnego <math>n.</math>

A zatem
: <math>A^1 = A,</math>
: <math>A^2 = A \cdot A,</math>
: <math>A^3 = A \cdot A \cdot A,</math>

itd.

Operacja potęgowania macierzy ma następujące własności:
* <math>A^{n+m} = A^n \cdot A^m,</math>
* <math>(A^n)^m = A^{nm}.</math>

Naiwny algorytm obliczenia potęgi <math>A^n</math> wymaga <math>\Theta(n)</math> mnożeń.

Za pomocą [[algorytm szybkiego potęgowania|algorytmu szybkiego potęgowania]] potęgę <math>A^n</math> możemy obliczyć w czasie <math>\Theta(\log n).</math>

Możliwe jest również potęgowanie za pomocą [[diagonalizacja|diagonalizacji]] – wymaga to podniesienia [[macierz diagonalna|macierzy diagonalnej]] do <math>n</math>-tej potęgi (zob. [[#Złożoność obliczeniowa|złożoność obliczeniowa iloczynu macierzy]]); jeżeli macierz <math>A</math> 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 macierzy <math>n</math>-wskaźnikowych ==
Macierz <math>n</math>-wskaźnikowa <math>A</math> zawiera <math>n</math> wskaźników przebiegających <math>m</math> wartości. Taka macierz zawiera <math>m^n</math> elementów macierzowych o wartościach zespolonych,
: <math>a_{k_1,\dots,k_n}.</math>

Dla macierzy <math>A</math> zdefiniowana jest operacja '''transpozycji cyklicznej''', <math>T_c</math> przesuwającej wskaźniki o jeden do przodu
: <math>(a_{k_1,\dots,k_{n-1},k_n})^{T_c}=a_{k_n,k_1,\dots,k_{n-1}}.</math>

Mnożenie (iloczyn) macierzy <math>n</math>-wskaźnikowych, zdefiniowane jest jako '''<math>n</math>-arne działanie wewnętrzne''' dla dokładnie <math>n</math> macierzy, z których każda ma <math>n</math> wskaźników przebiegających <math>m</math> wartości. Każda macierz zawiera <math>m^n</math> wartości. Wynikiem jest również macierz <math>n</math>-wskaźnikowa.

Jeżeli <math>B=A^{(1)}A^{(2)}\ldots A^{(n-1)}A^{(n)},</math> a <math>b_{k_1,k_2,\dots,k_n}</math> oznacza element <math>B</math> na pozycji <math>(k_1,k_2,\dots,k_n),</math> to
: <math>b_{k_1,\dots,k_n} = \sum_{l_1,\dots, l_{n-1} =1}^m a^{(1)}_{k_1,l_1\dots,l_{n-1}}*a^{(2)}_{l_{n-1},k_2,l_1\dots,l_{n-2}}*\ldots *a^{(n-1)}_{l_2,\dots,k_{n-1},l_1}*a^{(n)}_{l_1,l_2,\dots,k_n}</math>

dla każdego wskaźnika <math>k_i, l_j</math> dla których <math>1 \leqslant k_i \leqslant m</math> oraz <math>1 \leqslant l_j \leqslant m.</math>

=== Własności mnożenia macierzy <math>n</math>-wskaźnikowych ===
Mnożenie macierzy <math>n</math>-wskaźnikowych nie jest działaniem łącznym, np. dla <math>n=3</math> istnieje macierz <math>A,</math> taka że <math>A*A*(A*A*A) \ne A*(A*A*A)*A.</math>

Transpozycja cykliczna iloczynu macierzy <math>B=A^{(1)}\ldots A^{(n-1)}A^{(n)}</math> ma postać
: <math>B^{T_c}=(A^{(n)})^{T_c}(A^{(1)})^{T_c}\ldots (A^{(n-1)})^{T_c}.</math>

=== Szczególne macierze <math>n</math>-wskaźnikowe ===
'''Macierze jednostkowe'''

Macierze jednostkowe definiuje się z pomocą '''macierzy pomocniczej''' <math>A</math> (numer w nawiasie oznacza położenie macierzy jednostkowych cyklicznie za macierz pomocniczą, gdy macierz pomocnicza jest w innym położeniu to przy pomocy transpozycji cyklicznej przestawić na ostatnie miejsce równania):
: <math>A=I^{(1)}\ldots I^{(n-1)}A.</math>

Dla macierzy binarnych (przyjmujących tylko wartości 0 i 1) równanie jest jednoznacznie rozwiązywalne.
: <math>I^{(p)}_{k_1,\dots, k_n}=\delta_{k_p,k_{2p}},</math>

gdzie <math>\delta_{k_p,k_{2p}}</math> jest symbolem Kroneckera.

Podindeksy uważamy za cyklicznie równoważne gdy różnią się o wielokrotność <math>n.</math>

Gdy przemieścimy macierz pomocniczą o <math>q</math> miejsc, to
: <math>I^{(p)}_{k_1,\dots, k_n}=\delta_{k_{p+q},k_{2p+q}}.</math>

Dla pełnego zagadnienia z dowolnym położeniem macierzy pomocniczej i z uwzględnieniem symetrii symbolu Kroneckera otrzymujemy <math>\frac{n(n-1)}2</math> macierzy jednostkowych. [[Macierz jednostkowa]] w niewłaściwym położeniu nie musi być w nim macierzą jednostkową.

Macierze jednostkowe dla każdego położenia wyróżniają parę wskaźników. Dogodnie jest traktować macierz <math>n</math>-wskaźnikową jako zbiór <math>m^{n-2}</math> dwuwskaźnikowych '''warstw''' numerowanych przez pozostałe <math>n-2</math> wskaźniki.

'''Macierze diagonalne'''

Jeżeli każda warstwa macierzy <math>B</math> jest dwuwskaźnikową macierzą diagonalną to taką macierz nazywamy macierzą diagonalną.

'''Macierze odwrotne'''

Macierze odwrotne definiuje się przez rozwiązanie poniższych dwóch równań (macierze <math>B</math> i <math>D</math> są w tym samym położeniu, uzupełniające macierze jednostkowe nie zostały zaznaczone)
: <math>C=\ldots B \ldots A,</math>
: <math>A=\ldots D \ldots C.</math>

Macierz <math>D</math> jest macierzą odwrotną do <math>B.</math>

Każda warstwa macierzy <math>D</math> jest macierzą odwrotną (dwuwskaźnikową) warstwy o tym samym numerze macierzy <math>B.</math>

Zadanie jest wykonalne jeżeli iloczyn wszystkich wyznaczników warstw macierzy <math>B</math> jest różny od zera. Taki iloczyn nazwiemy '''wyznacznikiem''' macierzy <math>B.</math>

Dla macierzy diagonalnej wyznacznik jest równy iloczynowi wszystkich diagonalnych elementów macierzowych wszystkich warstw.

'''Macierz osobliwa'''

Macierz nazwiemy osobliwą, gdy jej wyznacznik jest równy zero.

=== Zagadnienie odwrotne ===
'''Zagadnieniem odwrotnym''' nazywamy wyznaczenie macierzy <math>X</math> z równania
: <math>B=A^{(1)}A^{(2)}\ldots A^{(n-1)}X.</math>

Zagadnienie odwrotne jest rozwiązywalne gdy wspólne działanie <math>n-1</math> macierzy: <math>A^{(1)}A^{(2)}\ldots A^{(n-1)}</math> jest nieosobliwe.

Jeżeli co najwyżej jedna macierz <math>A^{(p)}</math> jest niediagonalna to działanie jest nieosobliwe gdy wszystkie macierze są nieosobliwe.

Jeżeli co najmniej dwie macierza <math>A^{(p)},</math> <math>A^{(q)}</math> są niediagonalne to osobliwość działania jest nieokreślona.

=== Mnożenie macierzy <math>n</math>-wskaźnikowych jako działanie zewnętrzne ===
Mnożenie
: <math>Y=A^{(1)}A^{(2)}\ldots A^{(n-1)}X</math>

możemy traktować jako przekształcenie <math>m^n</math> wymiarowego wektora <math>X</math> przez wspólne działanie <math>n-1</math> macierzy <math>A^{(1)}A^{(2)}\ldots A^{(n-1)},</math> zapisujemy to w postaci
: <math>Y=M X,</math> gdzie <math>M</math> jest <math>m^n \times m^n</math> macierzą.

Przekształcenie macierzy <math>A^{(p)}</math> w macierz <math>M</math> jest jednoznaczne, a [[Funkcja odwrotna|przekształcenie odwrotne]] jest niejednoznaczne, a po wykonaniu przekształceń macierzy <math>M</math> może być nieodwracalne.

Elementy macierzowe macierzy <math>M</math> są następujące
: <math>m_{k,l} = a^{(1)}_{k_1,l_1\dots,l_{n-1}}*a^{(2)}_{l_{n-1},k_2,l_1\dots,l_{n-2}}*\ldots *a^{(n-1)}_{l_2,\dots,k_{n-1},l_1}*\delta_{k_n,l_n},</math>

gdzie:
: <math>k=k_1+(k_2-1)*m^1+(k_3-1)*m^2+\ldots +(k_n-1)*m^{n-1},</math>
: <math>l=l_1+(l_2-1)*m^1+(l_3-1)*m^2+\ldots +(l_n-1)*m^{n-1}.</math>

Macierz <math>M</math> ma postać quasidiagonalną zawierającą <math>m</math> podmacierzy <math>m^{n-1} \times m^{n-1}.</math>

Jeżeli w wyrażeniu <math>A^{(1)}A^{(2)}\ldots A^{(n-1)}</math> jest tylko <math>q</math> macierzy niediagonalnych to przy zmianie kolejności (wskaźniki primowane) wyliczanych wskaźników (najpierw <math>q</math> wskaźników macierzy niediagonalnych, a następnie <math>n-1-q</math> macierzy diagonalnych)
: <math>k'=k'_1+(k'_2-1)*m^1+(k'_3-1)*m^2+\ldots +(k'_n-1)*m^{n-1},</math>
: <math>l'=l'_1+(l'_2-1)*m^1+(l'_3-1)*m^2+\ldots +(l'_n-1)*m^{n-1},</math>

macierz <math>M</math> przyjmie postać quasidiagonalną zawierającą <math>m^{n-q}</math> podmacierzy <math>m^q \times m^q.</math>

Tak wyznaczona macierz <math>M</math> daje formalną podstawę do wyznaczania macierzy odwrotnych, rozwiązywania zagadnienia odwrotnego, jak również do badania [[Równanie własne|zagadnienia własnego]] wspólnego działania jednej lub więcej macierzy <math>A^{(p)}.</math>

== Mnożenie przez skalar ==
{{zobacz też|mnożenie przez skalar}}
Mnożenie macierzy <math>A = (a_{ij})</math> przez skalar <math>r</math> daje w wyniku iloczyn <math>rA</math> będący macierzą tego samego typu co <math>A.</math> Jej współczynniki dane są wzorem
: <math>(rA)_{ij} = r \cdot a_{ij}.</math>

Na przykład jeśli
: <math>A = \begin{bmatrix}
   1 & 2 \\
   3 & 4
\end{bmatrix},</math>

to
: <math>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}.</math>

Jeżeli jesteśmy zainteresowani macierzami nad [[pierścień (matematyka)|pierścieniem]], to powyższe mnożenie nazywa się czasem ''mnożeniem lewostronnym'', podczas gdy ''mnożenie prawostronne'' definiowane jest jako
: <math>(Ar)_{ij} = a_{ij} \cdot r.</math>

Jeżeli pierścień jest [[pierścień przemienny|przemienny]], np. [[ciało (matematyka)|ciało]] [[liczby rzeczywiste|liczb rzeczywistych]] lub [[liczby zespolone|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
: <math>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.</math>

== 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 [[Jacques Salomon Hadamard|Hadamarda]] dwóch macierzy <math>A, B</math> typu <math>m \times n</math> oznaczany przez <math>A \bullet B</math> jest również macierzą typu <math>m \times n</math> daną wzorem
: <math>(A \bullet B)_{ij} = a_{ij} b_{ij}.</math>

Dla przykładu:
: <math>\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}.</math>

Zauważmy, że iloczyn Hadamarda jest [[Macierz#Podstawowe pojęcia|podmacierzą]] iloczynu Kroneckera (zob. niżej). Iloczyn Hadamarda badany jest w teorii macierzy i pojawia się w algorytmach [[kompresja stratna|kompresji stratnej]] takiej jak [[JPEG]], jednak właściwie nie pojawia się w [[Algebra liniowa|algebrze liniowej]]{{Wątpliwe|data=2023-09}}. Dyskusja na ten temat zawarta jest w ''Horn & Johnson, 1994, rozdz. 5''.

== Iloczyn Kroneckera ==
{{Osobny artykuł|iloczyn Kroneckera}}
Dla dowolnych dwóch macierzy <math>A</math> oraz <math>B</math> definiuje się '''iloczyn prosty''' lub '''iloczyn Kroneckera''' (od nazwiska [[Leopold Kronecker|Leopolda Kroneckera]]) jako
: <math>A \otimes B = \begin{bmatrix}
   a_{11}B & a_{12}B & \ldots & a_{1n}B \\
   \vdots & \vdots & \ddots & \vdots \\
   a_{m1}B & a_{m2}B & \ldots & a_{mn}B
\end{bmatrix}.</math>

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

Na przykład
: <math>\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}.</math>

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

== Wspólne własności ==
Wszystkie rodzaje mnożenia macierzy są [[łączność (matematyka)|łączne]]:
: <math>A (B C) = (A B) C,</math>

[[Rozdzielność|rozdzielne]] względem [[Dodawanie macierzy|dodawania]]:
: <math>A (B + C) = A B + A C</math>

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

i zgodne z [[Mnożenie przez skalar|mnożeniem przez skalar]]:
: <math>c (A B) = (c A) B,</math>
: <math>(A c) B = A (c B),</math>
: <math>(A B) c = A (B c).</math>

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|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 <math>A:B,</math> jest [[przestrzeń unitarna|iloczynem wewnętrznym]] po składowych dwóch macierzy traktowanych jako wektory. Innymi słowy jest to suma elementów iloczynu Hadamarda, czyli
: <math>A:B = \sum_i\sum_j A_{ij} B_{ij} = \operatorname{tr}(A^\top B) = \operatorname{tr}(A B^\top).</math>

Ten [[przestrzeń unitarna|iloczyn skalarny]] indukuje [[Norma macierzowa#Norma Frobeniusa|normę Frobeniusa]].

== Zobacz też ==
* [[algorytm Strassena]]
* [[Basic Linear Algebra Subprograms]]
* [[dodawanie macierzy]]
* [[eksponenta macierzy]]
* [[iloczyn skalarny]]
* [[krakowian]] (kolejny iloczyn macierzy)
* [[macierz odwrotna]]
* [[problem nawiasowania ciągu macierzy]]
* [[złożenie relacji]]

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{Pismo Delta |url = temat/matematyka/algebra/2014/01/31/Schemat_Falka/ |autor = Przemysław Kiciak |tytuł = Schemat Falka |data = luty 2014 |data dostępu = 2022-07-19}}
* {{otwarty dostęp}} Piotr Stachura, nagrania dla [[Khan Academy]] na [[YouTube]] [dostęp 2024-06-22]:
** ''[https://www.youtube.com/watch?v=yHLRbTcHbLI Wprowadzenie do mnożenia macierzy]'', 19 września 2017.
** ''[https://www.youtube.com/watch?v=V8tj_-in_O0 Przykład mnożenia macierzy]'', 19 września 2017.
** ''[https://www.youtube.com/watch?v=JT8WyVk35as Czy mnożenie macierzy jest przemienne?]'', 21 września 2017.
** ''[https://www.youtube.com/watch?v=z2xUSDvgVXg Czy mnożenie macierzy jest łączne?]'', 21 września 2017.
** ''[https://www.youtube.com/watch?v=hKCa3sdAgco Macierze zerowe i mnożenie macierzy]'',  10 października 2017.
** ''[https://www.youtube.com/watch?v=0r01buwe-LE Transpozycja iloczynu macierzy]'', 30 kwietnia 2021.
* {{otwarty dostęp}} ''[https://www.youtube.com/watch?v=fDAPJ7rvcUw How AI Discovered a Faster Matrix Multiplication Algorithm]'', kanał Quanta Magazine na [[YouTube]], 22 maja 2023 [dostęp 2024-08-24].

{{Macierz}}
{{Przekształcenia liniowe}}
{{Teoria grup}}

[[Kategoria:Działania na macierzach]]
[[Kategoria:Działania dwuargumentowe]]