Kondensacja Dodgsona

W matematyce kondensacja Dodgsona lub metoda kontraktantów to metoda obliczania wyznaczników macierzy kwadratowych . Został nazwany na cześć swojego wynalazcy, Charlesa Lutwidge'a Dodgsona (lepiej znanego pod pseudonimem, jako Lewis Carroll, popularny autor). Metoda w przypadku n × n polega na skonstruowaniu macierzy ( n - 1) × ( n - 1), macierzy ( n - 2) × ( n - 2) i tak dalej, kończąc na 1 × 1 macierz, która ma jeden wpis, wyznacznik oryginalnej macierzy.

Metoda ogólna

Algorytm ten można opisać w następujących czterech krokach:

Niech A będzie daną macierzą n × n . Ułóż A tak, aby w jego wnętrzu nie było zer. Wyraźną definicją wnętrza byłoby wszystko za $n}$ _, ≠ . Można to zrobić za pomocą dowolnej operacji, którą można normalnie wykonać bez zmiany wartości wyznacznika, takiej jak dodanie wielokrotności jednego wiersza do drugiego.
Utwórz ( n − 1) × ( n − 1) macierz B, składającą się z wyznaczników każdej podmacierzy 2 × 2 A. Jawnie piszemy ${\ Displaystyle b_ {i, j} = {\ rozpocząć {vmatrix} a_ {i, j} i a_ {i, j + 1} \\ a_ {i + 1, j} i a_ {i + 1, j + 1} \end{vmatrix}}.}$
Używając tej macierzy ( n - 1) × ( n - 1), wykonaj krok 2, aby otrzymać macierz C ( n - 2) × ( n - 2) . Podziel każdy wyraz w C przez odpowiadający mu wyraz we wnętrzu A tak ${\ Displaystyle c_ {i, j} = {\ zacząć {vmatrix} b_ {i, j} i b_ {i, j + 1} \\ b_ {i + 1, j} i b_ {i+1,j+1}\end{vmatrix}}/a_{i+1,j+1}}$ .
Niech A = B i B = C. W razie potrzeby powtórz krok 3, aż zostanie znaleziona macierz 1 × 1; jego jedynym wpisem jest wyznacznik.

Przykłady

Bez zer

Chciałoby się znaleźć

{\ Displaystyle {\ rozpocząć {vmatrix} -2 i -1 i -1 i -4 \\ -1 i -2 i -1 i -6 \\ -1 i -1 i 2 i 4 \\ 2 i 1 i -3 i -8 \ koniec {vmatrix}}.}

Wszystkie elementy wnętrza są niezerowe, więc nie ma potrzeby ponownego układania macierzy.

Tworzymy macierz jej podmacierzy 2 × 2.

