Lewis Carroll Computed Determinants

Summary

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 ...