Generalized Cauchy-Binet sum over a fixed subset of indices

Question

I originally posted this on math.stackexchange, but it quickly got buried. I removed it not too long after, thinking of rewriting it for MO, but I didn’t have a chance to post it until now. Apologies if you were one of the lucky 24 people who already saw it there.

Background

The Cauchy-Binet formula states that

$$ \det(AB) = \sum_{S\in\tbinom{[n]}m} \det(A_{[m],S})\det(B_{S,[m]}), $$

where $A$ is an $m$ by $n$ matrix, $B$ is an $n$ by $m$ matrix, $[n]$ is notation for the set $\{1,\dots,n\}$ (similarly for $[m]$), $\binom{[n]}{m}$ is the set of all $m$-element subsets of $[n]$, and if $M$ is a $k$ by $l$ matrix and $J,K$ are subsets of $[k],[l]$, respectively, then $M_{J,K}$ denotes the submatrix of $M$ consisting of rows indexed by $J$ and columns indexed by $K$.

Question

Is there a version of the Cauchy-Binet formula to evaluate the following sum for general integers $0\leq j\leq m$?

$$ ? = \sum_{S\in\tbinom{[n-j]}{m-j}} \det(A_{[m],S\cup T})\det(B_{S\cup T,[m]})\quad\quad (*)$$

Here $T=\{n-j+1,\dots,n\}$ so that the columns labeled by $T$ are forced to appear in the submatrices of $A$ included in the sum, and similarly for rows $n-j+1,\dots,n$ in the submatrices of $B$.

When $A^T=B$ is the incidence matrix for a graph $G$, then Kirchhoff's matrix-tree theorem and effective resistance formula imply that I can compute this sum as the determinant of the Laplacian matrix of the graph $G'$, where $G'$ is $G$ where all the edges indexed by $n-j+1,\dots,n$ have been contracted. The motivation of this question is thus to try to understand contraction in a slightly more general setting.

This paper by Konstantopoulos gives a nice coordinate-free version of Cauchy-Binet, but I couldn't wrangle it into what I wanted.

It may also be possible that evaluating this is equivalent to evaluating the permanent or something so I shouldn’t expect anything nice after all. But I would be quite disappointed if that were so.

Other special cases

When $j=0$, $(*)$ reduces to ordinary Cauchy-Binet, and when $j=m$ it is of course just $\det(A_{[m],T}B_{T,[m]})$.

When $j=1$, $(*)$ is equal to $\det(AB)-\det(A_{[m],[n-1]}B_{[n-1],[m]})$, and by using inclusion-exclusion I can extend this to all the other $j$. However, for large $j$, there will be a mess of terms, and it will be a rather inefficient way of evaluating this sum. Is there a simpler formula just involving one determinant?

Update (13 Oct 2014)

While I quite like the answer of Igor Khavkine, I would still like to know if there are any other quick ways to evaluate this. Is there any faster way? If the polynomial trick is the best, then are there some efficient ways to extract the leading coefficient of a polynomial? Interpolation can get me all $j+1$ coefficients, and thus requires $j+1$ evaluations of the determinant. It seems to me that if I have a bound on the other coefficients, I could just evaluate the determinant once with a large value of $x$ then divide by $x^j$ and then round off everything else.

Answer 1

This is probably a bit late, but the following formula is proved in this paper (Eq. S4 in the Supplementary Material):

\begin{equation} \sum_{S \in \binom{[n - j]}{m - j}} \det(A_{[m], S \cup T}) \det(B_{S\cup T, [m]}) = (-1)^{j} \det \left(\begin{array}{c c} \mathbf{0}_{j \times j} & B_{T, [m]} \\ A_{[m], T} & A_{[m], [n - j]}B_{[n - j], [m]} \end{array} \right) \rm{,} \end{equation}

