Równania

Wyznacznik macierzy ( ang. matrix determinant ) jest liczbą powiązaną ze wszystkimi wyrazami macierzy kwadratowej. Możemy go potraktować jako funkcję. Argumentem funkcji jest macierz kwadratowa ( macierz o tej samej liczbie wierszy i kolumn ), a wartością funkcji jest wyznacznik tej macierzy.

Zacznijmy od najprostszej macierzy o rozmiarze 1 × 1, czyli macierzą stopnia 1. Macierz taka zawiera tylko jeden element:

Wyznacznik tej macierzy jest równy jej elementowi:

To było proste. Wyznacznik macierzy wyższego stopnia definiowany jest rekurencyjnie. Wprowadźmy pojęcie minora ( ang. minor ) macierzy.

Minor M_ij macierzy A jest wyznacznikiem podmacierzy, która powstaje przez skreślenie w macierzy A i-tego wiersza oraz j-tej kolumny.

Na przykład mamy macierz A_{4 × 4}:

Minor M₁₁ tej macierzy powstanie po usunięciu z niej pierwszego wiersza i pierwszej kolumny i wyliczeniu wyznacznika powstałej w ten sposób podmacierzy:

Zajmijmy się macierzą stopnia 2:

Wyznacznik obliczamy następująco:

Na pierwszy rzut oka wzór wygląda skomplikowanie, jednak jest prosty. Aby policzyć wyznacznik tej macierzy, wybieramy jeden wiersz ( tutaj jest to wiersz nr 1, ale ogólnie może być to dowolny wiersz ). Wyrazy tego wiersza mnożymy przez minory, powstałe przez usunięcie wiersza i kolumny z mnożonym wyrazem, po czym iloczyn ten  mnożony jest jeszcze przez czynnik (-1)^{i + j}, gdzie i to wiersz z mnożonym wyrazem, a j to kolumna z mnożonym wyrazem.  Otrzymane iloczyny sumujemy. Gdy to już powiedzieliśmy, możemy wyprowadzić wzór na wyznacznik macierzy stopnia 2:

Wzór ten łatwo zapamiętać: mnożymy przez siebie wyrazy na przekątnej głównej i odejmujemy iloczyn wyrazów na drugiej przekątnej:

Macierz stopnia 3:

Wzór na wyznacznik komplikuje się z powodu jego rekurencyjnej natury, jednak definicja jest identyczna jak poprzednio: kolejne wyrazy wybranego wiersza i-tego mnożymy przez czynnik (-1)^{i + j} ( i jest numerem wybranego wiersza, j to numer kolumny z mnożonym wyrazem ) oraz przez ich minory M_ij. Otrzymane iloczyny sumujemy. Dla wiersza nr 1 otrzymamy:

Minory są tutaj wyznacznikami macierzy o rozmiarach 2 × 2 i obliczamy je poprzednim wzorem na wyznacznik macierzy 2 × 2 ( pojawia się rekurencja ):

Otrzymane wzory minorów wstawiamy do wzoru na wyznacznik macierzy głównej i otrzymujemy:

Otrzymany wzór jest dość skomplikowany, jednak istnieje prosta metoda zapamiętania tego wzoru zwana regułą Sarrusa.

Załóżmy, że mamy macierz stopnia 3 ( wyrazy tej macierzy są oznaczone literami dla większej czytelności ):

Z prawej strony macierzy dopisujemy jej pierwsze dwie kolumny (istnieje równoważna wersja z dopisywaniem pod macierzą jej dwóch pierwszych wierszy ):

W tak rozszerzonej macierzy mnożymy przez siebie wyrazy w trzech pierwszych przekątnych z lewa na prawo i sumujemy te iloczyny:

Następnie mnożymy przez siebie wyrazy w trzech przekątnych z prawa na lewo i otrzymane iloczyny odejmujemy od otrzymanej poprzednio sumy:

Otrzymujemy wartość wyznacznika macierzy (sprawdź to z wyprowadzonym powyżej wzorem ):

Poniższy program wykorzystuje regułę Sarrusa do wyliczania wartości wyznacznika macierzy stopnia 3. Dane są wprowadzane ze standardowego strumienia sposobem opisanym w poprzednim podrozdziale.

Ponieważ macierz jest kwadratowa stopnia 3, to rozmiar macierzy nie jest umieszczany w danych wejściowych.

Przykładowe dane ( przekopiuj je do schowka i wklej w programie ):

