AFTD Auto-Formalizing Theoretical Domains

binary_six_zero_sum_gram_rank

theoremverified

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
Used by 1

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.

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

    lines 5–9

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

    line 10

    uses binary_six_zero_sum_differences_independent

      have hLI := binary_six_zero_sum_differences_independent v hinj hsum
  3. The 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.

    lines 11–22

    uses LinearMap.ker_eq_bot, LinearMap.ker_eq_bot', Fintype.linearIndependent_iff.mp

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

    lines 23–34

    uses congrFun, Fin.sum_univ_succ, Matrix.mul_apply, Matrix.transpose_apply

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

    lines 35–38

    uses Matrix.rank, Matrix.mulVecLin_mul, LinearMap.range_comp, Submodule.equivMapOfInjective

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

    lines 39–40

    uses Matrix.rank_of_det_ne_zero

      have hJ : J.rank = 4 := by
        simpa using Matrix.rank_of_det_ne_zero (show J.det ≠ 0 by decide)
  7. 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.

    lines 41–42

    uses Matrix.mul_assoc, Matrix.rank_transpose, Matrix.transpose_mul, Matrix.transpose_transpose

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

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