Dodgson kondens

Inom matematiken är Dodgson-kondensering en metod för att beräkna determinanter . Metoden är uppkallad efter dess skapare , Charles Dodgson (mer känd som Lewis Carroll ). Metoden består i att sänka ordningen på determinanten på ett speciellt sätt till ordning 1, vars enda element är den önskade determinanten.

Allmän metod

Algoritmen kan beskrivas med följande fyra steg:

1. Låt vara en given kvadratisk matris av storlek . Låt oss skriva matrisen på ett sådant sätt att den bara innehåller icke-noll element i den inre delen, det vill säga om . Detta kan till exempel göras genom att lägga till någon annan rad i matrisraden, multiplicerad med något tal. $A$ $n\ gånger n$ $A$ $a_{ij}\neq 0$ $i,j\neq 1,n$

2. Skriv ner en matris av storlek som består av ordning 2 mindre av matrisen . Explicit: $B$ $(n-1)\ gånger (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. Genom att tillämpa steg nr 2 på matrisen skriver vi en storleksmatris , och delar upp motsvarande element i den resulterande matrisen i matrisens interna element : $B$ $C$ $(n-2)\ gånger (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. Låt och . Vi upprepar steg nr 3 tills vi får en matris av ordning 1. Dess enda element kommer att vara den önskade determinanten. $A=B$ $B=C$

Exempel

Inga nollor

Låt det vara nödvändigt att beräkna determinanten

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

Vi sammanställer en matris av minderåriga av ordning 2: $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}}.

Låt oss skapa en matris : $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}}.

Vi erhöll elementen i matrisen genom att dividera elementen i den resulterande matrisen $C$

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

på de inre elementen i matrisen $A$

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

Vi upprepar denna process tills vi får en matris av ordning 1:

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

Vi dividerar med den inre delen av matrisen av storlek , det vill säga med , vi får . $3 gånger 3$ $-5$ ${\begin{bmatrix}-8\end{bmatrix))$

$-åtta$ och är den önskade determinanten för den ursprungliga matrisen.

Med nollor

Låt oss skriva ner de nödvändiga matriserna:

{\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)).

Det finns ett problem. Om vi fortsätter denna process blir det nödvändigt att dividera med 0. Men vi kan ordna om raderna i den ursprungliga matrisen och upprepa processen:

{\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}}\to {\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}}.

Således är determinanten för den ursprungliga matrisen 36.

Dodgson-identiteten och riktigheten av Dodgson-kondenseringen

Dodgsons identitet

Beviset för Dodgson-kondenseringsmetoden är baserat på en identitet som kallas Dodgson-identiteten ( Jacobi- identiteten ).

Låta vara en kvadratisk matris, och för allt betecknar vi matrisen minor , som erhålls genom att ta bort den -th raden och den -th kolumnen. På liknande sätt, för vi betecknar moll, som erhålls från matrisen genom att radera -th och -th rader och -th och -th kolumner. Sedan ${\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$ $sid$ $q$

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

Bevis på Dodgson-identiteten

Bevis på riktigheten av Dodgson-kondenseringen

Litteratur

CL Dodgson. Kondensering av determinanter, att vara en ny och kort metod för att beräkna deras aritmetiska värden // Proceedings of the Royal Society of London. - 1866-1867. - T. 15 . — S. 150–155 .
A. L. En ny metod för beräkning av determinanter // Matematisk utbildning . Andra serien. - 1958. - Utgåva. 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 och Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society , 46 (1999), 637-646.
D. Knuth (1996) Overlapping Pfaffians , Electronic Journal of Combinatorics , 3 , nr. 2.
Mills, William H., Robbins, David P. och Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae , 66 (1982), 73-87.
Mills, William H., Robbins, David P., och Rumsey, Howard, Jr., Alternerande teckenmatriser och descendens plan partitioner, Journal of Combinatorial Theory, Series A , 34 (1983), 340-359.
Robbins, David P., The story of 1, 2, 7, 42, 429, 7436, …, The Mathematical Intelligencer , 13 (1991), 12-19.
Doron Zeilberger, Dodgsons avgörande utvärderingsregel som bevisats av tvåtimmande män och kvinnor. Elec. J Comb. 4 (1997).

Länkar

Weisstein, Eric W. Condensation (engelska) på Wolfram MathWorld- webbplatsen .