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