Dodgson condensation

Dodgson condensation

In mathematics, Dodgson condensation is a method of computing the determinants of square matrices. It is named for its inventor Charles Dodgson (better known as Lewis Carroll). The method in the case of an n × n matrix is to construct an (n − 1) × (n − 1)matrix, an (n − 2) × (n − 2), and so on, finishing with a 1 × 1 matrix, which has one entry, the determinant of the original matrix.

Contents

The General Method

This algorithm can be described in the following 4 steps:

  1. Let A be the given n × n matrix. Arrange A so that no zeros occur in its interior. An explicit definition of interior would be all ai,j with i,j\ne1,n. We can do this using any operation that we could normally perform without changing the value of the determinant, such as adding a multiple of one row to another.
  2. Create an (n − 1) × (n − 1) matrix B, consisting of the determinants of every 2 × 2 submatrix of A. Explicitly, we write  b_{i,j}=\begin{vmatrix}  a_{i, j} & a_{i, j + 1} \\ a_{i + 1, j} & a_{i + 1, j + 1} \end{vmatrix}.
  3. Using this (n − 1) × (n − 1) matrix, perform step 2 to obtain an (n − 2) × (n − 2) matrix C. Divide each term in C by the corresponding term in the interior of A.  c_{i,j} = \dfrac{b_{i,j}}{a_{i + 1, j + 1}}.\,\!
  4. Let A = B, and B = C. Repeat step 3 as necessary until the 1 × 1 matrix is found; its only entry is the determinant.

Examples

Without Zeros

We wish to find


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

We make a matrix of its 2 × 2 submatrices.


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

We then find another matrix of determinants:


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

We must then divide each element by the corresponding element of our original matrix. The interior of our original matrix is 
\begin{bmatrix}
-2 & -1 \\
-1 & 2
\end{bmatrix}
, so after dividing we get 
\begin{bmatrix}
8 & -2 \\
-4 & 6
\end{bmatrix}
. The process must be repeated to arrive at a 1 × 1 matrix. 
\begin{bmatrix}
\begin{vmatrix}
8 & -2 \\
-4 & 6
\end{vmatrix}
\end{bmatrix}
=
\begin{bmatrix}
40
\end{bmatrix}.
We divide by the interior of our 3 × 3 matrix, which is just -5, giving us \begin{bmatrix} -8 \end{bmatrix}. -8 is indeed the determinant of the original matrix.

With Zeros

Simply writing out the 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}.

Here we run into trouble. If we continue the process, we will eventually be dividing by 0. We can perform four row exchanges on the initial matrix to preserve the determinant and repeat the process, with most of the determinants precalculated:


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

Hence, we arrive at a determinant of 36.

The Desnanot-Jacobi identity and proof of correctness of the condensation algorithm

The proof that the condensation method computes the determinant of the matrix if no divisions by zero are encountered is based on an identity known as the Desnanot-Jacobi identity.

Let M=(m_{i,j})_{i,j=1}^k be a square matrix, and for each 1\le i, j\le k denote by M_i^j the matrix that results from M by deleting the i-th row and the j-th column. Similarly, for 1\le i, j, p,q\le k denote by M_{i,j}^{p,q} the matrix that results from M by deleting the i-th and j-th rows and the p-th and q-th columns.

The Desnanot-Jacobi identity

\det(M) \det(M_{1,k}^{1,k}) = \det(M_1^1)\det(M_k^k) - \det(M_1^k) \det(M_k^1).

Proof of the correctness of Dodgson condensation

Rewrite the identity as

\det(M) = \frac{\det(M_1^1)\det(M_k^k) - \det(M_1^k) \det(M_k^1)}{\det(M_{1,k}^{1,k})}.

Now note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix A of order n, the matrix in the k-th stage of the computation (where the first stage k = 1 corresponds to the matrix A itself) consists of all the connected minors of order k of A, where a connected minor is the determinant of a connected k\times k sub-block of adjacent entries of A. In particular, in the last stage k = n we get a matrix containing a single element equal to the unique connected minor of order n, namely the determinant of A.

Proof of the Desnanot-Jacobi identity

We follow the treatment in Bressoud's book; for an alternative combinatorial proof see the paper by Zeilberger. Denote a_{i,j} = (-1)^{i+j} \det(M_i^j) (up to sign, the (i,j)-th minor of M), and define a k\times k matrix M' by


M' = \begin{pmatrix} a_{1,1} & 0 & 0 & 0 & \ldots & 0 & a_{k,1} \\
a_{1,2} & 1 & 0 & 0 & \ldots & 0 & a_{k,2} \\
a_{1,3} & 0 & 1 & 0 & \ldots & 0 & a_{k,3} \\
a_{1,4} & 0 & 0 & 1 & \ldots & 0 & a_{k,4} \\
\vdots & \vdots & \vdots & \vdots & & \vdots & \vdots \\
a_{1,k-1} & 0 & 0 & 0 & \ldots & 1 & a_{k,k-1} \\
a_{1,k} & 0 & 0 & 0 & \ldots & 0 & a_{k,k}
\end{pmatrix}.


