4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Idéophage Mar 5 at 13:30
2
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.