# Factor a sum of products of cofactors

Let $M$ be any $n\times n$ matrix.

We define the usual cofactors: $C_{i,j}$ is $(-1)^{i+j}$ times the determinant of the submatrix obtained by deleting row $i$ and column $j$ of $M$.

We can write the determinant of $M$ using Laplace expansion along column $p$ as:

$$\det M = \sum_{q=1}^n M_{q,p} C_{q,p}$$

Now, for any $k, p\in \{1,...,n\}$ consider the sum:

$$W_{n,p}(k) = \sum_{q=1}^n {M_{q,p} C_{q,p}^2 \prod_{j\ne q}{C_{j,k}}}$$

Clearly $W_{n,p}(p)$ can always be factored, with $\det M$ as one factor:

$$W_{n,p}(p) = \sum_{q=1}^n{M_{q,p} C_{q,p}^2 \prod_{j\ne q}{C_{j,p}}} = \sum_{q=1}^n{M_{q,p} C_{q,p} \prod_{j=1}^n{C_{j,p}}} = \left(\det M\right) \prod_{j=1}^n{C_{j,p}}$$

But in all the specific cases I've examined, $\det M$ appears as a factor of $W_{n,p}(k)$ even when $k\ne p$. For example, with $n=3$, $p=1$ and $k=2$:

$$W_{3,1}(2)=\sum_{q=1}^3{M_{q,1} C_{q,1}^2 \prod_{j\ne q}{C_{j,2}}}=\\ \left(\det M\right)\left(M_{2,2} M_{2,3} M_{3,1}^2 M_{1,3}^2+M_{2,1} M_{2,3} M_{3,1} M_{3,2} M_{1,3}^2-M_{2,1} M_{2,2} M_{3,1} M_{3,3} M_{1,3}^2-M_{2,1}^2 M_{3,2} M_{3,3} M_{1,3}^2-M_{1,2} M_{2,3}^2 M_{3,1}^2 M_{1,3}+M_{1,2} M_{2,1}^2 M_{3,3}^2 M_{1,3}+M_{1,1} M_{2,1} M_{2,2} M_{3,3}^2 M_{1,3}-M_{1,1} M_{2,3}^2 M_{3,1} M_{3,2} M_{1,3}-M_{1,1} M_{1,2} M_{2,1} M_{2,3} M_{3,3}^2-M_{1,1}^2 M_{2,2} M_{2,3} M_{3,3}^2+M_{1,1} M_{1,2} M_{2,3}^2 M_{3,1} M_{3,3}+M_{1,1}^2 M_{2,3}^2 M_{3,2} M_{3,3}\right)$$

It might be worth noting that the second factor here cannot be written as a linear combination of products of the cofactors, with purely numeric coefficients. This is in stark contrast to the case $k=p$, when the quotient is simply a product of cofactors.

I am seeking a proof that $\det M$ always divides $W_{n,p}(k)$, and a general formula for the quotient in the non-trivial case $k\ne p$.

• Is your $S_n(k)$ divisible by $\sum_{q=1}^n C_{q,1}$ if you don't require $M$ to have its first column filled with $1$'s? – darij grinberg Aug 1 '14 at 13:10
• If $M$ has no special properties $S_n(k)$ doesn't factor at all for $k\ne 1$ (at least for the low values of $n$ I'm able to check by explicit computations). – Greg Egan Aug 1 '14 at 13:48
• I've now generalised the question to apply to a matrix $M$ with no special properties. – Greg Egan Aug 2 '14 at 5:18
• This suggests an identity of Dodgson (yes a.k.a. Lewis Carroll). I may be misremembering, but the word "condensation" pops into my head when I look at this. – The Masked Avenger Aug 2 '14 at 5:49
• The quotient given for $p=1$, $k=2$ can be written as $\sum M_{h,p}M_{i,3}M_{j,3}(M_{h,k}C_{h,k}-M_{h,p}C_{h,p})$ where the sum is over the three cyclic permutations $(h,i,j)=(1,2,3)$ or $(2,3,1)$ or $(3,1,2)$. It probably won't help for $n>3$ unless you can generalize the $M_{i,3}M_{j,3}$ terms, since they come from "the column(s) not including column $p$ or $k$". I'm sure you already know your quotient in the $n=2$ (non-trivial) case is the permanent. – Zack Wolske Aug 2 '14 at 15:02

This is a proof that $\det M$ divides $W_{n,p}(k)$. I can assume that the entries of $M$ are variables of polynomial ring $\mathbb{C}[M_{11},\ldots,M_{nn}]$; then, it suffices to prove that points from the (irreducible) variety $\det M=0$ satisfy $W_{n,p}(k)=0$.
Indeed, let $M'$ be a generic point on this variety; denote by $v^i$ the $i$th column vector of $M'$. Since $M'$ is generic, there is $l\notin\{p,k\}$ such that $v^l=\sum_{t\neq l} \lambda_t v^t$ with all $\lambda_t$ nonzero. Then, the ratio of cofactors $C_{qp}/C_{qk}$ equals $\alpha=\lambda_p/\lambda_k$ and, in particular, it does not depend on $q$. We conclude $$W_{n,p}(k)=\sum\limits_{q=1}^{n}\,M'_{qp}C_{qp}^2\prod\limits_{j\neq q}C_{jk}=\sum\limits_{q=1}^{n}\,M'_{qp}C_{qp}\alpha\prod\limits_{j=1}^nC_{jk}=\alpha\prod\limits_{j=1}^nC_{jk}\cdot\left(\sum\limits_{q=1}^{n}\,M'_{qp}C_{qp}\right)=0.$$
• Nice work. Here is a minor variation on this argument, which is purely algebraic (completely avoiding any mention of varieties and generic points): Let $\Delta = \det M$. For any $u < v$ and $a < b$, we have $C_{ua} C_{vb} \equiv C_{ub} C_{vd} \mod \Delta$ (indeed, the Desnanot-Jacobi identity yields that $C_{ua} C_{vb} - C_{ub} C_{vd} = \pm \Delta m$, where $m$ is a certain $\left(n-2\right)\times\left(n-2\right)$-minor of $M$). We shall call this the 2-by-2 congruence. Now we can easily ... – darij grinberg Aug 18 at 13:31
• ... see that $C_{qp} \prod\limits_{j\neq q} C_{jk} \equiv C_{1p} \prod\limits_{j\neq 1} C_{jk} \mod \Delta$ for any $n$, $p$, $k$ and $q$ (indeed, for $q = 1$ this is obvious, whereas for $q > 1$ it follows from the 2-by-2 congruence $C_{qp} C_{1k} \equiv C_{1p} C_{qk} \mod \Delta$). Substituting this congruence into the definition of $W_{n,p}\left(k\right)$, we ... – darij grinberg Aug 18 at 13:34
• ... find $W_{n,p}\left(k\right) \equiv \sum\limits_{q=1}^n M_{qp} C_{qp} C_{1p} \prod\limits_{j\neq 1} C_{jk} = \underbrace{\left(\sum\limits_{q=1}^n M_{qp} C_{qp}\right)}_{= \det M = \Delta \equiv 0 \mod \Delta} C_{1p} \prod\limits_{j\neq 1} C_{jk} \equiv 0 \mod \Delta$, qed. – darij grinberg Aug 18 at 13:34