Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The Cauchy-Binet formula

Proved
ClassicalGaps.cauchy_binet_det

by Rizwan G Mir · Sep 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

determinantslinear-algebramatrix-tree-theorem

For an m×nm \times nm×n real matrix AAA and n×mn \times mn×m real matrix BBB with m≤nm \le nm≤n, the Cauchy-Binet formula expresses det⁡(AB)\det(AB)det(AB) as ∑Sdet⁡(AS)det⁡(BS)\sum_{S} \det(A_S)\det(B_S)∑S​det(AS​)det(BS​), summed over all mmm-element subsets SSS of {1,…,n}\{1,\dots,n\}{1,…,n}, where ASA_SAS​ (resp. BSB_SBS​) is the m×mm\times mm×m submatrix of AAA (resp. BBB) keeping only the columns (resp. rows) indexed by SSS, reindexed to Fin m\mathrm{Fin}\,mFinm via the order isomorphism Finset.orderIsoOfFin.

This is a foundational, widely reusable linear-algebra identity (special cases include det⁡(AB)=det⁡Adet⁡B\det(AB)=\det A\det Bdet(AB)=detAdetB when m=nm=nm=n, 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me