AFTD Auto-Formalizing Theoretical Domains

unit_incidence_matrix_isTotallyUnimodular

theoremverified

Every square minor of a matrix whose rows are differences of standard basis vectors e_{u i} - e_{v i} is 0, 1 or -1 (Mathlib: the matrix is totally unimodular).

Statement

theorem unit_incidence_matrix_isTotallyUnimodular {m n : Type*} [DecidableEq n] (u v : m → n) :
    (unit_incidence_matrix u v).IsTotallyUnimodular
Source
step towards nus_min_card_ge_near_quadratic
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • unit_incidence_matrixThe matrix whose row i is the unit difference e_{u i} − e_{v i} in Z^{n}.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

The proof, explained

The unit incidence matrix of a directed graph has rows of the form e_{u(i)} - e_{v(i)}. The proof establishes that any integer matrix with entries in {0, 1, -1} having at most one 1 and at most one -1 per row is totally unimodular, by induction on the size k of square submatrices. In the inductive step, if a submatrix has a row with at most one non-zero entry, expanding along that row reduces the determinant to a single smaller minor; otherwise, every row contains exactly one 1 and one -1, causing all row sums to vanish, which makes the columns linearly dependent and the determinant zero. Checking that the unit incidence matrix satisfies these row conditions completes the proof.

  1. For every natural number N, (-1)^N lies in {0, 1, -1}.

    The set {0, 1, -1} is the range of the sign homomorphism SignType.castHom, which is a submonoid of the integers under multiplication. Since -1 is in this submonoid, any natural power (-1)^N is also in it by pow_mem.

    lines 1–5

    uses pow_mem

    lemma unit_incidence_matrix_isTotallyUnimodular_pow_mem (N : ℕ) :
        (-1 : ℤ) ^ N ∈ Set.range SignType.cast := by
      change (-1 : ℤ) ^ N ∈ MonoidHom.mrange SignType.castHom.toMonoidHom
      refine pow_mem ?_ N
      exact ⟨-1, rfl⟩
  2. The set {0, 1, -1} is closed under integer multiplication.

    Viewing the range of SignType.cast as the range of the multiplicative monoid homomorphism SignType.castHom, the product of any two elements in this range lies in the range by mul_mem.

    lines 7–13

    uses mul_mem

    lemma unit_incidence_matrix_isTotallyUnimodular_mul_mem {a b : ℤ}
        (ha : a ∈ Set.range SignType.cast) (hb : b ∈ Set.range SignType.cast) :
        a * b ∈ Set.range SignType.cast := by
      change a ∈ MonoidHom.mrange SignType.castHom.toMonoidHom at ha
      change b ∈ MonoidHom.mrange SignType.castHom.toMonoidHom at hb
      change a * b ∈ MonoidHom.mrange SignType.castHom.toMonoidHom
      exact mul_mem ha hb
  3. Any integer equal to 0, 1, or -1 belongs to the range of SignType.cast.

    By case analysis on the hypothesis x = 0 ∨ x = 1 ∨ x = -1, each value is exhibited as the cast of the corresponding SignType element (SignType.zero, SignType.pos, or SignType.neg), using SignType.coe_one and SignType.coe_neg_one.

    lines 15–20

    uses SignType.coe_one, SignType.coe_neg_one

    lemma unit_incidence_matrix_isTotallyUnimodular_tri_mem {x : ℤ}
        (h : x = 0 ∨ x = 1 ∨ x = -1) : x ∈ Set.range SignType.cast := by
      rcases h with h | h | h
      · exact ⟨0, h.symm⟩
      · exact ⟨1, by rw [SignType.coe_one]; exact h.symm⟩
      · exact ⟨-1, by rw [SignType.coe_neg_one]; exact h.symm⟩
  4. Any 0x0 submatrix of A has determinant in {0, 1, -1}.

    We induct on the minor size k. For the base case k = 0, any submatrix indexed by Fin 0 is empty (Matrix.submatrix_empty) and has determinant 1 (Matrix.det_fin_zero), which equals SignType.cast 1.

    lines 22–31

    uses Matrix.submatrix_empty, Matrix.det_fin_zero, SignType.coe_one

    lemma unit_incidence_matrix_isTotallyUnimodular_aux {m n : Type*} (A : Matrix m n ℤ)
        (h0 : ∀ (i : m) (j : n), A i j = 0 ∨ A i j = 1 ∨ A i j = -1)
        (h1 : ∀ (i : m) (j j' : n), A i j = 1 → A i j' = 1 → j = j')
        (h2 : ∀ (i : m) (j j' : n), A i j = -1 → A i j' = -1 → j = j') :
        A.IsTotallyUnimodular := by
      intro k
      induction k with
      | zero =>
          intro f g _ _
          exact ⟨1, by rw [Matrix.submatrix_empty, Matrix.det_fin_zero, SignType.coe_one]⟩
  5. Any (k+1) x (k+1) submatrix B of A inherits the entry and row uniqueness properties of A.

    Let B be the submatrix defined by injective row and column maps f and g. Since each entry B i j is A (f i) (g j) by Matrix.submatrix_apply, the entries of B lie in {0, 1, -1}. Furthermore, because f and g are injective, B inherits from A the property that each row contains at most one 1 and at most one -1.

    lines 32–49

    uses Matrix.submatrix_apply

      | succ k ih =>
          intro f g hf hg
          set B : Matrix (Fin (k+1)) (Fin (k+1)) ℤ := A.submatrix f g with hB
          have hBapp : ∀ (i j : Fin (k+1)), B i j = A (f i) (g j) := fun i j => by
            rw [hB, Matrix.submatrix_apply]
          have hB0 : ∀ (i j : Fin (k+1)), B i j = 0 ∨ B i j = 1 ∨ B i j = -1 := fun i j => by
            rw [hBapp i j]
            exact h0 (f i) (g j)
          have hB1 : ∀ (i : Fin (k+1)) (j j' : Fin (k+1)), B i j = 1 → B i j' = 1 → j = j' := by
            intro i j j' hj hj'
            have hjA : A (f i) (g j) = 1 := by rw [← hBapp i j]; exact hj
            have hjA' : A (f i) (g j') = 1 := by rw [← hBapp i j']; exact hj'
            exact hg (h1 (f i) (g j) (g j') hjA hjA')
          have hB2 : ∀ (i : Fin (k+1)) (j j' : Fin (k+1)), B i j = -1 → B i j' = -1 → j = j' := by
            intro i j j' hj hj'
            have hjA : A (f i) (g j) = -1 := by rw [← hBapp i j]; exact hj
            have hjA' : A (f i) (g j') = -1 := by rw [← hBapp i j']; exact hj'
            exact hg (h2 (f i) (g j) (g j') hjA hjA')
  6. If some row of B has at most one non-zero entry, then det(B) lies in {0, 1, -1}.

    Suppose row i0 of B has B(i0, j) = 0 for all j ≠ j0. Expanding det(B) along row i0 via Matrix.det_succ_row reduces the Laplace expansion sum to the single term at j0 via Finset.sum_eq_single, vanishing elsewhere. The remaining minor is a k x k submatrix of A by Matrix.submatrix_submatrix, whose determinant lies in {0, 1, -1} by the induction hypothesis. Since the sign (-1)^(i0 + j0) and the entry B(i0, j0) also lie in {0, 1, -1}, their product lies in {0, 1, -1} by the helper lemmas.

    lines 50–70

    uses Matrix.det_succ_row, Finset.sum_eq_single, Matrix.submatrix_submatrix, unit_incidence_matrix_isTotallyUnimodular_mul_mem, unit_incidence_matrix_isTotallyUnimodular_pow_mem, unit_incidence_matrix_isTotallyUnimodular_tri_mem, Finset.mem_univ

          by_cases hex : ∃ (i0 : Fin (k+1)) (j0 : Fin (k+1)), ∀ j, j ≠ j0 → B i0 j = 0
          · obtain ⟨i0, j0, hj0⟩ := hex
            rw [Matrix.det_succ_row B i0]
            rw [Finset.sum_eq_single j0]
            · have hminor : (B.submatrix i0.succAbove j0.succAbove).det
                  = (A.submatrix (fun i => f (i0.succAbove i))
                      (fun j => g (j0.succAbove j))).det := by
                rw [hB, Matrix.submatrix_submatrix]
                rfl
              rw [hminor]
              exact unit_incidence_matrix_isTotallyUnimodular_mul_mem
                (unit_incidence_matrix_isTotallyUnimodular_mul_mem
                  (unit_incidence_matrix_isTotallyUnimodular_pow_mem _)
                  (unit_incidence_matrix_isTotallyUnimodular_tri_mem (hB0 i0 j0)))
                (ih (fun i => f (i0.succAbove i)) (fun j => g (j0.succAbove j))
                  (hf.comp i0.succAbove_right_injective) (hg.comp j0.succAbove_right_injective))
            · intro b _ hb
              rw [hj0 b hb]
              simp
            · intro h
              exact absurd (Finset.mem_univ j0) h
  7. If every row of B has at least two non-zero entries, then each row of B sums to zero.

    When every row has at least two non-zero entries, each row must contain at least two distinct columns with non-zero values. Since entries are in {0, 1, -1} and each row has at most one 1 and at most one -1, every row must contain exactly one 1 at some index jp, exactly one -1 at some jq ≠ jp, and 0 everywhere else. Restricting the row sum to {jp, jq} using Finset.sum_subset and Finset.sum_pair, the sum evaluates to 1 + (-1) = 0.

    lines 71–106

    uses Or.inl, Or.inr, Finset.sum_subset, Finset.mem_insert, Finset.mem_singleton, not_or, Finset.sum_pair

          · push Not at hex
            have hrow : ∀ i : Fin (k+1), ∑ j, B i j = 0 := by
              intro i
              obtain ⟨p, hp1, hp2⟩ := hex i 0
              obtain ⟨q, hq1, hq2⟩ := hex i p
              have hpq : p ≠ q := fun h => hq1 h.symm
              have hpnz : B i p = 1 ∨ B i p = -1 := by
                rcases hB0 i p with h | h | h
                · exact absurd h hp2
                · exact Or.inl h
                · exact Or.inr h
              have hqnz : B i q = 1 ∨ B i q = -1 := by
                rcases hB0 i q with h | h | h
                · exact absurd h hq2
                · exact Or.inl h
                · exact Or.inr h
              have hmain : ∃ jp jq, jp ≠ jq ∧ B i jp = 1 ∧ B i jq = -1 := by
                rcases hpnz with hp | hp <;> rcases hqnz with hq | hq
                · exact absurd (hB1 i p q hp hq) hpq
                · exact ⟨p, q, hpq, hp, hq⟩
                · exact ⟨q, p, hpq.symm, hq, hp⟩
                · exact absurd (hB2 i p q hp hq) hpq
              obtain ⟨jp, jq, hjn, hjp, hjq⟩ := hmain
              have key : ∀ j, j ≠ jp → j ≠ jq → B i j = 0 := by
                intro j hj1 hj2
                rcases hB0 i j with h | h | h
                · exact h
                · exact absurd (hB1 i j jp h hjp) hj1
                · exact absurd (hB2 i j jq h hjq) hj2
              have hsub := Finset.sum_subset (s₁ := {jp, jq}) (s₂ := Finset.univ) (by simp)
                (by
                  intro x _ hx
                  simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx
                  exact key x hx.1 hx.2)
              rw [← hsub, Finset.sum_pair hjn, hjp, hjq]
              norm_num
  8. If every row of B sums to zero, then det(B) = 0, which lies in {0, 1, -1}.

    Because every row of B sums to zero, summing the rows of the transpose B^T with coefficient 1 yields the zero vector. By Fintype.linearIndependent_iff.mp, this contradicts linear independence since 1 ≠ 0 (one_ne_zero). Thus the rows of B^T are linearly dependent, so det(B^T) = 0 by Matrix.det_eq_zero_of_not_linearIndependent_rows. Since det(B) = det(B^T) by Matrix.det_transpose, det(B) = 0, which is the cast of SignType.zero.

    lines 107–119

    uses Fintype.linearIndependent_iff.mp, one_ne_zero, Finset.sum_apply, Matrix.det_eq_zero_of_not_linearIndependent_rows, Matrix.det_transpose

            have hnotLI : ¬ LinearIndependent ℤ (fun j : Fin (k+1) => Matrix.transpose B j) := by
              intro h
              have h' := Fintype.linearIndependent_iff.mp h (fun _ => 1) ?_
              · exact one_ne_zero (h' 0)
              · ext i
                rw [Finset.sum_apply]
                simp [hrow i]
            have hdet : (Matrix.transpose B).det = 0 :=
              Matrix.det_eq_zero_of_not_linearIndependent_rows hnotLI
            rw [Matrix.det_transpose] at hdet
            rw [hdet]
            exact ⟨0, rfl⟩
    
  9. Every entry of the unit incidence matrix lies in {0, 1, -1}.

    We apply unit_incidence_matrix_isTotallyUnimodular_aux. By definition, the (i, j)-th entry is (if u i = j then 1 else 0) - (if v i = j then 1 else 0). Case analysis on whether u i = j and v i = j shows that this difference is 0, 1, or -1 in all four cases.

    lines 120–126

    uses unit_incidence_matrix_isTotallyUnimodular_aux, Matrix.of_apply

    /-- Hou-Yang Lemma 2.2: a matrix whose rows are differences of standard basis vectors is totally unimodular, so every square minor is 0, 1 or -1. -/
    theorem unit_incidence_matrix_isTotallyUnimodular {m n : Type*} [DecidableEq n] (u v : m → n) :
        (unit_incidence_matrix u v).IsTotallyUnimodular := by
      refine unit_incidence_matrix_isTotallyUnimodular_aux _
        (fun i j => ?_) (fun i j j' hj hj' => ?_) (fun i j j' hj hj' => ?_)
      · simp only [unit_incidence_matrix, Matrix.of_apply]
        by_cases hu : u i = j <;> by_cases hv : v i = j <;> simp [hu, hv]
  10. Each row of the unit incidence matrix contains at most one 1.

    If entry (i, j) equals 1, evaluating the difference of indicator functions implies j must equal u i, because if u i ≠ j, the entry is either 0 or -1. Thus any two column indices j, j' with entry 1 must both equal u i and are therefore equal.

    lines 127–136

    uses Matrix.of_apply, if_neg, if_pos

      · have key : ∀ j : n, unit_incidence_matrix u v i j = 1 → j = u i := by
          intro j hj
          simp only [unit_incidence_matrix, Matrix.of_apply] at hj
          by_cases hu : u i = j
          · exact hu.symm
          · rw [if_neg hu] at hj
            by_cases hv : v i = j
            · rw [if_pos hv] at hj; norm_num at hj
            · rw [if_neg hv] at hj; norm_num at hj
        rw [key j hj, key j' hj']
  11. Each row of the unit incidence matrix contains at most one -1.

    Similarly, if entry (i, j) equals -1, evaluating the difference implies j must equal v i. Hence any two column indices j, j' with entry -1 both equal v i and must be identical. This completes the verification of the hypotheses of the auxiliary lemma.

    lines 137–146

    uses Matrix.of_apply, if_neg, if_pos

      · have key : ∀ j : n, unit_incidence_matrix u v i j = -1 → j = v i := by
          intro j hj
          simp only [unit_incidence_matrix, Matrix.of_apply] at hj
          by_cases hv : v i = j
          · exact hv.symm
          · rw [if_neg hv] at hj
            by_cases hu : u i = j
            · rw [if_pos hu] at hj; norm_num at hj
            · rw [if_neg hu] at hj; norm_num at hj
        rw [key j hj, key j' hj']
pow_mem
In a monoid, any submonoid is closed under natural powers of its elements.
mul_mem
A submonoid is closed under multiplication.
SignType.coe_one
The coercion of the sign 1 to an integer is 1.
SignType.coe_neg_one
The coercion of the sign -1 to an integer is -1.
Matrix.submatrix_empty
A submatrix indexed by an empty type is the empty matrix.
Matrix.det_fin_zero
The determinant of a 0x0 matrix is 1.
Matrix.submatrix_apply
The (i, j)-th entry of a submatrix is the entry of the original matrix at the mapped indices.
Matrix.det_succ_row
Laplace expansion of the determinant of an (n+1) x (n+1) matrix along row i.
Finset.sum_eq_single
If a function on a finite set is nonzero at at most one point, its sum equals its value at that point.
Matrix.submatrix_submatrix
A submatrix of a submatrix is the submatrix given by the composition of index maps.
unit_incidence_matrix_isTotallyUnimodular_pow_mem
Any natural power of -1 lies in {0, 1, -1}.
unit_incidence_matrix_isTotallyUnimodular_mul_mem
The product of two integers in {0, 1, -1} is in {0, 1, -1}.
unit_incidence_matrix_isTotallyUnimodular_tri_mem
An integer equal to 0, 1, or -1 belongs to the range of SignType.cast.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Or.inl
If a holds, then a ∨ b holds.
Or.inr
If b holds, then a ∨ b holds.
Finset.sum_subset
The sum over a subset equals the sum over the whole set if the summand is zero outside the subset.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or is in s.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
not_or
The negation of a disjunction is the conjunction of the negations.
Finset.sum_pair
The sum over a two-element set {a, b} with a ≠ b is f(a) + f(b).
Fintype.linearIndependent_iff.mp
In a linearly independent family, any linear combination that sums to zero has all zero coefficients.
one_ne_zero
1 is not equal to 0.
Finset.sum_apply
Evaluating a finite sum of functions at an index equals the sum of their individual evaluations.
Matrix.det_eq_zero_of_not_linearIndependent_rows
A square matrix over an integral domain with linearly dependent rows has determinant zero.
Matrix.det_transpose
The determinant of the transpose of a square matrix equals the determinant of the matrix.
unit_incidence_matrix_isTotallyUnimodular_aux
An integer matrix with entries in {0, 1, -1} and at most one 1 and at most one -1 per row is totally unimodular.
Matrix.of_apply
Evaluating a matrix constructed from a function gives the value of that function.
if_neg
If condition c is false, then if c then t else e is e.
if_pos
If condition c is true, then if c then t else e is t.

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

lemma unit_incidence_matrix_isTotallyUnimodular_pow_mem (N : ℕ) :    (-1 : ℤ) ^ N ∈ Set.range SignType.cast := by  change (-1 : ℤ) ^ N ∈ MonoidHom.mrange SignType.castHom.toMonoidHom  refine pow_mem ?_ N  exact ⟨-1, rfl⟩lemma unit_incidence_matrix_isTotallyUnimodular_mul_mem {a b : ℤ}    (ha : a ∈ Set.range SignType.cast) (hb : b ∈ Set.range SignType.cast) :    a * b ∈ Set.range SignType.cast := by  change a ∈ MonoidHom.mrange SignType.castHom.toMonoidHom at ha  change b ∈ MonoidHom.mrange SignType.castHom.toMonoidHom at hb  change a * b ∈ MonoidHom.mrange SignType.castHom.toMonoidHom  exact mul_mem ha hblemma unit_incidence_matrix_isTotallyUnimodular_tri_mem {x : ℤ}    (h : x = 0 ∨ x = 1 ∨ x = -1) : x ∈ Set.range SignType.cast := by  rcases h with h | h | h  · exact ⟨0, h.symm⟩  · exact ⟨1, by rw [SignType.coe_one]; exact h.symm⟩  · exact ⟨-1, by rw [SignType.coe_neg_one]; exact h.symm⟩lemma unit_incidence_matrix_isTotallyUnimodular_aux {m n : Type*} (A : Matrix m n ℤ)    (h0 : ∀ (i : m) (j : n), A i j = 0 ∨ A i j = 1 ∨ A i j = -1)    (h1 : ∀ (i : m) (j j' : n), A i j = 1 → A i j' = 1 → j = j')    (h2 : ∀ (i : m) (j j' : n), A i j = -1 → A i j' = -1 → j = j') :    A.IsTotallyUnimodular := by  intro k  induction k with  | zero =>      intro f g _ _      exact ⟨1, by rw [Matrix.submatrix_empty, Matrix.det_fin_zero, SignType.coe_one]⟩  | succ k ih =>      intro f g hf hg      set B : Matrix (Fin (k+1)) (Fin (k+1)) ℤ := A.submatrix f g with hB      have hBapp : ∀ (i j : Fin (k+1)), B i j = A (f i) (g j) := fun i j => by        rw [hB, Matrix.submatrix_apply]      have hB0 : ∀ (i j : Fin (k+1)), B i j = 0 ∨ B i j = 1 ∨ B i j = -1 := fun i j => by        rw [hBapp i j]        exact h0 (f i) (g j)      have hB1 : ∀ (i : Fin (k+1)) (j j' : Fin (k+1)), B i j = 1 → B i j' = 1 → j = j' := by        intro i j j' hj hj'        have hjA : A (f i) (g j) = 1 := by rw [← hBapp i j]; exact hj        have hjA' : A (f i) (g j') = 1 := by rw [← hBapp i j']; exact hj'        exact hg (h1 (f i) (g j) (g j') hjA hjA')      have hB2 : ∀ (i : Fin (k+1)) (j j' : Fin (k+1)), B i j = -1 → B i j' = -1 → j = j' := by        intro i j j' hj hj'        have hjA : A (f i) (g j) = -1 := by rw [← hBapp i j]; exact hj        have hjA' : A (f i) (g j') = -1 := by rw [← hBapp i j']; exact hj'        exact hg (h2 (f i) (g j) (g j') hjA hjA')      by_cases hex : ∃ (i0 : Fin (k+1)) (j0 : Fin (k+1)), ∀ j, j ≠ j0 → B i0 j = 0      · obtain ⟨i0, j0, hj0⟩ := hex        rw [Matrix.det_succ_row B i0]        rw [Finset.sum_eq_single j0]        · have hminor : (B.submatrix i0.succAbove j0.succAbove).det              = (A.submatrix (fun i => f (i0.succAbove i))                  (fun j => g (j0.succAbove j))).det := by            rw [hB, Matrix.submatrix_submatrix]            rfl          rw [hminor]          exact unit_incidence_matrix_isTotallyUnimodular_mul_mem            (unit_incidence_matrix_isTotallyUnimodular_mul_mem              (unit_incidence_matrix_isTotallyUnimodular_pow_mem _)              (unit_incidence_matrix_isTotallyUnimodular_tri_mem (hB0 i0 j0)))            (ih (fun i => f (i0.succAbove i)) (fun j => g (j0.succAbove j))              (hf.comp i0.succAbove_right_injective) (hg.comp j0.succAbove_right_injective))        · intro b _ hb          rw [hj0 b hb]          simp        · intro h          exact absurd (Finset.mem_univ j0) h      · push Not at hex        have hrow : ∀ i : Fin (k+1), ∑ j, B i j = 0 := by          intro i          obtain ⟨p, hp1, hp2⟩ := hex i 0          obtain ⟨q, hq1, hq2⟩ := hex i p          have hpq : p ≠ q := fun h => hq1 h.symm          have hpnz : B i p = 1 ∨ B i p = -1 := by            rcases hB0 i p with h | h | h            · exact absurd h hp2            · exact Or.inl h            · exact Or.inr h          have hqnz : B i q = 1 ∨ B i q = -1 := by            rcases hB0 i q with h | h | h            · exact absurd h hq2            · exact Or.inl h            · exact Or.inr h          have hmain : ∃ jp jq, jp ≠ jq ∧ B i jp = 1 ∧ B i jq = -1 := by            rcases hpnz with hp | hp <;> rcases hqnz with hq | hq            · exact absurd (hB1 i p q hp hq) hpq            · exact ⟨p, q, hpq, hp, hq⟩            · exact ⟨q, p, hpq.symm, hq, hp⟩            · exact absurd (hB2 i p q hp hq) hpq          obtain ⟨jp, jq, hjn, hjp, hjq⟩ := hmain          have key : ∀ j, j ≠ jp → j ≠ jq → B i j = 0 := by            intro j hj1 hj2            rcases hB0 i j with h | h | h            · exact h            · exact absurd (hB1 i j jp h hjp) hj1            · exact absurd (hB2 i j jq h hjq) hj2          have hsub := Finset.sum_subset (s₁ := {jp, jq}) (s₂ := Finset.univ) (by simp)            (by              intro x _ hx              simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx              exact key x hx.1 hx.2)          rw [← hsub, Finset.sum_pair hjn, hjp, hjq]          norm_num        have hnotLI : ¬ LinearIndependent ℤ (fun j : Fin (k+1) => Matrix.transpose B j) := by          intro h          have h' := Fintype.linearIndependent_iff.mp h (fun _ => 1) ?_          · exact one_ne_zero (h' 0)          · ext i            rw [Finset.sum_apply]            simp [hrow i]        have hdet : (Matrix.transpose B).det = 0 :=          Matrix.det_eq_zero_of_not_linearIndependent_rows hnotLI        rw [Matrix.det_transpose] at hdet        rw [hdet]        exact ⟨0, rfl⟩/-- Hou-Yang Lemma 2.2: a matrix whose rows are differences of standard basis vectors is totally unimodular, so every square minor is 0, 1 or -1. -/theorem unit_incidence_matrix_isTotallyUnimodular {m n : Type*} [DecidableEq n] (u v : m → n) :    (unit_incidence_matrix u v).IsTotallyUnimodular := by  refine unit_incidence_matrix_isTotallyUnimodular_aux _    (fun i j => ?_) (fun i j j' hj hj' => ?_) (fun i j j' hj hj' => ?_)  · simp only [unit_incidence_matrix, Matrix.of_apply]    by_cases hu : u i = j <;> by_cases hv : v i = j <;> simp [hu, hv]  · have key : ∀ j : n, unit_incidence_matrix u v i j = 1 → j = u i := by      intro j hj      simp only [unit_incidence_matrix, Matrix.of_apply] at hj      by_cases hu : u i = j      · exact hu.symm      · rw [if_neg hu] at hj        by_cases hv : v i = j        · rw [if_pos hv] at hj; norm_num at hj        · rw [if_neg hv] at hj; norm_num at hj    rw [key j hj, key j' hj']  · have key : ∀ j : n, unit_incidence_matrix u v i j = -1 → j = v i := by      intro j hj      simp only [unit_incidence_matrix, Matrix.of_apply] at hj      by_cases hv : v i = j      · exact hv.symm      · rw [if_neg hv] at hj        by_cases hu : u i = j        · rw [if_pos hu] at hj; norm_num at hj        · rw [if_neg hu] at hj; norm_num at hj    rw [key j hj, key j' hj']
See it in the graphDiscuss this resultChallenge it