# Cauchy-Binet formula: general form

In Wikipedia, the Cauchy-Binet formula is stated for determinant of product of matrices $A_{m\times n}$ and $B_{n\times m}$.

However, Handbook of Linear Algebra state the formula (without proof) as

A $k\times k$ minor in product $AB$ can be obtained as sum of products of $k\times k$ minors in $A$ and $k\times k$ minors in $B$. More precisely let $\alpha,\beta,\gamma$ denotes $k$-tuples of increasing sequences of positive integers (within maximum sizes of matrices $A,B$). Let $A[\alpha,\beta]$ denote the $k\times k$ minor of $A$ whose $k$ rows are w.r.t indices in $\alpha$ and $k$ columns are w.r.t. indices in $\beta$. Then $$(AB)[\alpha,\beta] = \sum_{\gamma} A[\alpha,\gamma]B[\gamma,\beta],$$ where sum is over all $k$-tuples $\gamma$ of increasing sequence of positive integers (within maximum sizes of matrices $A,B$).

Q.1 Where can I find the proof of this generalized Cauchy-Binet formula?

In many books of matrices, I didn't find its proof (except proof of determinant expansion of product $AB$- the largest minor when sizes of $A,B$ are dual i.e. if $A$ has size $m\times n$, then $B$ has size $n\times m$.)

Q.2 Can one state some reference or book which contains interesting applications of this formula.

(Let me know if there is anything missing in above expansion formula; you may edit as well for correction.)

• We can see this formula as a consequence of the functoriality of $\Lambda^k$ (the $k$th exterior power). The coefficients of the matrix of $\Lambda^k f$ are the $k×k$ minors of the matrix of $f$. Then, $\Lambda^k (f \circ g) = (\Lambda^k f) \circ (\Lambda^k g)$ translates as the given formula. – Idéophage Mar 5 '19 at 13:30

Question 1: For example, there is a proof in Volume 1 of Gantmacher's classic The Theory of Matrices. (It's in Chapter 1, §4, as a corollary of Cauchy–Binet from §2.)

to Question 1: See the proof of Corollary 7.182 in my Notes on the combinatorial fundamentals of algebra, 10th of January 2019.

to Question 2: This generalized Cauchy-Binet formula appears as (1.10) in Masatoshi Noumi, Yasuhiko Yamada, Tropical Robinson-Schensted-Knuth correspondence and birational Weyl group actions, arXiv:math-ph/0203030v2. They use it as an alternative to the standard "sign-reversing involution" proof of the Lindström-Gessel-Viennot theorem in the particular case when the digraph is a lattice of a specific form (see their Proposition 1.1, for example). I don't think this formula is strong enough to prove the Lindström-Gessel-Viennot theorem in full generality, but I would not be surprised if it can extend it in a different direction.