AFTD Auto-Formalizing Theoretical Domains

bordered_goethals_seidel_lower_block

theoremverified

If the circulants A, B, C, D (m > 0) satisfy AAᵀ + BBᵀ + CCᵀ + DDᵀ = (4m+4)I - 4J, then L Lᵀ + M Mᵀ = (4m+4) I for the left border L and the Goethals-Seidel array M of the bordered Goethals-Seidel matrix.

Statement

theorem bordered_goethals_seidel_lower_block {m : ℕ} [NeZero m] (a b c d : Fin m → ℤ)
    (hsum : Matrix.circulant a * (Matrix.circulant a).transpose
        + Matrix.circulant b * (Matrix.circulant b).transpose
        + Matrix.circulant c * (Matrix.circulant c).transpose
        + Matrix.circulant d * (Matrix.circulant d).transpose
        = (4 * m + 4 : ℤ) • (1 : Matrix (Fin m) (Fin m) ℤ) - 4 • Matrix.of (fun _ _ => (1 : ℤ))) :
    (Matrix.of fun (p : Fin 4 × Fin m) (c : Fin 4) =>
        !![(1 : ℤ), 1, 1, 1; -1, 1, 1, -1; -1, -1, 1, 1; -1, 1, -1, 1] p.1 c)
      * (Matrix.of fun (p : Fin 4 × Fin m) (c : Fin 4) =>
        !![(1 : ℤ), 1, 1, 1; -1, 1, 1, -1; -1, -1, 1, 1; -1, 1, -1, 1] p.1 c).transpose
      + goethals_seidel_array (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c)
          (Matrix.circulant d) (back_identity_matrix m)
        * (goethals_seidel_array (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c)
          (Matrix.circulant d) (back_identity_matrix m)).transpose
      = (4 * m + 4 : ℤ) • (1 : Matrix (Fin 4 × Fin m) (Fin 4 × Fin m) ℤ)
