In mathematics, Dodgson condensation or method of contractants is a method of computing the determinants of square matrices.
It is named for its inventor, Charles Lutwidge Dodgson (better known by his pseudonym, as Lewis Carroll, the popular author), who discovered it in 1866.
[1] 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.
This algorithm can be described in the following four steps: One wishes to find All of the interior elements are non-zero, so there is no need to re-arrange the matrix.
We make a matrix of its 2 × 2 submatrices.
We then find another matrix of determinants: We must then divide each element by the corresponding element of our original matrix.
The interior of the original matrix is
The process must be repeated to arrive at a 1 × 1 matrix.
Dividing by the interior of the 3 × 3 matrix, which is just −5, gives
and −8 is indeed the determinant of the original matrix.
Simply writing out the matrices: 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: Hence, we arrive at a determinant of 36.
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 (1841) or, more generally, the Sylvester determinant identity (1851).
be a square matrix, and for each
Rewrite the identity as Now note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix
itself) consists of all the connected minors of order
sub-block of adjacent entries of
, one gets a matrix containing a single element equal to the unique connected minor of order
, namely the determinant of
We follow the treatment in the book Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture;[3] an alternative combinatorial proof was given in a paper by Doron Zeilberger.
(Note that the first and last column of
are equal to those of the adjugate matrix of
The identity is now obtained by computing
First, we can directly compute the matrix product
(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
Second, this is equal to the product of the determinants,
so the identity follows from equating the two expressions we obtained for
(this is allowed if one thinks of the identities as polynomial identities over the ring of polynomials in the
indeterminate variables