goethals_seidel_array_mul_transpose
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
- 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…
- back_identity_matrix_transposeThe back-identity matrix is symmetric: Rᵀ = R.
- back_identity_matrix_mul_selfThe back-identity matrix is an involution: R R = I.
- back_identity_matrix_mul_circulantR times the circulant with first column v equals the circulant of i ↦ v(-i) times R.
- back_identity_matrix_mul_circulant_mulR (circulant v Z) = circulant(i ↦ v(-i)) (R Z): the back-identity moves rightward past a circulant, transposing it.
- circulant_mul_left_commCirculant matrices over Fin m commute past one another: circulant v (circulant w Z) = circulant w (circulant v Z).
- 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,…
- 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.
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.
ext ⟨p, i⟩ ⟨q, j⟩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.
uses
Matrix.mul_apply,Fintype.sum_prod_type,Matrix.transpose_apply,Matrix.of_apply,Matrix.sum_applyhave 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]
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).
uses
goethals_seidel_array,Matrix.of_applyrw [goethals_seidel_array, key] simp only [Matrix.of_apply]
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.
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_commfin_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).
- The 16 block equations corresponding to (p, q) ∈ {0, 1, 2, 3}² are handled in parallel by tactical automation: `fin_cases` creates all 16 subgoals, and `simp` combined with `abel_nf` computes the products and cancels the cross-terms in the additive group of matrices without writing out each case by hand.
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 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