Dodgson kondens

I matematik er Dodgson-kondensering en metode til beregning af determinanter . Metoden er opkaldt efter dens skaber , Charles Dodgson (bedre kendt som Lewis Carroll ). Metoden består i at sænke rækkefølgen af determinanten på en særlig måde til rækkefølge 1, hvis eneste element er den ønskede determinant.

Generel metode

Algoritmen kan beskrives ved hjælp af følgende fire trin:

1. Lade være en given kvadratisk matrix af størrelse . Lad os skrive matricen på en sådan måde, at den kun indeholder ikke-nul elementer i den indre del, det vil sige hvis . Dette kan for eksempel gøres ved at tilføje en anden række til matrixrækken, ganget med et eller andet tal. $EN$ $n\ gange n$ $EN$ $a_{ij}\neq 0$ $i,j\neq 1,n$

2. Nedskriv en matrix af størrelse, der består af rækkefølge 2 mindre af matricen . Eksplicit: $B$ $(n-1)\ gange (n-1)$ $EN$

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. Ved at anvende trin nr. 2 til matricen skriver vi en matrix af størrelse , der deler de tilsvarende elementer i den resulterende matrix i interne elementer af matrixen : $B$ $C$ $(n-2)\ gange (n-2)$ $EN$

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. Lad og . Vi gentager trin nr. 3, indtil vi får en matrix af orden 1. Dens eneste element vil være den ønskede determinant. $A=B$ $B=C$

Eksempler

Ingen nuller

Lad det være nødvendigt at beregne determinanten

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

Vi sammensætter en matrix af mindreårige af orden 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}}.

Lad os lave en matrix : $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 opnåede grundstofferne i matrixen ved at dividere elementerne i den resulterende matrix $C$

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

på de indre elementer i matrixen $EN$

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

Vi gentager denne proces, indtil vi får en matrix af orden 1:

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

Vi dividerer med den indre del af matrixen af størrelse , det vil sige med , vi får . $3 gange 3$ $-5$ ${\begin{bmatrix}-8\end{bmatrix))$

$-otte$ og er den ønskede determinant af den oprindelige matrix.

Med nuller

Lad os skrive de nødvendige matricer ned:

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

Der er et problem. Hvis vi fortsætter denne proces, bliver det nødvendigt at dividere med 0. Vi kan dog omarrangere rækkerne i den oprindelige matrix og gentage 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 er determinanten for den oprindelige matrix 36.

Dodgson-identiteten og korrektheden af Dodgson-kondenseringen

Dodgsons identitet

Beviset for Dodgson-kondenseringsmetoden er baseret på en identitet kendt som Dodgson-identiteten ( Jacobi- identiteten ).

Lade være en firkantet matrix, og for alle betegner vi matrixen mindre , som er opnået ved at slette -th række og -th kolonne. På samme måde, for vi betegner minor, som fås fra matrixen ved at slette -th og -th rækker og -th og -th kolonner. Derefter ${\displaystyle A=(m_{i,j})_{i,j=1}^{k))$ $1\leqslant i,j\leqslant k$ ${\displaystyle M_{i}^{j))$ $EN$ $jeg$ $j$ $1\leqslant i,j,p,q\leqslant k$ ${\displaystyle M_{i,j}^{p,q))$ $EN$ $jeg$ $j$ $s$ $q$

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

Bevis for Dodgson-identiteten

Bevis for rigtigheden af Dodgson-kondenseringen

Litteratur

CL Dodgson. Kondensering af determinanter, der er en ny og kort metode til beregning af deres aritmetiske værdier // Proceedings of the Royal Society of London. - 1866-1867. - T. 15 . — S. 150–155 .
A. L. En ny metode til beregning af determinanter // Matematisk uddannelse . Anden serie. - 1958. - Udgave. 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 og Propp, James, Hvordan den alternerende tegnmatrixformodning blev løst, 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. og Rumsey, Howard, Jr., Proof of the Macdonald-formodning, Inventiones Mathematicae , 66 (1982), 73-87.
Mills, William H., Robbins, David P., og Rumsey, Howard, Jr., Alternerende tegnmatricer og nedadgående 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 bestemmende evalueringsregel bevist af to-timing mænd og kvinder. Elec. J Comb. 4 (1997).