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[uredi | uredi kodo]

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\neq 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}={\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 $(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}={\dfrac {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[uredi | uredi kodo]

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

{\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 $2\times 2\,$

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

{\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 ${\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}$ po deljenju pa dobimo ${\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}$ . Postopek ponovimo in dobimo matriko $1\times 1$ . ${\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 $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 ${\begin{bmatrix}-8\end{bmatrix}}$ , kar pa je tudi prava vrednost determinante začetne matrike.