circulant_mul_back_identity_matrix_row_sum
Every row of X R, X the circulant with first column v and R the back-identity, sums to the sum of v.
Statement
theorem circulant_mul_back_identity_matrix_row_sum {m : ℕ} [NeZero m] (v : Fin m → ℤ)
(i : Fin m) :
∑ j, (Matrix.circulant v * back_identity_matrix m) 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- Built on 3
- 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…
- mul_back_identity_matrix_applyRight multiplication by the back-identity matrix reverses the columns: (X R) i j = X i (m - 1 - j).
- circulant_row_sumEvery row of the circulant matrix with first column v sums to the sum of v.
- Used by 1
- bordered_goethals_seidel_cross_blockIf the first columns a, b, c, d (m > 0) sum to 2, 0, 0, 0, then K Lᵀ + T Mᵀ = 0, where K is the 4 × 4 corner, L the 4m × 4 left border of…
The proof, explained
Multiplying on the right by the back-identity matrix reverses the order of the columns, so the row sum of $X R$ is the sum of the entries of row $i$ of $X$ in reversed order. Since the row sum of a circulant matrix $X$ equals the sum of its generating vector $v$, and reversing the finite index set $\operatorname{Fin} m$ is a permutation that preserves the sum, the row sum of $X R$ equals the sum of $v$.
The row sum of $X R$ is the sum of row $i$ of $X$ with reversed column indices: $\sum_x (\operatorname{circulant} v)_{i, \operatorname{rev}(x)} = \sum_j v_j$.
Multiplying a matrix on the right by the back-identity matrix reverses each row. Applying `mul_back_identity_matrix_apply`, each term $((\operatorname{circulant} v) R)_{i, j}$ in the row sum simplifies to $(\operatorname{circulant} v)_{i, \operatorname{rev}(j)}$.
uses
mul_back_identity_matrix_applysimp only [mul_back_identity_matrix_apply]It suffices to show that $\sum_x (\operatorname{circulant} v)_{i, \operatorname{rev}(x)} = \sum_j (\operatorname{circulant} v)_{i, j}$.
By `circulant_row_sum`, any row of a circulant matrix sums to $\sum_j v_j$. Rewriting the right-hand side in reverse replaces $\sum_j v_j$ with the unreversed row sum $\sum_j (\operatorname{circulant} v)_{i, j}$.
uses
circulant_row_sumrw [← circulant_row_sum v i]The row sum with reversed column indices equals the original row sum.
The reversal operation $x \mapsto \operatorname{rev}(x)$ is a permutation of $\operatorname{Fin} m$ (`Fin.revPerm`). Reindexing a finite sum along a bijection preserves the total sum (`Fintype.sum_equiv`), and the corresponding terms are definitionally identical.
uses
Fintype.sum_equiv,Fin.revPermexact Fintype.sum_equiv Fin.revPerm _ _ (fun _ => rfl)
mul_back_identity_matrix_apply- The $(i, j)$-entry of $X$ multiplied on the right by the back-identity matrix is $X_{i, \operatorname{rev}(j)}$.
circulant_row_sum- The sum of any row of the circulant matrix generated by $v$ equals the sum of the elements of $v$.
Fintype.sum_equiv- A sum over a finite type is invariant under reindexing by an equivalence between index types.
Fin.revPerm- The permutation of $\operatorname{Fin} n$ that sends each index $x$ to its reversal $\operatorname{rev}(x) = n - 1 - x$.
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_back_identity_matrix_row_sum {m : ℕ} [NeZero m] (v : Fin m → ℤ) (i : Fin m) : ∑ j, (Matrix.circulant v * back_identity_matrix m) i j = ∑ j, v j := by simp only [mul_back_identity_matrix_apply] rw [← circulant_row_sum v i] exact Fintype.sum_equiv Fin.revPerm _ _ (fun _ => rfl)