AFTD Auto-Formalizing Theoretical Domains

bordered_goethals_seidel_is_hadamard

theoremverifiedformalization

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.

  1. 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.

    lines 12–15

      have hm0 : m ≠ 0 := by
        rintro rfl
        simp at hsa
      have : NeZero m := ⟨hm0⟩
  2. 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.

    line 16

    uses bordered_goethals_seidel_matrix_entries

      refine ⟨bordered_goethals_seidel_matrix_entries a b c d ha hb hc hd, ?_⟩
  3. 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.

    line 17

    uses bordered_goethals_seidel_matrix, Matrix.fromBlocks_transpose, Matrix.fromBlocks_multiply

      rw [bordered_goethals_seidel_matrix, Matrix.fromBlocks_transpose, Matrix.fromBlocks_multiply]
  4. 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.

    lines 18–20

    uses Matrix.fromBlocks_one, Matrix.fromBlocks_smul, smul_zero

      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]
  5. 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.

    lines 21–23

    uses bordered_goethals_seidel_cross_block, Matrix.fromBlocks_inj.mpr, bordered_goethals_seidel_corner_block, bordered_goethals_seidel_lower_block

      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⟩
  6. 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.

    lines 24–27

    uses congrArg, Matrix.transpose_add, Matrix.transpose_mul, Matrix.transpose_transpose, Matrix.transpose_zero

      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
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.

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_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
See it in the graphDiscuss this resultChallenge it