Dodgson kondenzáció

A matematikában a Dodgson-kondenzáció a determinánsok kiszámításának módszere . A módszer nevét megalkotójáról , Charles Dodgsonról (ismertebb nevén Lewis Carrollról ) kapta. A módszer abból áll, hogy a determináns sorrendjét speciális módon csökkentjük az 1-es sorrendre, amelynek egyetlen eleme a kívánt determináns.

Általános módszer

Az algoritmus a következő négy lépéssel írható le:

1. Legyen adott méretű négyzetmátrix . Írjuk fel a mátrixot úgy, hogy a belső részben csak nem nulla elemeket tartalmazzon, vagyis ha . Ezt megtehetjük például úgy, hogy a mátrixsorhoz hozzáadunk egy másik sort, megszorozva valamilyen számmal. $A$ $n\szer n$ $A$ $a_{ij}\neq 0$ $i,j\neq 1,n$

2. Írjon fel egy méretű mátrixot, amely a mátrix 2-es rendszámából áll . Kifejezetten: $B$ ${\megjelenítési stílus (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. A 2. lépést alkalmazva a mátrixra egy méretű mátrixot írunk , a kapott mátrix megfelelő elemeit a mátrix belső elemeire osztva : $B$ $C$ ${\megjelenítési stílus (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{vmátrix}}{a_{i+1,j+1}}},\quad i,j=1\ldots n-2.

4. Legyen és . Addig ismételjük a 3. lépést, amíg egy 1. rendű mátrixot nem kapunk. Ennek egyetlen eleme a kívánt determináns lesz. $A=B$ $B=C$

Példák

Nincs nulla

Legyen szükséges a determináns kiszámítása

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

Összeállítunk egy mátrixot a 2. rendű kiskorúakból: $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{bmátrix}}.

Hozzunk létre egy mátrixot : $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{bmátrix}}.

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

A mátrix elemeit a kapott mátrix elemeinek elosztásával kaptuk meg $C$

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

a mátrix belső elemein $A$

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

Ezt a folyamatot addig ismételjük, amíg egy 1-es sorrendű mátrixot nem kapunk:

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

A méretű mátrix belső részével osztunk , azaz -vel, megkapjuk . $3 alkalommal 3$ $-5$ ${\begin{bmatrix}-8\end{bmatrix))$

$-nyolc$ és az eredeti mátrix kívánt meghatározója.

Nullákkal

Írjuk fel a szükséges mátrixokat:

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

Van egy probléma. Ha ezt a folyamatot folytatjuk, akkor 0-val való osztás válik szükségessé, de átrendezhetjük az eredeti mátrix sorait és megismételhetjük a folyamatot:

{\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 {bmátrix}}\a {\begin{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\to {\begin{ 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}}.

Így az eredeti mátrix determinánsa 36.

A Dodgson-azonosság és a Dodgson-sűrítés helyessége

Dodgson személyazonossága

A Dodgson-féle kondenzációs módszer bizonyítása a Dodgson-identitás (a Jacobi -identitás ) néven ismert azonosságon alapul.

Legyen négyzetes mátrix, és mindenre a mátrix minort jelöljük , amelyet a -edik sor és -edik oszlop törlésével kapunk. Ugyanígy jelöljük ugyanis a minort, amelyet a -edik és -edik sor, valamint a -edik és -edik oszlop törlésével kapunk meg a mátrixból . Akkor $A=(m_{i,j})_{i,j=1}^{k}$ $1\leqslant i,j\leqslant k$ ${\displaystyle M_{i}^{j))$ $A$ $én$ $j$ $1\leqslant i,j,p,q\leqslant k$ ${\displaystyle M_{i,j}^{p,q))$ $A$ $én$ $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}.

A Dodgson-azonosság igazolása

A Dodgson-kondenzáció helyességének bizonyítéka

Irodalom

CL Dodgson. A determinánsok sűrítése, új és rövid módszer az aritmetikai értékek kiszámítására // A Londoni Királyi Társaság közleménye. - 1866-1867. - T. 15 . – S. 150–155 .
A. L. Új módszer a determinánsok kiszámítására // Matematikai oktatás . Második sorozat. - 1958. - Kiadás. 3 . - S. 194 .
David Bressoud, Bizonyítások és megerősítések: A váltakozó jelmátrix sejtés története , MAA Spectrum, Mathematical Associations of America, Washington, DC, 1999.
David Bressoud és Propp, James: Hogyan oldották meg a váltakozó jelmátrix sejtést, 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. és Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae , 66 (1982), 73-87.
Mills, William H., Robbins, David P. és Rumsey, Howard, Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A , 34 (1983), 340-359.
Robbins, David P.: Az 1., 2., 7., 42., 429., 7436., … története, The Mathematical Intelligencer , 13 (1991), 12-19.
Doron Zeilberger, Dodgson meghatározó értékelési szabálya, amelyet a férfiak és a nők kétszeresen igazoltak. Elec. J Comb. 4 (1997).

Linkek

Weisstein, Eric W. Condensation (angol) a Wolfram MathWorld webhelyén .