Dodgson Condensation

The Reverend Charles Dodgson (alias Lewis Carroll) invented a neat method of taking determinants without cofactor expansion or row reduction. I like to think of his condensation method as building an imaginary pyramid of matrices. The base of the pyramid is the matrix whose determinant you’re trying to find. In the air above each of the base matrix’s interior whitespaces, you imagine writing the determinant of the two-by-two submatrix centered on that whitespace. This imaginary hovering matrix is the first level of the pyramid. You then build up the second level by writing determinants of the first level’s submatrices in the air above the first level’s whitespaces. The one additional rule is that whenever you write an entry directly above another entry two levels below, you have to divide the entry above by the entry beneath. You continue on in this fashion, writing additional levels in the air above the existing levels til you get to the apex of the pyramid, which is the determinant of the base.(1) (1)I got this pyramid image from Leo Goldmakher. Maybe Leo invented it; maybe it’s folklore.

The obvious catch is that this method doesn’t work when one of the base’s interior entries is zero, since another entry will eventually appear above it, and you’ll get a division by zero error. The workaround is to move all interior zeroes to the edges of the matrix using elementery row operations before you start building the pyramid. This will always be possible unless the determinant of the base matrix is zero.

In case my description of the pyramid didn’t do much for you, I also made a small interactive visualization showing how you would calculate ⊕

\[ \begin{vmatrix} 5 & 0 & 3 \\ 0 & 2 & 1 \\ 4 & 3 & 4 \\ \end{vmatrix} = 1\]

using Dodgson condensation.

A puzzle #

Suppose we have an $n\times n$ matrix $A$, and we rotate it a quarter turn counterclockwise to obtain the matrix $R(A)$. What is $\det R(A)$ in terms of $\det A$?

As a quick point of clarification, rotating $A$ means writing it down on a piece of paper, turning the paper ninety degrees to the left, and turning the entries right side up again. So for example, if $n=3$, we have

\[A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{pmatrix} \; R(A) = \begin{pmatrix} a_{13} & a_{23} & a_{33} \\ a_{12} & a_{22} & a_{32} \\ a_{11} & a_{21} & a_{31} \\ \end{pmatrix}.\]

One can solve this puzzle using the determinant rules for elementary row operations, but I’d like to show how you might solve it using Dodgson condensation instead. First note that rotating a $2\times 2$ matrix a quarter turn inverts the determinant since the diagonal entries become the off-diagonal entries and vice versa.

What does rotating the base matrix do to the first level of the Dodgson pyramid? Given what we’ve noticed, it clearly just rotates the first level and inverts all its entries. If we denote the $i$th level of the pyramid built atop $A$ by $A^{(i)},$ we can write this result as

\[ R(A)^{(1)} = -R(A^{(1)}). \]

To build the second level of the pyramid, we have to take determinants of the first level’s $2\times 2$ submatrices. Inverting all the entries of a $2\times 2$ matrix does nothing to its determinant because two is even. However, the rotation still introduces a minus sign, so

\[ R(A)^{(2)} = -R(A^{(2)}). \]

The same thing happens when we build the third level except that we have to divide by the entries of the first level, all of which were inverted. Two minus signs cancel, and we get

\[ R(A)^{(3)} = R(A^{(2)}). \]

Likewise

\[ R(A)^{(4)} = R(A^{(4)}). \]

At this point, we’re done. The Dodgson condensation algorithm never looks back more than two levels, so we know that this pattern will repeat forever. The sign of the $i$th level will be inverted when $i$ is congruent to 1 or 2 mod 4, and the sign will be unchanged when $i$ is congruent to 3 or 0 mod 4. In slightly more concise notation,

\[ R(A)^{(i)} = (-1)^{\lfloor (n+1) /2\rfloor} R(A^{(i)}) \]

This is kind of cool, but what does that mean for the determinant of the rotated matrix? The key observation is that rotating the apex of the pyramid does nothing to its determinant, which equals the determinant of the base matrix:

\[\det R(A) = \det R(A)^{(n-1)} = \det \big[(-1)^{\lfloor n /2\rfloor} R(A^{(n-1)}) \big] \\[4pt] = (-1)^{\lfloor n /2\rfloor} \det R(A^{(n-1)}) = (-1)^{\lfloor n /2\rfloor} \det A. \]

Questions #

• Did Lewis Carroll sneak any references to the condensation method into his fiction?
• Why hasn’t condensation replaced cofactor expansion in mathematical pedagogy?
• How do the proofs of basic theorems in linear algebra look if you take the condensation method as your definition of the determinant?
• What happens if you get an interior zero in one of the matrices above the base? Is there some guarantee that this can’t happen, and if not, what’s the workaround?

Reading List #

• Dodgson’s original paper describing his method of condensation.
• Abeles on the history of the method. The bibliography looks rich.
• Terry Tao on the method and its relation to something called Schur complementation.
• Wilson’s Lewis Carroll in Numberland

Last updated 5 November 2024