bordered_goethals_seidel_is_hadamard
Let 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 - 4J, A of row sum 2 and B, C, D of row sum 0. Then the bordered Goethals-Seidel matrix of order 4m+4 (corner 4 × 4 block with diagonal 1, off-diagonal -1; borders of ±j; Goethals-Seidel array in A, BR, CR, DR with R the back-identity) is a Hadamard matrix.
Statement
theorem bordered_goethals_seidel_is_hadamard (m : ℕ) (hm : Even m) (a b c d : Fin m → ℤ) (ha : ∀ i, a i = 1 ∨ a i = -1) (hb : ∀ i, b i = 1 ∨ b i = -1) (hc : ∀ i, c i = 1 ∨ c i = -1) (hd : ∀ i, d i = 1 ∨ d i = -1) (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 : ℤ))) (hsa : ∑ i, a i = 2) (hsb : ∑ i, b i = 0) (hsc : ∑ i, c i = 0) (hsd : ∑ i, d i = 0) : IsHadamardMatrix (bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c) (Matrix.circulant d))
- Formalizes
- arXiv:2610.27175 (Recent progress in the construction of Hadamard matrices), Theorem 5. Circulants are Mathlib's `Matrix.circulant` (entry (i, j) = v(i - j)); the paper's convention (first row) gives the same set of matrices. The matrix is indexed by Fin 4 ⊕ (Fin 4 × Fin m), of size 4m + 4.
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- IsHadamardMatrixA square integer matrix H indexed by a finite type of size n is a Hadamard matrix when every entry is 1 or -1 and H Hᵀ = n I.
- bordered_goethals_seidel_matrixThe (4m+4) × (4m+4) matrix of arXiv:2610.27175 Theorem 5, indexed by Fin 4 ⊕ (Fin 4 × Fin m): top-left 4 × 4 block with diagonal 1 and…
- bordered_goethals_seidel_matrix_entriesIf a, b, c, d : Fin m → ℤ take only the values 1 and -1, every entry of the bordered Goethals-Seidel matrix built from their circulants is…
- bordered_goethals_seidel_corner_blockFor 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 ×…
- bordered_goethals_seidel_cross_blockIf the first columns a, b, c, d (m > 0) sum to 2, 0, 0, 0, then K Lᵀ + T Mᵀ = 0, where K is the 4 × 4 corner, L the 4m × 4 left border of…
- bordered_goethals_seidel_lower_blockIf 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…
- 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,…
The proof, explained
To prove that the bordered Goethals-Seidel matrix H of order 4m + 4 is a Hadamard matrix, the proof verifies that all its entries are ±1 and that H Hᵀ = (4m + 4)I. The entry condition is handled by a specialized helper lemma, while the orthogonality condition expands H Hᵀ as a 2×2 block matrix. The diagonal blocks evaluate to (4m + 4)I by helper lemmas based on the circulant Gram sum identity, the top-right cross block vanishes by the row-sum conditions, and the bottom-left block vanishes by taking the transpose of the top-right block.
m is non-zero, satisfying the NeZero m typeclass requirement.
If m were 0, the sum of the entries of a over Fin 0 would be 0, which contradicts the hypothesis that the sum is 2. Hence m ≠ 0.
have hm0 : m ≠ 0 := by rintro rfl simp at hsa have : NeZero m := ⟨hm0⟩
All entries of the matrix are ±1, reducing the Hadamard property to the orthogonality condition H Hᵀ = (4m + 4)I.
By definition, an integer matrix H is Hadamard if its entries belong to {1, -1} and H Hᵀ = n I where n is its order. The entry condition holds directly by bordered_goethals_seidel_matrix_entries.
uses
bordered_goethals_seidel_matrix_entriesrefine ⟨bordered_goethals_seidel_matrix_entries a b c d ha hb hc hd, ?_⟩The product H Hᵀ is expanded into 2×2 block form.
Unfolding the definition bordered_goethals_seidel_matrix expresses H as a 2×2 block matrix. Rewriting with Matrix.fromBlocks_transpose and Matrix.fromBlocks_multiply expands H Hᵀ into the four standard block matrix products.
uses
bordered_goethals_seidel_matrix,Matrix.fromBlocks_transpose,Matrix.fromBlocks_multiplyrw [bordered_goethals_seidel_matrix, Matrix.fromBlocks_transpose, Matrix.fromBlocks_multiply]The target matrix (4m + 4)I is expressed as a block diagonal matrix.
The total dimension |Fin 4 ⊕ (Fin 4 × Fin m)| evaluates to 4 + 4m = 4m + 4. Writing the identity matrix in 2×2 block form via Matrix.fromBlocks_one and distributing the scalar factor 4m + 4 via Matrix.fromBlocks_smul and smul_zero decomposes the target into diagonal blocks (4m + 4)I₄ and (4m + 4)I₄ₘ with zero off-diagonal blocks.
uses
Matrix.fromBlocks_one,Matrix.fromBlocks_smul,smul_zerohave hcard : (Fintype.card (Fin 4 ⊕ Fin 4 × Fin m) : ℤ) = 4 * m + 4 := by simp; ring rw [hcard, ← Matrix.fromBlocks_one, Matrix.fromBlocks_smul, smul_zero]
The top-left, top-right, and bottom-right blocks match the target block matrix, leaving only the bottom-left block to be checked.
By Matrix.fromBlocks_inj.mpr, equality of block matrices reduces to equality of each of the four blocks. The 4×4 corner block equals (4m + 4)I₄ by bordered_goethals_seidel_corner_block; the top-right cross block is 0 by bordered_goethals_seidel_cross_block using the row-sum hypotheses; and the bottom-right block equals (4m + 4)I₄ₘ by bordered_goethals_seidel_lower_block using the Gram matrix sum hypothesis.
uses
bordered_goethals_seidel_cross_block,Matrix.fromBlocks_inj.mpr,bordered_goethals_seidel_corner_block,bordered_goethals_seidel_lower_blockhave h12 := bordered_goethals_seidel_cross_block a b c d hsa hsb hsc hsd refine Matrix.fromBlocks_inj.mpr ⟨bordered_goethals_seidel_corner_block m, h12, ?_, bordered_goethals_seidel_lower_block a b c d hsum⟩
The bottom-left block is zero, which concludes the proof.
The bottom-left block is the transpose of the top-right block. Taking the transpose of the top-right vanishing equation h12 via congrArg and distributing the transpose across additions and products (using Matrix.transpose_add, Matrix.transpose_mul, Matrix.transpose_transpose, and Matrix.transpose_zero) shows that the bottom-left block is also 0.
uses
congrArg,Matrix.transpose_add,Matrix.transpose_mul,Matrix.transpose_transpose,Matrix.transpose_zerohave := congrArg Matrix.transpose h12 rw [Matrix.transpose_add, Matrix.transpose_mul, Matrix.transpose_mul, Matrix.transpose_transpose, Matrix.transpose_transpose, Matrix.transpose_zero] at this exact this
bordered_goethals_seidel_matrix_entries- Every entry of the bordered Goethals-Seidel matrix constructed from circulant ±1-matrices is equal to 1 or -1.
bordered_goethals_seidel_matrix- The definition of the bordered Goethals-Seidel matrix as a 2×2 block matrix with a 4×4 corner block, borders of ±1s, and a 4×4 Goethals-Seidel array of circulants.
Matrix.fromBlocks_transpose- The transpose of a 2×2 block matrix is obtained by transposing each block and swapping the off-diagonal blocks.
Matrix.fromBlocks_multiply- The product of two 2×2 block matrices is computed by standard block matrix multiplication.
Matrix.fromBlocks_one- The 2×2 block matrix with identity diagonal blocks and zero off-diagonal blocks is the identity matrix.
Matrix.fromBlocks_smul- Scalar multiplication distributes over every block of a 2×2 block matrix.
smul_zero- Multiplying the zero matrix by any scalar yields the zero matrix.
bordered_goethals_seidel_cross_block- The top-right 4×4m cross block in the Goethals-Seidel product vanishes when the row sums of the four matrices are 2, 0, 0, and 0.
Matrix.fromBlocks_inj.mpr- Two 2×2 block matrices are equal if all four of their corresponding blocks are equal.
bordered_goethals_seidel_corner_block- The top-left 4×4 corner block in the product equals (4m + 4) times the 4×4 identity matrix.
bordered_goethals_seidel_lower_block- The bottom-right 4m×4m block in the product equals (4m + 4) times the 4m×4m identity matrix, given that the sum of the four circulant Gram matrices equals (4m + 4)I - 4J.
congrArg- Applying a function to equal inputs yields equal outputs.
Matrix.transpose_add- The transpose of a sum of matrices is the sum of their transposes.
Matrix.transpose_mul- The transpose of a product of matrices is the product of their transposes in reverse order.
Matrix.transpose_transpose- Transposing a matrix twice returns the original matrix.
Matrix.transpose_zero- The transpose of the zero matrix is the zero matrix.
- The hypothesis `Even m` is present in the theorem statement but not explicitly referenced in the proof body, as its requirements are absorbed by the lower-level helper lemmas.
- The proof establishes `NeZero m` from the hypothesis $\sum_i a_i = 2$ solely to satisfy Lean's typeclass synthesis, a formal requirement that does not arise on paper.
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_is_hadamard (m : ℕ) (hm : Even m) (a b c d : Fin m → ℤ) (ha : ∀ i, a i = 1 ∨ a i = -1) (hb : ∀ i, b i = 1 ∨ b i = -1) (hc : ∀ i, c i = 1 ∨ c i = -1) (hd : ∀ i, d i = 1 ∨ d i = -1) (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 : ℤ))) (hsa : ∑ i, a i = 2) (hsb : ∑ i, b i = 0) (hsc : ∑ i, c i = 0) (hsd : ∑ i, d i = 0) : IsHadamardMatrix (bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c) (Matrix.circulant d)) := by have hm0 : m ≠ 0 := by rintro rfl simp at hsa have : NeZero m := ⟨hm0⟩ refine ⟨bordered_goethals_seidel_matrix_entries a b c d ha hb hc hd, ?_⟩ rw [bordered_goethals_seidel_matrix, Matrix.fromBlocks_transpose, Matrix.fromBlocks_multiply] have hcard : (Fintype.card (Fin 4 ⊕ Fin 4 × Fin m) : ℤ) = 4 * m + 4 := by simp; ring rw [hcard, ← Matrix.fromBlocks_one, Matrix.fromBlocks_smul, smul_zero] have h12 := bordered_goethals_seidel_cross_block a b c d hsa hsb hsc hsd refine Matrix.fromBlocks_inj.mpr ⟨bordered_goethals_seidel_corner_block m, h12, ?_, bordered_goethals_seidel_lower_block a b c d hsum⟩ have := congrArg Matrix.transpose h12 rw [Matrix.transpose_add, Matrix.transpose_mul, Matrix.transpose_mul, Matrix.transpose_transpose, Matrix.transpose_transpose, Matrix.transpose_zero] at this exact this