bordered_goethals_seidel_lower_block
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.
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.
uses
goethals_seidel_array_mul_transposerw [goethals_seidel_array_mul_transpose, hsum]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.
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_applyext ⟨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]
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.
uses
Fin.sum_univ_fourfin_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
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_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]