Wyznacznik macierzy - metoda Chió

[Gouranga]

Metoda Chió
Chió kontra Laplace
Najbardziej rozpowszechnioną metodą liczenia wyznacznika macierzy większych niż \(\displaystyle{ 3 \times 3}\) jest chyba rozwinięcie Laplace'a i to z nim należałoby wstępnie porównać prezentowana tu metodę Chió.
Obie te metody działają rekurencyjnie, co oznacza, że stopniowo będziemy schodzić do coraz mniejszych macierzy. Rozwinięcie Laplace'a może posłużyć do liczenia wyznacznika dowolnie dużej macierzy, metoda Chió posiada jedno zasadnicze ograniczenie - nie można nią liczyć wyznaczników macierzy \(\displaystyle{ 2 \times 2}\) gdyż to obliczenie stanowi w niej rolę operacji elementarnej.
Przy rozwinięciu Laplace'a dla macierzy rozmiaru \(\displaystyle{ n}\) musimy wyznaczyć \(\displaystyle{ n}\) macierzy rozmiaru \(\displaystyle{ n-1}\), następnie z każdej z nich wyznaczyć \(\displaystyle{ n-1}\) macierzy rozmiaru \(\displaystyle{ n-2}\) i tak dalej co wiąże się z koniecznością przechowywania jednocześnie coraz większej ilości liczb co jest kłopotliwe zarówno w komputerze jak i na kartce. W metodzie Chió natomiast najpierw z macierzy rozmiaru \(\displaystyle{ n}\) robimy jedną macierz rozmiaru \(\displaystyle{ n-1}\) i wejściowa macierz nie jest nam już potrzebna, następnie z tak powstałej tworzymy jeszcze mniejszą \(\displaystyle{ n-2 \times n-2}\) i możemy zapomnieć o poprzedniej co jest zdecydowanie wygodniejsze gdy liczymy na papierze i daje większe możliwości na komputerze ponieważ nie wymaga tyle pamięci co rozwinięcie Laplace'a.

Definicja
Macierz \(\displaystyle{ n \times n}\) będziemy redukować do macierzy \(\displaystyle{ n-1 \times n-1}\) a każdy element nowej macierzy będziemy obliczać jako wyznacznik \(\displaystyle{ 2 \times 2}\). Obliczanie takiego wyznacznika stanowi tu rolę operacji elementarnej, można do tego użyć np. metody Sarrusa (liczenia "na krzyż").

