AFTD Auto-Formalizing Theoretical Domains

cauchy_binet_det

theoremverifiedformalization

For 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 determinant of A * B equals the sum over all strictly increasing functions f : Fin m → Fin n of the determinant of the submatrix of A with column indices f multiplied by the determinant of the submatrix of B with row indices f.

Statement

theorem cauchy_binet_det {R : Type*} [CommRing R] {m n : ℕ}
    (A : Matrix (Fin m) (Fin n) R) (B : Matrix (Fin n) (Fin m) R) :
    Matrix.det (A * B) =
      ∑ f ∈ Finset.filter StrictMono (Finset.univ : Finset (Fin m → Fin n)),
        Matrix.det (A.submatrix id f) * Matrix.det (B.submatrix f id)
Formalizes
arXiv:2610.04621 Lemma 5 proof (Appendix B)
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • cauchyBinetCauchy–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,:])…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

Let $R$ be a commutative ring and let $m, n \in \mathbb{N}$. For any $m \times n$ matrix $A$ with entries in $R$ and any $n \times m$ matrix $B$ with entries in $R$, the determinant of the $m \times m$ product matrix $A B$ equals the sum, over all strictly monotonic functions $f : \mathrm{Fin}(m) \to \mathrm{Fin}(n)$, of the product of: 1. the determinant of the $m \times m$ submatrix of $A$ formed by taking all rows (via the identity map) and columns indexed by $f$, and 2. the determinant of the $m \times m$ submatrix of $B$ formed by taking rows indexed by $f$ and all columns (via the identity map).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof rewrites det(A * B) using an already established version of the Cauchy-Binet formula (cauchyBinet) that sums over all m-element subsets S ⊆ Fin n. It then applies Finset.sum_bij to re-index this sum over all strictly increasing functions f : Fin m → Fin n via the canonical order-preserving embedding of each subset S. This correspondence is a bijection because order embeddings are strictly increasing, subsets are uniquely determined as the images of their order embeddings, and every strictly increasing function is the canonical order embedding of its image (which has cardinality m by injectivity).

  1. The product determinant det(A * B) is expressed as a sum over all m-element subsets of Fin n of the products of the corresponding submatrix determinants.

    We enable classical logic and rewrite the left-hand side det(A * B) using the established Cauchy-Binet formula cauchyBinet, which indexes the sum by m-element subsets S of Fin n, where each subset indexes columns of A and rows of B via its canonical order-preserving embedding from Fin m.

    lines 7–8

    uses cauchyBinet

      classical
      rw [cauchyBinet]
  2. The identity reduces to showing that mapping each m-element subset to its canonical order embedding is a bijection onto the strictly increasing functions Fin m → Fin n, with identical summands.

    By Finset.sum_bij, two finite sums agree if there is a bijection between their indexing sets that matches corresponding terms. We propose the map that assigns to each subset S of size m its unique order embedding orderEmbOfFin from Fin m.

    lines 9–10

    uses Finset.sum_bij

      refine Finset.sum_bij
        (fun S _ => S.1.orderEmbOfFin S.2) ?_ ?_ ?_ ?_
  3. The canonical order embedding of any m-element subset is strictly increasing.

    By definition, an order embedding is strictly monotonic. Hence, using Finset.mem_filter.mpr and Finset.mem_univ, the embedding belongs to the finset of strictly increasing functions from Fin m to Fin n.

    lines 11–12

    uses Finset.mem_filter.mpr, Finset.mem_univ

      · intro S _
        exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (S.1.orderEmbOfFin S.2).strictMono⟩
  4. The map from m-element subsets to order embeddings is injective.

    Let S and S' be m-element subsets whose order embeddings agree. By Subtype.ext, it suffices to show that their underlying sets are equal. By Finset.image_orderEmbOfFin_univ, any subset equals the image of the universal set under its canonical order embedding; since the two embeddings coincide, their images coincide, so S = S'.

    lines 13–16

    uses Subtype.ext, Finset.image_orderEmbOfFin_univ

      · intro S _ S' _ h
        apply Subtype.ext
        rw [← Finset.image_orderEmbOfFin_univ S.1 S.2,
            ← Finset.image_orderEmbOfFin_univ S'.1 S'.2, h]
  5. The map is surjective: every strictly increasing function is the canonical order embedding of its image.

    Given a strictly increasing function f : Fin m → Fin n, we unpack its defining condition using Finset.mem_filter. Its image f(univ) is an m-element subset because strictly monotonic functions are injective, so Finset.card_image_of_injective implies that the image has the same cardinality as Fin m (which simplifies to m). By Finset.orderEmbOfFin_unique, any strictly increasing map onto a subset of size m is the canonical order embedding of that subset, establishing surjectivity.

    lines 17–22

    uses Finset.mem_filter, Finset.mem_univ, Finset.card_image_of_injective, Finset.orderEmbOfFin_unique, Finset.mem_image_of_mem

      · intro f hf
        rw [Finset.mem_filter] at hf
        refine ⟨⟨Finset.image f Finset.univ, ?_⟩, Finset.mem_univ _, ?_⟩
        · rw [Finset.card_image_of_injective _ hf.2.injective]
          simp
        · exact (Finset.orderEmbOfFin_unique _ (fun x => Finset.mem_image_of_mem f (Finset.mem_univ x)) hf.2).symm
  6. Corresponding summands on both sides are definitionally equal.

    For each m-element subset S, the summand indexed by S is definitionally identical to the summand indexed by the order embedding of S, so the terms match by reflexivity (rfl).

    lines 23–24

      · intro S _
        rfl
