Charles Dodgson, better known by his pen name Lewis Carroll, discovered a method of calculating determinants now known variously as the method of contractants, Dodgson condensation, or simply condensation.
The method was devised for ease of computation by hand, but it has features that make it a practical method for computation by machine.
Overview
The basic idea is to repeatedly condense a matrix, replacing it by a matrix with one less row and one less column. Each element is replaced by the determinant of the 2×2 matrix formed by that element and its neighbors to the south, east, and southeast. The bottom row and rightmost column have no such neighbors and are removed. There is one additional part of the algorithm that will be easier to describe after introducing some notation.
Details
Let A be the matrix whose determinant we want to compute and let A(k) be the matrix obtained after k steps of the condensation algorithm.
The matrix A(1) is computed as described in the overview:
Starting with A(2) the terms are similar, except each 2×2 determinant is divided by an element from two steps back:
Dodgson’s original paper from 1867 is quite readable, surprisingly so given that math notation and terminology changes over time.
One criticism I have of the paper is that it is hard to understand which element should be in the denominator, whether the subscripts should be i and j or i+1 and j+1. His first example doesn’t clarify this because these elements happen to be equal in the example.
Example
Here’s an example using condensation to find the determinant of a 4×4 matrix.
We can verify this with Mathematica:
Det[{{3, 1, 4, 1}, {5, 9, 2, 6},
{0, 7, 1, 0}, {2, 0, 2, 3}}]
which also produces 228.
Division
The algorithm above involves a division and so we should avoid dividing by zero. Dodgson says to
Arrange the given block, if necessary, so that no ciphers [zeros] occur in its interior. This may be done either by transposing rows or columns, or by adding to certain rows the several terms of other rows multiplied by certain multipliers.
He expands on this remark and gives examples. I’m not sure whether this preparation is necessary only to avoid division by zero, but it does avoid the problem of dividing by a zero.
If the original matrix has all integer entries, then the division in Dodgson’s condensation algorithm is exact. The sequence of matrices produced by the algorithm will all have integer entries.
Efficiency
Students usually learn cofactor expansion as their first method of calculating determinants. This rule is easy to explain, but inefficient since the number of steps required is O(n!).
The more efficient way to compute determinants is by Gaussian elimination with partial pivoting. As with condensation, one must avoid dividing by zero, hence the partial pivoting.
Gaussian elimination takes O(n³) operations, and so does Dodgson’s condensation algorithm. Condensation is easy to teach and easy to carry out by hand, but unlike cofactor expansion it scales well.
If a matrix has all integer entries, Gaussian elimination can produce non-integer values in intermediate steps. Condensation does not. Also, condensation is inherently parallelizable: each of the 2 × 2 determinants can be calculated simultaneously.
Thank you for such an interesting article! I have enjoyed reading your blog. I have one suggestion though. I think you meant to write Laplace expansion or cofactor expansion rather than Cramer’s Rule. Cramer’s rule is used to solve systems of equations with n variables and n equations, which have a unique answer.
This smells like the technique called “deflation” when computing eigenvalues using e.g. the QR algo. In deflation the goal is to eliminate the matrix element at the bottom left corner before proceeding to process the rest of the matrix. Is there any deep connection here, or just a superficial analogy?
Doh! Reading my comment about deflation … I made a mistake. Deflation removes the matrix element on the lower right, not the lower left.