---
tag: F7D849A4RZ
kind: definition
name: Dodgson condensation
msc: [15A15, 65F40]
defines: RQ44FKS5QM
uses: [00KDZRW4C0, 0BT9BYWVRY, 04C5ZBG1WT]
sources:
  - url: https://en.wikipedia.org/wiki/Dodgson_condensation
---

## Definition

Let $F$ be a [[field|04C5ZBG1WT]], let $n \ge 2$, and let $A$ be an $n \times n$ matrix over $F$.
Let $A^{(-1)}$ be the $(n+1) \times (n+1)$ matrix with all entries $1$, and let $A^{(0)} = A$.
For $k = 1, \dots, n-1$, let $A^{(k)}$ be the $(n-k) \times (n-k)$ matrix with entries
$$a^{(k)}_{ij} = \frac{a^{(k-1)}_{ij}\, a^{(k-1)}_{i+1,j+1} - a^{(k-1)}_{i,j+1}\, a^{(k-1)}_{i+1,j}}{a^{(k-2)}_{i+1,j+1}}, \qquad 1 \le i, j \le n-k.$$
This is defined when every divisor $a^{(k-2)}_{i+1,j+1}$ is nonzero.
*Dodgson condensation* is the computation of the sequence $A^{(0)}, A^{(1)}, \dots, A^{(n-1)}$.
When it is defined, the single entry of $A^{(n-1)}$ equals the [[determinant|00KDZRW4C0]] of $A$.

## Remarks

The divisors in step $k$ are the interior entries of $A^{(k-2)}$, that is, the entries not in its first or last row or column.
For $k = 1$ all divisors are $1$, so $A^{(1)}$ is the matrix of connected $2 \times 2$ [[minors|0BT9BYWVRY]] of $A$.

Example: for $A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{pmatrix}$, the first step gives $A^{(1)} = \begin{pmatrix} -3 & -3 \\ -3 & 2 \end{pmatrix}$.
The only divisor in the second step is the central entry $5$ of $A$, so $A^{(2)} = \big((-3)(2) - (-3)(-3)\big)/5 = -3$.
Expansion along the first row also gives $\det A = 2 + 4 - 9 = -3$.

Non-example: for $A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$, the central entry is $0$, so $A^{(2)}$ is not defined, although $\det A = -1$.
In such a case one can first permute rows or columns, or use a different order of elimination.
The correctness of the method follows from the Desnanot–Jacobi identity, a form of the case $k = n - 2$ of [[Sylvester's determinant identity|7SSKBQYFW1]].

## Explanations

### L1 human

The method shrinks a matrix by one row and one column at each step, using only $2 \times 2$ determinants and divisions.
It stops when one number is left, and that number is the determinant.
It fails when it must divide by zero.