AFTD Auto-Formalizing Theoretical Domains

circulant_mul_back_identity_matrix

theoremverified

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

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

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

    line 4

      ext i j
  2. For 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}}$.

    lines 5–6

    uses mul_back_identity_matrix_apply, back_identity_matrix_mul_apply, Matrix.transpose_apply, Matrix.circulant_apply, fin_sub_rev_comm

      rw [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

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