The Cauchy-Binet formula
ProvedClassicalGaps.cauchy_binet_detdeterminantslinear-algebramatrix-tree-theorem
For an real matrix and real matrix with , the Cauchy-Binet formula expresses as , summed over all -element subsets of , where (resp. ) is the submatrix of (resp. ) keeping only the columns (resp. rows) indexed by , reindexed to via the order isomorphism Finset.orderIsoOfFin.
This is a foundational, widely reusable linear-algebra identity (special cases include when , and the Gram determinant expansion). It is not yet in Mathlib. It is a child lemma of ClassicalGaps.kirchhoff_matrix_tree, where it is applied to the oriented incidence matrix to reduce a cofactor of the graph Laplacian to a sum of squared minors indexed by edge subsets.
Preamble
import Mathlib open Classical Matrix Finset
Formal statement
theorem ClassicalGaps.cauchy_binet_det {m n : ℕ} (hmn : m ≤ n) (A : Matrix (Fin m) (Fin n) ℝ) (B : Matrix (Fin n) (Fin m) ℝ) :
(A * B).det = ∑ S ∈ (Finset.univ : Finset (Fin n)).powersetCard m,
if hS : S.card = m then
(A.submatrix id (fun i : Fin m => (S.orderIsoOfFin hS i : Fin n))).det *
(B.submatrix (fun i : Fin m => (S.orderIsoOfFin hS i : Fin n)) id).det
else 0 := by sorry