TL;DR
In 1867 Charles Dodgson (better known as Lewis Carroll) described an iterative procedure for computing determinants now called Dodgson condensation or the method of contractants. The method reduces an n×n matrix stepwise using 2×2 determinants, requires occasional division by earlier entries (so zeros must be avoided), and matches Gaussian elimination in asymptotic cost while keeping integer intermediates when the input is integral.
What happened
Charles Dodgson proposed a hands-on algorithm to compute matrix determinants by repeatedly shrinking the matrix. At each step the algorithm forms a new (n-1)×(n-1) matrix whose entries are determinants of 2×2 subblocks taken from neighboring entries (south, east and southeast). After the first condensation, subsequent steps also divide each new 2×2 determinant by a particular element from two steps earlier; the precise subscript placement in Dodgson’s original exposition is a little ambiguous. Because the process involves division, Dodgson recommended rearranging rows or columns or adding multiples of rows to eliminate interior zeros before beginning. For integer matrices the intermediate divisions are exact, so all produced matrices remain integral. The method has the same O(n^3) operation count as Gaussian elimination, is well suited to hand calculation, and offers inherent opportunities for parallel computation. A 4×4 example in the source is verified to produce 228 as the determinant.
Why it matters
- Provides a compact, iterative alternative to cofactor expansion that scales to larger matrices.
- Preserves integer entries throughout for integer-input matrices, avoiding fractional intermediates.
- Matches Gaussian elimination in asymptotic complexity (O(n^3)) while being easy to teach and perform by hand.
- Each condensation step can be parallelized because the requisite 2×2 determinants are independent.
- Requires preparation to avoid dividing by zero; users must handle interior zeros before applying the algorithm.
Key facts
- The method is variously called the method of contractants, Dodgson condensation, or simply condensation.
- Start: replace each interior element by the determinant of the 2×2 block formed with its south, east and southeast neighbors.
- From the second condensation onward, each new entry is divided by an element from two steps earlier.
- Dodgson warned against zeros in the interior and suggested reordering rows/columns or adding multiples of rows to remove them.
- When the original matrix has integer entries, the divisions in the algorithm are exact and intermediate matrices remain integer-valued.
- Condensation and Gaussian elimination both require O(n^3) operations, unlike the factorial cost of cofactor expansion.
- The algorithm is naturally parallelizable because computing the many 2×2 determinants can be done simultaneously.
- An example 4×4 matrix processed with condensation yields determinant 228, confirmed with Mathematica.
- Dodgson’s original paper (1867) is noted as readable but contains some notational ambiguity about denominator indices.
What to watch next
- Division by zero during the process — Dodgson recommends rearranging or modifying the matrix to avoid interior zeros.
- Ambiguity in indexing of the denominator in Dodgson’s original write-up; implementers should verify which element to use.
- Potential for parallel implementation since individual 2×2 determinants at each step are independent.
- Connections to other matrix reduction techniques (for example, eigenvalue deflation or QR methods) are not confirmed in the source.
Quick glossary
- Determinant: A scalar value computed from a square matrix that encodes properties like invertibility and volume scaling of the associated linear map.
- Dodgson condensation: An iterative method that reduces a matrix by replacing entries with determinants of neighboring 2×2 blocks and, after the first step, dividing by earlier elements.
- Gaussian elimination: A standard algorithm to solve linear systems and compute determinants by row-reducing a matrix to triangular form, typically using partial pivoting to avoid division by zero.
- Cofactor (Laplace) expansion: A determinant computation technique that expands along a row or column using minors and cofactors; easy to teach but computationally expensive for large matrices.
- Parallelizable: Describes an algorithm whose independent subcomputations can be executed simultaneously on multiple processors to reduce wall-clock time.
Reader FAQ
Who was Lewis Carroll in relation to this method?
Charles Dodgson, the mathematician who published the method, is better known by his pen name Lewis Carroll.
Does Dodgson condensation always avoid fractions?
For integer-input matrices the divisions are exact and intermediate matrices remain integral; otherwise fractional values can occur if the input is not integral.
Is condensation faster than Gaussian elimination?
Asymptotically it is not faster: both condensation and Gaussian elimination require O(n^3) operations.
What about zeros that would be used as denominators?
Dodgson advised rearranging rows/columns or adding multiples of rows to remove interior zeros before applying the method.
Is this method widely used in modern numerical libraries?
not confirmed in the source
How Lewis Carroll computed determinants Posted on 10 July 2023 by John Charles Dodgson, better known by his pen name Lewis Carroll, discovered a method of calculating determinants now known…
Sources
- How Lewis Carroll computed determinants
- Dodgson condensation
- Dodgson condensation: The historical and mathematical …
- Dodgson condensation – Wikipedia, the free encyclopedia
Related posts
- How uv got so fast: design choices behind a speedy Python installer
- How Lewis Carroll computed determinants: Dodgson condensation explained
- How to disable Chrome’s built-in AI features and remove Gemini