Dodgsonova kondenzace

V matematice je Dodgsonova kondenzace metodou pro výpočet determinantů . Metoda je pojmenována po svém tvůrci Charlesi Dodgsonovi (známějším jako Lewis Carroll ). Metoda spočívá ve snížení řádu determinantu speciálním způsobem na řád 1, jehož jediným prvkem je požadovaný determinant.

Obecná metoda

Algoritmus lze popsat pomocí následujících čtyř kroků:

1. Dovolit je daná čtvercová matice velikosti . Matici zapišme tak, aby ve vnitřní části obsahovala pouze nenulové prvky, tedy pokud . To lze provést například tak, že do řádku matice přidáme nějaký další řádek, vynásobený nějakým číslem. $A$ $n\krát n$ $A$ $a_{ij}\neq 0$ $i,j\neq 1,n$

2. Zapište matici velikosti sestávající z řádu 2 minoritních matic matice . Výslovně: $B$ $(n-1)\times (n-1)$ $A$

b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1} \end{vmatrix}},\quad i,j=1\ldots n-1.

3. Aplikováním kroku č. 2 na matici napíšeme matici velikosti , přičemž příslušné prvky výsledné matice rozdělíme na vnitřní prvky matice : $B$ $C$ $(n-2)\times (n-2)$ $A$

c_{i,j}={\dfrac {\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j +1}\end{vmatrix}}{a_{i+1,j+1}}},\quad i,j=1\ldots n-2.

4. Nechte a . Opakujeme krok č. 3, dokud nezískáme matici řádu 1. Jejím jediným prvkem bude požadovaný determinant. $A=B$ $B=C$

Příklady

Žádné nuly

Nechť je třeba vypočítat determinant

{\begin{vmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{vmatrix)).

Sestavíme matici nezletilých 2. řádu: $B$

B={\begin{bmatrix}{\begin{vmatrix}-2&-1\\-1&-2\end{vmatrix}}&{\begin{vmatrix}-1&-1\\-2&-1 \end{vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\[0,5ex]{\begin{vmatrix}-1&-2\\-1&- 1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\ [0,5ex]{\begin{vmatrix}-1&-1\\2&1\end{vmatrix}}&{\begin{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\begin{vmatrix} 2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.

Vytvoříme matici : $C$

{\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\ \[0.5ex]{\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}}.

C={\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}.

Prvky matice jsme získali dělením prvků výsledné matice $C$

{\begin{bmatrix}-16&2\\4&12\end{bmatrix}}

na vnitřní prvky matice $A$

{\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}.

Tento proces opakujeme, dokud nezískáme matici řádu 1:

{\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.

Dělíme vnitřní částí matice velikosti , tedy tím , dostaneme . $3 krát 3$ $-5$ ${\begin{bmatrix}-8\end{bmatrix))$

$-osm$ a je požadovaným determinantem původní matice.

S nulami

Zapišme si potřebné matice:

{\begin{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}}\to {\begin{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\end{bmatrix}}\to {\begin{bmatrix}-30&6&-12\\0&0&6\\6&-6&8\end{bmatrix)).

Vyskytl se problém. Pokud budeme v tomto procesu pokračovat, bude nutné dělení 0. Můžeme však přeskupit řádky původní matice a proces opakovat:

{\begin{bmatrix}1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\\2&-1&2&1&-3\end {bmatrix}}\do {\začátek{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\do {\začátek{ bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\to {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\to {\begin{bmatrix}36\end{ bmatrix}}.

Takže determinant původní matice je 36.

Dodgsonova identita a správnost Dodgsonovy kondenzace

Dodgsonova identita

Důkaz Dodgsonovy kondenzační metody je založen na identitě známé jako Dodgsonova identita ( Jakobiho identita ).

Nechť je čtvercová matice a za všechny označíme matici minor , kterou získáme smazáním -tého řádku a -tého sloupce. Podobně pro označujeme minor, který se získá z matice vymazáním -tého a -tého řádku a -tého a -tého sloupce. Pak ${\displaystyle A=(m_{i,j})_{i,j=1}^{k))$ $1\leqslant i,j\leqslant k$ ${\displaystyle M_{i}^{j))$ $A$ $i$ $j$ $1\leqslant i,j,p,q\leqslant k$ ${\displaystyle M_{i,j}^{p,q))$ $A$ $i$ $j$ $p$ $q$

\det(A)\cdot M_{1,k}^{1,k}=M_{1}^{1}\cdot M_{k}^{k}-M_{1}^{k} \cdot M_{k}^{1}.

Důkaz identity Dodgson

Důkaz správnosti Dodgsonovy kondenzace

Literatura

CL Dodgson. Kondenzace determinantů, která je novou a krátkou metodou pro výpočet jejich aritmetických hodnot // Proceedings of the Royal Society of London. - 1866-1867. - T. 15 . — S. 150–155 .
A. L. Nová metoda pro výpočet determinantů // Matematické vzdělávání . Druhá série. - 1958. - Vydání. 3 . - S. 194 .
David Bressoud, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture , MAA Spectrum, Mathematical Associations of America, Washington, DC, 1999.
David Bressoud a Propp, James, Jak byla vyřešena domněnka matice střídavého znamení, Notices of the American Mathematical Society , 46 (1999), 637-646.
D. Knuth (1996) Overlapping Pfaffians , Electronic Journal of Combinatorics , 3 , no. 2.
Mills, William H., Robbins, David P. a Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae , 66 (1982), 73-87.
Mills, William H., Robbins, David P. a Rumsey, Howard, Jr., Alternativní znakové matice a klesající rovinné oddíly, Journal of Combinatorial Theory, Series A , 34 (1983), 340-359.
Robbins, David P., Příběh 1, 2, 7, 42, 429, 7436, …, The Mathematical Intelligencer , 13 (1991), 12-19.
Doron Zeilberger, Dodgsonovo determinantní hodnotící pravidlo dokázané dvěma muži a ženami. Elec. J Comb. 4 (1997).

Odkazy

Weisstein, Eric W. Condensation (anglicky) na webových stránkách Wolfram MathWorld .