Mnożenie macierzy

Mnożenie macierzy – 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  jest macierzą  a  macierzą typu  to ich iloczyn, oznaczany  czasem też  jest macierzą o wymiarach  Jeżeli  a  oznacza element  na pozycji  to
 

dla każdej pary  dla której  oraz

Obliczanie z definicji 
Poniżej zilustrowany został sposób obliczania elementów  oraz  macierzy wynikowej  będącej iloczynem macierzy  i 

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

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

gdzie  oznacza transpozycję macierzy b.

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

Przykładowo:

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
    oraz   

to
 

Dla powyższych danych jest:
 
 

Wiersze macierzy po lewej są listą współczynników. Macierz po prawej jest listą wektorów. W przykładzie pierwszy wiersz to  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:
 

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

Raz jeszcze stosując dane przykładowe, mamy:
 
 

Wektory  oraz  zostały równocześnie przekształcone na  oraz  Można je również przekształcić po kolei, czyniąc te same kroki:

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
    oraz   

gdzie:
  to wektor wierszowy wszystkich elementów postaci   to wektor wierszowy wszystkich elementów postaci  itd.,
 a  jest wektorem kolumnowym wszystkich elementów postaci   wektorem kolumnowym wszystkich elementów postaci  itd.,

to wtedy

Własności 
Mnożenie macierzy nie jest w ogólności przemienne, tj.  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  oraz  są zawsze równe (jeżeli  i  są macierzami kwadratowymi tego samego stopnia), co wyjaśnione jest w artykule o wyznaczniku.

Mnożenie Cauchy’ego jest istotne, ponieważ jeśli macierze  i  reprezentują przekształcenia liniowe (co powszechnie się czyni), to ich iloczyn  odpowiada złożeniu tych przekształceń, w którym odwzorowanie  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  przez macierz typu  wymaga  mnożeń. Dla macierzy kwadratowych daje to algorytm o złożoności 

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  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.  Dolne oszacowanie złożoności mnożenia macierzy, wynikające z konieczności obliczenia  wartości, to 

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

Potęgowanie macierzy 
Definiujemy potęgę macierzy kwadratowej  rekurencyjnie za pomocą wzorów:
  gdzie  jest wymiarem macierzy 
  dla całkowitego nieujemnego 

A zatem
 
 
 

itd.

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

Naiwny algorytm obliczenia potęgi  wymaga  mnożeń.

Za pomocą algorytmu szybkiego potęgowania potęgę  możemy obliczyć w czasie 

Możliwe jest również potęgowanie za pomocą diagonalizacji – wymaga to podniesienia macierzy diagonalnej do -tej potęgi (zob. złożoność obliczeniowa iloczynu macierzy); jeżeli macierz  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 -wskaźnikowych 
Macierz -wskaźnikowa  zawiera  wskaźników przebiegających  wartości. Taka macierz zawiera  elementów macierzowych o wartościach zespolonych,
 

Dla macierzy  zdefiniowana jest operacja transpozycji cyklicznej,  przesuwającej wskaźniki o jeden do przodu
 

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

Jeżeli  a  oznacza element  na pozycji  to
 

dla każdego wskaźnika  dla których  oraz

Własności mnożenia macierzy -wskaźnikowych 
Mnożenie macierzy -wskaźnikowych nie jest działaniem łącznym, np. dla  istnieje macierz  taka że 

Transpozycja cykliczna iloczynu macierzy  ma postać

Szczególne macierze -wskaźnikowe 
Macierze jednostkowe

Macierze jednostkowe definiuje się z pomocą macierzy pomocniczej  (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):
 

Dla macierzy binarnych (przyjmujących tylko wartości 0 i 1) równanie jest jednoznacznie rozwiązywalne.
 

gdzie  jest symbolem Kroneckera.

Podindeksy uważamy za cyklicznie równoważne gdy różnią się o wielokrotność 

