AFTD Auto-Formalizing Theoretical Domains

cauchyBinet

theoremverifiedformalizationimported Lean

Cauchy–Binet formula for rectangular matrices: if A is m × n and B is n × m, then det(A * B) = ∑_S det(A[:,S]) * det(B[S,:]) where the sum is over m-element subsets S of the column/row index.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BigOperators Matrix in
variable {d : Type*} [Fintype d] [DecidableEq d] in
set_option maxHeartbeats 400000 in
lemma cauchyBinet {m : ℕ} {n : Type*} [Fintype n] [DecidableEq n] [LinearOrder n]
    {R : Type*} [CommRing R]
    (A : Matrix (Fin m) n R) (B : Matrix n (Fin m) R) :
    (A * B).det = ∑ S : {S : Finset n // S.card = m},
      (A.submatrix id (S.1.orderEmbOfFin S.2)).det *
      (B.submatrix (S.1.orderEmbOfFin S.2) id).det
Formalizes
QuantumInfo, `cauchyBinet`
Lean proof
By Alex Meiburg, from github.com/leanprover-community/physlib at e411c6e89692 (Copyright (c) 2026 Alex Meiburg. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.34.1.
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • cauchy_binet_detFor any commutative ring R, natural numbers m and n, and matrices A : Matrix (Fin m) (Fin n) R and B : Matrix (Fin n) (Fin m) R, the…

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BigOperators Matrix in
variable {d : Type*} [Fintype d] [DecidableEq d] in
set_option maxHeartbeats 400000 in
/-- **Cauchy–Binet formula** for rectangular matrices: if `A` is `m × n` and `B` is `n × m`, then `det(A * B) = ∑_S det(A[:,S]) * det(B[S,:])` where the sum is over `m`-element subsets `S` of the column/row index. -/
lemma cauchyBinet {m : ℕ} {n : Type*} [Fintype n] [DecidableEq n] [LinearOrder n]
    {R : Type*} [CommRing R]
    (A : Matrix (Fin m) n R) (B : Matrix n (Fin m) R) :
    (A * B).det = ∑ S : {S : Finset n // S.card = m},
      (A.submatrix id (S.1.orderEmbOfFin S.2)).det *
      (B.submatrix (S.1.orderEmbOfFin S.2) id).det := by
  have h_cauchy_binet : ∀ (A : Matrix (Fin m) n R) (B : Matrix n (Fin m) R), Matrix.det (A * B) = ∑ σ : Fin m → n, (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) := by
    simp [Matrix.det_apply']
    simp [Matrix.mul_apply, Finset.mul_sum]
    intro A B; rw [← Finset.sum_comm]; congr; ext x; simp [mul_comm]
    simp only [prod_sum, sum_mul]
    refine' Finset.sum_bij (fun f _ => fun i => f (x.symm i) (Finset.mem_univ _)) _ _ _ _
    · simp
    · simp only [univ_pi_univ, mem_univ, funext_iff, forall_true_left, forall_const]
      exact fun a₁ a₂ h i => by simpa using h (x i)
    · simp only [mem_univ, univ_pi_univ, exists_const, forall_const]
      exact fun b => ⟨fun i _ => b (x i), by ext i; simp⟩
    · simp only [univ_pi_univ, mem_univ, prod_mul_distrib, prod_attach_univ,
      Equiv.symm_apply_apply, forall_const]
      intro a
      rw [← Equiv.prod_comp x.symm]
      ring_nf
      rw [← Equiv.prod_comp x.symm]
      simp only [mul_comm, mul_assoc]
      conv_rhs => rw [← Equiv.prod_comp x]
      simp [Equiv.symm_apply_apply]
  -- Split the sum into injective and non-injective functions.
  have h_split : ∑ σ : Fin m → n, (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) = ∑ σ : Fin m → n, if Function.Injective σ then (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) else 0 := by
    refine Finset.sum_congr rfl fun σ _ => ?_
    split_ifs with hσ <;> simp_all [Function.Injective]
    obtain ⟨i, j, hij, hne⟩ := hσ
    exact mul_eq_zero_of_right _ (Matrix.det_zero_of_row_eq hne (by ext1; simp only [of_apply, hij]))
  -- Group the sum by the image of the injective functions.
  have h_group : ∑ σ : Fin m → n, (if Function.Injective σ then (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) else 0) = ∑ S : {S : Finset n // S.card = m}, ∑ σ : Fin m → n, (if Function.Injective σ ∧ Finset.image σ Finset.univ = S.val then (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) else 0) := by
    rw [← Finset.sum_comm, Finset.sum_congr rfl]
    intro σ _
    by_cases hσ : Function.Injective σ
    · simp [hσ]
      rw [Finset.sum_eq_single ⟨Finset.image σ Finset.univ, by simp [Finset.card_image_of_injective _ hσ]⟩]
      · simp
      · grind
      · simp
    · simp [hσ]
  -- For each subset $S$ of size $m$, the inner sum is equal to the product of the determinants of the submatrices of $A$ and $B$ corresponding to $S$.
  have h_inner : ∀ S : {S : Finset n // S.card = m}, ∑ σ : Fin m → n, (if Function.Injective σ ∧ Finset.image σ Finset.univ = S.val then (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) else 0) = Matrix.det (Matrix.submatrix A id (S.val.orderEmbOfFin S.property)) * Matrix.det (Matrix.submatrix B (S.val.orderEmbOfFin S.property) id) := by
    intro S
    have h_inner_sum : ∑ σ : Fin m → n, (if Function.Injective σ ∧ Finset.image σ Finset.univ = S.val then (∏ i, A i (σ i)) * Matrix.det (Matrix.of (fun i j ↦ B (σ i) j)) else 0) = ∑ τ : Equiv.Perm (Fin m), (∏ i, A i (S.val.orderEmbOfFin S.property (τ i))) * Matrix.det (Matrix.of (fun i j ↦ B (S.val.orderEmbOfFin S.property (τ i)) j)) := by
      have h_inner_sum : Finset.filter (fun σ : Fin m → n => Function.Injective σ ∧ Finset.image σ Finset.univ = S.val) Finset.univ = Finset.image (fun τ : Equiv.Perm (Fin m) => fun i => S.val.orderEmbOfFin S.property (τ i)) Finset.univ := by
        ext σ
        simp [Finset.mem_image]
        constructor
        · intro hσ
          obtain ⟨a, ha⟩ : ∃ a : Fin m → Fin m, ∀ i, σ i = S.val.orderEmbOfFin S.property (a i) := by
            have h_exists_a : ∀ i, ∃ a : Fin m, σ i = S.val.orderEmbOfFin S.property a := by
              intro i
              have h_exists_a : σ i ∈ S.val := by
                exact hσ.2 ▸ Finset.mem_image_of_mem _ (Finset.mem_univ _)
              have h_exists_a : Finset.image (fun a : Fin m => S.val.orderEmbOfFin S.property a) Finset.univ = S.val := by
                refine' Finset.eq_of_subset_of_card_le (Finset.image_subset_iff.mpr fun a _ => Finset.orderEmbOfFin_mem _ _ _) _
                rw [Finset.card_image_of_injective _ fun a b h => by simpa [Fin.ext_iff] using h]; simp [S.2]
              grind
            exact ⟨fun i => Classical.choose (h_exists_a i), fun i => Classical.choose_spec (h_exists_a i)⟩
          have ha_inj : Function.Injective a := by
            exact fun i j hij => hσ.1 <| by simp [ha, hij]
          exact ⟨Equiv.ofBijective a ⟨ha_inj, Finite.injective_iff_surjective.mp ha_inj⟩, funext fun i => ha i ▸ rfl⟩
        · rintro ⟨a, rfl⟩
          constructor
          · exact fun i j hij => a.injective <| by simpa using hij
          · refine Finset.eq_of_subset_of_card_le (Finset.image_subset_iff.mpr fun i _ => Finset.orderEmbOfFin_mem _ _ _) ?_
            rw [Finset.card_image_of_injective _ fun i j hij => by simpa [Fin.ext_iff] using hij]; simp [S.2]
      rw [← Finset.sum_filter, h_inner_sum, Finset.sum_image]
      exact fun τ _ τ' _ h => Equiv.Perm.ext fun i => by simpa using congr_fun h i
    rw [h_inner_sum, Matrix.det_apply', Matrix.det_apply']
    simp [Matrix.det_apply', Finset.sum_mul]
    refine' Finset.sum_bij (fun σ _ => σ⁻¹) _ _ _ _ <;> simp [Equiv.Perm.sign_inv]
    · exact fun b => ⟨b⁻¹, inv_inv b⟩
    · intro σ
      rw [← Equiv.prod_comp σ⁻¹]
      simp [mul_assoc, mul_left_comm, Finset.mul_sum]
      refine' Finset.sum_bij (fun τ _ => σ * τ) _ _ _ _ <;> simp [Equiv.Perm.sign_mul]
      · exact fun b => ⟨σ⁻¹ * b, by simp⟩
      · cases' Int.units_eq_one_or (Equiv.Perm.sign σ) with h h <;> simp [h]
  rw [h_cauchy_binet, h_split, h_group, Finset.sum_congr rfl fun S hS => h_inner S]
See it in the graphDiscuss this resultChallenge it