Macierz:

// Macierze
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicja klasy, może być w pliku nagłówkowym
//----------------------------------------------

#ifndef _matrix_class
    #define _matrix_class

    template <class T> class matrix
    {
        private:
            T * A;                // Elementy
        public:
            matrix();             // Konstruktor
            ~matrix();            // Destruktor
            T  getv(int r, int c);
            T det();              // Wylicza wyznacznik
    };

    // Konstruktor - tworzy macierz ze strumienia cin
    //-----------------------------------------------
    template <class T> matrix<T>::matrix()
    {
        A = new T [9]; // Rezerwujemy pamięć na macierz 3 x 3

        for(int i = 0; i < 9; i++) cin >> A[i]; // Wczytujemy wyrazy macierzy
    }

    // Destruktor - usuwa macierz i zwraca zajętą przez nią pamięć
    //------------------------------------------------------------
    template <class T> matrix<T>::~matrix()
    {
        delete [] A;
    }

    // Zwraca wartość elementu
    // r - numer wiersza
    // c - numer kolumny
    //-------------------------
    template <class T> T matrix<T>::getv(int r, int c)
    {
        return A[r * 3 + c];
    }

    // Oblicza wyznacznik macierzy
    //----------------------------
    template <class T> T matrix<T>::det()
    {
        T D;
        D  = getv(0,0) * getv(1,1) * getv(2,2);
        D += getv(0,1) * getv(1,2) * getv(2,0);
        D += getv(0,2) * getv(1,0) * getv(2,1);
        D -= getv(0,2) * getv(1,1) * getv(2,0);
        D -= getv(0,0) * getv(1,2) * getv(2,1);
        D -= getv(0,1) * getv(1,0) * getv(2,2);
        return D;
    }
#endif // _matrix_class

// Program główny
//---------------

int main()
{

    // Wczytujemy dane dla macierzy

    setlocale(LC_ALL,"");

    cout << "Wpisz dane dla macierzy:" << endl << endl;

    matrix<int> A;

    cout << endl
         << "Wyznacznik macierzy:" << endl
         << "--------------------" << endl << endl;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++) cout << setw(6) << A.getv(i,j);
        cout << endl;
    }

    cout << endl << "det A = " << A.det();

    cout << endl << endl;

    return 0;
}

Jedną z nich jest rozwinięcie Laplace'a. W praktyce się z niego nie korzysta z uwagi na dużą złożoność obliczeniową (O(n!)), jednak dla celów dydaktycznych zaprezentujemy tę metodę. Wykorzystuje ona bezpośrednio definicję wyznacznika ( nic dziwnego, gdyż definicję tę podał właśnie matematyk francuski Pierre Simon de Laplace ):

W metodzie rozwinięcia Laplace'a wyliczamy rekurencyjnie wyznaczniki ( minory ) coraz niższych stopni. Macierze, dla których liczone są te wyznaczniki są podmacierzami macierzy wejściowej, zawierają jej wyrazy, zatem nie ma sensu tworzyć osobnych macierzy i zajmować pamięć, wszystko wykonamy w miejscu na macierzy głównej. Aby zrozumieć naszą metodę, zobaczmy, jak liczony będzie wyznacznik:

Załóżmy, że mamy macierz kwadratową piątego stopnia:

Wiersze i kolumny tej macierzy zostały ponumerowane poczynając od zera, aby zachować zgodność z numeracją wierszy i kolumn w języku C++. Wiersz pierwszy i pierwsza kolumna mają tutaj numer 0. Nic to nie zmienia, a będzie nam później wygodniej przejść do programu.

Wybieramy dowolny z wierszy macierzy. Dla prostoty wybierzemy wiersz pierwszy, czyli wiersz o numerze 0:

W wybranym wierszu przechodzimy kolejno przez poszczególne wyrazy i dla każdego z nich wyznaczamy dopełnienie algebraiczne, które mnożymy przez wyraz i sumujemy iloczyny:

Aby policzyć dopełnienie algebraiczne C₀₀ dla wyrazu a, musimy obliczyć wyznacznik podmacierzy niezawierającej wiersza 0 i kolumny 0, a następnie wyznacznik ten pomnożyć przez (-1)⁰⁺⁰, czyli przez 1:

Przy obliczaniu tego wyznacznika postępujemy identycznie ( rekurencja). Jednak w nowej podmacierzy należy przenumerować kolumny i wiersze, ponieważ jest to osobna macierz:

