Dodgsonova kondenzacija

Dodgsonova kondenzacija je postopek, ki nam omogoča računanje determinant kvadratnih matrik.

Postopek se imenuje po angleškem pisatelju, matematiku, logiku in anglikanskem diakonu Charlesu Lutwidgu Dodgsonu (1832 – 1898). Znan je bolj kot pisatelj, njegovo najznamenitejše delo je Aličine dogodivščine v čudežni deželi, ki ga je izdal pod psevdonimom Lewis Carroll.

Postopek je sestavljen iz zaporedja kreiranja vedno manjših matrik. Prične se z matriko $n\times n$, nato se nadaljuje s kreiranjem matrike $(n-1)\times (n-1)$ in matrike $(n-2)\times (n-2)$ dokler ne pridemo do matrike z razsežnostjo $1\times 1$, ki vsebuje samo en element, ki je enak determinanti začetne matrike.

Splošni postopek

Način določanja vrednosti determinante lahko opišemo s štirimi koraki

1. korak Naj bo $A$ matrika z razsežnostjo $n\times n$. Najprej preuredimo matriko $A$ tako, da ne bo imela ničel v svoji notranjosti. Notranjost predstavljajo vsi elementi matrike $a_{i,j}$ za katere je $i,j\ne 1,n.$

2. korak Kreiramo matriko $B$, ki pa ima razsežnost $(n-1)\times (n-1)$, ki jo sestavljajo determinante vsake od $2\times 2$ podmatrik matrike $A$. To pomeni, da je vsak $b_{i,j}$ enak $b_{i,j}=\left|\begin{array}{cc}{a}_{i,j}& a_{i,j+1}\\ a_{i+1,j}& a_{i+1,j+1}\end{array}\right|.$

3. korak Z uporabo matrike $(n-1)\times (n-1)$ ponovimo drugi korak in dobimo matriko $(n-2)\times (n-2)$, ki naj bo matrika $C$. Sedaj delimo vsak člen v $C$ z odgovarjajočim členom iz notranjosti matrike $A$. Torej dobimo elmente $c_{i,j}=\frac{b_{i,j}}{a_{i+1,j+1}}.$

4. korak Naj bo $A=B$ in $B=C.$ Če je potrebno ponavljamo tretji korak tako dolgo, da dobimo matriko $1\times 1$. Element, ki ga vsebuje je vrednost determinante prvotne matrike.

Zgled

Hočemo izračunati vrednost determinante matrike $4\times 4$

$\left|\begin{array}{cccc}-2& -1& -1& -4\\ -1& -2& -1& -6\\ -1& -1& 2& 4\\ 2& 1& -3& -8\end{array}\right|.$

Najprej izdelamo matriko, ki jo sestavljajo podmatrike z razsežnostjo $2\times 2$

$\left[\begin{array}{ccc}\left|\begin{array}{cc}-2& -1\\ -1& -2\end{array}\right|& \left|\begin{array}{cc}-1& -1\\ -2& -1\end{array}\right|& \left|\begin{array}{cc}-1& -4\\ -1& -6\end{array}\right|\\ \\ \left|\begin{array}{cc}-1& -2\\ -1& -1\end{array}\right|& \left|\begin{array}{cc}-2& -1\\ -1& 2\end{array}\right|& \left|\begin{array}{cc}-1& -6\\ 2& 4\end{array}\right|\\ \\ \left|\begin{array}{cc}-1& -1\\ 2& 1\end{array}\right|& \left|\begin{array}{cc}-1& 2\\ 1& -3\end{array}\right|& \left|\begin{array}{cc}2& 4\\ -3& -8\end{array}\right|\end{array}\right]=\left[\begin{array}{ccc}3& -1& 2\\ -1& -5& 8\\ 1& 1& -4\end{array}\right].$

Iz tega dobimo naslednjo matriko determinant

$\left[\begin{array}{cc}\left|\begin{array}{cc}3& -1\\ -1& -5\end{array}\right|& \left|\begin{array}{cc}-1& 2\\ -5& 8\end{array}\right|\\ \\ \left|\begin{array}{cc}-1& -5\\ 1& 1\end{array}\right|& \left|\begin{array}{cc}-5& 8\\ 1& -4\end{array}\right|\end{array}\right]=\left[\begin{array}{cc}-16& 2\\ 4& 12\end{array}\right].$

Temu sledi deljenje z notranjostjo začetne matrike. Notranjost začetne matrike je enaka $\left[\begin{array}{cc}-2& -1\\ -1& 2\end{array}\right]$ po deljenju pa dobimo $\left[\begin{array}{cc}8& -2\\ -4& 6\end{array}\right]$. Postopek ponovimo in dobimo matriko $1\times 1$. $\left[\begin{array}{c}\left|\begin{array}{cc}8& -2\\ -4& 6\end{array}\right|\end{array}\right]=\left[\begin{array}{c}40\end{array}\right].$ Sedaj moramo deliti z elementom, ki predstavlja notranjost matrike $3\times 3$, to pa je -5 (problem nastane, kadar je element v notranjosti enak 0. V tem primeru preuredimo vrstice tako, da element ni več enak nič. Pri preurejanju vrstic se vrednost determinante ne spremeni.). V našem primeru dobimo $\left[\begin{array}{c}-8\end{array}\right]$, kar pa je tudi prava vrednost determinante začetne matrike.

Zunanje povezave

• Dodgsonova kondenzacija na MathWorld Predloga:Ikona en
• Dodgsonova kondenzacija na Mathematical Association of America (MAA) Predloga:Ikona en