AFTD Auto-Formalizing Theoretical Domains

goethals_seidel_array_mul_transpose

theoremverified

For 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ᵀ = diag(S, S, S, S) with S = AAᵀ + BBᵀ + CCᵀ + DDᵀ.

Statement

theorem goethals_seidel_array_mul_transpose {m : ℕ} [NeZero m] (a b c d : Fin m → ℤ) :
    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
      = Matrix.of fun p q => if p.1 = q.1 then
          (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) p.2 q.2 else 0
Source
arXiv:2610.27175 (Recent progress in the construction of Hadamard matrices), the computation behind Theorem 3; serves Theorem 5
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1
  • 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…

The proof, explained

The Goethals-Seidel array M is a 4 × 4 block matrix constructed from circulant blocks A, B, C, D and the back-identity matrix R. The proof establishes a block-multiplication lemma showing that each block of M Mᵀ is given by ∑_{r=0}^3 M_{p, r} (M_{q, r})ᵀ, and then exhaustively verifies this formula across all 16 block positions (p, q) ∈ {0, 1, 2, 3}². Using the involutory and symmetric properties of R (R² = I, Rᵀ = R), the reflection identity R C = Cᵀ R, and the commutativity of circulant matrices, the diagonal blocks simplify to A Aᵀ + B Bᵀ + C Cᵀ + D Dᵀ while the off-diagonal cross-terms cancel out to zero.

  1. It suffices to prove equality of the entries at index ((p, i), (q, j)) for arbitrary block coordinates p, q ∈ Fin 4 and internal coordinates i, j ∈ Fin m.

    By matrix extensionality (`ext ⟨p, i⟩ ⟨q, j⟩`), two block matrices indexed by (Fin 4 × Fin m) are equal if and only if all of their corresponding scalar entries match.

    line 11

      ext ⟨p, i⟩ ⟨q, j⟩
  2. For any 4 × 4 block matrix G with m × m blocks, the ((p, i), (q, j)) entry of G Gᵀ equals the (i, j) entry of the block sum ∑_{r=0}^3 G_{p, r} (G_{q, r})ᵀ.

    By the definition of matrix multiplication, entry ((p, i), (q, j)) is a sum over all intermediate index pairs (r, k) ∈ Fin 4 × Fin m. Applying `Fintype.sum_prod_type` splits this sum into an outer sum over block index r ∈ Fin 4 and an inner sum over k ∈ Fin m. The inner sum ∑ₖ G_{p, r}(i, k) (G_{q, r})ᵀ(k, j) is precisely the (i, j) entry of the block product G_{p, r} (G_{q, r})ᵀ, which by `Matrix.sum_apply` gives the claimed block multiplication formula.

    lines 12–18

    uses Matrix.mul_apply, Fintype.sum_prod_type, Matrix.transpose_apply, Matrix.of_apply, Matrix.sum_apply

      have key : ∀ (G : Fin 4 → Fin 4 → Matrix (Fin m) (Fin m) ℤ),
          ((Matrix.of fun (p q : Fin 4 × Fin m) => G p.1 q.1 p.2 q.2)
            * (Matrix.of fun (p q : Fin 4 × Fin m) => G p.1 q.1 p.2 q.2).transpose) (p, i) (q, j)
            = (∑ r, G p r * (G q r).transpose) i j := by
        intro G
        simp only [Matrix.mul_apply, Fintype.sum_prod_type, Matrix.transpose_apply,
          Matrix.of_apply, Matrix.sum_apply]
  3. The goal reduces to showing that for each pair of block indices p, q ∈ Fin 4, the (p, q) block of the Goethals-Seidel product ∑_{r=0}^3 M_{p, r} (M_{q, r})ᵀ equals A Aᵀ + B Bᵀ + C Cᵀ + D Dᵀ when p = q, and 0 when p ≠ q.

    Rewriting with the definition of `goethals_seidel_array` and the block multiplication lemma `key` expresses the left-hand side entry as the (i, j) entry of the block sum ∑ᵣ M_{p, r} (M_{q, r})ᵀ. Simplifying the right-hand side with `Matrix.of_apply` reduces it to the (i, j) entry of A Aᵀ + B Bᵀ + C Cᵀ + D Dᵀ on the block diagonal (p = q) and 0 off the block diagonal (p ≠ q).

    lines 19–20

    uses goethals_seidel_array, Matrix.of_apply

      rw [goethals_seidel_array, key]
      simp only [Matrix.of_apply]
  4. For each of the 16 block index pairs (p, q) ∈ Fin 4 × Fin 4, the block sum ∑_{r=0}^3 M_{p, r} (M_{q, r})ᵀ evaluates to A Aᵀ + B Bᵀ + C Cᵀ + D Dᵀ when p = q and to 0 when p ≠ q. automation

    An exhaustive case split on p and q (`fin_cases p <;> fin_cases q`) produces 16 subgoals. For each block, `Fin.sum_univ_four` expands the 4-term sum. The simplifier distributes transposes over products ((X Y)ᵀ = Yᵀ Xᵀ), applies the symmetry and involution properties of R (Rᵀ = R, R² = I), and uses the intertwining relation R C = Cᵀ R and commutativity of circulants. For diagonal blocks (p = q), each of the four terms simplifies to one of A Aᵀ, B Bᵀ, C Cᵀ, D Dᵀ. For off-diagonal blocks (p ≠ q), the cross-terms cancel in opposite-sign pairs. Finally, `abel_nf` normalises the additive group expressions to close all 16 cases.

    lines 21–26

    uses Fin.sum_univ_four, Matrix.transpose_mul, Matrix.transpose_circulant, back_identity_matrix_transpose, Matrix.mul_assoc, back_identity_matrix_mul_circulant_mul, back_identity_matrix_mul_circulant, back_identity_matrix_mul_self, Matrix.circulant_mul_comm, circulant_mul_left_comm

      fin_cases p <;> fin_cases q <;>
        simp [Fin.sum_univ_four, Matrix.transpose_mul, Matrix.transpose_circulant,
          back_identity_matrix_transpose, Matrix.mul_assoc, back_identity_matrix_mul_circulant_mul,
          back_identity_matrix_mul_circulant, back_identity_matrix_mul_self,
          Matrix.circulant_mul_comm, circulant_mul_left_comm] <;>
        abel_nf
