A method of computing the determinant of a square matrix due to Charles Dodgson (1866) (who is more famous under his pseudonym Lewis Carroll). The method is useful for hand calculations because, for an integer matrix, all entries in submatrices computed along the way must also be integers. The method is also implemented efficiently in a parallel computation. Condensation is also known as the method of contractants (Macmillan 1955, Lotkin 1959).
Given an matrix, condensation successively computes an matrix, an matrix, etc., until arriving at a matrix whose only entry ends up being the determinant of the original matrix. To compute the matrix (), take the connected subdeterminants of the matrix and divide them by the central entries of the matrix, with no divisions performed for . The matrices arrived at in this manner are the matrices of determinants of the connected submatrices of the original matrices.
For example, the first condensation of the matrix
|
(1) |
yields the matrix
|
(2) |
and the second condensation yields
|
(3) |
which is the determinant of the original matrix. Collecting terms gives
|
(4) |
of which the nonzero terms correspond to the permutation matrices. In the case, 24 nonzero terms are obtained together with 18 vanishing ones. These 42 terms correspond to the alternating sign matrices for which any s in a row or column must have a "outside" it (i.e., all s are "bordered" by s).