Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 32 — vanishing minors of a circuit matrix and circuits avoiding a set

Proved
WhitneyMatroid.Fano.det_eq_zero_iff_circuit

by mikedeng1 · 1 vote · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

circuitsdeterminantsmatricesmatroidsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let M′\mathbf M'M′ be a real matrix whose matroid M′M'M′ has elements e1,…,ene_1,\dots,e_ne1​,…,en​, and let M\mathbf MM be a circuit matrix of M′\mathbf M'M′. Let P1,…,PqP_1,\dots,P_qP1​,…,Pq​ form a strict fundamental set of circuits in M′M'M′ with respect to en−q+1,…,ene_{n-q+1},\dots,e_nen−q+1​,…,en​, and let the first qqq rows of M\mathbf MM be those corresponding to P1,…,PqP_1,\dots,P_qP1​,…,Pq​. Let i1<⋯<isi_1<\cdots<i_si1​<⋯<is​ be numbers from {1,…,q}\{1,\dots,q\}{1,…,q}, j1<⋯<jsj_1<\cdots<j_sj1​<⋯<js​ numbers from {1,…,n−q}\{1,\dots,n-q\}{1,…,n−q}, and i1′<⋯<iq−s′i'_1<\cdots<i'_{q-s}i1′​<⋯<iq−s′​ the complement of {i1,…,is}\{i_1,\dots,i_s\}{i1​,…,is​} in {1,…,q}\{1,\dots,q\}{1,…,q}. Let

  • DDD be the determinant of M\mathbf MM with rows i1,…,isi_1,\dots,i_si1​,…,is​ and columns j1,…,jsj_1,\dots,j_sj1​,…,js​;
  • D′D'D′ be the determinant of M\mathbf MM with rows 1,…,q1,\dots,q1,…,q and columns j1,…,js, n−q+i1′,…,n−q+iq−s′j_1,\dots,j_s,\ n-q+i'_1,\dots,n-q+i'_{q-s}j1​,…,js​, n−q+i1′​,…,n−q+iq−s′​.

Then

D=0  ⟺  D′=0  ⟺  some circuit P of M′ contains none of ej1,…,ejs,en−q+i1′,…,en−q+iq−s′.D=0\iff D'=0\iff \text{some circuit } P \text{ of } M' \text{ contains none of } e_{j_1},\dots,e_{j_s},e_{n-q+i'_1},\dots,e_{n-q+i'_{q-s}}.D=0⟺D′=0⟺some circuit P of M′ contains none of ej1​​,…,ejs​​,en−q+i1′​​,…,en−q+iq−s′​​.

The theorem turns the combinatorics of M′M'M′ into polynomial equations on the entries of a normalised circuit matrix; Whitney applies it in §16 to the triples (1,4;1,2)(1,4;1,2)(1,4;1,2), (2,4;1,3)(2,4;1,3)(2,4;1,3), (3,4;2,3)(3,4;2,3)(3,4;2,3) and (1,2,3;1,2,3)(1,2,3;1,2,3)(1,2,3;1,2,3) to show that the Fano matroid has no real matrix.

Formalization Note The elements are Fin (p + q) with n=p+qn=p+qn=p+q: eje_jej​ (1≤j≤n−q1\le j\le n-q1≤j≤n−q) is Fin.castAdd q (j-1) and en−q+ie_{n-q+i}en−q+i​ (1≤i≤q1\le i\le q1≤i≤q) is Fin.natAdd p (i-1). The row of PiP_iPi​ is k (i-1). The increasing lists i∙i_\bulleti∙​, j∙j_\bulletj∙​, i∙′i'_\bulleti∙′​ are order embeddings I : Fin s ↪o Fin q, J : Fin s ↪o Fin p, I' : Fin t ↪o Fin q with s+t=qs+t=qs+t=q and the range of I' the complement of the range of I; this avoids natural-number subtraction. The columns of D′D'D′ are listed in the paper's order with Fin.append. Only the vanishing of DDD and D′D'D′ is asserted, so the order of rows and columns does not matter.

Preamble
import Mathlib
import Definitions.Def_WhitneyMatroid_Fano_IsMatroidOf
import Definitions.Def_WhitneyMatroid_Fano_FundamentalCircuits
import Definitions.Def_WhitneyMatroid_Fano_IsCircuitMatrix
Formal statement
namespace WhitneyMatroid.Fano

/-- Whitney, Theorem 32 (pp. 528–529). The elements are `Fin (p + q)` with `n = p + q`: Whitney's
`e_j` (`1 ≤ j ≤ n − q`) is `Fin.castAdd q (j-1)` and `e_{n−q+i}` (`1 ≤ i ≤ q`) is
`Fin.natAdd p (i-1)`. `B` (Whitney's `𝐌`) is the circuit matrix of the real matrix `A`
(Whitney's `𝐌′`), whose matroid is `M′`; the circuits `P_i = row (k i)` form a strict fundamental
set of circuits in `M′` with respect to `e_{n−q+1}, …, e_n`, and the rows `B (k i)` are "the first
`q` rows". `I` lists `i₁ < ⋯ < i_s` from `{1, …, q}`, `J` lists `j₁ < ⋯ < j_s` from
`{1, …, n − q}`, and `I'` lists the complementary `i′₁ < ⋯ < i′_{q−s}` (`t = q − s`). Then the
determinant `D` of `B` with rows `i₁, …, i_s` and columns `j₁, …, j_s` vanishes iff the
determinant `D′` with rows `1, …, q` and columns `j₁, …, j_s, n−q+i′₁, …, n−q+i′_{q−s}` vanishes,
iff some circuit of `M′` contains none of the columns `e_{j₁}, …, e_{j_s}, e_{n−q+i′₁}, …,
e_{n−q+i′_{q−s}}`. -/
theorem det_eq_zero_iff_circuit {p q m : ℕ} {κ : Type*}
    (A : Matrix (Fin m) (Fin (p + q)) ℝ) (M' : Matroid (Fin (p + q)))
    (B : Matrix κ (Fin (p + q)) ℝ) (row : κ ≃ {P : Set (Fin (p + q)) // M'.IsCircuit P})
    (hB : IsCircuitMatrix M' A B row) (k : Fin q → κ)
    (hP : IsStrictFundamentalCircuitSetWrt M' (fun i => (row (k i) : Set (Fin (p + q))))
      (Fin.natAdd p))
    {s t : ℕ} (hst : s + t = q) (I : Fin s ↪o Fin q) (J : Fin s ↪o Fin p) (I' : Fin t ↪o Fin q)
    (hI' : ∀ i : Fin q, i ∈ Set.range I' ↔ i ∉ Set.range I) :
    let D : ℝ := (Matrix.of fun a b : Fin s => B (k (I a)) (Fin.castAdd q (J b))).det
    let cols : Fin (s + t) → Fin (p + q) :=
      Fin.append (fun b : Fin s => Fin.castAdd q (J b)) (fun c : Fin t => Fin.natAdd p (I' c))
    let D' : ℝ := (Matrix.of fun (i c : Fin q) => B (k i) (cols (Fin.cast hst.symm c))).det
    (D = 0 ↔ D' = 0) ∧
      (D = 0 ↔
        ∃ P : Set (Fin (p + q)), M'.IsCircuit P ∧ ∀ c : Fin (s + t), cols c ∉ P) := by sorry

end WhitneyMatroid.Fano
Source
Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), pp. 528–529, Theorem 32
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

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