Matrix.mul_apply
The (i, k)-entry of the matrix product MN is the sum ∑ⱼ M_{i, j} N_{j, k} over the shared intermediate index j.
Fintype.sum_prod_type
A finite sum over a product type α₁ × α₂ equals the iterated double sum ∑_x ∑_y f(x, y).
Matrix.transpose_apply
The (i, j)-entry of the transpose Mᵀ is M_{j, i}.
Matrix.of_apply
The (i, j)-entry of the matrix constructed from a bivariate function f is f(i, j).
Matrix.sum_apply
The (i, j)-entry of a finite sum of matrices is the sum of their individual (i, j)-entries.
goethals_seidel_array
The 4 × 4 block matrix constructed from four m × m matrices A, B, C, D and the back-identity matrix R, with first block row [A, BR, CR, DR] and cyclically signed permutations in the remaining rows.
Fin.sum_univ_four
A sum over Fin 4 equals the sum of the four values at 0, 1, 2, and 3: f(0) + f(1) + f(2) + f(3).
Matrix.transpose_mul
The transpose of a matrix product reverses the factors: (M N)ᵀ = Nᵀ Mᵀ.
Matrix.transpose_circulant
The transpose of a circulant matrix generated by vector v is the circulant matrix generated by the reflected vector i ↦ v(-i).
back_identity_matrix_transpose
The back-identity matrix R is symmetric: Rᵀ = R.
Matrix.mul_assoc
Matrix multiplication is associative: (L M) N = L (M N).
back_identity_matrix_mul_circulant_mul
Multiplying the back-identity matrix R by a circulant matrix C and another matrix Z satisfies R (C Z) = Cᵀ (R Z).
back_identity_matrix_mul_circulant
The back-identity matrix R satisfies R C = Cᵀ R for any circulant matrix C.
back_identity_matrix_mul_self
The back-identity matrix R is an involution: R² = I.
Matrix.circulant_mul_comm
Any two circulant matrices commute: circ(v) * circ(w) = circ(w) * circ(v).
circulant_mul_left_comm
Circulant matrix multiplication left-commutes: C₁ (C₂ Z) = C₂ (C₁ Z).

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 goethals_seidel_array_mul_transpose {m : ℕ} [NeZero m] (a b c d : Fin m → ℤ) :    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      = Matrix.of fun p q => if p.1 = q.1 then          (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) p.2 q.2 else 0 := by  ext ⟨p, i⟩ ⟨q, j⟩  have key : ∀ (G : Fin 4 → Fin 4 → Matrix (Fin m) (Fin m) ℤ),      ((Matrix.of fun (p q : Fin 4 × Fin m) => G p.1 q.1 p.2 q.2)        * (Matrix.of fun (p q : Fin 4 × Fin m) => G p.1 q.1 p.2 q.2).transpose) (p, i) (q, j)        = (∑ r, G p r * (G q r).transpose) i j := by    intro G    simp only [Matrix.mul_apply, Fintype.sum_prod_type, Matrix.transpose_apply,      Matrix.of_apply, Matrix.sum_apply]  rw [goethals_seidel_array, key]  simp only [Matrix.of_apply]  fin_cases p <;> fin_cases q <;>    simp [Fin.sum_univ_four, Matrix.transpose_mul, Matrix.transpose_circulant,      back_identity_matrix_transpose, Matrix.mul_assoc, back_identity_matrix_mul_circulant_mul,      back_identity_matrix_mul_circulant, back_identity_matrix_mul_self,      Matrix.circulant_mul_comm, circulant_mul_left_comm] <;>    abel_nf
See it in the graphDiscuss this resultChallenge it