AFTD Auto-Formalizing Theoretical Domains

back_identity_matrix_mul_circulant

theoremverified

R times the circulant with first column v equals the circulant of i ↦ v(-i) times R.

Statement

theorem back_identity_matrix_mul_circulant {m : ℕ} [NeZero m] (v : Fin m → ℤ) :
    back_identity_matrix m * Matrix.circulant v
      = Matrix.circulant (fun i => v (-i)) * back_identity_matrix m
Source
helper for the Goethals-Seidel array identity, arXiv:2610.27175 Theorem 3
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • circulant_mul_back_identity_matrixFor a circulant integer matrix X of order m > 0 and the back-identity matrix R, X R = R Xᵀ.
Used by 2

The proof, explained

The proof rewrites the right-hand side using the relation that multiplying a circulant matrix by the back-identity matrix R on the right produces R times the circulant's transpose. Since transposing a circulant reflects its generating vector (i ↦ v(-i)), transposing the already reflected vector produces a double negation i ↦ v(- -i), which simplifies back to v.

  1. The equality reduces to showing that R · circulant(v) = R · circulant(i ↦ v(- -i)).

    Applying circulant_mul_back_identity_matrix to the right-hand side circulant(i ↦ v(-i)) * R replaces it with R * (circulant(i ↦ v(-i)))ᵀ. Then Matrix.transpose_circulant rewrites the transpose of this circulant matrix by negating the indices, resulting in R * circulant(i ↦ v(- -i)).

    line 4

    uses circulant_mul_back_identity_matrix, Matrix.transpose_circulant

      rw [circulant_mul_back_identity_matrix, Matrix.transpose_circulant]
  2. Both sides of the equation are identical.

    Simplification cancels the double negation - -i = i in the index, which makes the right-hand side R * circulant(v), matching the left-hand side.

    line 5

      simp
circulant_mul_back_identity_matrix
Multiplying a circulant matrix by the back-identity matrix on the right equals multiplying the back-identity matrix on the left by the transpose of the circulant matrix.
Matrix.transpose_circulant
The transpose of a circulant matrix with first column v is the circulant matrix with first column i ↦ v(-i).

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 back_identity_matrix_mul_circulant {m : ℕ} [NeZero m] (v : Fin m → ℤ) :    back_identity_matrix m * Matrix.circulant v      = Matrix.circulant (fun i => v (-i)) * back_identity_matrix m := by  rw [circulant_mul_back_identity_matrix, Matrix.transpose_circulant]  simp
See it in the graphDiscuss this resultChallenge it