AFTD Auto-Formalizing Theoretical Domains

matrix_unit_difference_rows_isTotallyUnimodular

theoremverifiedformalization

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

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.

  1. 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}.

    lines 6–13

    uses Matrix.det_isEmpty

      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
  2. 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`.

    lines 14–33

    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.2
  3. If 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.

    lines 34–39

    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
  4. 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.

    lines 40–58

    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
  5. 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}.

    lines 59–67

    uses Fin.succAbove_right_injective, Matrix.det_succ_row, Finset.sum_eq_single, neg_one_pow_eq_or

            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]
  6. 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).

    lines 68–87

    uses Matrix.submatrix_apply, Pi.single_apply, if_neg

      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
  7. 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.

    lines 88–92

      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.

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

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]⟩
See it in the graphDiscuss this resultChallenge it