AFTD Auto-Formalizing Theoretical Domains

circulant_mul_left_comm

theoremverified

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

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

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

    line 5

    uses Matrix.mul_assoc, Matrix.circulant_mul_comm

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

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