cauchyBinet
For matrices A of size m × n and B of size n × m over a commutative ring, det(A * B) equals the sum over all m-element subsets S of det(A submatrix indexed by S) * det(B submatrix indexed by S), where S indexes rows and columns via its canonical order embedding.
Finset.sum_bij
Two finite sums ∑_{x ∈ s} f(x) and ∑_{y ∈ t} g(y) are equal if there is a map i from s to t that maps into t, is injective, is surjective, and preserves summands (f(x) = g(i(x))).
Finset.mem_filter.mpr
An element x belongs to the filtered sub-finset of elements satisfying property p if x belongs to the ambient finset and p(x) holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Finset.image_orderEmbOfFin_univ
For a linearly ordered set, the image of the universal finset of Fin k under the canonical order embedding of a finset s of cardinality k is s itself.
Finset.mem_filter
An element x belongs to Finset.filter p s if and only if x ∈ s and p(x) holds.
Finset.card_image_of_injective
If a function f is injective on a finite set s, then the cardinality of its image f(s) equals the cardinality of s.
Finset.orderEmbOfFin_unique
A strictly increasing function from Fin k into a finset s of cardinality k is equal to the canonical order embedding of s.
Finset.mem_image_of_mem
If an element a belongs to s, then f(a) belongs to the image of s under f.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The Cauchy-Binet formula for the determinant of the product of two rectangular matrices. -/theorem cauchy_binet_det {R : Type*} [CommRing R] {m n : ℕ}    (A : Matrix (Fin m) (Fin n) R) (B : Matrix (Fin n) (Fin m) R) :    Matrix.det (A * B) =      ∑ f ∈ Finset.filter StrictMono (Finset.univ : Finset (Fin m → Fin n)),        Matrix.det (A.submatrix id f) * Matrix.det (B.submatrix f id) := by  classical  rw [cauchyBinet]  refine Finset.sum_bij    (fun S _ => S.1.orderEmbOfFin S.2) ?_ ?_ ?_ ?_  · intro S _    exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (S.1.orderEmbOfFin S.2).strictMono⟩  · intro S _ S' _ h    apply Subtype.ext    rw [← Finset.image_orderEmbOfFin_univ S.1 S.2,        ← Finset.image_orderEmbOfFin_univ S'.1 S'.2, h]  · intro f hf    rw [Finset.mem_filter] at hf    refine ⟨⟨Finset.image f Finset.univ, ?_⟩, Finset.mem_univ _, ?_⟩    · rw [Finset.card_image_of_injective _ hf.2.injective]      simp    · exact (Finset.orderEmbOfFin_unique _ (fun x => Finset.mem_image_of_mem f (Finset.mem_univ x)) hf.2).symm  · intro S _    rfl
See it in the graphDiscuss this resultChallenge it