where $0_{j \times j}$ is the $j \times j$ matrix of all zeroes. I'll leave the detailed proof to the paper, but the essential idea is to apply the Laplace expansion by complementary minors formula to the columns $T$ of $A$ and rows $T$ of $B$, rearrange sums to apply the ordinary Cauchy-Binet formula over $S$, and then recognize what remains as another expansion by complimentary minors of the above matrix on the r.h.s. The $j \times j$ block of zeros is to ensure that the minors you don't want to count end up vanishing, much along the same lines as Adam Przeździecki's answer. Notice that the special case for $j = 0$ is the ordinary Cauchy-Binet formula.

Answer 2

Let $I_j(x)$ be the diagonal $n\times n$ matrix with all 1's on the diagonal, except the last $j$ elements, where a 1 is replaced by an $x$. I believe that the identity you are looking for is $$ [x^j] \det(A I_j(x) B) = \sum_{S\in\binom{[n-j]}{m-j}} \det(A_{[m],S\cup T}) \det(B_{S\cup T,[m]}) , $$ where the notation $[x^j]$ denotes the coefficient of $x^j$ in whatever follows it, which is a polynomial in $x$. If you apply the standard Cauchy-Binet formula to $\det(A I_j(x) B)$, then the only way to get $j$ powers of $x$ is from the terms that involve the columns of $A$ or rows of $B$ that you want to keep fixed.

You can write $I_j(x) = Q_j + x P_j$, where $Q_j$ and $P_j$ are projections defined in the obvious way. So, essentially, you want the highest power of $x$ from the polynomial $\det (AQ_j B + x A P_j B)$.

Answer 3

You may modify one of your matrices without changing any of the relevant determinants. Lets choose $B$. Write $$ B = \begin{bmatrix} B_{[n-j],[m]} \\ \hline B_T \end{bmatrix} $$ If the rank of $B_T$ is less than $j$ then all the determinants $\det(B_{S\cup T,[m]})$ are $0$. Otherwise, assume for simplicity that the first $j$ columns of $B_T$ are linearly independent. You may apply row operations to $B_T$ so as to obtain $$ B' = \begin{bmatrix} \begin{matrix} B_{[n-j],[m]} \end{matrix} \\ \hline \begin{matrix} D & \vert &B_T' \end{matrix} \end{bmatrix} $$ where $D$ is some nonsingular diagonal matrix and the interesting determinants don't change. Then subtract from the rows of $B_{[n-j],[m]}$ suitable multiplicities of the last $j$ rows so as to obtain the matrix $$ B'' = \begin{bmatrix} 0 & \vert & * \\ \hline D & \vert & B_T' \end{bmatrix} $$ The interesting determinants are still the same. Now you apply the usual Cauchy-Binet formula to the product $AB''$ and see that all the determinants you didn't want to count are null.

Note that the algorithm described by Igor Khavkine, although slower, still has its value. Write $[n_1]=\{1,2,\ldots,n_1\}$, $[n_2]=\{n_1+1,n_1+2,\ldots,n\}$ and $m=m_1+m_2$. An obvious modification of his algorithm will count the following $$ \sum_{s_1\in\tbinom{[n_1]}{m_1}}\sum_{s_2\in\tbinom{[n_2]}{m_2}} \det(A_{[m],s_1\cup s_2})\det(B_{s_1\cup s_2,[m]}) $$

Answer 4

The application I originally had in mind was the following. I was interested in studying a probability measure on the bases of a certain linear matroid, represented by the rows of a matrix $M$. The probability of a base here is proportional to the corresponding term in the Cauchy-Binet expansion of $\det(M^tM)$ (with $M^t$ the transpose of $M$). I was hoping to compute the probability that a base would contain any given set of elements of the ground set by evaluating sums like the above.

It turns out this is a well-studied situation. The above probability measure turns out to be determinantal, as explained in the paper "Determinantal Probability Measures" by Russ Lyons. In this case it means that one can compute the probability of a random base containing a set of elements $T$ by first computing a certain projection matrix and then taking the principal minor corresponding to rows and columns labeled by $T$. (Thus in the case $A=B^t$, we can compute the sums in the question by taking this probability and multiplying by the normalizing factor $\det(B^tB)$.)

For my purposes, what was more important is that there's a pretty good algorithm for exact sampling from this distribution, described in "Determinantal Processes and Independence" by Hough, Krishnapur, Peres and Virág.