Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5 (Heller–Tompkins), p. 23 — a {0,±1} matrix with ≤ 2 nonzeros per column and a sign-compatible row bipartition is totally unimodular

Proved
ProConChoice.Rational.lemma_5

by mikedeng1 · Oct 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

integer-programmingmatricesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1total-unimodularity

Let AAA be a real m×nm \times nm×n matrix whose rows are partitioned into two disjoint sets R1R_1R1​ and R2R_2R2​. Then AAA is totally unimodular (every square submatrix has determinant 000, 111 or −1-1−1) if

  1. every entry of AAA is 000, 111 or −1-1−1;
  2. every column of AAA contains at most two nonzero entries;
  3. if two nonzero entries in a column have the same sign, then the row of one is in R1R_1R1​ and the row of the other is in R2R_2R2​;
  4. if two nonzero entries in a column have opposite signs, then both rows are in R1R_1R1​ or both are in R2R_2R2​.

The paper uses this criterion to show that the coefficient matrix of the system (RS)–(CS) is totally unimodular.

Formalization Note Rows and columns are indexed by finite types; R1R_1R1​ is a set of rows and R2R_2R2​ its complement. "Two nonzero entries" refers to two different rows i≠i′i \ne i'i=i′; same sign is aijai′j>0a_{ij} a_{i'j} > 0aij​ai′j​>0, opposite signs aijai′j<0a_{ij} a_{i'j} < 0aij​ai′j​<0. Total unimodularity is Mathlib's Matrix.IsTotallyUnimodular.

Preamble
import Mathlib
Formal statement
namespace ProConChoice.Rational

/-- Lemma 5 (Heller–Tompkins, p. 23): a matrix whose rows are split into `R₁` and its complement
`R₂` is totally unimodular if (1) every entry is `0`, `1` or `-1`; (2) every column has at most two
nonzero entries; (3) two nonzero entries of a column with the same sign lie in rows of different
parts; (4) two nonzero entries of a column with opposite signs lie in rows of the same part. -/
theorem lemma_5 {m n : Type*} [Fintype m] [DecidableEq m] [Fintype n]
    (A : Matrix m n ℝ) (R₁ : Set m)
    (h1 : ∀ i j, A i j = 0 ∨ A i j = 1 ∨ A i j = -1)
    (h2 : ∀ j, (Finset.univ.filter (fun i => A i j ≠ 0)).card ≤ 2)
    (h3 : ∀ j i i', i ≠ i' → 0 < A i j * A i' j → (i ∈ R₁ ↔ i' ∉ R₁))
    (h4 : ∀ j i i', i ≠ i' → A i j * A i' j < 0 → (i ∈ R₁ ↔ i' ∈ R₁)) :
    A.IsTotallyUnimodular := by sorry

end ProConChoice.Rational
Source
Dogan & Yildiz, Every choice function is pro-con rationalizable, SSRN 3085542 (January 10, 2021), p. 23, Lemma 5 (Heller & Tompkins (1956)); definition of total unimodularity p. 22
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 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