Dodgsonova kondenzace - Dodgson condensation - Wikipedia

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Ledna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, Dodgsonova kondenzace nebo metoda smluvních partnerů je metoda výpočtu determinanty z čtvercové matice. Je pojmenován podle svého vynálezce, Charles Lutwidge Dodgson (známější pod pseudonymem, jako populární autor Lewis Carroll). Metoda v případě n × n matice je postavit (n − 1) × (n - 1) matice, (n − 2) × (n - 2) atd. A končí maticí 1 × 1, která má jednu položku, determinant původní matice.

Obecná metoda

Tento algoritmus lze popsat v následujících čtyřech krocích:

1. Nechť A je dané n × n matice. Uspořádejte A tak, aby se v jeho vnitřku nevyskytovaly nuly. Explicitní definice interiéru by byla vše a_{já, j} s ${ displaystyle i, j neq 1, n}$. Lze to udělat pomocí jakékoli operace, kterou by člověk mohl normálně provést, aniž by změnil hodnotu determinantu, jako je přidání násobku jednoho řádku do druhého.
2. Vytvořte (n − 1) × (n - 1) matice B, skládající se z determinantů každé 2 × 2 submatice A. Explicitně píšeme ${ displaystyle b_ {i, j} = { begin {vmatrix} a_ {i, j} & a_ {i, j + 1} a_ {i + 1, j} & a_ {i + 1, j + 1} end {vmatrix}}.}$
3. Pomocí tohoto (n − 1) × (n - 1) matice, proveďte krok 2 a získejte (n − 2) × (n - 2) matice C. Rozdělte každý člen v C odpovídajícím členem uvnitř A tak ${ displaystyle c_ {i, j} = { 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}}$.
4. Nechť A = B a B = C. Opakujte krok 3 podle potřeby, dokud nenajdete matici 1 × 1; jeho jediný záznam je určující.

Příklady

Bez nul

Jeden si přeje najít

${ displaystyle { begin {vmatrix} -2 & -1 & -1 & -4 - 1 & -2 & -1 & -6 - 1 & -1 & 2 & 4 2 & 1 & -3 & -8 end {vmatrix}}.}$

Všechny prvky interiéru jsou nenulové, takže není nutné matici znovu uspořádat.

Vytvoříme matici z jejích 2 × 2 submatric.

${ displaystyle { 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}} { begin {vmatrix} -1 & -2 - 1 & -1 end { vmatrix}} & { begin {vmatrix} -2 & -1 - 1 & 2 end {vmatrix}} & { begin {vmatrix} -1 & -6 2 & 4 end {vmatrix}} { začátek {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}}.}$

Poté najdeme další matici determinantů:

${ displaystyle { begin {bmatrix} { begin {vmatrix} 3 & -1 - 1 & -5 end {vmatrix}} & { begin {vmatrix} -1 & 2 - 5 & 8 end {vmatrix}} { 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}}.}$

Potom musíme každý prvek rozdělit na odpovídající prvek naší původní matice. Vnitřek původní matice je${ displaystyle { begin {bmatrix} -2 & -1 - 1 & 2 end {bmatrix}}}$, takže po rozdělení dostaneme${ displaystyle { begin {bmatrix} 8 & -2 - 4 & 6 end {bmatrix}}}$.Pro dosažení matice 1 × 1 je nutné postup opakovat.${ displaystyle { begin {bmatrix} { begin {vmatrix} 8 & -2 - 4 & 6 end {vmatrix}} end {bmatrix}} = { begin {bmatrix} 40 end {bmatrix}}.}$Dělení vnitřkem matice 3 × 3, což je jen −5, dává ${ displaystyle { begin {bmatrix} -8 end {bmatrix}}}$ a −8 je skutečně determinant původní matice.

S nulami

Jednoduše vypisujte matice:

${ displaystyle { 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} -15 & 6 & 12 0 & 0 & 6 6 & -6 & 8 end {bmatrix}}.}$

Tady narazíme na potíže. Pokud budeme pokračovat v procesu, nakonec ho vydělíme 0. Můžeme provést čtyři řádkové výměny na počáteční matici, abychom zachovali determinant a proces opakovali, přičemž většina determinantů byla předem vypočítána:

