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 ${\displaystyle n\times n\,}$, nato se nadaljuje s kreiranjem matrike ${\displaystyle (n-1)\times (n-1)\,}$ in matrike ${\displaystyle (n-2)\times (n-2)\,}$ dokler ne pridemo do matrike z razsežnostjo ${\displaystyle 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 ${\displaystyle A}$ matrika z razsežnostjo ${\displaystyle n\times n\,}$. Najprej preuredimo matriko ${\displaystyle A}$ tako, da ne bo imela ničel v svoji notranjosti. Notranjost predstavljajo vsi elementi matrike ${\displaystyle a_{i,j}$ za katere je ${\displaystyle i,j\neq 1,n.}$

2. korak Kreiramo matriko ${\displaystyle B\,}$, ki pa ima razsežnost ${\displaystyle (n-1)\times (n-1)\,}$, ki jo sestavljajo determinante vsake od ${\displaystyle 2\times 2\,}$ podmatrik matrike ${\displaystyle A}$. To pomeni, da je vsak ${\displaystyle b_{i,j}$ enak ${\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. korak Z uporabo matrike ${\displaystyle (n-1)\times (n-1)\,}$ ponovimo drugi korak in dobimo matriko ${\displaystyle (n-2)\times (n-2)\,}$, ki naj bo matrika ${\displaystyle C}$. Sedaj delimo vsak člen v ${\displaystyle C}$ z odgovarjajočim členom iz notranjosti matrike ${\displaystyle A}$. Torej dobimo elmente ${\displaystyle c_{i,j}={\dfrac {b_{i,j}{a_{i+1,j+1}.\,}$

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

Zgled

Hočemo izračunati vrednost determinante matrike ${\displaystyle 4\times 4\,}$

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

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

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

Iz tega dobimo naslednjo matriko 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}.}$

Temu sledi deljenje z notranjostjo začetne matrike. Notranjost začetne matrike je enaka ${\displaystyle {\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}$ po deljenju pa dobimo ${\displaystyle {\begin{bmatrix}8&-2\\-4&6\end{bmatrix}$. Postopek ponovimo in dobimo matriko ${\displaystyle 1\times 1}$. ${\displaystyle {\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}\end{bmatrix}={\begin{bmatrix}40\end{bmatrix}.}$ Sedaj moramo deliti z elementom, ki predstavlja notranjost matrike ${\displaystyle 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 ${\displaystyle {\begin{bmatrix}-8\end{bmatrix}$, kar pa je tudi prava vrednost determinante začetne matrike.

Zunanje povezave

• Dodgsonova kondenzacija na MathWorld (angleško)
• Dodgsonova kondenzacija na Mathematical Association of America (MAA) (angleško)