Dodgson condensation

Encyclopedia : D : DO : DOD : Dodgson condensation

In mathematics, Dodgson condensation is a method of computing the determinants of square matrices. It is named for its inventor Charles Dodgson (better known as Lewis Carroll). The method in the case of an n × n matrix is to construct an (n − 1) × (n − 1) matrix, an (n − 2) × (n − 2), as so on, finishing with a 1 × 1 matrix, which has one entry, the determinant of the original matrix.

The first stage, in the case of an n x n matrix, is to generate an (n − 1) × (n − 1) matrix, made up of the determinants of the 2 × 2 connected submatrices. For example, in the case of the matrix

[\begin5 & 1 & 0 \\2 & 8 & 5 \\ 0 & 6 & 7\end,]

the submatrices are

[\begin 5 & 1\\2 & 8\end, \begin1 & 0 \\8 & 5 \end,\begin2 & 8 \\ 0 & 6 \end,\begin8 & 5 \\ 6 & 7 \end.]

The determinants of these will be the entries of the 2 × 2 matrix. In particular the entry in row r, column c is the determinant of the 2 × 2 submatrix of the original matrix with row r and column c in the top left corner. In this case the top left corner of the 2 × 2 matrix is the determinant of the submatrix

[\begin 5 & 1\\2 & 8\end. ]

For the other matrices, the k × k matrix is generated by taking the determinants of the 2 × 2 submatrices of the (k + 1) × (k + 1) matrices, as above, and dividing them by the corresponding entries in the central submatrix (i.e. the matrix generated by removing the top and bottom rows, and left and right-hand columns), of the (k + 2) × (k + 2) matrix.

References and further reading

Bressoud, David M., Proofs and Confirmations, MAA Spectrum, Mathematical Associations of America, Washington, D.C., 1999.
Bressoud, David M. and Propp, James, How the alternating sign matrix conjecture was solved, Notices of the American Mathematical Society, 46 (1999), 637-646.
Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Proof of the Macdonald conjecture, Inventiones Mathematicae, 66 (1982), 73-87.
Mills, William H., Robbins, David P., and Rumsey, Howard, Jr., Alternating sign matrices and descending plane partitions, Journal of Combinatorial Theory, Series A, 34 (1983), 340-359.
Robbins, David P., The story of [1, 2, 7, 42, 429, 7436, \cdots], The Mathematical Intelligencer, 13 (1991), 12-19.

External links

[Dodgson Condensation] entry in MathWorld

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.