unit_incidence_matrix_isTotallyUnimodular
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.
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.
uses
pow_memlemma 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⟩
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.
uses
mul_memlemma 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
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.
uses
SignType.coe_one,SignType.coe_neg_onelemma 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⟩
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.
uses
Matrix.submatrix_empty,Matrix.det_fin_zero,SignType.coe_onelemma 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]⟩
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.
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')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.
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_univby_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
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.
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
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.
uses
Fintype.linearIndependent_iff.mp,one_ne_zero,Finset.sum_apply,Matrix.det_eq_zero_of_not_linearIndependent_rows,Matrix.det_transposehave 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⟩
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.
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]
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.
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']
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.
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
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.
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']