circulant_mul_back_identity_matrix
For a circulant integer matrix X of order m > 0 and the back-identity matrix R, X R = R Xᵀ.
Statement
theorem circulant_mul_back_identity_matrix {m : ℕ} [NeZero m] (v : Fin m → ℤ) :
Matrix.circulant v * back_identity_matrix m
= back_identity_matrix m * (Matrix.circulant v).transpose- Source
- arXiv:2610.27175 (Recent progress in the construction of Hadamard matrices), proof of Theorem 3 and Theorem 5: the relation X R = R Xᵀ for circulants
- 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).
- back_identity_matrix_mul_applyLeft multiplication by the back-identity matrix reverses the rows: (R X) i j = X (m - 1 - i) j.
- fin_sub_rev_commIn Fin m (m > 0), i - (m - 1 - j) = j - (m - 1 - i), both being i + j + 1 mod m.
- Used by 1
- back_identity_matrix_mul_circulantR times the circulant with first column v equals the circulant of i ↦ v(-i) times R.
The proof, explained
The proof establishes matrix equality entry-by-entry. Multiplying by the back-identity matrix $R$ reflects the columns of $X$ on the right and the rows of $X^\top$ on the left. Because $X$ is circulant, the resulting entries evaluate to $v(i - j^{\mathrm{rev}})$ and $v(j - i^{\mathrm{rev}})$, which coincide by the index identity $i - j^{\mathrm{rev}} = j - i^{\mathrm{rev}}$.
It suffices to show that $(X R)_{i, j} = (R X^\top)_{i, j}$ for arbitrary indices $i, j \in \mathrm{Fin}(m)$.
By matrix extensionality, two matrices are identical if and only if all of their corresponding entries are equal.
ext i jFor all indices $i, j$, the $(i, j)$-th entry of $X R$ equals the $(i, j)$-th entry of $R X^\top$.
Right-multiplying $X$ by the back-identity matrix $R$ yields entry $X_{i, j^{\mathrm{rev}}}$, while left-multiplying $X^\top$ by $R$ yields $(X^\top)_{i^{\mathrm{rev}}, j} = X_{j, i^{\mathrm{rev}}}$. Since $X$ is circulant, these entries expand to $v(i - j^{\mathrm{rev}})$ and $v(j - i^{\mathrm{rev}})$, respectively. These arguments are equal because index reversal satisfies $i - j^{\mathrm{rev}} = j - i^{\mathrm{rev}}$.
uses
mul_back_identity_matrix_apply,back_identity_matrix_mul_apply,Matrix.transpose_apply,Matrix.circulant_apply,fin_sub_rev_commrw [mul_back_identity_matrix_apply, back_identity_matrix_mul_apply, Matrix.transpose_apply, Matrix.circulant_apply, Matrix.circulant_apply, fin_sub_rev_comm]
mul_back_identity_matrix_apply- Multiplying a matrix on the right by the back-identity matrix reverses its columns: $(X R)_{i, j} = X_{i, j^{\mathrm{rev}}}$.
back_identity_matrix_mul_apply- Multiplying a matrix on the left by the back-identity matrix reverses its rows: $(R X)_{i, j} = X_{i^{\mathrm{rev}}, j}$.
Matrix.transpose_apply- The $(i, j)$-th entry of the transpose of a matrix $M$ is $M_{j, i}$.
Matrix.circulant_apply- The $(i, j)$-th entry of the circulant matrix generated by vector $v$ is $v(i - j)$.
fin_sub_rev_comm- In the cyclic index group $\mathrm{Fin}(m)$, reversing indices satisfies $i - j^{\mathrm{rev}} = j - i^{\mathrm{rev}}$.
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 circulant_mul_back_identity_matrix {m : ℕ} [NeZero m] (v : Fin m → ℤ) : Matrix.circulant v * back_identity_matrix m = back_identity_matrix m * (Matrix.circulant v).transpose := by ext i j rw [mul_back_identity_matrix_apply, back_identity_matrix_mul_apply, Matrix.transpose_apply, Matrix.circulant_apply, Matrix.circulant_apply, fin_sub_rev_comm]