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
General method
This algorithm can be described in the following four steps:
- 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 ≠ 1 , n . One can do this using any operation that one could normally perform without changing the value of the determinant, such as adding a multiple of one row to another. - 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 = | a i , j a i , j + 1 a i + 1 , j a i + 1 , j + 1 | . - 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 so
c i , j = | b i , j b i , j + 1 b i + 1 , j b i + 1 , j + 1 | / a i + 1 , j + 1 - Let A = B, and B = C. Repeat step 3 as necessary until the 1 × 1 matrix is found; its only entry is the determinant.
Without zeros
One wishes to find
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
With zeros
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.
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 or Lewis Carroll identity.
Let
Desnanot–Jacobi identity
Proof of the correctness of Dodgson condensation
Rewrite the identity as
Now note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix
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
(Note that the first and last column of
where we use
Second, this is equal to the product of the determinants,
so the identity follows from equating the two expressions we obtained for