Dodgson condensation
Encyclopedia
In mathematics
, Dodgson condensation is a method of computing the determinant
s 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), and so on, finishing with a 1 × 1 matrix, which has one entry, the determinant of the original 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 our original matrix is
, so after dividing we get
.
The process must be repeated to arrive at a 1 × 1 matrix.
We divide by the interior of our 3 × 3 matrix, which is just -5, giving us
. -8 is indeed the determinant of the original matrix.
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.
Let
be a square matrix, and for each 
denote by 
the matrix that results from 
by deleting the 
-th row and the 
-th column. Similarly, for
denote by 
the matrix that results from 
by deleting the 
-th and 
-th rows and the 
-th and 
-th columns.
Now note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix
of order 
, the matrix in the 
-th stage of the computation
(where the first stage
corresponds to the matrix 
itself) consists of all the connected minors of order 
of
, where a connected minor is the determinant of a connected 
sub-block of adjacent entries of 
. In particular, in the last stage 
we get a matrix containing a single element equal to the unique connected minor of order 
, namely the determinant of 
.
Denote
(up to sign, the 
-th minor of 
), and define a 
matrix
by
(Note that the first and last column of
are equal to those of the adjugate matrix
of
). The identity is now obtained by computing 
in two ways. First, we can directly compute the matrix product 
(using simple properties of the adjugate matrix, or alternatively using the formula for the expansion of a matrix determinant in terms of a row or a column)
to arrive at
where we use
to denote the 
-th entry of 
. The determinant of this matrix is 
.
Second, this is equal to the product of the determinants,
. But clearly
so the identity follows from equating the two expressions we obtained for
and dividing out by 
(this is allowed if one thinks of the identities as polynomial identities over the ring of polynomials in the 
indeterminate variables 
).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Dodgson condensation is a method of computing the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
s of square matrices. It is named for its inventor Charles Dodgson (better known as Lewis Carroll
Lewis Carroll
Charles Lutwidge Dodgson , better known by the pseudonym Lewis Carroll , was an English author, mathematician, logician, Anglican deacon and photographer. His most famous writings are Alice's Adventures in Wonderland and its sequel Through the Looking-Glass, as well as the poems "The Hunting of the...
). 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.
The General Method
This algorithm can be described in the following 4 steps:- Let A be the given n × n matrix. Arrange A so that no zeros occur in its interior. An explicit definition of interior would be all ai,j with
. We can do this using any operation that we could normally perform without changing the value of the determinant, such as adding a multiple of one row to another. - Create an (n − 1) × (n − 1) matrix B, consisting of the determinants of every 2 × 2 submatrix of A. Explicitly, we write
- Using this (n − 1) × (n − 1) matrix, perform step 2 to obtain an (n − 2) × (n − 2) matrix C. Divide each term in C by the corresponding term in the interior of A.
- Let A = B, and B = C. Repeat step 3 as necessary until the 1 × 1 matrix is found; its only entry is the determinant.
Without Zeros
We wish to findWe 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 our original matrix is
, so after dividing we get.The process must be repeated to arrive at a 1 × 1 matrix.
We divide by the interior of our 3 × 3 matrix, which is just -5, giving us
. -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.
The 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.Let
be a square matrix, and for each denote by the matrix that results from by deleting the -th row and the -th column. Similarly, for denote by the matrix that results from by deleting the -th and -th rows and the -th and -th columns.The Desnanot-Jacobi identity
Proof of the correctness of Dodgson condensation
Rewrite the identity asNow note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix
of order , the matrix in the -th stage of the computation(where the first stage
corresponds to the matrix itself) consists of all the connected minors of order of
, where a connected minor is the determinant of a connected sub-block of adjacent entries of . In particular, in the last stage we get a matrix containing a single element equal to the unique connected minor of order , namely the determinant of .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
(up to sign, the -th minor of ), and define a matrix
by(Note that the first and last column of
are equal to those of the adjugate matrixAdjugate matrix
In linear algebra, the adjugate or classical adjoint of a square matrix is a matrix that plays a role similar to the inverse of a matrix; it can however be defined for any square matrix without the need to perform any divisions....
of
). The identity is now obtained by computing in two ways. First, we can directly compute the matrix product (using simple properties of the adjugate matrix, or alternatively using the formula for the expansion of a matrix determinant in terms of a row or a column)to arrive at
where we use
to denote the -th entry of . The determinant of this matrix is .Second, this is equal to the product of the determinants,
. But clearlyso the identity follows from equating the two expressions we obtained for
and dividing out by (this is allowed if one thinks of the identities as polynomial identities over the ring of polynomials in the indeterminate variables ).External links
- Dodgson Condensation entry in MathWorldMathWorldMathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...