Wybieramy pierwszy wiersz i jego wyrazy mnożymy kolejno przez ich dopełnienia algebraiczne, sumując iloczyny:

To samo robimy z każdą z podmacierzy 3 × 3: liczymy ich wyznaczniki i używamy je do wyliczenia dopełnień algebraicznych elementów macierzy na wyższym poziomie. Rekurencja kończy się, gdy dojdziemy do podmacierzy jednoelementowych. Wyznacznik macierzy jednoelementowej jest równy wartości jej elementu. Możemy również wykorzystać wzory bezpośrednie na wyznaczniki macierzy drugiego i trzeciego stopnia.

Podstawowym problemem jest sposób wyznaczania elementów podmacierzy. Jak to efektywnie zrobić? Musimy odwzorować numery wierszy i kolumn podmacierzy w zależności od numeru wiersza i kolumny elementu wybierającego tę podmacierz.

Zrobimy to następująco ( nie jest to jedyny sposób ):

Utworzymy tzw. wektor kolumnowy vc, który będzie zawierał numery kolumn, które należą do wybranej podmacierzy. Wektor ten będzie miał tyle elementów, ile wynosi stopień podmacierzy. Dla pierwszego wiersza macierzy głównej wszystkie podmacierze są stopnia 4:

W jaki sposób tworzony jest wektor kolumn? Otóż dla każdego poziomu wektor ten musi być tworzony z wektora poziomu wyższego. Podmacierz nie zawiera kolumny, w której znajduje się wyraz wiersza mnożony przez dopełnienie algebraiczne. Wektor kolumnowy przepisujemy do wektora niższego poziomu z pominięciem numeru kolumny, w której znajduje się wybrany wyraz wiersza. Na przykład przypadek pierwszy ( wyraz wybrany to a ). Wektor kolumnowy wyższego poziomu zawiera wszystkie kolumny macierzy:

Tworzymy wektor kolumnowy vc' podmacierzy dla elementu a. W tym celu przeglądamy kolejne elementy wektora wyższego poziomu z pominięciem elementu o indeksie 0, ponieważ element ten zawiera numer kolumny z elementem a. Przeglądane elementy kopiujemy do wektora kolumnowego podmacierzy:

Dla elementu b pomijamy element wektora vc o indeksie 1 przy tworzeniu wektora kolumnowego vc':

Dla elementu c pomijamy element wektora vc o indeksie 2 przy tworzeniu wektora kolumnowego vc':

Postępowanie to kontynuujemy dla wszystkich wyrazów wiersza 0.

W kolejnych podmacierzach wykonujemy identyczną operację: elementy pierwszego wiersza podmacierzy mnożymy przez ich dopełnienia algebraiczne. Dla przykładu  Rozważmy przypadek trzeci:

Pierwszym wierszem podmacierzy jest wiersz numer 1. Otrzymamy go odejmując od rozmiaru macierzy początkowej rozmiar podmacierzy: 5 - 4 = 1. Kolejne wyrazy tego wiersza ( z wyjątkiem h ) mnożymy przez ich dopełnienia algebraiczne i w ten sposób wyliczamy wyznacznik podmacierzy.  Pod uwagę bierzemy tylko te wyrazy, których numery kolumn mamy w wektorze vc. Tworzymy kolejne podmacierze stopnia 3:

Do wyznaczenia dopełnień algebraicznych potrzebny jest nam jeszcze czynnik (-1)^{i + j}, przez który mnożymy minory. Czynnik ten po prostu przyjmuje kolejne wartości 1, -1, 1, -1, ...

Mamy już wszystkie elementy, aby skonstruować algorytm dla rozwinięcia Laplace'a.

Najpierw przygotowujemy wektor kolumnowy macierzy głównej. Wektor ten ma tyle elementów, ile wynosi stopień tej macierzy. W kolejnych elementach wektora umieszczamy numery kolumn macierzy głównej, czyli: 0, 1, 2, ... . n - 1, gdzie n jest stopniem macierzy.

Gdy wektor kolumnowy jest gotowy, wywołujemy rekurencyjną procedurę obliczania wyznacznika det(). Procedura ta musi mieć dostęp do wektora kolumnowego vc, do stopnia macierzy m, dla której liczy wyznacznik oraz do macierzy głównej A i jej stopnia n.

