Dodgson Condensation

In mathematics , Dodgson's condensation is a method of calculating determinants . The method is named after its creator Charles Dodgson (better known as Lewis Carroll ). The method consists in lowering the order of the determinant in a special way to order 1, the only element of which is the desired determinant.

Content

General method

The algorithm can be described using the following four steps:

1. Let $A$ ${\ displaystyle A}$ - given square matrix of size $n\times n$ ${\ displaystyle n \ times n}$ . We write the matrix $A$ ${\ displaystyle A}$ so that it contains only non-zero elements in the inner part, i.e. $a_{ij}\neq 0$ ${\ displaystyle a_ {ij} \ neq 0}$ , if a $i,j\neq 1,n$ ${\ displaystyle i, j \ neq 1, n}$ . This can be done, for example, using the operation of adding to the row matrix of some other row multiplied by some number.

2. We write the matrix $B$ ${\ displaystyle B}$ the size $(n-1)\times (n-1)$ ${\ displaystyle (n-1) \ times (n-1)}$ consisting of minors of order 2 of the matrix $A$ ${\ displaystyle A}$ . Explicitly -

b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}},~i,j=1\ldots n-1

{\ displaystyle b_ {i, j} = {\ begin {vmatrix} a_ {i, j} & a_ {i, j + 1} \\ a_ {i + 1, j} & a_ {i + 1, j + 1} \ end {vmatrix}}, ~ i, j = 1 \ ldots n-1}

.

3. Applying step number 2 to the matrix $B$ ${\ displaystyle B}$ we write the matrix $C$ ${\ displaystyle C}$ the size $(n-2)\times (n-2)$ ${\ displaystyle (n-2) \ times (n-2)}$ by dividing the corresponding elements of the resulting matrix into internal elements of the matrix $A$ ${\ displaystyle A}$ :

c_{i,j}={\dfrac {\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}}},i,j=1\ldots n-2

{\ displaystyle c_ {i, j} = {\ dfrac {\ 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}}}, i, j = 1 \ ldots n-2}

.

4. Let $A=B$ ${\ displaystyle A = B}$ and $B=C$ ${\ displaystyle B = C}$ . We repeat step No. 3 until we obtain a matrix of order 1. Its only element will be the desired determinant.

Examples

No Zeros

Let it be necessary to calculate the determinant:

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

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

Make a matrix $B$ ${\ displaystyle B}$ of minors of the order of 2.

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

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

Make a matrix $C$ ${\ displaystyle C}$ :

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

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

$C={\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}.$ ${\ displaystyle C = {\ begin {bmatrix} 8 & -2 \\ - 4 & 6 \ end {bmatrix}}.}$

Matrix Elements $C$ ${\ displaystyle C}$ we got by dividing the elements of the resulting matrix ${\begin{bmatrix}-16&2\\4&12\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} -16 & 2 \\ 4 & 12 \ end {bmatrix}}}$ to the internal elements of the matrix $A$ ${\ displaystyle A}$ ${\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}.$ ${\ displaystyle {\ begin {bmatrix} -2 & -1 \\ - 1 & 2 \ end {bmatrix}}.}$

We repeat this process until we get a matrix of order 1. ${\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.$ ${\ displaystyle {\ begin {bmatrix} {\ begin {vmatrix} 8 & -2 \\ - 4 & 6 \ end {vmatrix}} \ end {bmatrix}} = {\ begin {bmatrix} 40 \ end {bmatrix}}.}$ Divide by the inside of the size matrix $3\times 3$ ${\ displaystyle 3 \ times 3}$ , i.e. on $-5$ ${\ displaystyle -5}$ we get ${\begin{bmatrix}-8\end{bmatrix}}$ ${\ displaystyle {\ begin {bmatrix} -8 \ end {bmatrix}}}$ .

$-8$ ${\ displaystyle -8}$ and there is the desired determinant of the original matrix.

With zeros

We write the necessary matrices:

{\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}-30&6&-12\\0&0&6\\6&-6&8\end{bmatrix}}.

{\ 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} -30 & 6 & -12 \\ 0 & 0 & 6 \\ 6 & -6 & 8 \ end {bmatrix}}.}

There is a problem. If we continue this process, we will need to divide by 0. However, we can rearrange the rows of the original matrix and repeat the process:

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

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

Thus, the determinant of the original matrix 36.

Dodgson Identity and Dodgson Condensation Correctness

Dodgson's identity

The proof of Dodgson’s condensation method is based on an identity known as the Dodgson identity ( Jacobi identity).

Let be $A=(m_{i,j})_{i,j=1}^{k}$ ${\ displaystyle A = (m_ {i, j}) _ {i, j = 1} ^ {k}}$ Is a square matrix, and for all $1\leq i,j\leq k$ ${\ displaystyle 1 \ leq i, j \ leq k}$ denote $M_{i}^{j}$ ${\ displaystyle M_ {i} ^ {j}}$ minor matrix $A$ ${\ displaystyle A}$ which is obtained by crossing out $i$ ${\ displaystyle i}$ th row and $j$ ${\ displaystyle j}$ th column. Similarly for $1\leq i,j,p,q\leq k$ ${\ displaystyle 1 \ leq i, j, p, q \ leq k}$ denote $M_{i,j}^{p,q}$ ${\ displaystyle M_ {i, j} ^ {p, q}}$ minor, which is obtained from the matrix $A$ ${\ displaystyle A}$ by striking out $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ st rows and $p$ ${\ displaystyle p}$ th and $q$ ${\ displaystyle q}$ columns. Then

\det(A)\cdot M_{1,k}^{1,k}=M_{1}^{1}\cdot M_{k}^{k}-M_{1}^{k}\cdot M_{k}^{1}.

{\ displaystyle \ det (A) \ cdot M_ {1, k} ^ {1, k} = M_ {1} ^ {1} \ cdot M_ {k} ^ {k} -M_ {1} ^ {k} \ cdot M_ {k} ^ {1}.}

Dodgson's proof of identity