back_identity_matrix_mul_apply
Left multiplication by the back-identity matrix reverses the rows: (R X) i j = X (m - 1 - i) j.
Statement
theorem back_identity_matrix_mul_apply {m : ℕ} (X : Matrix (Fin m) (Fin m) ℤ) (i j : Fin m) :
(back_identity_matrix m * X) i j = X i.rev j- Source
- helper for bordered_goethals_seidel_is_hadamard (arXiv:2610.27175 Theorem 5)
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- back_identity_matrix_applyEntry (i, j) of the back-identity matrix is 1 when j is the reversal m - 1 - i of i and 0 otherwise.
- Used by 2
- back_identity_matrix_mul_selfThe back-identity matrix is an involution: R R = I.
- circulant_mul_back_identity_matrixFor a circulant integer matrix X of order m > 0 and the back-identity matrix R, X R = R Xᵀ.
The proof, explained
Left multiplication by the back-identity matrix $R$ computes each entry of $R X$ as the dot product of row $i$ of $R$ with column $j$ of $X$. Since row $i$ contains a single 1 at index $i.\text{rev}$ (which corresponds to $m - 1 - i$) and 0 everywhere else, expanding the product leaves a sum with only one nonzero term, which collapses to $X_{i.\text{rev}, j}$.
The $(i, j)$-th entry of the product is expressed as the sum $\sum_{x} (\text{if } x = i.\text{rev} \text{ then } X_{x j} \text{ else } 0)$.
By the definition of matrix multiplication, entry $(i, j)$ of $\text{back\_identity\_matrix } m * X$ is the sum $\sum_x R_{i x} X_{x j}$. Applying the formula for the entries of the back-identity matrix replaces $R_{i x}$ with $\text{if } x = i.\text{rev} \text{ then } 1 \text{ else } 0$. Distributing the multiplication by $X_{x j}$ into the conditional branches and simplifying $1 \cdot X_{x j} = X_{x j}$ and $0 \cdot X_{x j} = 0$ leaves a sum where only the branch for $x = i.\text{rev}$ is nonzero.
uses
Matrix.mul_apply,back_identity_matrix_apply,ite_mul,one_mul,zero_mulsimp only [Matrix.mul_apply, back_identity_matrix_apply, ite_mul, one_mul, zero_mul]The sum collapses to $X_{i.\text{rev}, j}$, completing the proof.
In the sum over all $x : \text{Fin } m$, every summand with $x \neq i.\text{rev}$ evaluates to $0$. The simplifier evaluates this single-point sum to the value at $x = i.\text{rev}$, namely $X_{i.\text{rev}, j}$.
simp
Matrix.mul_apply- The $(i, k)$-th entry of a matrix product $M N$ is given by the sum $\sum_j M_{i j} N_{j k}$ over the common index.
back_identity_matrix_apply- The $(i, j)$-th entry of the back-identity matrix of size $m$ is $1$ if $j = i.\text{rev}$ and $0$ otherwise.
ite_mul- Multiplication distributes into an if-then-else expression: $(\text{if } P \text{ then } a \text{ else } b) \cdot c = \text{if } P \text{ then } a \cdot c \text{ else } b \cdot c$.
one_mul- $1 \cdot a = a$ for any element $a$.
zero_mul- $0 \cdot a = 0$ for any element $a$.
- In Mathlib, `Fin.rev i` represents the reversed index $m - 1 - i$ in `Fin m`.
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 back_identity_matrix_mul_apply {m : ℕ} (X : Matrix (Fin m) (Fin m) ℤ) (i j : Fin m) : (back_identity_matrix m * X) i j = X i.rev j := by simp only [Matrix.mul_apply, back_identity_matrix_apply, ite_mul, one_mul, zero_mul] simp