1. Jeśli m = 1, to jako wynik procedury zwracany jest element A [ n - 1 ][ vc [ 0 ] ], ponieważ macierz składa się tylko z jednego elementu. Rekurencja kończy się.
2. W przeciwnym razie tworzone są zmienne:
   sum i nadawana jest jej wartość 0
   mp i nadawana jej jest wartość 1
   wektor vcp o rozmiarze m - 1
3. Przechodzimy przez kolejne elementy wiersza n - m, których numery kolumn znajdują się w otrzymanym wektorze vc. Elementów tych jest m.
4. Do wektora vcp kopiujemy z vc kolejne numery kolumn z pominięciem numeru kolumny aktualnie wybranego elementu.
5. Wywołujemy rekurencyjnie procedurę det() z parametrami m - 1 jako stopień macierzy i vcp jako wektor kolumnowy.
6. Wynik det() mnożymy przez mp i dodajemy do zmiennej sum.
7. Zmieniamy znak mp na przeciwny.
8. Kontynuujemy pętlę z kroku 3.
9. Usuwamy wektor vcp, jeśli był tworzony dynamicznie.
10. Jako wynik zwracamy zmienną sum.
11. Koniec.

Poniższy program wykorzystuje opisany algorytm do obliczania wyznacznika. Dane wprowadzane są poprzez strumień wejścia. Macierz powinna zawierać liczby całkowite. Pierwsza liczba określa stopień macierzy, pozostałe liczby to jej elementy wprowadzane kolejnymi wierszami.

Macierz:

// Macierze
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Definicja klasy, może być w pliku nagłówkowym
//----------------------------------------------

#ifndef _matrix_class
    #define _matrix_class

    template <class T> class matrix
    {
        private:
            T * A;                   // Wyrazy macierzy
        public:
            int n;                   // Stopień macierzy
            matrix();                // Konstruktor
            ~matrix();               // Destruktor
            T  getv(int r, int c);
            T detr(int * vp, int m); // Wylicza wyznacznik rekurencyjnie
            T det();                 // Inicjuje obliczanie wyznacznika
    };

    // Konstruktor - tworzy macierz ze strumienia cin
    //-----------------------------------------------
    template <class T> matrix<T>::matrix()
    {
        cin >> n;       // Stopień macierzy
        int nn = n * n;
        A = new T [nn]; // Rezerwujemy pamięć na macierz n x n

        for(int i = 0; i < nn; i++) cin >> A[i]; // Wczytujemy wyrazy macierzy
    }

    // Destruktor - usuwa macierz i zwraca zajętą przez nią pamięć
    //------------------------------------------------------------
    template <class T> matrix<T>::~matrix()
    {
        delete [] A;
    }

    // Zwraca wartość elementu
    // r - numer wiersza
    // c - numer kolumny
    //-------------------------
    template <class T> T matrix<T>::getv(int r, int c)
    {
        return A[r * n + c];
    }

    // Oblicza rekurencyjnie wyznacznik macierzy
    // vc - wektor kolumnowy
    // m  - stopień macierzy
    //------------------------------------------
    template <class T> T matrix<T>::detr(int * vc, int m)
    {
       if(m == 1)                   // Macierz jednoelementowa?
       return getv(n - 1, vc[0]);   // Zwracamy wartość elementu
       T sum = 0;
       int mp = 1;
       int * vcp = new int [m - 1]; // Tworzymy wektor kolumnowy dla podmacierzy

       // Przechodzimy przez kolejne wyrazy pierwszego wiersza

       int i,j,k;
       for(i = 0; i < m; i++)
       {
           for(j = k + 0; j < m; j++ )
           {
               if(j == i) j++;   // Pomijamy kolumnę wybranego wyrazu
               vcp[k++] = vc[j]; // Kopiujemy numery kolumn
           }
           // Sumujemy iloczyn wyrazu przez jego dopełnienie algebraiczne
           sum += getv(n - m, vc[i]) * mp * detr(vcp, m - 1);
           mp = -mp;             // Zmieniamy znak mp na przeciwny
       }
       delete [] vcp;            // Usuwamy wektor kolumnowy podmacierzy
       return sum;               // Zwracamy wartość wyznacznika
    }

    // Przygotowuje obliczanie wyznacznika macierzy
    //---------------------------------------------
    template <class T> T matrix<T>::det()
    {
        int * vc = new int[n]; // Tworzymy wektor kolumnowy główny
        for(int i = 0; i < n; i++) vc[i] = i; // Wypełniamy go numerami kolumn
        T result = detr(vc,n); // Obliczamy wyznacznik
        delete [] vc;          // Usuwamy wektor kolumnowy z pamięci
        return result;         // Zwracamy wartość wyznacznika
    }