Source
step of arXiv:2610.27175 Theorem 5 (bottom-right block of H Hᵀ)
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • back_identity_matrixThe back-identity (reversal) matrix R of order m over ℤ: R i j = 1 when i + j ≡ m - 1 (mod m), equivalently i + j + 1 = m for indices…
  • goethals_seidel_arrayThe Goethals-Seidel array of order 4m in four m × m matrices A, B, C, D and R, indexed by (block row, row): rows of blocks (A, BR, CR,…
  • goethals_seidel_array_mul_transposeFor circulant integer matrices A, B, C, D of order m > 0 and R the back-identity matrix, the Goethals-Seidel array M satisfies M Mᵀ =…
Used by 1
  • bordered_goethals_seidel_is_hadamardLet m be even and let A, B, C, D be circulant {±1}-matrices of order m (first columns a, b, c, d) with AAᵀ + BBᵀ + CCᵀ + DDᵀ = (4m+4)I -…

The proof, explained

The proof verifies the identity L Lᵀ + M Mᵀ = (4m+4) I by examining its block structure. Using a known algebraic property of the Goethals-Seidel array and the hypothesis on the circulant matrices, M Mᵀ is block-diagonal with diagonal blocks equal to (4m+4) I_m - 4 J_m and zero off-diagonal blocks. The product L Lᵀ is block-constant, with each (p, q) block given by the dot product of row p and row q of an explicit 4 × 4 Hadamard matrix. An exhaustive check of all 16 block pairs (p, q) shows that the dot product is 4 when p = q (cancelling the -4 from -4 J_m to leave (4m+4) I) and 0 when p ≠ q by row orthogonality, completing the identity.

  1. The product M Mᵀ is replaced by a block-diagonal matrix whose diagonal blocks are (4m + 4) I_m - 4 J_m and whose off-diagonal blocks are zero.

    By lemma goethals_seidel_array_mul_transpose, the product of the Goethals-Seidel array with its transpose is block-diagonal with diagonal blocks given by A Aᵀ + B Bᵀ + C Cᵀ + D Dᵀ and off-diagonal blocks equal to zero. Substituting the hypothesis hsum replaces each diagonal block with (4m + 4) I_m - 4 J_m, where J_m is the all-ones matrix.

    line 16

    uses goethals_seidel_array_mul_transpose

      rw [goethals_seidel_array_mul_transpose, hsum]
  2. The matrix equation reduces entrywise to checking that for all block indices p, q ∈ Fin 4 and internal indices i, j ∈ Fin m, the dot product of rows p and q of the 4 × 4 border template plus the (p, q)-block contribution equals (4m + 4) δ_{(p, i), (q, j)}.

    Matrix extensionality reduces matrix equality to checking equality at each index pair ((p, i), (q, j)). Then, expanding the entrywise definitions of matrix addition, matrix multiplication, scalar multiplication, subtraction, and the identity matrix expresses the ((p, i), (q, j)) entry of L Lᵀ as the dot product ∑_{k=0}^3 H_{p, k} H_{q, k} of rows p and q of the 4 × 4 border matrix H, while the M Mᵀ term contributes ((4m + 4) δ_{i, j} - 4) if p = q and 0 otherwise.

    lines 17–19

    uses Matrix.add_apply, Matrix.mul_apply, Matrix.of_apply, Matrix.smul_apply, Matrix.sub_apply, Matrix.one_apply, smul_eq_mul, Prod.mk.injEq, Matrix.transpose_apply

      ext ⟨p, i⟩ ⟨q, j⟩
      simp only [Matrix.add_apply, Matrix.mul_apply, Matrix.of_apply, Matrix.smul_apply,
        Matrix.sub_apply, Matrix.one_apply, smul_eq_mul, Prod.mk.injEq, Matrix.transpose_apply]
  3. The entrywise identity holds for every choice of block indices p, q ∈ Fin 4 and internal indices i, j ∈ Fin m.

    Case exhaustion over p, q ∈ Fin 4 splits the goal into 16 cases. In each case, Fin.sum_univ_four expands the dot product of rows p and q of the border matrix into 4 terms. When p = q, the self dot product is 1² + 1² + 1² + 1² = 4, which cancels the -4 from the diagonal block of M Mᵀ, leaving (4m + 4) δ_{i, j}. When p ≠ q, the two rows are orthogonal with dot product 0, which matches the off-diagonal block value 0.

    lines 20–21

    uses Fin.sum_univ_four

      fin_cases p <;> fin_cases q <;>
        simp [Fin.sum_univ_four]
goethals_seidel_array_mul_transpose
The product of a Goethals-Seidel array with its transpose is a block-diagonal matrix whose diagonal blocks are the sum of the four circulants multiplied by their transposes, and whose off-diagonal blocks are zero.
Matrix.add_apply
The (i, j) entry of the sum of two matrices is the sum of their (i, j) entries.
Matrix.mul_apply
The (i, k) entry of the product of two matrices M and N is the sum over j of M i j * N j k.
Matrix.of_apply
Evaluating a matrix defined by a function f at indices (i, j) yields f i j.
Matrix.smul_apply
The (i, j) entry of a scalar multiple r • A is r times the (i, j) entry of A.
Matrix.sub_apply
The (i, j) entry of the difference of two matrices is the difference of their (i, j) entries.
Matrix.one_apply
The (i, j) entry of the identity matrix is 1 if i = j and 0 otherwise.
smul_eq_mul
Scalar multiplication on integers is ordinary integer multiplication.
Prod.mk.injEq
Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Matrix.transpose_apply
The (i, j) entry of the transpose matrix Mᵀ is the (j, i) entry of M.
Fin.sum_univ_four
The sum of a function over Fin 4 is the sum of its values at indices 0, 1, 2, and 3.

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 bordered_goethals_seidel_lower_block {m : ℕ} [NeZero m] (a b c d : Fin m → ℤ)    (hsum : Matrix.circulant a * (Matrix.circulant a).transpose        + Matrix.circulant b * (Matrix.circulant b).transpose        + Matrix.circulant c * (Matrix.circulant c).transpose        + Matrix.circulant d * (Matrix.circulant d).transpose        = (4 * m + 4 : ℤ) • (1 : Matrix (Fin m) (Fin m) ℤ) - 4 • Matrix.of (fun _ _ => (1 : ℤ))) :    (Matrix.of fun (p : Fin 4 × Fin m) (c : Fin 4) =>        !![(1 : ℤ), 1, 1, 1; -1, 1, 1, -1; -1, -1, 1, 1; -1, 1, -1, 1] p.1 c)      * (Matrix.of fun (p : Fin 4 × Fin m) (c : Fin 4) =>        !![(1 : ℤ), 1, 1, 1; -1, 1, 1, -1; -1, -1, 1, 1; -1, 1, -1, 1] p.1 c).transpose      + goethals_seidel_array (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c)          (Matrix.circulant d) (back_identity_matrix m)        * (goethals_seidel_array (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c)          (Matrix.circulant d) (back_identity_matrix m)).transpose      = (4 * m + 4 : ℤ) • (1 : Matrix (Fin 4 × Fin m) (Fin 4 × Fin m) ℤ) := by  rw [goethals_seidel_array_mul_transpose, hsum]  ext ⟨p, i⟩ ⟨q, j⟩  simp only [Matrix.add_apply, Matrix.mul_apply, Matrix.of_apply, Matrix.smul_apply,    Matrix.sub_apply, Matrix.one_apply, smul_eq_mul, Prod.mk.injEq, Matrix.transpose_apply]  fin_cases p <;> fin_cases q <;>    simp [Fin.sum_univ_four]
See it in the graphDiscuss this resultChallenge it