four_cycle_weighted_matrix_rank_eq_four
For any field F of characteristic two and any injective function t : Fin 4 → F, the cycle weighted adjacency matrix cycle_weighted_adjacency_matrix 4 t has rank 4.
Statement
theorem four_cycle_weighted_matrix_rank_eq_four {F : Type*} [Field F] [CharP F 2] (t : Fin 4 → F) (hinj : Function.Injective t) : (cycle_weighted_adjacency_matrix 4 t).rank = 4
- Formalizes
- arXiv:2610.27080, Section III.1, Eq. (17)
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cycle_weighted_adjacency_matrixFor a type α equipped with AddZeroClass, a natural number n, and a function t : Fin n → α, cycle_weighted_adjacency_matrix n t is the Fin…
Read back from the Lean
For any field $F$ of characteristic 2, and any injective function $t : Fin 4 → F$, the rank of cycle_weighted_adjacency_matrix 4 t is equal to 4.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We show that the weighted adjacency matrix has trivial kernel and therefore full rank 4.
The rank is 4
The rank of the matrix is 4.
have ht02 : t 0 ≠ t 2 := by intro h have : (0 : Fin 4) = 2 := hinj h revert this; decide have ht13 : t 1 ≠ t 3 := by intro h have : (1 : Fin 4) = 3 := hinj h revert this; decide have h_inj : Function.Injective (cycle_weighted_adjacency_matrix 4 t).mulVecLin := by intro v w hvw have h_sub : (cycle_weighted_adjacency_matrix 4 t).mulVecLin (v - w) = 0 := by rw [map_sub, hvw, sub_self] have h_zero : (cycle_weighted_adjacency_matrix 4 t).mulVec (v - w) = 0 := h_sub have h_ker : ∀ (u : Fin 4 → F), (cycle_weighted_adjacency_matrix 4 t).mulVec u = 0 → u = 0 := by intro u hu have e0 : (t 0 + t 1) * u 1 + (t 0 + t 3) * u 3 = 0 := by have := congr_fun hu 0 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a01 : (SimpleGraph.cycleGraph 4).Adj (0 : Fin 4) 1 := by decide have a02 : ¬ (SimpleGraph.cycleGraph 4).Adj (0 : Fin 4) 2 := by decide have a03 : (SimpleGraph.cycleGraph 4).Adj (0 : Fin 4) 3 := by decide simp [a01, a02, a03] at this exact this have e1 : (t 1 + t 0) * u 0 + (t 1 + t 2) * u 2 = 0 := by have := congr_fun hu 1 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a10 : (SimpleGraph.cycleGraph 4).Adj (1 : Fin 4) 0 := by decide have a12 : (SimpleGraph.cycleGraph 4).Adj (1 : Fin 4) 2 := by decide have a13 : ¬ (SimpleGraph.cycleGraph 4).Adj (1 : Fin 4) 3 := by decide simp [a10, a12, a13] at this exact this have e2 : (t 2 + t 1) * u 1 + (t 2 + t 3) * u 3 = 0 := by have := congr_fun hu 2 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a20 : ¬ (SimpleGraph.cycleGraph 4).Adj (2 : Fin 4) 0 := by decide have a21 : (SimpleGraph.cycleGraph 4).Adj (2 : Fin 4) 1 := by decide have a23 : (SimpleGraph.cycleGraph 4).Adj (2 : Fin 4) 3 := by decide simp [a20, a21, a23] at this exact this have e3 : (t 3 + t 0) * u 0 + (t 3 + t 2) * u 2 = 0 := by have := congr_fun hu 3 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a30 : (SimpleGraph.cycleGraph 4).Adj (3 : Fin 4) 0 := by decide have a31 : ¬ (SimpleGraph.cycleGraph 4).Adj (3 : Fin 4) 1 := by decide have a32 : (SimpleGraph.cycleGraph 4).Adj (3 : Fin 4) 2 := by decide simp [a30, a31, a32] at this exact this have hu13 : (t 0 + t 2) * (u 1 + u 3) = 0 := four_cycle_weighted_matrix_rank_eq_four_step1 (t 0) (t 1) (t 2) (t 3) (u 1) (u 3) e0 e2 have hu1_eq_3 : u 1 = u 3 := four_cycle_weighted_matrix_rank_eq_four_step2 (t 0) (t 2) (u 1) (u 3) ht02 hu13 have hu1_zero : u 1 = 0 := four_cycle_weighted_matrix_rank_eq_four_step3 (t 0) (t 1) (t 3) (u 1) (u 3) e0 hu1_eq_3 ht13 have hu3_zero : u 3 = 0 := by rw [← hu1_eq_3, hu1_zero] have hu02 : (t 1 + t 3) * (u 0 + u 2) = 0 := four_cycle_weighted_matrix_rank_eq_four_step1 (t 1) (t 0) (t 3) (t 2) (u 0) (u 2) e1 e3 have hu0_eq_2 : u 0 = u 2 := four_cycle_weighted_matrix_rank_eq_four_step2 (t 1) (t 3) (u 0) (u 2) ht13 hu02 have hu0_zero : u 0 = 0 := four_cycle_weighted_matrix_rank_eq_four_step3 (t 1) (t 0) (t 2) (u 0) (u 2) e1 hu0_eq_2 ht02 have hu2_zero : u 2 = 0 := by rw [← hu0_eq_2, hu0_zero] ext i fin_cases i · exact hu0_zero · exact hu1_zero · exact hu2_zero · exact hu3_zero have h_diff : v - w = 0 := h_ker (v - w) h_zero exact sub_eq_zero.mp h_diff rw [Matrix.rank, LinearMap.finrank_range_of_inj h_inj] simp
- Unresolved check: no step explains line(s) 8, 9, 10, 11, 16, 17, 18, 19, 20, 21, 22, 28, 29, 30, 31, 32, 33, 34, 35, 36 -- every tactic of the proof has to belong to some step
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.
open scoped CharTwolemma four_cycle_weighted_matrix_rank_eq_four_step1 {F : Type*} [CommRing F] [CharP F 2] (a b c d v1 v3 : F) (h0 : (a + b) * v1 + (a + d) * v3 = 0) (h2 : (c + b) * v1 + (c + d) * v3 = 0) : (a + c) * (v1 + v3) = 0 := by have h : (a + c) * (v1 + v3) = ((a + b) * v1 + (a + d) * v3) + ((c + b) * v1 + (c + d) * v3) - 2 * (b * v1 + d * v3) := by ring rw [h, h0, h2] simplemma four_cycle_weighted_matrix_rank_eq_four_step2 {F : Type*} [Field F] [CharP F 2] (a c v1 v3 : F) (hac : a ≠ c) (h : (a + c) * (v1 + v3) = 0) : v1 = v3 := by have hac_add : a + c ≠ 0 := by intro h0 apply hac rwa [CharTwo.add_eq_zero] at h0 cases mul_eq_zero.mp h with | inl h1 => exact (hac_add h1).elim | inr h2 => rwa [CharTwo.add_eq_zero] at h2lemma four_cycle_weighted_matrix_rank_eq_four_step3 {F : Type*} [Field F] [CharP F 2] (a b d v1 v3 : F) (h0 : (a + b) * v1 + (a + d) * v3 = 0) (hv : v1 = v3) (hbd : b ≠ d) : v1 = 0 := by have hbd_add : b + d ≠ 0 := by intro h0' apply hbd rwa [CharTwo.add_eq_zero] at h0' have hid : (b + d) * v1 = 0 := by calc (b + d) * v1 _ = ((a + b) * v1 + (a + d) * v3) - 2 * a * v1 - (a + d) * (v3 - v1) := by ring _ = 0 := by rw [h0, hv]; simp cases mul_eq_zero.mp hid with | inl h1 => exact (hbd_add h1).elim | inr h2 => exact h2/-- For any field of characteristic two and any injective 4-tuple, the weighted adjacency matrix of the 4-cycle has full rank 4. -/theorem four_cycle_weighted_matrix_rank_eq_four {F : Type*} [Field F] [CharP F 2] (t : Fin 4 → F) (hinj : Function.Injective t) : (cycle_weighted_adjacency_matrix 4 t).rank = 4 := by have ht02 : t 0 ≠ t 2 := by intro h have : (0 : Fin 4) = 2 := hinj h revert this; decide have ht13 : t 1 ≠ t 3 := by intro h have : (1 : Fin 4) = 3 := hinj h revert this; decide have h_inj : Function.Injective (cycle_weighted_adjacency_matrix 4 t).mulVecLin := by intro v w hvw have h_sub : (cycle_weighted_adjacency_matrix 4 t).mulVecLin (v - w) = 0 := by rw [map_sub, hvw, sub_self] have h_zero : (cycle_weighted_adjacency_matrix 4 t).mulVec (v - w) = 0 := h_sub have h_ker : ∀ (u : Fin 4 → F), (cycle_weighted_adjacency_matrix 4 t).mulVec u = 0 → u = 0 := by intro u hu have e0 : (t 0 + t 1) * u 1 + (t 0 + t 3) * u 3 = 0 := by have := congr_fun hu 0 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a01 : (SimpleGraph.cycleGraph 4).Adj (0 : Fin 4) 1 := by decide have a02 : ¬ (SimpleGraph.cycleGraph 4).Adj (0 : Fin 4) 2 := by decide have a03 : (SimpleGraph.cycleGraph 4).Adj (0 : Fin 4) 3 := by decide simp [a01, a02, a03] at this exact this have e1 : (t 1 + t 0) * u 0 + (t 1 + t 2) * u 2 = 0 := by have := congr_fun hu 1 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a10 : (SimpleGraph.cycleGraph 4).Adj (1 : Fin 4) 0 := by decide have a12 : (SimpleGraph.cycleGraph 4).Adj (1 : Fin 4) 2 := by decide have a13 : ¬ (SimpleGraph.cycleGraph 4).Adj (1 : Fin 4) 3 := by decide simp [a10, a12, a13] at this exact this have e2 : (t 2 + t 1) * u 1 + (t 2 + t 3) * u 3 = 0 := by have := congr_fun hu 2 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a20 : ¬ (SimpleGraph.cycleGraph 4).Adj (2 : Fin 4) 0 := by decide have a21 : (SimpleGraph.cycleGraph 4).Adj (2 : Fin 4) 1 := by decide have a23 : (SimpleGraph.cycleGraph 4).Adj (2 : Fin 4) 3 := by decide simp [a20, a21, a23] at this exact this have e3 : (t 3 + t 0) * u 0 + (t 3 + t 2) * u 2 = 0 := by have := congr_fun hu 3 simp only [Matrix.mulVec, dotProduct, Fin.sum_univ_four] at this dsimp [cycle_weighted_adjacency_matrix] at this have a30 : (SimpleGraph.cycleGraph 4).Adj (3 : Fin 4) 0 := by decide have a31 : ¬ (SimpleGraph.cycleGraph 4).Adj (3 : Fin 4) 1 := by decide have a32 : (SimpleGraph.cycleGraph 4).Adj (3 : Fin 4) 2 := by decide simp [a30, a31, a32] at this exact this have hu13 : (t 0 + t 2) * (u 1 + u 3) = 0 := four_cycle_weighted_matrix_rank_eq_four_step1 (t 0) (t 1) (t 2) (t 3) (u 1) (u 3) e0 e2 have hu1_eq_3 : u 1 = u 3 := four_cycle_weighted_matrix_rank_eq_four_step2 (t 0) (t 2) (u 1) (u 3) ht02 hu13 have hu1_zero : u 1 = 0 := four_cycle_weighted_matrix_rank_eq_four_step3 (t 0) (t 1) (t 3) (u 1) (u 3) e0 hu1_eq_3 ht13 have hu3_zero : u 3 = 0 := by rw [← hu1_eq_3, hu1_zero] have hu02 : (t 1 + t 3) * (u 0 + u 2) = 0 := four_cycle_weighted_matrix_rank_eq_four_step1 (t 1) (t 0) (t 3) (t 2) (u 0) (u 2) e1 e3 have hu0_eq_2 : u 0 = u 2 := four_cycle_weighted_matrix_rank_eq_four_step2 (t 1) (t 3) (u 0) (u 2) ht13 hu02 have hu0_zero : u 0 = 0 := four_cycle_weighted_matrix_rank_eq_four_step3 (t 1) (t 0) (t 2) (u 0) (u 2) e1 hu0_eq_2 ht02 have hu2_zero : u 2 = 0 := by rw [← hu0_eq_2, hu0_zero] ext i fin_cases i · exact hu0_zero · exact hu1_zero · exact hu2_zero · exact hu3_zero have h_diff : v - w = 0 := h_ker (v - w) h_zero exact sub_eq_zero.mp h_diff rw [Matrix.rank, LinearMap.finrank_range_of_inj h_inj] simp