bordered_goethals_seidel_corner_block
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.
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'.
ext r r'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'.
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_mulsimp 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]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`).
uses
Fin.sum_univ_fourfin_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.
- Rather than establishing algebraically that the corner matrix K satisfies K Kᵀ = 4 I₄ and that the repeating block H is a Hadamard matrix (so H Hᵀ = 4 I₄, yielding T Tᵀ = 4m I₄), the formal proof verifies the equation by exhaustively evaluating all 16 matrix entries via case exhaustion and automated ring simplification.
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 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