Słynna anegdota z XIX wieku mówi, że królowa Wiktoria była tak zachwycona powieścią Alicja w Krainie Czarów, że po lekturze natychmiast poprosiła o przesłanie jej pozostałych dzieł Lewisa Carrolla. Wkrótce w ręce monarchini trafiła matematyczna pozycja An Elementary Theory of Determinants niejakiego Charlesa Dodgsona – gdyż tak brzmi prawdziwe nazwisko autora przygód Alicji. W jednym z dodatków do podręcznika znajduje się opis metody obliczania wyznaczników, znanej obecnie jako kondensacja Dodgsona. Oczywiście nas, matematyków, od reakcji królowej dużo bardziej interesuje, na czym polega wspomniana metoda?
– Hm – rzekł Gołąb z powagą – najlepiej wytłumaczę ci to praktycznie.
‘Why,’ said the Dodo, ‘the best way to explain it is to do it.’ – cytat z Alicji w Krainie Czarów w przekładzie Antoniego Marianowicza.
Aby wykonać kondensację Dodgsona, wystarczy umieć liczyć wyznaczniki macierzy \(2\times2.\) Oczywiście wyznacznikiem macierzy \(\left[\begin{smallmatrix}a&b\\c&d \end{smallmatrix}\right]\) jest \(\left|\begin{smallmatrix}a&b\\c&d \end{smallmatrix}\right|= {ad-bc}.\) Rozważmy następującą macierz: \[\displaystyle M_4=\left[\def\arraystretch{1}\begin{array}{r@{\ \ \ }r@{\ \ \ }r@{\ \ \ }r}1&3&1&-4\\5&1&2&4\\1&1&1&1\\1&5&3&-3\end{array}\right].\] Przyjmijmy, że wnętrzem \(M_4\) jest macierz \(% \left[% \begin{smallmatrix} \textcolor{magenta}1&\textcolor{magenta}2\\\textcolor{magenta}1&\textcolor{magenta}1% \end{smallmatrix} \right] ,\) która powstała przez usunięcie pierwszego i ostatniego wiersza oraz pierwszej i ostatniej kolumny.
Następnie dla macierzy \(M_4\) obliczamy wyznaczniki każdej podmacierzy \(2\times2\) złożonej z elementów sąsiednich wierszy i kolumn i tworzymy z nich macierz \(M_3\) (\(3\times3\)), układając je w kolejności indukowanej przez macierz \(M_4.\) Mamy zatem \[M_3=\left[\def\arraystretch{1}\begin{array}{ccc} \rule{0pt}{4ex} \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}1&3\\5&1\end{array}\right| & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}3&1\\1&2\end{array}\right| & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}1&-4\\2&4\end{array}\right| \\ \rule{0pt}{4ex} \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}5&1\\1&1\end{array}\right| & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}1&2\\1&1\end{array}\right| & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}2&4\\1&1\end{array}\right| \\ \rule{0pt}{4ex} \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}1&1\\1&5\end{array}\right| & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}1&1\\5&3\end{array}\right| & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}1&1\\3&-3\end{array}\right| \end{array}\right]= \left[\def\arraystretch{1}\begin{array}{ccc}-14&5&12\\4&-1&-2\\4&-2&-6\end{array}\right].\] Podobnie jak wyżej, określamy wnętrze macierzy \(M_3,\) czyli macierz \(W_1=[\textcolor{orange}{-1}].\)
Na podstawie macierzy \(M_3\) tworzymy analogicznie macierz \(M_2,\) ale tym razem oprócz obliczania wyznaczników wykonujemy również dzielenie ich przez odpowiadające im elementy macierzy \(W_2\): \[M_2=\left[\def\arraystretch{1}\begin{array}{r@{\ \ \ }r@{\ \ \ }r@{\ \ \ }r} \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}-14&5\\4&-1\end{array}\right|/\textcolor{magenta}1 & & & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}5&12\\-1&-2\end{array}\right|/\textcolor{magenta}2 \\ \rule{0pt}{5ex} \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}4&-1\\4&-2\end{array}\right|/\textcolor{magenta}1 & & & \left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}-1&-2\\-2&-6\end{array}\right|/\textcolor{magenta}1 \end{array}\right]=\left[\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}-6&1\\-4&2\end{array}\right].\] W ostatnim kroku obliczamy macierz \(M_1,\) która składa się wyłącznie z wyznacznika macierzy \(M_2\) podzielonego przez jedyny element macierzy \(W_1\): \[M_1=\left[\left|\def\arraystretch{1}\begin{array}{r@{\ \ \ }r}-6&1\\-4&2\end{array}\right|/(\textcolor{orange}{-1})\right]=[8].\] Liczba \(8\) (jedyny element macierzy \(M_1\)) jest szukanym wyznacznikiem macierzy \(M_4.\)
Jak można wywnioskować z przedstawionego przykładu, pojedynczy krok kondensacji Dodgsona polega na otrzymywaniu macierzy o jeden wymiar mniejszej poprzez obliczenie odpowiednich wyznaczników \(2\times2\) i dzieleniu ich przez odpowiednie elementy wnętrza mającego ten sam wymiar (o ile takie wnętrze zostało wyznaczone, czyli dzielenia zaczynamy wykonywać dopiero w drugim kroku). Kiedy już otrzymamy macierz \(1\times 1,\) jej jedyny wyraz to wyznacznik wyjściowej macierzy.
Metoda jest zatem relatywnie prosta – sprowadza się do redukcji wymiaru macierzy poprzez obliczanie wyznaczników \(2\times2.\) Dlaczego zatem nie jest ona powszechnie omawiana na podstawowym kursie algebry liniowej? Czytelnik Wnikliwy na pewno dostrzegł już jej fatalną wadę, którą jest wielokrotne dzielenie. Za każdym razem dzielnik (element odpowiedniej macierzy) musi być różny od \(0.\) Wynika stąd, że nie dla każdej macierzy da się wykonać kondensację Dodgsona (przykładowo macierz \(3\times3\) podlega kondensacji tylko wtedy, gdy jej środkowy element jest niezerowy).
Czytelnikowi Ambitnemu polecamy sprawdzenie, że koszt obliczeniowy metody Dodgsona to \(O(n^3)\) (\(n\) jest wymiarem macierzy), jak również to, że jeśli wystartujemy od macierzy o wyrazach całkowitych, to wszystkie uzyskiwane po drodze macierze również będą miały (pomimo występującego dzielenia) wyrazy całkowite.
Wedle relacji samego Dodgsona urocza anegdotka o królowej Wiktorii nie jest prawdziwa. Pisarz-matematyk, żyjący w epoce Marka Twaina, najwyraźniej zignorował przestrogę kolegi po literackim fachu: Never let the truth get in the way of a good story.