(Note that the first and last column of M' are equal to those of the adjugate matrix of A). The identity is now obtained by computing det(MM') in two ways. First, we can directly compute the matrix product MM' (using simple properties of the adjugate matrix, or alternatively using the formula for the expansion of a matrix determinant in terms of a row or a column) to arrive at


M M' = \begin{pmatrix}
\det(M) & m_{1,2} & m_{1,3} & \ldots &  m_{1,k-1} & 0 \\
0 &  m_{2,2} & m_{2,3} & \ldots & m_{2,k-1} & 0 \\
0 &  m_{3,2} & m_{3,3} & \ldots & m_{3,k-1} & 0 \\
\vdots & \vdots & \vdots & & \vdots & \vdots & \vdots \\
0 &  m_{k-1,2} & m_{k-1,3} & \ldots & m_{k-1,k-1} & 0 \\
0 & m_{k,2} & m_{k,3} & \ldots & m_{k,k-1} & \det(M)
\end{pmatrix}


where we use mi,j to denote the (i,j)-th entry of M. The determinant of this matrix is \det(M)^2 \cdot \det(M_{1,k}^{1,k}).
Second, this is equal to the product of the determinants, \det(M) \cdot \det(M'). But clearly

\det(M') = a_{1,1} a_{k,k} - a_{k,1} a_{1,k} = \det(M_1^1)\det(M_k^k) - \det(M_1^k) \det(M_k^1),
so the identity follows from equating the two expressions we obtained for det(MM') and dividing out by det(M) (this is allowed if one thinks of the identities as polynomial identities over the ring of polynomials in the k2 indeterminate variables (m_{i,j})_{i,j=1}^k).

References and further reading

  • Condensation of Determinants, Being a New and Brief Method for Computing their Arithmetical Values, by C. L. Dodgson

Proceedings of the Royal Society of London © 1866 The Royal Society

  • Bressoud, David M., Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.
  • Bressoud, David M. and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637-646.
  • Knuth, D. (1996) Overlapping Pfaffians, Electronic Journal of Combinatorics 3 no. 2.
  • Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae, 66 (1982), 73-87.
  • Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A, 34 (1983), 340-359.
  • Robbins, David P., The story of 1, 2, 7, 42, 429, 7436, \cdots, The Mathematical Intelligencer, 13 (1991), 12-19.
  • Zeilberger, D., Dodgson's determinant evaluation rule proved by two-timing men and women. Elec. J. Comb. 4 (1997).

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Dodgson — People Dodgson can be a surname. Its origin is son of Roger , Dodge being a mediaeval nickname for Roger, as were Rodge and Hodge. Charles Lutwidge Dodgson, English mathematician, logician, clergyman, photographer and author better known by his… …   Wikipedia

  • Charles Dodgson — Lewis Carroll Pour les articles homonymes, voir Carroll. Lewis Carroll (autoportrait) Lewis Carroll (de son vrai nom Charles Lutwidge Dodgson) es …   Wikipédia en Français

  • Charles Lutwidge Dodgson — Lewis Carroll Pour les articles homonymes, voir Carroll. Lewis Carroll (autoportrait) Lewis Carroll (de son vrai nom Charles Lutwidge Dodgson) es …   Wikipédia en Français

  • Lewis Carroll — Charles Lutwidge Dodgson Born 27 January 1832(1832 01 27) Daresbury, Halton, Cheshire, England Died …   Wikipedia

  • Lewis Carroll identity — The Lewis Carroll identity is an identity involving minors of a square matrix proved by Charles Dodgson (pseudonym Lewis Carroll), who used it in a method of numerical evaluation of matrix determinants called the Dodgson condensation. From the… …   Wikipedia

  • Конденсация Доджсона — В математике, конденсация Доджсона это метод вычисления определителей. Метод назван в честь его создателя Чарльза Доджсона (более известного, как Льюис Кэррол). Метод заключается в понижении порядка определителя специальным образом до порядка 1,… …   Википедия

  • List of matrices — This page lists some important classes of matrices used in mathematics, science and engineering: Matrices in mathematics*(0,1) matrix a matrix with all elements either 0 or 1. Also called a binary matrix . *Adjugate matrix * Alternant matrix a… …   Wikipedia

  • Alternating sign matrix — In mathematics, an alternating sign matrix is a square matrix of 0s, 1s, and −1s such that the sum of each row and column is 1 and the nonzero entries in each row and column alternate in sign. These matrices arise naturally when using Dodgson… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Lewis Carol — Lewis Carroll Pour les articles homonymes, voir Carroll. Lewis Carroll (autoportrait) Lewis Carroll (de son vrai nom Charles Lutwidge Dodgson) es …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”