Gdy przemieścimy macierz pomocniczą o  miejsc, to
 

Dla pełnego zagadnienia z dowolnym położeniem macierzy pomocniczej i z uwzględnieniem symetrii symbolu Kroneckera otrzymujemy  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 -wskaźnikową jako zbiór  dwuwskaźnikowych warstw numerowanych przez pozostałe  wskaźniki.

Macierze diagonalne

Jeżeli każda warstwa macierzy  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  i  są w tym samym położeniu, uzupełniające macierze jednostkowe nie zostały zaznaczone)
 
 

Macierz  jest macierzą odwrotną do 

Każda warstwa macierzy  jest macierzą odwrotną (dwuwskaźnikową) warstwy o tym samym numerze macierzy 

Zadanie jest wykonalne jeżeli iloczyn wszystkich wyznaczników warstw macierzy  jest różny od zera. Taki iloczyn nazwiemy wyznacznikiem macierzy 

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  z równania
 

Zagadnienie odwrotne jest rozwiązywalne gdy wspólne działanie  macierzy:  jest nieosobliwe.

Jeżeli co najwyżej jedna macierz  jest niediagonalna to działanie jest nieosobliwe gdy wszystkie macierze są nieosobliwe.

Jeżeli co najmniej dwie macierza   są niediagonalne to osobliwość działania jest nieokreślona.

Mnożenie macierzy -wskaźnikowych jako działanie zewnętrzne 
Mnożenie
 

możemy traktować jako przekształcenie  wymiarowego wektora  przez wspólne działanie  macierzy  zapisujemy to w postaci
  gdzie  jest  macierzą.

Przekształcenie macierzy  w macierz  jest jednoznaczne, a przekształcenie odwrotne jest niejednoznaczne, a po wykonaniu przekształceń macierzy  może być nieodwracalne.

Elementy macierzowe macierzy  są następujące
 

gdzie:
 
 

Macierz  ma postać quasidiagonalną zawierającą  podmacierzy 

Jeżeli w wyrażeniu  jest tylko  macierzy niediagonalnych to przy zmianie kolejności (wskaźniki primowane) wyliczanych wskaźników (najpierw  wskaźników macierzy niediagonalnych, a następnie  macierzy diagonalnych)
 
 

macierz  przyjmie postać quasidiagonalną zawierającą  podmacierzy 

Tak wyznaczona macierz  daje formalną podstawę do wyznaczania macierzy odwrotnych, rozwiązywania zagadnienia odwrotnego, jak również do badania zagadnienia własnego wspólnego działania jednej lub więcej macierzy

Mnożenie przez skalar 

Mnożenie macierzy  przez skalar  daje w wyniku iloczyn  będący macierzą tego samego typu co  Jej współczynniki dane są wzorem
 

Na przykład jeśli
 

to
 

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
 

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

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  typu  oznaczany przez  jest również macierzą typu  daną wzorem
 

Dla przykładu:
 

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  oraz  definiuje się iloczyn prosty lub iloczyn Kroneckera (od nazwiska Leopolda Kroneckera) jako
 

Zauważmy, że jeśli  jest macierzą typu  zaś  macierzą typu  to  jest macierzą typu  To mnożenie również nie jest przemienne.

Na przykład
 

Jeżeli  i  reprezentują przekształcenia liniowe, odpowiednio  oraz  to  reprezentuje iloczyn tensorowy dwóch odwzorowań,

Wspólne własności 
Wszystkie rodzaje mnożenia macierzy są łączne:
 

rozdzielne względem dodawania:
 

oraz
 

i zgodne z mnożeniem przez skalar:
 
 
 

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  jest iloczynem wewnętrznym po składowych dwóch macierzy traktowanych jako wektory. Innymi słowy jest to suma elementów iloczynu Hadamarda, czyli
 

Ten iloczyn skalarny indukuje 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

Linki zewnętrzne 
 

Działania na macierzach
Działania dwuargumentowe