Dodgson condensation

In mathematics, Dodgson condensation or method of contractants is a method of computing the determinants of square matrices. It is named for its inventor, Charles Lutwidge Dodgson (better known by his pseudonym, as Lewis Carroll, the popular author). The method in the case of an "n" × "n" matrix is to construct an ("n" − 1) × ("n" − 1) matrix, an ("n" − 2) × ("n" − 2), and so on, finishing with a 1 × 1 matrix, which has one entry, the determinant of the original matrix.
General method.
This algorithm can be described in the following four steps:
Examples.
Without zeros.
One wishes to find
All of the interior elements are non-zero, so there is no need to re-arrange the matrix.
We make a matrix of its 2 × 2 submatrices.
We then find another matrix of determinants:
We must then divide each element by the corresponding element of our original matrix. The interior of the original matrix is
formula_7, so after dividing we get
formula_8.
The process must be repeated to arrive at a 1 × 1 matrix.
formula_9
Dividing by the interior of the 3 × 3 matrix, which is just −5, gives formula_10 and −8 is indeed the determinant of the original matrix.
With zeros.
Simply writing out the matrices:
Here we run into trouble. If we continue the process, we will eventually be dividing by 0. We can perform four row exchanges on the initial matrix to preserve the determinant and repeat the process, with most of the determinants precalculated:
Hence, we arrive at a determinant of 36.
Desnanot–Jacobi identity and proof of correctness of the condensation algorithm.
The proof that the condensation method computes the determinant of the matrix if no divisions by zero are encountered is based on an identity known as the Desnanot–Jacobi identity (1841) or, more generally the Sylvester determinant identity (1851).
Let formula_13 be a square matrix, and for each formula_14, denote by formula_15 the matrix that results from formula_16 by deleting the formula_17-th row and the formula_18-th column. Similarly, for
formula_19, denote by formula_20 the matrix that results from formula_16 by deleting the formula_17-th and formula_18-th rows and the formula_24-th and formula_25-th columns.
Proof of the correctness of Dodgson condensation.
Rewrite the identity as
Now note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix formula_28 of order formula_29, the matrix in the formula_30-th stage of the computation (where the first stage formula_31 corresponds to the matrix formula_28 itself) consists of all the "connected minors" of order formula_30
of formula_28, where a connected minor is the determinant of a connected formula_35 sub-block of adjacent entries of formula_28. In particular, in the last stage formula_37, one gets a matrix containing a single element equal to the unique connected minor of order formula_29, namely the determinant of formula_28.
Proof of the Desnanot-Jacobi identity.
We follow the treatment in Bressoud's book; for an alternative combinatorial proof see the paper by Zeilberger.
Denote formula_40 (up to sign, the formula_41-th minor of formula_16), and define a formula_35
matrix formula_44 by
to arrive at
where we use formula_51 to denote the formula_41-th entry of formula_16. The determinant of this matrix is formula_54.
Second, this is equal to the product of the determinants, formula_55. But clearly
formula_56
so the identity follows from equating the two expressions we obtained for formula_48 and dividing out by formula_58 (this is allowed if one thinks of the identities as polynomial identities over the ring of polynomials in the formula_59 indeterminate variables formula_60).