matrix_unit_difference_rows_isTotallyUnimodular
Every integer matrix whose rows are differences e_u − e_v of two standard basis vectors is totally unimodular: each square minor is 0, 1 or −1.
Statement
theorem matrix_unit_difference_rows_isTotallyUnimodular {m n : Type*} [DecidableEq n] (u v : m → n) : (Matrix.of fun (i : m) (j : n) => (Pi.single (u i) (1 : ℤ) : n → ℤ) j - (Pi.single (v i) (1 : ℤ) : n → ℤ) j).IsTotallyUnimodular
- Formalizes
- arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Lemma 2.2 (determinants of unit-incidence minors). Stated as total unimodularity (Mathlib's `Matrix.IsTotallyUnimodular`) of the matrix with rows e_{u(i)} − e_{v(i)}; rows with u(i) = v(i) (zero rows) are allowed.
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- midpoint_certificate_matrix_minor_abs_leThe absolute value of every k x k minor of a (k+1) x (k+1) midpoint-certificate matrix is bounded by 2^k, proved by multilinear expansion…
The proof, explained
To show that an integer matrix whose rows are differences of standard basis vectors e_{u(i)} - e_{v(i)} is totally unimodular, we first prove by induction on matrix dimension k that every k × k integer matrix with entries in {0, 1, -1} having at most one 1 and at most one -1 per row has determinant in {0, 1, -1}. In the inductive step, if every row has both signs, each row sums to 0, placing the all-ones vector in the kernel and forcing the determinant to be 0. Otherwise, some row contains at most one nonzero entry: if the row is all zeros, the determinant is 0; if it contains a single nonzero entry ±1, Laplace expansion along that row reduces the determinant to ±1 times the determinant of a (k - 1) × (k - 1) minor, which is in {0, 1, -1} by induction. Finally, any square submatrix of the difference matrix inherits the property that each row has at most one 1 and at most one -1 by injectivity of the column selection, completing the proof.
State the key induction lemma and prove the base case k = 0: any 0 × 0 matrix has determinant 1.
We set up an auxiliary lemma (`key`): any k × k integer matrix B whose entries belong to {0, 1, -1} and whose rows each contain at most one 1 and at most one -1 has det B ∈ {0, 1, -1}. We argue by induction on k. For k = 0, the indexing type Fin 0 is empty, and the determinant of an empty matrix is 1 by `Matrix.det_isEmpty`, which is in {0, 1, -1}.
uses
Matrix.det_isEmptyhave key : ∀ k : ℕ, ∀ B : Matrix (Fin k) (Fin k) ℤ, (∀ i j, B i j = 0 ∨ B i j = 1 ∨ B i j = -1) → (∀ i j j', B i j = 1 → B i j' = 1 → j = j') → (∀ i j j', B i j = -1 → B i j' = -1 → j = j') → B.det = 0 ∨ B.det = 1 ∨ B.det = -1 := by intro k induction k with | zero => intro B _ _ _; right; left; exact Matrix.det_isEmpty
In the induction step, if every row of B contains both a 1 and a -1, then det B = 0.
Assume the induction hypothesis for k × k matrices, and let B be a (k + 1) × (k + 1) matrix satisfying the conditions. If every row contains both a 1 and a -1, then by the uniqueness of 1 and -1 in each row, every other entry in that row is 0. Each row therefore sums to 1 + (-1) = 0. Thus the all-ones vector 1 = (1, 1, …, 1)ᵀ lies in the kernel of B. Since 1 ≠ 0 (using `one_ne_zero` and `congrFun`), B has a non-trivial kernel, so det B = 0 by `Matrix.exists_mulVec_eq_zero_iff`.
uses
Matrix.exists_mulVec_eq_zero_iff,one_ne_zero,congrFun,Finset.sum_eq_add| succ k ih => intro B h0 h1 h2 by_cases hall : ∀ i, (∃ j, B i j = 1) ∧ (∃ j, B i j = -1) · -- every row sums to zero, so the all-ones vector is in the kernel left rw [← Matrix.exists_mulVec_eq_zero_iff] refine ⟨fun _ => 1, fun h => one_ne_zero (congrFun h 0), ?_⟩ funext i obtain ⟨⟨j1, hj1⟩, ⟨j2, hj2⟩⟩ := hall i have hne : j1 ≠ j2 := by rintro rfl rw [hj1] at hj2 norm_num at hj2 simp only [Matrix.mulVec, dotProduct, mul_one, Pi.zero_apply] rw [Finset.sum_eq_add j1 j2 hne (fun c _ hc => ?_) (by simp) (by simp), hj1, hj2] · norm_num · rcases h0 i c with h | h | h · exact h · exact absurd (h1 i c j1 h hj1) hc.1 · exact absurd (h2 i c j2 h hj2) hc.2If some row of B does not contain both 1 and -1, either it is all zeros (so det B = 0), or it has at least one nonzero entry.
Negating the previous case gives some row i that does not contain both a 1 and a -1. If row i is identically zero, its determinant is immediately 0 by `Matrix.det_eq_zero_of_row_eq_zero`. Otherwise, row i has at least one nonzero entry, at some column j0.
uses
Matrix.det_eq_zero_of_row_eq_zero· push_neg at hall obtain ⟨i, hi⟩ := hall by_cases hz : ∀ j, B i j = 0 · left; exact Matrix.det_eq_zero_of_row_eq_zero i hz push_neg at hz obtain ⟨j0, hj0⟩ := hz
Row i contains exactly one nonzero entry, at column j0, and this entry is either 1 or -1.
Since B i j0 ≠ 0 and all entries lie in {0, 1, -1}, B i j0 must be 1 or -1. For any other column j ≠ j0, if B i j were nonzero, it would also be 1 or -1. If B i j and B i j0 had the same sign, that would contradict the hypothesis that row i has at most one 1 and at most one -1; if they had opposite signs, row i would contain both 1 and -1, contradicting the choice of row i. Hence, every entry of row i other than at j0 is 0.
uses
Or.inl,Or.inr-- row `i` has a single nonzero entry, at `j0` have honly : ∀ j, j ≠ j0 → B i j = 0 := by intro j hj by_contra hne rcases h0 i j with h | h | h · exact hne h · rcases h0 i j0 with h' | h' | h' · exact hj0 h' · exact hj (h1 i j j0 h h') · exact hi ⟨j, h⟩ j0 h' · rcases h0 i j0 with h' | h' | h' · exact hj0 h' · exact hi ⟨j0, h'⟩ j h · exact hj (h2 i j j0 h h') have hB : B i j0 = 1 ∨ B i j0 = -1 := by rcases h0 i j0 with h | h | h · exact absurd h hj0 · exact Or.inl h · exact Or.inr h
The (k × k) minor B' obtained by deleting row i and column j0 has det B' ∈ {0, 1, -1}, and Laplace expansion along row i yields det B ∈ {0, 1, -1}.
We delete row i and column j0 using the injective index embeddings `Fin.succAbove` to obtain a k × k matrix B'. Because `Fin.succAbove` is injective (`Fin.succAbove_right_injective`), B' preserves the property of having at most one 1 and at most one -1 per row, so det B' ∈ {0, 1, -1} by the induction hypothesis. Expanding det B along row i via `Matrix.det_succ_row` and using `Finset.sum_eq_single` reduces the determinant to det B = (-1)^(i + j0) * B i j0 * det B'. Since (-1)^(i + j0) ∈ {1, -1} by `neg_one_pow_eq_or`, B i j0 ∈ {1, -1}, and det B' ∈ {0, 1, -1}, their product det B must lie in {0, 1, -1}.
uses
Fin.succAbove_right_injective,Matrix.det_succ_row,Finset.sum_eq_single,neg_one_pow_eq_orset B' := B.submatrix i.succAbove j0.succAbove with hB' have hminor : B'.det = 0 ∨ B'.det = 1 ∨ B'.det = -1 := by refine ih B' (fun a b => h0 _ _) (fun a b b' hb hb' => ?_) (fun a b b' hb hb' => ?_) · exact Fin.succAbove_right_injective (h1 _ _ _ hb hb') · exact Fin.succAbove_right_injective (h2 _ _ _ hb hb') rw [Matrix.det_succ_row B i, Finset.sum_eq_single j0 (fun j _ hj => by rw [honly j hj]; ring) (by simp)] rcases neg_one_pow_eq_or ℤ (i + j0 : ℕ) with hp | hp <;> rcases hB with hb | hb <;> rcases hminor with hd | hd | hd <;> simp [hp, hb, ← hB', hd]
Any k × k submatrix B of the basis difference matrix has entries in {0, 1, -1}, with at most one 1 and at most one -1 in each row.
Let B be a k × k submatrix chosen by row indices f and column indices g with g injective. Using `Matrix.submatrix_apply` and `Pi.single_apply`, entry B i j is (if g j = u (f i) then 1 else 0) - (if g j = v (f i) then 1 else 0). Thus each entry is 0, 1, or -1. Using `if_neg`, B i j = 1 implies g j = u (f i), and B i j = -1 implies g j = v (f i).
uses
Matrix.submatrix_apply,Pi.single_apply,if_negintro k f g _ hg set B := (Matrix.of fun (i : m) (j : n) => (Pi.single (u i) (1 : ℤ) : n → ℤ) j - (Pi.single (v i) (1 : ℤ) : n → ℤ) j).submatrix f g with hBdef have entry : ∀ i j, B i j = (if g j = u (f i) then 1 else 0) - (if g j = v (f i) then 1 else 0) := by intro i j simp [hBdef, Matrix.submatrix_apply, Pi.single_apply] have e1 : ∀ i j, B i j = 1 → g j = u (f i) := by intro i j h by_contra hc rw [entry, if_neg hc] at h split_ifs at h <;> norm_num at h have e2 : ∀ i j, B i j = -1 → g j = v (f i) := by intro i j h by_contra hc rw [entry, if_neg hc] at h split_ifs at h <;> norm_num at h have h0 : ∀ i j, B i j = 0 ∨ B i j = 1 ∨ B i j = -1 := by intro i j; rw [entry]; split_ifs <;> simp
Injectivity of g implies each row has at most one 1 and at most one -1, so applying the key lemma proves total unimodularity.
If B i j = 1 and B i j' = 1, then g j = u (f i) = g j', so j = j' by the injectivity of g. Similarly, if B i j = -1 and B i j' = -1, then g j = v (f i) = g j', so j = j'. Thus B satisfies all hypotheses of `key`, giving det B ∈ {0, 1, -1}. Exhibiting 0, 1, or -1 as the corresponding element in the range of `SignType.cast` finishes the proof that the matrix is totally unimodular.
rcases key k B h0 (fun i j j' hj hj' => hg ((e1 i j hj).trans (e1 i j' hj').symm)) (fun i j j' hj hj' => hg ((e2 i j hj).trans (e2 i j' hj').symm)) with h | h | h · exact ⟨0, by simp [h]⟩ · exact ⟨1, by simp [h]⟩ · exact ⟨-1, by simp [h]⟩
Matrix.det_isEmpty- The determinant of an empty square matrix (indexed by an empty type) is 1.
Matrix.exists_mulVec_eq_zero_iff- Over an integral domain, a square matrix has determinant 0 if and only if there is a non-zero vector in its kernel.
one_ne_zero- In any structure where 1 is non-zero, 1 ≠ 0.
congrFun- Equal functions agree at every argument.
Finset.sum_eq_add- If all terms in a finite sum other than two distinct indices a and b are zero, the sum equals f(a) + f(b).
Matrix.det_eq_zero_of_row_eq_zero- A square matrix with an all-zero row has determinant 0.
Or.inl- Constructs a proof of a ∨ b from a proof of the left disjunct a.
Or.inr- Constructs a proof of a ∨ b from a proof of the right disjunct b.
Fin.succAbove_right_injective- The map skipping a designated element of Fin (n + 1) while preserving order is injective.
Matrix.det_succ_row- Laplace cofactor expansion of the determinant of an (n + 1) × (n + 1) matrix along a designated row.
Finset.sum_eq_single- If all terms in a finite sum except at a single index a are zero, the sum equals f(a).
neg_one_pow_eq_or- Any natural power of -1 in a ring is either 1 or -1.
Matrix.submatrix_apply- The entry at (i, j) of a submatrix formed by row map r and column map c is the entry of the original matrix at (r(i), c(j)).
Pi.single_apply- The indicator vector `Pi.single i x` evaluates to x at index i and 0 elsewhere.
if_neg- If a condition c is false, the conditional expression `if c then t else e` reduces to e.
- In Mathlib, `Matrix.IsTotallyUnimodular` is defined by requiring square minors to lie in `Set.range SignType.cast`, which maps the three constructors of `SignType` (zero, pos, neg) to 0, 1, and -1 in ℤ.
- Row and column deletion for minors is formally encoded using `Fin.succAbove`, the order-preserving injection that skips a specified index.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem matrix_unit_difference_rows_isTotallyUnimodular {m n : Type*} [DecidableEq n] (u v : m → n) : (Matrix.of fun (i : m) (j : n) => (Pi.single (u i) (1 : ℤ) : n → ℤ) j - (Pi.single (v i) (1 : ℤ) : n → ℤ) j).IsTotallyUnimodular := by -- square matrices whose rows have at most one `1`, at most one `-1`, and zeros elsewhere have key : ∀ k : ℕ, ∀ B : Matrix (Fin k) (Fin k) ℤ, (∀ i j, B i j = 0 ∨ B i j = 1 ∨ B i j = -1) → (∀ i j j', B i j = 1 → B i j' = 1 → j = j') → (∀ i j j', B i j = -1 → B i j' = -1 → j = j') → B.det = 0 ∨ B.det = 1 ∨ B.det = -1 := by intro k induction k with | zero => intro B _ _ _; right; left; exact Matrix.det_isEmpty | succ k ih => intro B h0 h1 h2 by_cases hall : ∀ i, (∃ j, B i j = 1) ∧ (∃ j, B i j = -1) · -- every row sums to zero, so the all-ones vector is in the kernel left rw [← Matrix.exists_mulVec_eq_zero_iff] refine ⟨fun _ => 1, fun h => one_ne_zero (congrFun h 0), ?_⟩ funext i obtain ⟨⟨j1, hj1⟩, ⟨j2, hj2⟩⟩ := hall i have hne : j1 ≠ j2 := by rintro rfl rw [hj1] at hj2 norm_num at hj2 simp only [Matrix.mulVec, dotProduct, mul_one, Pi.zero_apply] rw [Finset.sum_eq_add j1 j2 hne (fun c _ hc => ?_) (by simp) (by simp), hj1, hj2] · norm_num · rcases h0 i c with h | h | h · exact h · exact absurd (h1 i c j1 h hj1) hc.1 · exact absurd (h2 i c j2 h hj2) hc.2 · push_neg at hall obtain ⟨i, hi⟩ := hall by_cases hz : ∀ j, B i j = 0 · left; exact Matrix.det_eq_zero_of_row_eq_zero i hz push_neg at hz obtain ⟨j0, hj0⟩ := hz -- row `i` has a single nonzero entry, at `j0` have honly : ∀ j, j ≠ j0 → B i j = 0 := by intro j hj by_contra hne rcases h0 i j with h | h | h · exact hne h · rcases h0 i j0 with h' | h' | h' · exact hj0 h' · exact hj (h1 i j j0 h h') · exact hi ⟨j, h⟩ j0 h' · rcases h0 i j0 with h' | h' | h' · exact hj0 h' · exact hi ⟨j0, h'⟩ j h · exact hj (h2 i j j0 h h') have hB : B i j0 = 1 ∨ B i j0 = -1 := by rcases h0 i j0 with h | h | h · exact absurd h hj0 · exact Or.inl h · exact Or.inr h set B' := B.submatrix i.succAbove j0.succAbove with hB' have hminor : B'.det = 0 ∨ B'.det = 1 ∨ B'.det = -1 := by refine ih B' (fun a b => h0 _ _) (fun a b b' hb hb' => ?_) (fun a b b' hb hb' => ?_) · exact Fin.succAbove_right_injective (h1 _ _ _ hb hb') · exact Fin.succAbove_right_injective (h2 _ _ _ hb hb') rw [Matrix.det_succ_row B i, Finset.sum_eq_single j0 (fun j _ hj => by rw [honly j hj]; ring) (by simp)] rcases neg_one_pow_eq_or ℤ (i + j0 : ℕ) with hp | hp <;> rcases hB with hb | hb <;> rcases hminor with hd | hd | hd <;> simp [hp, hb, ← hB', hd] intro k f g _ hg set B := (Matrix.of fun (i : m) (j : n) => (Pi.single (u i) (1 : ℤ) : n → ℤ) j - (Pi.single (v i) (1 : ℤ) : n → ℤ) j).submatrix f g with hBdef have entry : ∀ i j, B i j = (if g j = u (f i) then 1 else 0) - (if g j = v (f i) then 1 else 0) := by intro i j simp [hBdef, Matrix.submatrix_apply, Pi.single_apply] have e1 : ∀ i j, B i j = 1 → g j = u (f i) := by intro i j h by_contra hc rw [entry, if_neg hc] at h split_ifs at h <;> norm_num at h have e2 : ∀ i j, B i j = -1 → g j = v (f i) := by intro i j h by_contra hc rw [entry, if_neg hc] at h split_ifs at h <;> norm_num at h have h0 : ∀ i j, B i j = 0 ∨ B i j = 1 ∨ B i j = -1 := by intro i j; rw [entry]; split_ifs <;> simp rcases key k B h0 (fun i j j' hj hj' => hg ((e1 i j hj).trans (e1 i j' hj').symm)) (fun i j j' hj hj' => hg ((e2 i j hj).trans (e2 i j' hj').symm)) with h | h | h · exact ⟨0, by simp [h]⟩ · exact ⟨1, by simp [h]⟩ · exact ⟨-1, by simp [h]⟩