Lemma 5 (Heller–Tompkins), p. 23 — a {0,±1} matrix with ≤ 2 nonzeros per column and a sign-compatible row bipartition is totally unimodular
ProvedProConChoice.Rational.lemma_5integer-programmingmatricesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1total-unimodularity
Let be a real matrix whose rows are partitioned into two disjoint sets and . Then is totally unimodular (every square submatrix has determinant , or ) if
- every entry of is , or ;
- every column of contains at most two nonzero entries;
- if two nonzero entries in a column have the same sign, then the row of one is in and the row of the other is in ;
- if two nonzero entries in a column have opposite signs, then both rows are in or both are in .
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; is a set of rows and its complement. "Two nonzero entries" refers to two different rows ; same sign is , opposite signs . 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.