AFTD Auto-Formalizing Theoretical Domains

circulant_row_sum

theoremverified

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

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.

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

    line 3

    uses Matrix.circulant_apply

      simp only [Matrix.circulant_apply]
  2. ∑ 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.

    line 4

    uses Fintype.sum_equiv, Equiv.subLeft

      exact 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

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