${ displaystyle { 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 konec {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 a 0 & 6 6 & -6 & 8 - 17 & 8 & -4 end {bmatrix}} to { begin {bmatrix} 0 a 12 18 & 40 end {bmatrix}} to { begin {bmatrix} 36 end { bmatrix}}.}$

Proto jsme dospěli k determinantu 36.

Desnanot – Jacobiho identita a důkaz správnosti kondenzačního algoritmu

Důkaz, že kondenzační metoda počítá determinant matice, pokud nedojde k žádnému dělení nulou, je založen na identitě známé jako Desnanot – Jacobi identita (1841) nebo, obecněji, Identita determinanta Sylvester (1851).^[1]

Nechat ${ displaystyle M = (m_ {i, j}) _ {i, j = 1} ^ {k}}$ být čtvercová matice a pro každou ${ displaystyle 1 leq i, j leq k}$, označují ${ displaystyle M_ {i} ^ {j}}$ matice, která je výsledkem ${ displaystyle M}$ odstraněním ${ displaystyle i}$-tá řada a ${ displaystyle j}$-tý sloupec. Podobně pro${ Displaystyle 1 leq já, j, p, q leq k}$, označují ${ displaystyle M_ {i, j} ^ {p, q}}$ matice, která je výsledkem ${ displaystyle M}$ odstraněním ${ displaystyle i}$-th a ${ displaystyle j}$-tý řádek a ${ displaystyle p}$-th a ${ displaystyle q}$-té sloupce.

Desnanot – Jacobi identita

${ displaystyle det (M) det (M_ {1, k} ^ {1, k}) = det (M_ {1} ^ {1}) det (M_ {k} ^ {k}) - det (M_ {1} ^ {k}) det (M_ {k} ^ {1}).}$

Důkaz o správnosti Dodgsonovy kondenzace

Přepište identitu na

${ displaystyle det (M) = { frac { det (M_ {1} ^ {1}) det (M_ {k} ^ {k}) - det (M_ {1} ^ {k}) det (M_ {k} ^ {1})} { det (M_ {1, k} ^ {1, k})}}}}$

Nyní si všimněte, že indukcí vyplývá, že při použití Dodgsonova kondenzačního postupu na čtvercovou matici ${ displaystyle A}$ řádu ${ displaystyle n}$, matice v ${ displaystyle k}$-tá fáze výpočtu (kde první fáze ${ displaystyle k = 1}$ odpovídá matici ${ displaystyle A}$ sám) se skládá ze všech připojené nezletilé řádu ${ displaystyle k}$z ${ displaystyle A}$, kde připojený vedlejší je determinant připojeného ${ displaystyle k krát k}$ dílčí blok sousedních záznamů ${ displaystyle A}$. Zejména v poslední fázi ${ displaystyle k = n}$, jeden dostane matici obsahující jediný prvek rovnající se jedinečné připojené vedlejší objednávce ${ displaystyle n}$, jmenovitě determinant ${ displaystyle A}$.

Důkaz identity Desnanot-Jacobi

