bordered_goethals_seidel_matrix_entries
If 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 1 or -1.
Statement
theorem bordered_goethals_seidel_matrix_entries {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) (i j : Fin 4 ⊕ Fin 4 × Fin m) :
bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b)
(Matrix.circulant c) (Matrix.circulant d) i j = 1 ∨
bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b)
(Matrix.circulant c) (Matrix.circulant d) i j = -1- Source
- step of arXiv:2610.27175 Theorem 5 (the matrix is a {±1}-matrix)
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- mul_back_identity_matrix_applyRight multiplication by the back-identity matrix reverses the columns: (X R) i j = X i (m - 1 - j).
- 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…
- 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_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 bordered Goethals-Seidel matrix is structured as a 2 × 2 block matrix consisting of a 4 × 4 border block, two rectangular border blocks of sizes 4 × 4m and 4m × 4, and a 4m × 4m Goethals-Seidel array. First, the proof establishes four helper lemmas showing that having all entries in {1, -1} is preserved under taking circulants, negation, right-multiplication by the back-identity matrix R, and transposition. Decomposing the row and column indices into border and array components, the three border blocks are verified by exhaustively checking their fixed coefficients in {1, -1}, while each of the 16 blocks in the Goethals-Seidel array matches one of the preserved operations on the circulants of a, b, c, and d.
Any circulant matrix whose defining vector has entries in {1, -1} has all its entries in {1, -1}.
By definition, the (i, j)-th entry of the circulant matrix circ(v) is v(i - j). Since every entry of v is 1 or -1, the difference i - j also indexes an entry in {1, -1}.
have hcirc : ∀ v : Fin m → ℤ, (∀ i, v i = 1 ∨ v i = -1) → ∀ i j, Matrix.circulant v i j = 1 ∨ Matrix.circulant v i j = -1 := fun v hv i j => hv (i - j)
The negation of any matrix with entries in {1, -1} also has all entries in {1, -1}.
By Matrix.neg_apply, the (i, j)-th entry of -X is -(X i j). If X i j = 1, its negation is -1; if X i j = -1, its negation is 1. In both cases the resulting entry lies in {1, -1}.
uses
Matrix.neg_applyhave hneg : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) → ∀ i j, (-X) i j = 1 ∨ (-X) i j = -1 := by intro X hX i j rw [Matrix.neg_apply] rcases hX i j with h | h <;> rw [h] <;> simp
Right-multiplication by the back-identity matrix preserves the property that all entries lie in {1, -1}.
By mul_back_identity_matrix_apply, the (i, j)-th entry of X * R is X i j.rev. Since this is an entry of X with a reversed column index, it is 1 or -1 by the hypothesis on X.
uses
mul_back_identity_matrix_applyhave hR : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) → ∀ i j, (X * back_identity_matrix m) i j = 1 ∨ (X * back_identity_matrix m) i j = -1 := by intro X hX i j rw [mul_back_identity_matrix_apply] exact hX i j.rev
Transposition preserves the property that all entries lie in {1, -1}.
The (i, j)-th entry of the transpose Xᵀ is X j i, which lies in {1, -1} by the hypothesis on X.
have hT : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) → ∀ i j, X.transpose i j = 1 ∨ X.transpose i j = -1 := fun X hX i j => hX j i
The four circulant matrices A, B, C, D formed from a, b, c, d all have entries in {1, -1}.
We apply the circulant lemma established in the first step to each of the vectors a, b, c, d and their respective hypotheses.
have hA := hcirc a ha have hB := hcirc b hb have hC := hcirc c hc have hD := hcirc d hd
The goal splits into four cases according to the block decomposition of the bordered matrix.
The row and column index type Fin 4 ⊕ (Fin 4 × Fin m) is a sum of border indices and array indices. Performing case analysis on both i and j splits the goal into the four blocks: top-left (4 × 4), top-right (4 × 4m), bottom-left (4m × 4), and bottom-right (4m × 4m).
rcases i with r | ⟨p, i⟩ <;> rcases j with r' | ⟨q, j⟩
Every entry of the top-left 4 × 4 border block is 1 or -1.
Exhaustive case analysis on row r ∈ Fin 4 and column r' ∈ Fin 4 evaluates all 16 entries of the explicit 4 × 4 border matrix, each of which is 1 or -1.
uses
bordered_goethals_seidel_matrix· fin_cases r <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix]Every entry of the top-right 4 × 4m border block is 1 or -1.
Exhaustive case analysis on border row r ∈ Fin 4 and block column q ∈ Fin 4 evaluates each entry to one from the explicit 4 × 4 coefficient matrix, which is independent of the within-block column index and always 1 or -1.
uses
bordered_goethals_seidel_matrix· fin_cases r <;> fin_cases q <;> simp [bordered_goethals_seidel_matrix]Every entry of the bottom-left 4m × 4 border block is 1 or -1.
Exhaustive case analysis on block row p ∈ Fin 4 and border column r' ∈ Fin 4 evaluates each entry to one from the explicit 4 × 4 coefficient matrix, which is independent of the within-block row index and always 1 or -1.
uses
bordered_goethals_seidel_matrix· fin_cases p <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix]Every entry of the bottom-right 4m × 4m Goethals-Seidel array block is 1 or -1.
The Goethals-Seidel array consists of 16 blocks indexed by (p, q) ∈ Fin 4 × Fin 4. For each pair (p, q), the block is of the form A, ±(X * R), or ±(Xᵀ * R) for some X ∈ {B, C, D}. Each such block has all entries in {1, -1} by combining the preservation properties proved earlier for circulants, negation, multiplication by R, and transposition.
· fin_cases p <;> fin_cases q <;> first | exact hA i j | exact hR _ hB i j | exact hR _ hC i j | exact hR _ hD i j | exact hneg _ (hR _ hB) i j | exact hneg _ (hR _ hC) i j | exact hneg _ (hR _ hD) i j | exact hR _ (hT _ hB) i j | exact hR _ (hT _ hC) i j | exact hR _ (hT _ hD) i j | exact hneg _ (hR _ (hT _ hB)) i j | exact hneg _ (hR _ (hT _ hC)) i j | exact hneg _ (hR _ (hT _ hD)) i j
Matrix.neg_apply- The entry at row i and column j of the negation of a matrix A is the negation -A i j of the corresponding entry of A.
mul_back_identity_matrix_apply- Multiplying a square matrix X of size m on the right by the back-identity matrix yields a matrix whose (i, j)-th entry is X i j.rev, which reverses the column index.
bordered_goethals_seidel_matrix- The bordered Goethals-Seidel matrix constructed from four blocks: a 4 × 4 border block, two rectangular border blocks of sizes 4 × 4m and 4m × 4, and the 4m × 4m Goethals-Seidel array of circulant matrices.
- The verification of all three border blocks and the 16 array blocks relies on exhausting the finite index type Fin 4, reducing each block to a check against explicit matrices with entries in {1, -1}.
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_matrix_entries {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) (i j : Fin 4 ⊕ Fin 4 × Fin m) : bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c) (Matrix.circulant d) i j = 1 ∨ bordered_goethals_seidel_matrix (Matrix.circulant a) (Matrix.circulant b) (Matrix.circulant c) (Matrix.circulant d) i j = -1 := by have hcirc : ∀ v : Fin m → ℤ, (∀ i, v i = 1 ∨ v i = -1) → ∀ i j, Matrix.circulant v i j = 1 ∨ Matrix.circulant v i j = -1 := fun v hv i j => hv (i - j) have hneg : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) → ∀ i j, (-X) i j = 1 ∨ (-X) i j = -1 := by intro X hX i j rw [Matrix.neg_apply] rcases hX i j with h | h <;> rw [h] <;> simp have hR : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) → ∀ i j, (X * back_identity_matrix m) i j = 1 ∨ (X * back_identity_matrix m) i j = -1 := by intro X hX i j rw [mul_back_identity_matrix_apply] exact hX i j.rev have hT : ∀ X : Matrix (Fin m) (Fin m) ℤ, (∀ i j, X i j = 1 ∨ X i j = -1) → ∀ i j, X.transpose i j = 1 ∨ X.transpose i j = -1 := fun X hX i j => hX j i have hA := hcirc a ha have hB := hcirc b hb have hC := hcirc c hc have hD := hcirc d hd rcases i with r | ⟨p, i⟩ <;> rcases j with r' | ⟨q, j⟩ · fin_cases r <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix] · fin_cases r <;> fin_cases q <;> simp [bordered_goethals_seidel_matrix] · fin_cases p <;> fin_cases r' <;> simp [bordered_goethals_seidel_matrix] · fin_cases p <;> fin_cases q <;> first | exact hA i j | exact hR _ hB i j | exact hR _ hC i j | exact hR _ hD i j | exact hneg _ (hR _ hB) i j | exact hneg _ (hR _ hC) i j | exact hneg _ (hR _ hD) i j | exact hR _ (hT _ hB) i j | exact hR _ (hT _ hC) i j | exact hR _ (hT _ hD) i j | exact hneg _ (hR _ (hT _ hB)) i j | exact hneg _ (hR _ (hT _ hC)) i j | exact hneg _ (hR _ (hT _ hD)) i j