TL;DR
Charles Dodgson (Lewis Carroll) devised a hand-friendly algorithm for determinants now called Dodgson condensation or the method of contractants. The procedure repeatedly compresses a matrix using 2×2 determinants, requires careful handling of divisions by zero, and matches Gaussian elimination in asymptotic cost while preserving integer entries for integer input.
What happened
In an 1867 note, Charles Dodgson (better known as Lewis Carroll) described a technique for computing determinants that iteratively "condenses" a matrix: each step produces a smaller matrix whose entries are determinants of adjacent 2×2 blocks from the previous matrix. After removing the bottom row and rightmost column at each condensation step, later stages divide those 2×2 determinants by specific entries from two steps earlier to continue the process. Dodgson’s exposition is readable but leaves an ambiguity about which element should appear in the denominator in some examples. The method was illustrated on a 4×4 matrix whose determinant computes to 228, which can be verified with standard software. Dodgson advised rearranging rows or columns or adding multiples of rows to eliminate interior zeros so the required divisions do not hit zero. The algorithm is practical for hand calculation and also amenable to machine implementation.
Why it matters
- Condensation scales as O(n³), the same asymptotic cost as Gaussian elimination, so it competes with standard methods for larger matrices.
- When the input matrix has integer entries, condensation performs only exact integer divisions, so intermediate matrices remain integral.
- Unlike Gaussian elimination, which can produce non-integer intermediates from integer input, condensation preserves integrality of intermediate values.
- The local 2×2 determinant computations are independent and thus the method is naturally parallelizable.
- The method historically aimed to simplify hand computation of determinants and still offers practical features for modern computation.
Key facts
- The method is known as the method of contractants, Dodgson condensation, or simply condensation.
- Each condensation step replaces matrix entries with determinants of 2×2 blocks formed by the element and its south, east, and southeast neighbors.
- After the first condensation, later steps divide each new 2×2 determinant by an element from two steps earlier in the sequence.
- Dodgson published the method in 1867; his paper is noted as readable but with some notational ambiguity about denominator subscripts.
- A worked example on a 4×4 matrix in the source produces a determinant of 228 (verifiable with Mathematica).
- The algorithm requires avoiding division by zero; Dodgson recommends rearranging rows/columns or adding multiples of rows to remove interior zeros.
- If the original matrix entries are integers, the divisions in the algorithm are exact and the sequence of matrices remains integral.
- Condensation has the same O(n³) operation count as Gaussian elimination with partial pivoting.
- Each 2×2 determinant in a condensation step can be computed in parallel because computations are local and independent.
What to watch next
- Whether rearrangement or row operations to remove interior zeros are needed for reasons beyond avoiding division by zero is not confirmed in the source.
- A possible conceptual connection between condensation and numerical deflation techniques (e.g., in QR algorithms) was suggested by a commenter but is not confirmed in the source.
- The precise index choice for the denominator in some of Dodgson’s examples (whether to use subscripts i,j or i+1,j+1) is ambiguous in the original paper according to the author.
Quick glossary
- Determinant: A scalar value associated with a square matrix that can characterize invertibility and volume scaling of the linear map represented by the matrix.
- Dodgson condensation: An algorithm that computes a matrix determinant by iteratively forming smaller matrices from 2×2 determinants of adjacent entries and dividing by prior elements.
- Gaussian elimination: A standard method for solving linear systems and computing determinants by transforming a matrix to upper triangular form, typically with partial pivoting.
- Cofactor (Laplace) expansion: A rule that computes a determinant by expanding along a row or column into smaller minors; conceptually simple but exponential in naive cost.
- Partial pivoting: A tactic in Gaussian elimination that swaps rows to place a nonzero (or larger magnitude) pivot on the diagonal to avoid division by zero or reduce numerical error.
Reader FAQ
Who discovered the condensation method?
Charles Dodgson, better known as Lewis Carroll, described the method in an 1867 paper.
Is condensation faster than Gaussian elimination?
No; both condensation and Gaussian elimination have O(n³) operation counts, though condensation is easier to do by hand and parallelize.
Does condensation handle integer matrices without producing fractions?
Yes. For integer-input matrices the divisions in Dodgson’s method are exact, so intermediate matrices remain integral.
Does the method avoid division by zero automatically?
No. Dodgson recommends rearranging rows or adding multiples of rows to eliminate interior zeros; whether further preparation is required is 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
- Lewis Carroll Computed Determinants
- Dodgson condensation
- Dodgson condensation – Wikipedia, the free encyclopedia
- Condensation — from Wolfram MathWorld
Related posts
- How to disable Chrome’s built-in AI features and remove Gemini
- Researchers Identify New Mushroom That Triggers ‘Little People’ Hallucinations
- Proclamation: Restoring the Em—Dash and Reclaiming Punctuation from AI