{\ Displaystyle {\ rozpocząć {bmatrix} {\ rozpocząć {vmatrix} -2 i -1 \\ -1 i -2 \ koniec {vmatrix}} i {\ rozpocząć {vmatrix} -1 i -1 \\ -2 i -1 \ koniec {vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\\\{\begin{vmatrix}-1&-2\\-1&-1\end{ vmatrix}}&{\początek{vmatrix}-2&-1\\-1&2\koniec{vmatrix}}&{\rozpoczęcie{vmatrix}-1&-6\\2&4\koniec{vmatrix}}\\\\{\ zacznij{vmatrix}-1&-1\\2&1\koniec{vmatrix}}&{\zacznij{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\rozpocznij{vmatrix}2&4\\-3&- 8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.}

Następnie znajdujemy kolejną macierz wyznaczników:

{\ Displaystyle {\ rozpocząć {bmatrix} {\ rozpocząć {vmatrix} 3 i -1 \\ -1 i -5 \ koniec {vmatrix}} i {\ rozpocząć {vmatrix} -1 i 2 \\ - 5 i 8 \ koniec {vmatrix}} \ \\\{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}\end{bmatrix}}={ \begin{bmatrix}-16&2\\4&12\end{bmatrix}}.}

Następnie musimy podzielić każdy element przez odpowiedni element naszej oryginalnej macierzy. Wnętrze oryginalnej macierzy to ${\ Displaystyle {\ rozpocząć {bmatrix} -2 i -1 \\ -1 i 2 \ koniec {bmatrix}}}$ , więc po podzieleniu otrzymujemy ${\ Displaystyle {\ rozpocząć {bmatrix} 8 i -2 \\ -4 i 6 \ koniec {bmatrix}}}$ . Proces należy powtórzyć, aby uzyskać macierz 1 × 1. ${\ Displaystyle {\ rozpocząć {bmatrix} {\ rozpocząć {vmatrix} 8 i -2 \\ -4 i 6 \ koniec {vmatrix}} \ koniec {bmatrix}} = {\ rozpocząć {bmatrix} 40 \ koniec {bmatrix}}.}$ Dzielenie przez wnętrze macierzy 3 × 3, która wynosi po prostu -5, daje ${\ Displaystyle {\ rozpocząć {bmatrix} -8 \ koniec {bmatrix}}}$ i -8 jest rzeczywiście wyznacznikiem oryginału matryca.

Z zerami

Po prostu wypisując macierze:

{\ Displaystyle {\ zacząć {bmatrix} 2&-1&2&1&-3\\1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\end {bmatrix}}\do {\początek{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\koniec{bmatrix}}\do {\rozpocząć{bmacierz}-15&6&12\\0&0&6\\6&-6&8\koniec{bmacierz}}.}

Tutaj wpadamy w kłopoty. Jeśli będziemy kontynuować proces, w końcu będziemy dzielić przez 0. Możemy wykonać cztery zamiany wierszy na początkowej macierzy, aby zachować wyznacznik i powtórzyć proces, z większością wyznaczników wstępnie obliczonych:

{\ Displaystyle {\ rozpocząć {bmatrix} 1 i 2 i 1 i -1 i 2 \\ 1 i -1 i -2 i -1 i -1 \\2 i 1 i -1 i -2 i -1 \\1 i -2 i -1 i -1 i 2 \\ 2 i -1 i 2 i 1 i -3 \ koniec {bmatrix}}\do {\początek{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\koniec{bmatrix}}\do {\rozpoczęcie{ bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\do {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\do {\begin{bmatrix}36\end{ bmacierz}}.}

W ten sposób dochodzimy do wyznacznika 36.

Tożsamość Desnanota-Jacobiego i dowód poprawności algorytmu kondensacji

Dowód, że metoda kondensacji oblicza wyznacznik macierzy, jeśli nie napotkano żadnych podziałów przez zero, opiera się na tożsamości znanej jako tożsamość Desnanota -Jacobiego (1841) lub, bardziej ogólnie, tożsamość wyznacznika Sylvestra (1851).

Niech ${\ Displaystyle M = (m_ {i, j}) _ {i, j = 1} ^ {k}}$ będzie macierzą kwadratową i dla każdego ${\ Displaystyle 1 \ równoważnik ja, j \ równoważnik k}$ , oznacz przez ${\ Displaystyle M_ {i} ^ {j}}$ macierz wynikającą z ${\ Displaystyle M_ {i} ^ {j}}$ przez usunięcie M ja jot ja ${\ displaystyle i}$ wiersz $-ta$ kolumna. Podobnie $q}}$ $_$ przez $_ ^ {p$ $,$ macierz wynikająca z usunięcia $-th$ wierszy oraz ${\ displaystyle p} -th i$ ${\ displaystyle p$ } ${\ Displaystyle q}$ -te kolumny.

Tożsamość Desnanota-Jacobiego

{\ Displaystyle \ det (M) \ det (M_ {1, k} ^ {1, k}) = \ det (M_ {1} ^ {1}) \ det (M_ {k} ^ {k}) - \det(M_{1}^{k})\det(M_{k}^{1}).}

Dowód poprawności kondensacji Dodgsona

Przepisz tożsamość jako

{\ Displaystyle \ det (M) = {\ Frac {\ det (M_ {1} ^ {1}) \ det (M_ {k} ^ {k}) - \ det (M_ {1} ^ {k}) \det(M_{k}^{1})}{\det(M_{1,k}^{1,k})}}.}

Zauważmy teraz, że z indukcji wynika, że przy zastosowaniu procedury kondensacji Dodgsona do macierzy kwadratowej $rzędu$ $n}$ $displaystyle$ macierz na etapie obliczeń ( gdzie pierwszy etap odpowiada samej macierzy , składa się ze wszystkich połączonych drugorzędnych rzędu k ${\ displaystyle$ $k$ $}$ z ${\ displaystyle A}$ , gdzie k = 1 $jest$ wyznacznikiem połączonego podbloku sąsiednich wpisów $displaystyle A$ } W szczególności na ostatnim etapie otrzymuje się macierz zawierającą pojedynczy element równy unikalnemu połączonemu drugorzędnemu rzędu $wyznacznikowi$ $displaystyle$ ZA $A }$ .

Dowód tożsamości Desnanot-Jacobi

Śledzimy leczenie w książce Bressouda; alternatywny dowód kombinatoryczny można znaleźć w artykule Zeilbergera. oznaczamy ${\ Displaystyle a_ {i, j} = (-1) ^ {i + j} \ det (M_ {i} ^ {j} )}$ (aż do znaku, $Displaystyle k \ razy k$ minor z ${\ Displaystyle M}$ $i$ zdefiniuj ${\ displaystyle M'}$ } wg

{\ Displaystyle M' = {\ rozpocząć {pmatrix} a_ {1,1}&0&0&0&\ldots &0&a_ {k,1}\\a_{1,2}&1&0&0&\ldots &0&a_ {k,2}\\a_ {1, 3}&0&1&0&\ldots &0&a_{k,3}\\a_{1,4}&0&0&1&\ldots &0&a_{k,4}\\\vdots &\vdots &\vdots &\vdots &&\vdots &\vdots \\a_ {1,k-1}&0&0&0&\ldokropki &1&a_{k,k-1}\\a_{1,k}&0&0&0&\ldokropki &0&a_{k,k}\end{pmacierz}}.}

$displaystyle A}$ Zauważ, że pierwsza i ostatnia kolumna są równe kolumnom macierzy wspomagającej M $\$ ). Tożsamość jest teraz uzyskiwana przez obliczenie ${\ Displaystyle \ det (MM')}$ na dwa sposoby. Po pierwsze, możemy bezpośrednio obliczyć iloczyn macierzowy $($ prostych właściwości macierzy pomocniczej lub alternatywnie używając wzoru na rozwinięcie wyznacznika macierzy pod względem wiersza lub kolumny), Na

{\ Displaystyle MM' = {\ rozpocząć {pmatrix} \ det (M) & m_ {1,2} & m_ {1,3} i \ ldots & m_ {1, k-1} i 0 \\ 0 & m_ {2,2} &m_{2,3}&\ldots &m_{2,k-1}&0\\0&m_{3,2}&m_{3,3}&\ldots &m_{3,k-1}&0\\\vdots &\ vdots &\vdots &&\vdots &\vdots &\vdots \\0&m_{k-1,2}&m_{k-1,3}&\ldots &m_{k-1,k-1}&0\\0&m_{k ,2}&m_{k,3}&\ldkropki &m_{k,k-1}&\det(M)\end{pmacierz}}}

$i$ używamy do oznaczenia $, j$ wpisu \ $displaystyle m_$ Wyznacznikiem tej macierzy jest ${\ Displaystyle \ det (M) ^ {2} \ cdot \ det (M_ {1, k} ^ {1, k })}$ . Po drugie, jest to równe iloczynowi wyznaczników, ${\ Displaystyle \ det (M) \ cdot \ det (M ')}$ . Ale wyraźnie $\ Displaystyle \ det (M ') = a_ {1,1} a_ {k, k} -a_ {k, 1} a_ {1, k} = \ det (M_ {1} ^ {1}) \det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}),} więc tożsamość wynika ze zrównania dwóch otrzymanych$ wyrażeń dla ${\ Displaystyle \ det (MM')}$ i dzieleniu przez ${\ Displaystyle \ det (M)}$ (jest to dozwolone, jeśli myśli się o tożsamościach jako o tożsamościach wielomianowych na pierścieniu wielomianów w zmiennych nieokreślonych ${i, j}) _ {i, j = 1}$ $jot$ ).

Notatki

Referencje i dalsze czytanie

Bressoud, David M. , Dowody i potwierdzenia: historia hipotetycznej macierzy znaków alternatywnych , MAA Spectrum, Mathematical Associations of America, Washington, DC, 1999.
Bressoud, David M. and Propp, James, Jak rozwiązano hipotezę macierzy znaków przemiennych , Zawiadomienia Amerykańskiego Towarzystwa Matematycznego , 46 (1999), 637-646.
Dodgson, CL (1866–1867). „Kondensacja wyznaczników, będąca nową i krótką metodą obliczania ich wartości arytmetycznych” (PDF) . Postępowanie Royal Society of London . 15 : 150–155.
Knuth, Donald , Overlapping Pfaffians , Electronic Journal of Combinatorics , 3 no. 2 (1996).
Lotkin, Mark (1959). „Uwaga dotycząca metody kontrahentów”. Amerykański miesięcznik matematyczny . 66 (6): 476–479. doi : 10.2307/2310629 . JSTOR 2310629 .
Mills, William H., Robbins, David P. i Rumsey, Howard, Jr., Dowód hipotezy Macdonalda, Inventiones Mathematicae , 66 (1982), 73-87.
Mills, William H., Robbins, David P. i Rumsey, Howard, Jr., Alternating sign matrixes and maleing plane partitions, Journal of Combinatorial Theory , Seria A , 34 (1983), 340-359.
$P.$ Historia Intelligencer ) _ 19.
Zeilberger, Doron , determinantowa reguła oceny Dodgsona udowodniona przez dwóch mężczyzn i kobiety , Electronic Journal of Combinatorics , 4 no. 2 (1997).

Linki zewnętrzne

Weisstein, Eric W. „Kondensacja Dodgsona” . MathWorld .