#endif // _matrix_class

// Program główny
//---------------

int main()
{

    // Wczytujemy dane dla macierzy

    setlocale(LC_ALL,"");

    cout << "Wpisz dane dla macierzy:" << endl << endl;

    matrix<int> A;

    cout << endl
         << "Wyznacznik macierzy metodą rozwinięcia Laplace'a:" << endl
         << "-------------------------------------------------" << endl << endl;
    for(int i = 0; i < A.n; i++)
    {
        for(int j = 0; j < A.n; j++) cout << setw(6) << A.getv(i,j);
        cout << endl;
    }

    cout << endl << "det A = " << A.det();

    cout << endl << endl;

    return 0;
}

Metoda rozwinięcia Laplace'a posiada bardzo niekorzystną złożoność obliczeniową O(n!), co wyklucza ją z praktycznego użycia dla większych macierzy. Następny rozdział opisuje metodę rozkładu LU i jej zastosowanie przy obliczaniu wyznacznika.

Wyznaczniki posiadają wiele ciekawych własności. Niektóre z nich opisujemy poniżej:

Sprawdźmy:

Transpozycja macierzy nie zmienia wartości wyznacznika:

Dzieje się tak dlatego, iż wyznacznik możemy liczyć rozwinięciem Laplace'a względem wiersza lub względem kolumny. Rozwinięcie względem kolumny odpowiada liczeniu wyznacznika rozwinięciem wg wiersza macierzy transponowanej. W obu przypadkach otrzymamy ten sam wynik. Sprawdź to.

Jeśli w macierzy A pomnożymy wyrazy w jednym z wierszy przez stałą c, to wyznacznik tej macierzy również będzie pomnożony przez c. Wynika to bezpośrednio z definicji wyznacznika. Załóżmy, że wiersz i-ty pomnożyliśmy przez c. Wiersz ten zawiera teraz wyrazy:

Jeśli teraz obliczymy wyznacznik przez rozwinięcie Laplace'a wg tego wiersza, to otrzymamy:

To samo dotyczy mnożenia wybranej kolumny macierzy A przez stałą c. Sprawdź to.

Jeśli pomnożymy macierz A przez stałą c, to wyznacznik macierzy wynikowej jest wyznacznikiem macierzy początkowej pomnożonym przez cⁿ, gdzie n jest stopniem macierzy Wynika to bezpośrednio z własności opisanej powyżej ( skoro pomnożenie jednego wiersza/kolumny przez c mnoży wyznacznik przez c, to pomnożenie n wierszy/kolumn przez c pomnoży wyznacznik n razy przez c, czyli przez cⁿ ).

Wyznacznik iloczynu dwóch macierzy jest iloczynem ich wyznaczników:

Jeśli macierz zawiera chociaż jeden wiersz lub kolumnę, które można otrzymać przez dowolną sumę pozostałych wierszy lub kolumn pomnożonych przez stałe, to wyznacznik tej macierzy przyjmuje wartość 0. Mówimy wtedy, iż wiersz lub kolumna są liniową kombinacją pozostałych wierszy/kolumn lub że są liniowo zależne od pozostałych wierszy/kolumn.

Przykłady:

Macierz jednostkowa posiada wyrazy równe zero za wyjątkiem wyrazów na głównej przekątnej, które są równe 1:

Wyznacznik macierzy jednostkowej dowolnego stopnia jest zawsze równy 1:

Macierz trójkątna ( ang. triangular matrix ) jest macierzą, której wyrazy leżące poniżej lub powyżej górnej przekątnej są równe zero, a pozostałe wyrazy są niezerowe. Z tego względu rozróżniamy dwa typy macierzy trójkątnych:

Macierz trójkątna górna ( ang. upper triangular matrix, U ) posiada wyrazy niezerowe na przekątnej głównej oraz powyżej przekątnej głównej:

Macierz trójkątna dolna ( ang. lower triangular matrix, L ) posiada wyrazy niezerowe na przekątnej głównej oraz poniżej przekątnej głównej:

Wyznacznik macierzy trójkątnej dolnej lub górnej jest iloczynem wyrazów leżących na przekątnej głównej.