AFTD Auto-Formalizing Theoretical Domains

bordered_goethals_seidel_corner_block

theoremverified

For the bordered Goethals-Seidel matrix: K Kᵀ + T Tᵀ = (4m+4) I₄, where K is the 4 × 4 corner (diagonal 1, off-diagonal -1) and T the 4 × 4m top border of ±j blocks.

Statement

theorem bordered_goethals_seidel_corner_block (m : ℕ) :
    !![(1 : ℤ), -1, -1, -1; -1, 1, -1, -1; -1, -1, 1, -1; -1, -1, -1, 1]
        * !![(1 : ℤ), -1, -1, -1; -1, 1, -1, -1; -1, -1, 1, -1; -1, -1, -1, 1].transpose
      + (Matrix.of fun (r : Fin 4) (q : Fin 4 × Fin m) =>
          !![(1 : ℤ), 1, 1, 1; 1, -1, 1, -1; 1, -1, -1, 1; 1, 1, -1, -1] r q.1)
        * (Matrix.of fun (r : Fin 4) (q : Fin 4 × Fin m) =>
          !![(1 : ℤ), 1, 1, 1; 1, -1, 1, -1; 1, -1, -1, 1; 1, 1, -1, -1] r q.1).transpose
      = (4 * m + 4 : ℤ) • (1 : Matrix (Fin 4) (Fin 4) ℤ)
Source
step of arXiv:2610.27175 Theorem 5 (top-left block of H Hᵀ)
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
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 theorem establishes that the corner block equation K Kᵀ + T Tᵀ = (4m + 4) I₄ holds in the bordered Goethals-Seidel matrix construction. Conceptually, the 4 × 4 corner matrix satisfies K Kᵀ = 4 I₄, and the 4 × 4m border matrix T consists of m copies of an order-4 Hadamard matrix H satisfying H Hᵀ = 4 I₄, so T Tᵀ = 4m I₄. The formal proof applies matrix extensionality, unfolds the matrix operations into coordinate-wise sums, and verifies the identity across all 16 pairs of indices by unrolling the finite sums and performing ring arithmetic.

  1. It suffices to show that the matrices are equal entrywise at every position (r, r') for r, r' ∈ Fin 4.

    By matrix extensionality (`ext`), two matrices of the same size are equal if and only if their entries match at every row r and column r'.

    line 9

      ext r r'
  2. The (r, r') entry of each side is expanded into sums of integer products.

    Using the entrywise definitions of matrix addition, matrix multiplication, transposition, and scalar multiplication, the left-hand side expands into a dot product of row r and row r' of the 4 × 4 corner matrix plus a sum over the 4m columns of the border matrix. Using `Fintype.sum_prod_type`, the summation over Fin 4 × Fin m is split into an outer sum over the 4 base columns and an inner sum over the m copies. The right-hand side simplifies to (4m + 4) when r = r' and 0 when r ≠ r'.

    lines 10–11

    uses Matrix.add_apply, Matrix.mul_apply, Matrix.of_apply, Matrix.transpose_apply, Fintype.sum_prod_type, Matrix.smul_apply, Matrix.one_apply, smul_eq_mul

      simp only [Matrix.add_apply, Matrix.mul_apply, Matrix.of_apply, Matrix.transpose_apply,
        Fintype.sum_prod_type, Matrix.smul_apply, Matrix.one_apply, smul_eq_mul]
  3. The entrywise equality holds for all 16 possible pairs of indices (r, r') ∈ Fin 4 × Fin 4.

    The tactic `fin_cases` splits the goal into 16 cases corresponding to all pairs of row r and column r' in {0, 1, 2, 3}. In each case, `Fin.sum_univ_four` unrolls the sums over Fin 4 into explicit four-term additions. The 12 off-diagonal entries (r ≠ r') evaluate to 0 because distinct rows in both the corner matrix and the Hadamard block are orthogonal; `simp` closes these goals directly. For the 4 diagonal entries (r = r'), the sum evaluates to 4 + (m + m + m + m), which matches the right-hand side 4m + 4 by basic ring arithmetic (`ring`).

    lines 12–13

    uses Fin.sum_univ_four

      fin_cases r <;> fin_cases r' <;>
        simp [Fin.sum_univ_four] <;> ring
Matrix.add_apply
The (i, j) entry of the sum of two matrices A + B is the sum of their entries A i j + B i j.
Matrix.mul_apply
The (i, k) entry of the matrix product M * N is the sum ∑ j, 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.transpose_apply
The (i, j) entry of the transpose matrix Mᵀ is M j i.
Fintype.sum_prod_type
A sum over a Cartesian product α₁ × α₂ of two finite types can be written as an iterated sum ∑ x, ∑ y, f (x, y).
Matrix.smul_apply
The (i, j) entry of a scalar multiple r • A is r • (A i j).
Matrix.one_apply
The (i, j) entry of the identity matrix is 1 if i = j and 0 otherwise.
smul_eq_mul
Scalar multiplication of integers coincides with standard integer multiplication (a • b = a * b).
Fin.sum_univ_four
A sum of a function f over Fin 4 equals f 0 + f 1 + f 2 + f 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_corner_block (m : ℕ) :    !![(1 : ℤ), -1, -1, -1; -1, 1, -1, -1; -1, -1, 1, -1; -1, -1, -1, 1]        * !![(1 : ℤ), -1, -1, -1; -1, 1, -1, -1; -1, -1, 1, -1; -1, -1, -1, 1].transpose      + (Matrix.of fun (r : Fin 4) (q : Fin 4 × Fin m) =>          !![(1 : ℤ), 1, 1, 1; 1, -1, 1, -1; 1, -1, -1, 1; 1, 1, -1, -1] r q.1)        * (Matrix.of fun (r : Fin 4) (q : Fin 4 × Fin m) =>          !![(1 : ℤ), 1, 1, 1; 1, -1, 1, -1; 1, -1, -1, 1; 1, 1, -1, -1] r q.1).transpose      = (4 * m + 4 : ℤ) • (1 : Matrix (Fin 4) (Fin 4) ℤ) := by  ext r r'  simp only [Matrix.add_apply, Matrix.mul_apply, Matrix.of_apply, Matrix.transpose_apply,    Fintype.sum_prod_type, Matrix.smul_apply, Matrix.one_apply, smul_eq_mul]  fin_cases r <;> fin_cases r' <;>    simp [Fin.sum_univ_four] <;> ring
See it in the graphDiscuss this resultChallenge it