AFTD Auto-Formalizing Theoretical Domains

back_identity_matrix_mul_circulant_mul

theoremverified

R (circulant v Z) = circulant(i ↦ v(-i)) (R Z): the back-identity moves rightward past a circulant, transposing it.

Statement

theorem back_identity_matrix_mul_circulant_mul {m : ℕ} [NeZero m] (v : Fin m → ℤ)
    (Z : Matrix (Fin m) (Fin m) ℤ) :
    back_identity_matrix m * (Matrix.circulant v * Z)
      = Matrix.circulant (fun i => v (-i)) * (back_identity_matrix m * Z)
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…
  • back_identity_matrix_mul_circulantR times the circulant with first column v equals the circulant of i ↦ v(-i) times R.
Used by 1

The proof, explained

The proof proceeds by reassociating the product so that the back-identity matrix $R$ multiplies the circulant matrix directly. It then applies the commutation identity $R \, \mathrm{circ}(v) = \mathrm{circ}(i \mapsto v(-i)) \, R$ and restores the original associativity.

  1. $R (C_v Z) = C_{v(-)} (R Z)$, where $R$ is the back-identity matrix and $C_v$ is the circulant matrix generated by $v$.

    Reassociate the product $R (C_v Z)$ to $(R C_v) Z$ using matrix associativity (`Matrix.mul_assoc`), substitute $R C_v$ with $C_{v(-)} R$ using `back_identity_matrix_mul_circulant`, and reassociate the product back to $C_{v(-)} (R Z)$ using associativity again.

    line 5

    uses Matrix.mul_assoc, back_identity_matrix_mul_circulant

      rw [← Matrix.mul_assoc, back_identity_matrix_mul_circulant, Matrix.mul_assoc]
Matrix.mul_assoc
Matrix multiplication is associative: $(L M) N = L (M N)$.
back_identity_matrix_mul_circulant
Multiplying the back-identity matrix on the left by a circulant matrix reflects its generating vector: $R \, \mathrm{circ}(v) = \mathrm{circ}(i \mapsto v(-i)) \, R$.

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