Lewis Carroll and His Telescoping Determinants

Doron Zeilberger of Rutgers University liked to describe Charles L. Dodgson (1832–1898) as perhaps the most famous mathematician in the world. But Dodgson isn't known for his mathematical work; he's famous as Lewis Carroll for writing Alice's Adventures in Wonderland, its sequel, and other fantasies.

Nonetheless, Dodgson can be credited with at least one curious mathematical advance, first published in 1866 in the Proceedings of the Royal Society of London. Indeed, Dodgson's ingenious method for computing the determinant of a square matrix deserves to be more widely known.

Given a 2 x 2 matrix A, its determinant (det A) is the difference between diametrically opposed entries in the matrix. In the matrix below, det A = ad – bc.


Determinants are useful in the analysis and solution of linear equations. For example, a system of linear equations has a unique solution if the determinant of the system's matrix is nonzero. In this case, the matrix is made up of the coefficients of the system's linear equations.

"Determinants emerged gradually during the 18th century through the theory of equations….," Adrian Rice and Eve Torrence noted in the March College Mathematics Journal. "By the 19th century, the subject had become a mathematical area of increasing significance." Carl Friedrich Gauss (1777–1855) was responsible for naming these mathematical objects determinants.

Although it's easy to calculate the determinant of a 2 x 2 matrix, the task gets increasingly tedious and time-consuming as the size of the matrix increases. The standard method involves breaking the n x n matrix down into a larger number of determinants of lower degree by taking the product of entries in designated rows and columns, then alternately adding and subtracting the results (see example, below).


Even in the case of a 5 x 5 matrix, the computation can get tedious. It involves five 4 x 4 determinants, which break down into twenty 3 x 3 determinants, or sixty 2 x 2 determinants, for a total of 120 multiplications (plus all the additions to get the final answer).

Dodgson came up with an alternative method that significantly simplifies the calculation. His "condensation" algorithm comes down to calculating nothing more than 2 x 2 determinants. In the 5 x 5 case, for example, Dodgson's method requires only 60 multiplications (plus a few divisions).

Here's an example of Dodgson's condensation method at work. You start with the following 4 x 4 matrix.


You condense this matrix into the following 3 x 3 matrix.


That matrix, in turn, condenses into the following 2 x 2 matrix.


You now divide each entry of this matrix by the corresponding term in the interior of the original matrix.


The determinant of this matrix is –42. When divided by –7 (the interior term in the 3 x 3 matrix), we get the correct answer of 6 for the determinant of the original matrix.

In effect, you start with an n x n matrix, then successively compute an (n – 1) x (n – 1) matrix, an (n – 2) x (n – 2) matrix, and so on, until you arrive at a 1 x 1 matrix whose sole entry is the determinant of the original n x n matrix. The rule for computing the smaller k x k matrix is to take k² 2 x 2 connected subdeterminants of the (k + 1) x (k + 1) matrix and divide them by the corresponding k² central entries of the (k + 2) x (k + 2) matrix.

In a 1999 article on the alternating sign matrix conjecture, David Bressoud and James Propp remarked that "the method is also useful for computer calculations, especially since it can be executed in parallel by many processors." At the same time, the division steps are a nice error check for hand calculations because the answers should all be integers for matrices with integer terms.

The only catch with using Dodgson's condensation algorithm is the requirement that there be no zeros in the interior of a matrix. Otherwise, some of the divisions would be undefined. One way around the problem is to rearrange the rows and columns of the matrix so that zeros don't occur in the interior, but that isn't always possible.

Dodgson also described his condensation method in the only textbook that he ever wrote: An Elementary Treatise on Determinants (with their application to simultaneous linear equations and algebraical geometry).

"Dodgson's Treatise on Determinants was not a bestseller, not even selling enough copies to warrant a second edition," Rice and Torrence wrote. "The limited availability of the book together with the obscurity of the text itself made it highly unlikely that Dodgson's algorithm would catch on."

"Nevertheless," they added, "when teaching linear algebra, we have consistently found Dodgson's method to be the most popular method among our students for evaluating determinants. Curious!"

References:

Amdeberhan, T., and D. Zeilberger. 2001. Determinants through the looking glass. Advances in Applied Mathematics 27(August):225-230.

Bressoud, D. 1999. Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Mathematical Association of America.

Bressoud, D., and J. Propp. 1999. How the Alternating Sign Matrix Conjecture Was Solved. Notices of the American Mathematical Society 46(June/July):637-646.

Dodgson, C.L. 1866. Condensation of determinants, being a new and brief method for comupting their arithmetical values. Proceedings of the Royal Society of London 15:150-155,

Rice, A., and E. Torrence. 2007. "Shutting up like a telescope": Lewis Carroll's "curious" condensation method for evaluating determinants. College Mathematics Journal 38(March):85-105.

Zeilberger, D. 1997. Dodgson's determinant-evaluation rule proved by two-timing men and women. Electronic Journal of Combinatorics 4(No. 2):R22.

______. 1996. Reverend Charles to the aid of Major Percy and Fields-Medalist Enrico. American Mathematical Monthly 103(July):501-502.