binary_six_zero_sum_gram_rank
The sum of the outer squares of six distinct binary vectors with zero sum has matrix rank exactly four.
Statement
theorem binary_six_zero_sum_gram_rank {n : ℕ} (v : Fin 6 → (Fin n → ZMod 2)) (hinj : Function.Injective v) (hsum : ∑ j, v j = 0) : (Matrix.of (fun i j => ∑ k : Fin 6, v k i * v k j)).rank = 4
- Source
- Supporting algebra for OP-3, arXiv:2610.01024, Section E.1; developed in deep session IN-184. These helpers do not establish a lower bound for arbitrary circuit gate lists.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- binary_six_zero_sum_differences_independentFor six distinct binary vectors with zero sum, the differences of vectors 1 through 4 from vector 0 are linearly independent.
- Used by 1
- binary_rank_two_even_zero_sum_support_card_gapA finite set of binary vectors with even cardinality, zero vector sum and Gram rank two has exactly four elements or at least eight.
The proof, explained
The Gram-like matrix M = ∑_{k=0}^5 v_k v_k^T over ZMod 2 is factored as M = V * J * V^T, where V is an n × 4 matrix whose columns are four linearly independent difference vectors, and J is the 4 × 4 hollow matrix of all ones with zero diagonal. Because V has linearly independent columns, left multiplication by V preserves matrix rank. Repeatedly applying this rank preservation and transposition reduces the rank of M to the rank of J, which is 4 because its determinant is non-zero over ZMod 2.
Define an n × 4 difference matrix V and a 4 × 4 hollow matrix J over ZMod 2.
We define V as the n × 4 matrix whose four columns are the difference vectors v (j + 1) + v 0 for j ∈ Fin 4, and J as the 4 × 4 matrix with 0 on the diagonal and 1 elsewhere.
classical let V : Matrix (Fin n) (Fin 4) (ZMod 2) := fun i j => v ⟨j.val + 1, by omega⟩ i + v 0 i let J : Matrix (Fin 4) (Fin 4) (ZMod 2) := fun i j => if i = j then 0 else 1
The columns of V are linearly independent over ZMod 2.
Applying binary_six_zero_sum_differences_independent to the injective family of six vectors summing to zero establishes that the four columns of V are linearly independent.
uses
binary_six_zero_sum_differences_independenthave hLI := binary_six_zero_sum_differences_independent v hinj hsumThe linear operator defined by V is injective.
By LinearMap.ker_eq_bot and LinearMap.ker_eq_bot', injectivity is equivalent to having a trivial kernel. If V a = 0 for some vector a, taking the components shows that the linear combination ∑ j, a j • (v (j + 1) + v 0) = 0. Since the columns are linearly independent, Fintype.linearIndependent_iff.mp forces every coefficient a j to be zero, so a = 0.
uses
LinearMap.ker_eq_bot,LinearMap.ker_eq_bot',Fintype.linearIndependent_iff.mphave hV : Function.Injective V.mulVecLin := by rw [← LinearMap.ker_eq_bot, LinearMap.ker_eq_bot'] intro a ha change V.mulVec a = 0 at ha have hrel : ∑ j : Fin 4, a j • (v ⟨j.val + 1, by omega⟩ + v 0) = 0 := by funext i have h := congrFun ha i simpa [V, Matrix.mulVecLin_apply, Matrix.mulVec, dotProduct, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, mul_comm, mul_add] using h have hc := Fintype.linearIndependent_iff.mp hLI a hrel funext j exact hc j
The Gram matrix factors as V * J * V.transpose.
We verify the identity entry by entry at each (i, j). From the zero-sum hypothesis ∑ k, v k = 0, applying congrFun and splitting the sum with Fin.sum_univ_succ gives v 5 = v 0 + v 1 + v 2 + v 3 + v 4 (in characteristic 2). Using Matrix.mul_apply and Matrix.transpose_apply to expand the product V * J * V.transpose and substituting for v 5, both sides reduce to the same polynomial expression over ZMod 2.
uses
congrFun,Fin.sum_univ_succ,Matrix.mul_apply,Matrix.transpose_applyhave hfactor : Matrix.of (fun i j => ∑ k : Fin 6, v k i * v k j) = V * J * V.transpose := by ext i j have hi := congrFun hsum i have hj := congrFun hsum j simp [Fin.sum_univ_succ] at hi hj have hi5 : v 5 i = v 0 i + v 1 i + v 2 i + v 3 i + v 4 i := by linear_combination (norm := ring_nf) hi <;> reduce_mod_char have hj5 : v 5 j = v 0 j + v 1 j + v 2 j + v 3 j + v 4 j := by linear_combination (norm := ring_nf) hj <;> reduce_mod_char simp_rw [Matrix.mul_apply, Matrix.transpose_apply] simp [Fin.sum_univ_succ, V, J, hi5, hj5] ring_nf <;> reduce_mod_char
Left multiplication by V preserves matrix rank.
By Matrix.rank, the rank of a matrix is the dimension of the range of its associated linear map. By Matrix.mulVecLin_mul and LinearMap.range_comp, the range of (V * B).mulVecLin is the image under V.mulVecLin of the range of B.mulVecLin. Because V.mulVecLin is injective, Submodule.equivMapOfInjective provides a linear isomorphism between B's range and its image, which preserves dimension.
uses
Matrix.rank,Matrix.mulVecLin_mul,LinearMap.range_comp,Submodule.equivMapOfInjectivehave hr {k : ℕ} (B : Matrix (Fin 4) (Fin k) (ZMod 2)) : (V * B).rank = B.rank := by rw [Matrix.rank, Matrix.rank, Matrix.mulVecLin_mul, LinearMap.range_comp] exact (Submodule.equivMapOfInjective V.mulVecLin hV _).finrank_eq.symm
The matrix J has rank 4.
The determinant of J is non-zero (evaluated by decide in ZMod 2). By Matrix.rank_of_det_ne_zero, a square matrix with non-zero determinant has full rank, so J has rank 4.
uses
Matrix.rank_of_det_ne_zerohave hJ : J.rank = 4 := by simpa using Matrix.rank_of_det_ne_zero (show J.det ≠ 0 by decide)
The Gram matrix has rank 4.
Substituting the factorization V * J * V.transpose and using Matrix.mul_assoc and rank preservation of V, rank(V * (J * V.transpose)) = rank(J * V.transpose). Transposing with Matrix.rank_transpose and Matrix.transpose_mul gives rank(V * J.transpose), which again by rank preservation reduces to rank(J.transpose) = rank(J) = 4.
uses
Matrix.mul_assoc,Matrix.rank_transpose,Matrix.transpose_mul,Matrix.transpose_transposerw [hfactor, Matrix.mul_assoc, hr, ← Matrix.rank_transpose, Matrix.transpose_mul, Matrix.transpose_transpose, hr, Matrix.rank_transpose, hJ]
binary_six_zero_sum_differences_independent- For six distinct vectors over ZMod 2 summing to zero, the four difference vectors v (i + 1) + v 0 (i = 0, 1, 2, 3) are linearly independent.
LinearMap.ker_eq_bot- A linear map is injective if and only if its kernel is the zero submodule.
LinearMap.ker_eq_bot'- A linear map has trivial kernel if and only if the only vector mapped to zero is zero.
Fintype.linearIndependent_iff.mp- For a linearly independent family of vectors over a finite type, any vanishing linear combination has all coefficients equal to zero.
congrFun- If two functions are equal, their values on any argument are equal.
Fin.sum_univ_succ- A sum over Fin (n + 1) equals the value at 0 plus the sum over the succ-shifted remaining elements.
Matrix.mul_apply- The (i, k)-th entry of a matrix product M * N is the sum over j of M i j * N j k.
Matrix.transpose_apply- The (i, j)-th entry of the transpose of M is M j i.
Matrix.rank- The rank of a matrix is defined as the dimension (finrank) of the range of its associated linear map.
Matrix.mulVecLin_mul- The linear map associated with a matrix product M * N is the composition of the linear maps for M and N.
LinearMap.range_comp- The range of the composition of two linear maps is the image under the second map of the range of the first.
Submodule.equivMapOfInjective- An injective linear map restricts to an isomorphism between any submodule and its image submodule, thereby preserving dimension.
Matrix.rank_of_det_ne_zero- A square matrix over a domain with non-zero determinant has full rank equal to its row/column count.
Matrix.mul_assoc- Matrix multiplication is associative: (L * M) * N = L * (M * N).
Matrix.rank_transpose- The rank of the transpose of a matrix over a field equals the rank of the matrix.
Matrix.transpose_mul- The transpose of a matrix product M * N is the product of the transposes in reverse order: N.transpose * M.transpose.
Matrix.transpose_transpose- The double transpose of a matrix is the matrix itself.
- The algebraic identity in step 4 is closed by ring normal form calculations modulo 2 (linear_combination, ring_nf, and reduce_mod_char).
- The non-vanishing of the determinant of J in step 6 is verified by native computational reflection (decide).
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 binary_six_zero_sum_gram_rank {n : ℕ} (v : Fin 6 → (Fin n → ZMod 2)) (hinj : Function.Injective v) (hsum : ∑ j, v j = 0) : (Matrix.of (fun i j => ∑ k : Fin 6, v k i * v k j)).rank = 4 := by classical let V : Matrix (Fin n) (Fin 4) (ZMod 2) := fun i j => v ⟨j.val + 1, by omega⟩ i + v 0 i let J : Matrix (Fin 4) (Fin 4) (ZMod 2) := fun i j => if i = j then 0 else 1 have hLI := binary_six_zero_sum_differences_independent v hinj hsum have hV : Function.Injective V.mulVecLin := by rw [← LinearMap.ker_eq_bot, LinearMap.ker_eq_bot'] intro a ha change V.mulVec a = 0 at ha have hrel : ∑ j : Fin 4, a j • (v ⟨j.val + 1, by omega⟩ + v 0) = 0 := by funext i have h := congrFun ha i simpa [V, Matrix.mulVecLin_apply, Matrix.mulVec, dotProduct, Finset.sum_apply, Pi.smul_apply, smul_eq_mul, mul_comm, mul_add] using h have hc := Fintype.linearIndependent_iff.mp hLI a hrel funext j exact hc j have hfactor : Matrix.of (fun i j => ∑ k : Fin 6, v k i * v k j) = V * J * V.transpose := by ext i j have hi := congrFun hsum i have hj := congrFun hsum j simp [Fin.sum_univ_succ] at hi hj have hi5 : v 5 i = v 0 i + v 1 i + v 2 i + v 3 i + v 4 i := by linear_combination (norm := ring_nf) hi <;> reduce_mod_char have hj5 : v 5 j = v 0 j + v 1 j + v 2 j + v 3 j + v 4 j := by linear_combination (norm := ring_nf) hj <;> reduce_mod_char simp_rw [Matrix.mul_apply, Matrix.transpose_apply] simp [Fin.sum_univ_succ, V, J, hi5, hj5] ring_nf <;> reduce_mod_char have hr {k : ℕ} (B : Matrix (Fin 4) (Fin k) (ZMod 2)) : (V * B).rank = B.rank := by rw [Matrix.rank, Matrix.rank, Matrix.mulVecLin_mul, LinearMap.range_comp] exact (Submodule.equivMapOfInjective V.mulVecLin hV _).finrank_eq.symm have hJ : J.rank = 4 := by simpa using Matrix.rank_of_det_ne_zero (show J.det ≠ 0 by decide) rw [hfactor, Matrix.mul_assoc, hr, ← Matrix.rank_transpose, Matrix.transpose_mul, Matrix.transpose_transpose, hr, Matrix.rank_transpose, hJ]