circulant_row_sum
Every row of the circulant matrix with first column v sums to the sum of v.
Statement
theorem circulant_row_sum {m : ℕ} [NeZero m] (v : Fin m → ℤ) (i : Fin m) :
∑ j, Matrix.circulant v i j = ∑ j, v j- Source
- helper for arXiv:2610.27175 Theorem 5 (row sums of the blocks)
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- circulant_mul_back_identity_matrix_row_sumEvery row of X R, X the circulant with first column v and R the back-identity, sums to the sum of v.
The proof, explained
The proof unfolds the definition of the circulant matrix, expressing the row sum as ∑ j, v (i - j). Since the reflection map j ↦ i - j is a permutation of Fin m, reindexing the finite sum by this bijection shows that it equals ∑ j, v j.
The row sum ∑ j, Matrix.circulant v i j reduces to ∑ j, v (i - j).
By definition of a circulant matrix (Matrix.circulant_apply), the entry at row i and column j is v(i - j).
uses
Matrix.circulant_applysimp only [Matrix.circulant_apply]∑ j, v (i - j) = ∑ j, v j
In the additive group Fin m, the reflection map j ↦ i - j is a bijection (Equiv.subLeft i). Reindexing the sum over this equivalence (Fintype.sum_equiv) preserves the sum, concluding the proof.
uses
Fintype.sum_equiv,Equiv.subLeftexact Fintype.sum_equiv (Equiv.subLeft i) _ _ (fun _ => rfl)
Matrix.circulant_apply- The entry at row i and column j of the circulant matrix generated by v is v(i - j).
Fintype.sum_equiv- Reindexing a sum over a finite type by an equivalence (bijection) does not change its value.
Equiv.subLeft- In an additive group, the map sending x to a - x is an equivalence (bijection).
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_row_sum {m : ℕ} [NeZero m] (v : Fin m → ℤ) (i : Fin m) : ∑ j, Matrix.circulant v i j = ∑ j, v j := by simp only [Matrix.circulant_apply] exact Fintype.sum_equiv (Equiv.subLeft i) _ _ (fun _ => rfl)