AFTD Auto-Formalizing Theoretical Domains

circulant_mul_back_identity_matrix_row_sum

theoremverified

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

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

    line 4

    uses mul_back_identity_matrix_apply

      simp only [mul_back_identity_matrix_apply]
  2. 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}$.

    line 5

    uses circulant_row_sum

      rw [← circulant_row_sum v i]
  3. 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.

    line 6

    uses Fintype.sum_equiv, Fin.revPerm

      exact 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

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