Postupujeme podle Bressoudovy knihy; pro alternativní kombinatorický důkaz viz článek od Zeilberger.Denote ${ displaystyle a_ {i, j} = (- 1) ^ {i + j} det (M_ {i} ^ {j})}$ (až podepsat, ${ displaystyle (i, j)}$-th menší z ${ displaystyle M}$) a definujte a ${ displaystyle k krát k}$matice ${ displaystyle M '}$ podle

${ displaystyle M '= { begin {pmatrix} a_ {1,1} & 0 & 0 & 0 & ldots & 0 & a_ {k, 1} a_ {1,2} & 1 & 0 & 0 & ldots & 0 & a_ {k, 2} a_ {1, 3} & 0 & 1 & 0 & ldots & 0 & a_ {k, 3} a_ {1,4} & 0 & 0 & 1 & ldots & 0 & a_ {k, 4} vdots & vdots & vdots & vdots && vdots & vdots a_ {1, k-1} & 0 & 0 & 0 & ldots & 1 & a_ {k, k-1} a_ {1, k} & 0 & 0 & 0 & ldots & 0 & a_ {k, k} end {pmatrix}}.}$

(Všimněte si, že první a poslední sloupec ${ displaystyle M '}$ jsou stejné jako u adjugovaná matice z ${ displaystyle A}$). Identita je nyní získána výpočtem ${ displaystyle det (MM ')}$ dvěma způsoby. Nejprve můžeme přímo vypočítat maticový produkt ${ displaystyle MM '}$ (pomocí jednoduchých vlastností adjugované matice nebo alternativně pomocí vzorce pro expanzi maticového determinantu ve smyslu řádku nebo sloupce) k dosažení

${ displaystyle MM '= { begin {pmatrix} det (M) & m_ {1,2} & m_ {1,3} & ldots & m_ {1, k-1} & 0 0 & m_ {2,2} & m_ {2,3} & ldots & m_ {2, k-1} & 0 0 & m_ {3,2} & m_ {3,3} & ldots & m_ {3, k-1} & 0 vdots & vdots & vdots && vdots & vdots & vdots 0 & m_ {k-1,2} & m_ {k-1,3} & ldots & m_ {k-1, k-1} & 0 0 & m_ {k, 2} & m_ {k, 3} & ldots & m_ {k, k-1} & det (M) end {pmatrix}}}$

kde používáme ${ displaystyle m_ {i, j}}$ označit ${ displaystyle (i, j)}$-tý vstup ${ displaystyle M}$. Determinant této matice je ${ displaystyle det (M) ^ {2} cdot det (M_ {1, k} ^ {1, k})}$.
Zadruhé, to se rovná součinu determinantů, ${ displaystyle det (M) cdot det (M ')}$. Ale jasně
${ displaystyle det (M ') = a_ {1,1} a_ {k, k} -a_ {k, 1} a_ {1, k} = det (M_ {1} ^ {1}) det (M_ {k} ^ {k}) - det (M_ {1} ^ {k}) det (M_ {k} ^ {1}),}$
identita tedy vyplývá z rovnání dvou výrazů, pro které jsme získali ${ displaystyle det (MM ')}$ a vydělením ${ displaystyle det (M)}$ (to je povoleno, pokud si někdo myslí o identitách jako o polynomiálních identitách přes kruh polynomů v ${ displaystyle k ^ {2}}$ neurčité proměnné ${ displaystyle (m_ {i, j}) _ {i, j = 1} ^ {k}}$).

Poznámky

Odkazy a další čtení

• Bressoud, David M., Důkazy a potvrzení: Příběh domněnky o střídavé matici znamení, MAA Spectrum, Mathematical Associations of America, Washington, DC, 1999.
• Bressoud, David M. a Propp, James, Jak byla vyřešena domněnka alternativní matice znamení, Oznámení Americké matematické společnosti, 46 (1999), 637-646.
• Dodgson, C. L. (1866–1867). „Kondenzace determinantů, nová a krátká metoda výpočtu jejich aritmetických hodnot“ (PDF). Sborník královské společnosti v Londýně. 15: 150–155.
• Knuth, Donald, Překrývající se Pfaffiani, Electronic Journal of Combinatorics, 3 Ne. 2 (1996).
• Lotkin, Mark (1959). "Poznámka k metodě smluvních partnerů". Americký matematický měsíčník. 66 (6): 476–479. doi:10.2307/2310629. JSTOR  2310629.
• Mills, William H., Robbins, David P. a Rumsey, Howard, Jr., důkaz Macdonaldova domněnky, Inventiones Mathematicae, 66 (1982), 73-87.
• Mills, William H., Robbins, David P. a Rumsey, Howard, Jr., Střídavé matice se znaménky a sestupné rovinné oddíly, Journal of Combinatorial Theory, Series A, 34 (1983), 340-359.
• Robbins, David P., Příběh ${ displaystyle 1,2,7,42,429,7436, cdots}$, Matematický zpravodaj, 13 (1991), 12-19.
• Zeilberger, Doron, Dodgsonovo rozhodující pravidlo hodnocení bylo prokázáno dvojími muži a ženami, Electronic Journal of Combinatorics, 4 Ne. 2 (1997).

externí odkazy

• Weisstein, Eric W. „Dodgsonova kondenzace“. MathWorld.