\(\displaystyle{ \begin{vmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & \ddots & \vdots \\
a_{n,1} & \ldots & a_{n,n}
\end{vmatrix} = \frac{1}{a_{1,1}^{n-2}} \begin{vmatrix}
\begin{vmatrix}
a_{1,1} & a_{1,2} \\
a_{2,1} & a_{2,2}
\end{vmatrix} & \ldots &
\begin{vmatrix}
a_{1,1} & a_{1,n} \\
a_{2,1} & a_{2,n}
\end{vmatrix} \\
\vdots &
\begin{vmatrix}
a_{1,1} & a_{1,j} \\
a_{i,1} & a_{i,j}
\end{vmatrix} & \vdots \\
\begin{vmatrix}
a_{1,1} & a_{1,2} \\
a_{n,1} & a_{n,2}
\end{vmatrix} & \ldots &
\begin{vmatrix}
a_{1,1} & a_{1,n} \\
a_{n,1} & a_{n,n}
\end{vmatrix}
\end{vmatrix}}\)

Jak widać element \(\displaystyle{ a_{1,1}}\) na żadnym etapie nie może być równy \(\displaystyle{ 0}\). Jeśłi tak się stanie należy zamienić miejscami pierwszy wiersz z innym, w którym w pierwszej kolumnie nie występuje \(\displaystyle{ 0}\).

Przykład
\(\displaystyle{ \begin{vmatrix}
5 & 1 & 1 & 2 & 3\\
4 & 2 & 1 & 7 & 3\\
2 & 1 & 2 & 4 & 7\\
9 & 1 & 0 & 7 & 0\\
1 & 4 & 7 & 2 & 2
\end{vmatrix} = \frac{1}{5^{5-2}}
\begin{vmatrix}
\begin{vmatrix}
5 & 1\\
4 & 2
\end{vmatrix} &
\begin{vmatrix}
5 & 1\\
4 & 1
\end{vmatrix} &
\begin{vmatrix}
5 & 2\\
4 & 7
\end{vmatrix} &
\begin{vmatrix}
5 & 3\\
4 & 3
\end{vmatrix} \\ \\
\begin{vmatrix}
5 & 1\\
2 & 1
\end{vmatrix} &
\begin{vmatrix}
5 & 1\\
2 & 2
\end{vmatrix} &
\begin{vmatrix}
5 & 2\\
2 & 4
\end{vmatrix} &
\begin{vmatrix}
5 & 3\\
2 & 7
\end{vmatrix} \\ \\
\begin{vmatrix}
5 & 1\\
9 & 1
\end{vmatrix} &
\begin{vmatrix}
5 & 1\\
9 & 0
\end{vmatrix} &
\begin{vmatrix}
5 & 2\\
9 & 7
\end{vmatrix} &
\begin{vmatrix}
5 & 3\\
9 & 0
\end{vmatrix} \\ \\
\begin{vmatrix}
5 & 1\\
1 & 4
\end{vmatrix} &
\begin{vmatrix}
5 & 1\\
1 & 7
\end{vmatrix} &
\begin{vmatrix}
5 & 2\\
1 & 2
\end{vmatrix} &
\begin{vmatrix}
5 & 3\\
1 & 2
\end{vmatrix}
\end{vmatrix} = \\=
\frac{1}{5^3}
\begin{vmatrix}
6 & 1 & 27 & 3 \\
3 & 8 & 16 & 29 \\
-4 & -9 & 17 & -27 \\
19 & 34 & 8 &7
\end{vmatrix} =
\frac{1}{5^3} \cdot \frac{1}{6^{4-2}}
\begin{vmatrix}
\begin{vmatrix}
6 & 1\\
3 & 8
\end{vmatrix} &
\begin{vmatrix}
6 & 27\\
3 & 16
\end{vmatrix} &
\begin{vmatrix}
6 & 3\\
3 & 29
\end{vmatrix} \\ \\
\begin{vmatrix}
6 & 1\\
-4 & -9
\end{vmatrix} &
\begin{vmatrix}
6 & 27\\
-4 & 17
\end{vmatrix} &
\begin{vmatrix}
6 & 3\\
-4 & -27
\end{vmatrix} \\ \\
\begin{vmatrix}
6 & 1\\
19 & 34
\end{vmatrix} &
\begin{vmatrix}
6 & 27\\
19 & 8
\end{vmatrix} &
\begin{vmatrix}
6 & 3\\
19 & 7
\end{vmatrix}
\end{vmatrix} =
\frac{1}{5^3 \cdot 6^2}
\begin{vmatrix}
45 & 15 & 165\\
-50 & 210 & -150\\
185 & -465 & -15
\end{vmatrix} = \\=
\frac{1}{5^3 \cdot 6^2 \cdot 45}
\begin{vmatrix}
\begin{vmatrix}
45 & 15\\
-50 & 210
\end{vmatrix} &
\begin{vmatrix}
45 & 165\\
-50 & -150
\end{vmatrix} \\ \\
\begin{vmatrix}
45 & 15\\
185 & -465
\end{vmatrix} &
\begin{vmatrix}
45 & 165\\
185 & -15
\end{vmatrix}
\end{vmatrix} = \frac{1}{125 \cdot 36 \cdot 45}
\begin{vmatrix}
10200 & 1500 \\
-23700 & -31200
\end{vmatrix} = \frac{10200 \cdot (-31200) - 1500 \cdot (-23700)}{125 \cdot 36 \cdot 45} =\\=
\frac{-318240000 + 35550000}{202500} = \frac{-282690000}{202500} = -1396}\)

Podsumowanie
Jak widać na przykładzie, na końcu dochodzimy do działań na dużych liczbach jednak ręczne liczenie wyznacznika tą metodą to kwestia wprawy. Przykład jest sprawdzony na każdym etapie z programem liczącym wyznaczniki i nie ma w nim błędów. Jeśli kogoś urządza ograniczenie ilości rzeczy, jakie trzeba na raz zapisywać kosztem działań na dużych liczbach to myślę, że ta metoda powinna mu się spodobać.

[jarek4700]

Zdaje się że to ma nawet złożoność rzędu \(\displaystyle{ O(n^{3})}\), przy czym Laplace ma znacznie gorszą \(\displaystyle{ O(n!)}\) liczoną względem potrzebnych obliczeń wyznaczników \(\displaystyle{ 2 \times 2}\)

[Gouranga]

jarek4700, no mniej więcej, bo samych wyznaczników \(\displaystyle{ 2 \times 2}\) będzie \(\displaystyle{ n^2}\), potem \(\displaystyle{ (n-1)^2}\) itd. a tych kroków nadrzędnych (zmniejszeń macierzy) jest \(\displaystyle{ n}\) czyli wychodzi około \(\displaystyle{ n^3}\)