Dodgson condensation

One wishes to find

${\displaystyle {\begin{vmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{vmatrix}}.}$

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.

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}-2&-1\\-1&-2\end{vmatrix}}&{\begin{vmatrix}-1&-1\\-2&-1\end{vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\\\{\begin{vmatrix}-1&-2\\-1&-1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\\\{\begin{vmatrix}-1&-1\\2&1\end{vmatrix}}&{\begin{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\begin{vmatrix}2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.}$

We then find another matrix of determinants:

${\displaystyle {\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}\\\\{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}-16&2\\4&12\end{bmatrix}}.}$

We must then divide each element by the corresponding element of our original matrix. The interior of the original matrix is ${\displaystyle {\begin{bmatrix}-2&-1\\-1&2\end{bmatrix}}}$, so after dividing we get ${\displaystyle {\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}}$. The process must be repeated to arrive at a 1 × 1 matrix. ${\displaystyle {\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}40\end{bmatrix}}.}$ Dividing by the interior of the 3 × 3 matrix, which is just −5, gives ${\displaystyle {\begin{bmatrix}-8\end{bmatrix}}}$ and −8 is indeed the determinant of the original matrix.

Simply writing out the matrices:

${\displaystyle {\begin{bmatrix}2&-1&2&1&-3\\1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\end{bmatrix}}\to {\begin{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\end{bmatrix}}\to {\begin{bmatrix}-15&6&12\\0&0&6\\6&-6&8\end{bmatrix}}.}$

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:

${\displaystyle {\begin{bmatrix}1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\\2&-1&2&1&-3\end{bmatrix}}\to {\begin{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\to {\begin{bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\to {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\to {\begin{bmatrix}36\end{bmatrix}}.}$

Hence, we arrive at a determinant of 36.

${\displaystyle \det(M)\det(M_{1,k}^{1,k})=\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}).}$

Rewrite the identity as

${\displaystyle \det(M)={\frac {\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1})}{\det(M_{1,k}^{1,k})}}.}$

Now note that by induction it follows that when applying the Dodgson condensation procedure to a square matrix ${\displaystyle A}$ of order ${\displaystyle n}$, the matrix in the ${\displaystyle k}$-th stage of the computation (where the first stage ${\displaystyle k=1}$ corresponds to the matrix ${\displaystyle A}$ itself) consists of all the connected minors of order ${\displaystyle k}$ of ${\displaystyle A}$, where a connected minor is the determinant of a connected ${\displaystyle k\times k}$ sub-block of adjacent entries of ${\displaystyle A}$. In particular, in the last stage ${\displaystyle k=n}$, one gets a matrix containing a single element equal to the unique connected minor of order ${\displaystyle n}$, namely the determinant of ${\displaystyle A}$.

We follow the treatment in Bressoud's book; for an alternative combinatorial proof see the paper by Zeilberger. Denote ${\displaystyle a_{i,j}=(-1)^{i+j}\det(M_{i}^{j})}$ (up to sign, the ${\displaystyle (i,j)}$-th minor of ${\displaystyle M}$), and define a ${\displaystyle k\times k}$ matrix ${\displaystyle M'}$ by

${\displaystyle M'={\begin{pmatrix}a_{1,1}&0&0&0&\ldots &0&a_{k,1}\\a_{1,2}&1&0&0&\ldots &0&a_{k,2}\\a_{1,3}&0&1&0&\ldots &0&a_{k,3}\\a_{1,4}&0&0&1&\ldots &0&a_{k,4}\\\vdots &\vdots &\vdots &\vdots &&\vdots &\vdots \\a_{1,k-1}&0&0&0&\ldots &1&a_{k,k-1}\\a_{1,k}&0&0&0&\ldots &0&a_{k,k}\end{pmatrix}}.}$

(Note that the first and last column of ${\displaystyle M'}$ are equal to those of the adjugate matrix of ${\displaystyle A}$). The identity is now obtained by computing ${\displaystyle \det(MM')}$ in two ways. First, we can directly compute the matrix product ${\displaystyle MM'}$ (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

${\displaystyle MM'={\begin{pmatrix}\det(M)&m_{1,2}&m_{1,3}&\ldots &m_{1,k-1}&0\\0&m_{2,2}&m_{2,3}&\ldots &m_{2,k-1}&0\\0&m_{3,2}&m_{3,3}&\ldots &m_{3,k-1}&0\\\vdots &\vdots &\vdots &&\vdots &\vdots &\vdots \\0&m_{k-1,2}&m_{k-1,3}&\ldots &m_{k-1,k-1}&0\\0&m_{k,2}&m_{k,3}&\ldots &m_{k,k-1}&\det(M)\end{pmatrix}}}$

where we use ${\displaystyle m_{i,j}}$ to denote the ${\displaystyle (i,j)}$-th entry of ${\displaystyle M}$. The determinant of this matrix is ${\displaystyle \det(M)^{2}\cdot \det(M_{1,k}^{1,k})}$.
Second, this is equal to the product of the determinants, ${\displaystyle \det(M)\cdot \det(M')}$. But clearly
${\displaystyle \det(M')=a_{1,1}a_{k,k}-a_{k,1}a_{1,k}=\det(M_{1}^{1})\det(M_{k}^{k})-\det(M_{1}^{k})\det(M_{k}^{1}),}$
so the identity follows from equating the two expressions we obtained for ${\displaystyle \det(MM')}$ and dividing out by ${\displaystyle \det(M)}$ (this is allowed if one thinks of the identities as polynomial identities over the ring of polynomials in the ${\displaystyle k^{2}}$ indeterminate variables ${\displaystyle (m_{i,j})_{i,j=1}^{k}}$).