Dodgsonin kondensaatio

Matematiikassa Dodgsonin kondensaatio on menetelmä determinanttien laskemiseen . Menetelmä on nimetty sen luojan Charles Dodgsonin (tunnetaan paremmin nimellä Lewis Carroll ) mukaan. Menetelmässä determinantin järjestystä alennetaan erityisellä tavalla luokkaan 1, jonka ainoa elementti on haluttu determinantti.

Yleinen menetelmä

Algoritmi voidaan kuvata käyttämällä seuraavia neljää vaihetta:

1. Antaa olla annettu neliömatriisi , jonka koko on . Kirjoitetaan matriisi siten, että sen sisäosassa on vain nollasta poikkeavia alkioita, eli jos . Tämä voidaan tehdä esimerkiksi lisäämällä matriisiriville jokin toinen rivi kerrottuna jollain numerolla. $A$ $n\ kertaa n$ $A$ $a_{ij}\neq 0$ ${\näyttötyyli i,j\neq 1,n}$

2. Kirjoita muistiin matriisi , jonka koko koostuu matriisin 2:sta kertaluvusta . Nimenomaan: $B$ ${\näyttötyyli (n-1)\kertaa (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. Soveltamalla vaihetta 2 matriisiin , kirjoitamme kokoisen matriisin jakaen tuloksena olevan matriisin vastaavat elementit matriisin sisäisiksi elementeiksi : $B$ $C$ ${\näyttötyyli (n-2)\kertaa (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. Anna ja . Toistamme vaihetta 3, kunnes saamme kertaluvun 1 matriisin. Sen ainoa elementti on haluttu determinantti. $A=B$ $B=C$

Esimerkkejä

Ei nollia

Olkoon tarpeen laskea determinantti

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

Luomme matriisin alaikäisistä, jotka ovat luokkaa 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}}.

Luodaan matriisi : $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}}.

Saimme matriisin elementit jakamalla tuloksena olevan matriisin elementit $C$

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

matriisin sisäisillä elementeillä $A$

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

Toistamme tätä prosessia, kunnes saamme järjestyksen 1 matriisin:

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

Jaamme koon matriisin sisäosalla , eli , saamme . $3 kertaa 3$ $-5$ ${\begin{bmatrix}-8\end{bmatrix))$

$-kahdeksan$ ja on alkuperäisen matriisin haluttu determinantti.

Nollien kanssa

Kirjataan ylös tarvittavat matriisit:

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

On ongelma. Jos jatkamme tätä prosessia, jakaminen 0:lla on tarpeen. Voimme kuitenkin järjestää alkuperäisen matriisin rivit uudelleen ja toistaa prosessin:

{\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}}\{\alkuun{bmatriisi}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\loppu{bmatrix}}\ja {\alkuun{ 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}}.

Näin ollen alkuperäisen matriisin determinantti on 36.

Dodgsonin identiteetti ja Dodgsonin kondensaation oikeellisuus

Dodgsonin henkilöllisyys

Dodgsonin kondensaatiomenetelmän todiste perustuu identiteettiin, joka tunnetaan nimellä Dodgson-identiteetti ( Jakobi -identiteetti ).

Olkoon neliömatriisi, ja kaikille merkitsemme matriisia molli , joka saadaan poistamalla rivi -:s ja sarake -. Vastaavasti sillä tarkoitamme mollia, joka saadaan matriisista poistamalla -th ja -th rivit sekä -th ja -th sarakkeet. Sitten ${\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$ $s$ $q$

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

Todiste Dodgsonin henkilöllisyydestä

Todiste Dodgsonin kondensaation oikeellisuudesta

Kirjallisuus

CL Dodgson. Determinanttien tiivistyminen, uusi ja lyhyt menetelmä niiden aritmeettisten arvojen laskemiseen // Proceedings of the Royal Society of London. - 1866-1867. - T. 15 . — S. 150–155 .
A. L. Uusi determinanttien laskentamenetelmä // Matemaattinen koulutus . Toinen sarja. - 1958. - Numero. 3 . - S. 194 .
David Bressoud, Todisteet ja vahvistukset: Vaihtelevan merkkimatriisin arvelun tarina , MAA-spektri, Mathematical Associations of America, Washington, DC, 1999.
David Bressoud ja Propp, James, How the alternating sign matrix conjecture was megolded, 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. ja Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae , 66 (1982), 73-87.
Mills, William H., Robbins, David P. ja Rumsey, Howard, Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A , 34 (1983), 340-359.
Robbins, David P., Tarina 1, 2, 7, 42, 429, 7436, …, The Mathematical Intelligencer , 13 (1991), 12-19.
Doron Zeilberger, Dodgsonin määräävä arviointisääntö, jonka kaksi kertaa miehet ja naiset todistavat. Elec. J Comb. 4 (1997).

Linkit

Weisstein, Eric W. Condensation (englanniksi) Wolfram MathWorld -verkkosivustolla .