Dodgsonova kondenzacija

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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 \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}=\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.

Zunanje povezave[uredi | uredi kodo]