circulant_mul_left_comm
Circulant matrices over Fin m commute past one another: circulant v (circulant w Z) = circulant w (circulant v Z).
Statement
theorem circulant_mul_left_comm {m : ℕ} [NeZero m] (v w : Fin m → ℤ)
(Z : Matrix (Fin m) (Fin m) ℤ) :
Matrix.circulant v * (Matrix.circulant w * Z)
= Matrix.circulant w * (Matrix.circulant v * Z)- Source
- helper for the Goethals-Seidel array identity, arXiv:2610.27175 Theorem 3
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- goethals_seidel_array_mul_transposeFor circulant integer matrices A, B, C, D of order m > 0 and R the back-identity matrix, the Goethals-Seidel array M satisfies M Mᵀ =…
The proof, explained
The identity establishes left-commutativity for circulant matrices acting on a general matrix Z: A * (B * Z) = B * (A * Z). Using the associativity of matrix multiplication, both expressions reassociate into (A * B) * Z and (B * A) * Z. The claim then follows directly from the fact that circulant matrices commute under multiplication (A * B = B * A).
Matrix.circulant v * (Matrix.circulant w * Z) = Matrix.circulant w * (Matrix.circulant v * Z)
Using associativity of matrix multiplication (Matrix.mul_assoc) twice in reverse reassociates the products on both sides, transforming the goal into (Matrix.circulant v * Matrix.circulant w) * Z = (Matrix.circulant w * Matrix.circulant v) * Z. Applying the commutativity of circulant matrix multiplication (Matrix.circulant_mul_comm) replaces Matrix.circulant v * Matrix.circulant w with Matrix.circulant w * Matrix.circulant v, making both sides identical.
uses
Matrix.mul_assoc,Matrix.circulant_mul_commrw [← Matrix.mul_assoc, ← Matrix.mul_assoc, Matrix.circulant_mul_comm]
Matrix.mul_assoc- Matrix multiplication is associative: (L * M) * N = L * (M * N).
Matrix.circulant_mul_comm- Multiplication of circulant matrices is commutative: circulant v * circulant w = circulant w * circulant v.
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_left_comm {m : ℕ} [NeZero m] (v w : Fin m → ℤ) (Z : Matrix (Fin m) (Fin m) ℤ) : Matrix.circulant v * (Matrix.circulant w * Z) = Matrix.circulant w * (Matrix.circulant v * Z) := by rw [← Matrix.mul_assoc, ← Matrix.mul_assoc, Matrix.circulant_mul_comm]