mul_back_identity_matrix_apply
Right multiplication by the back-identity matrix reverses the columns: (X R) i j = X i (m - 1 - j).
Statement
theorem mul_back_identity_matrix_apply {m : ℕ} (X : Matrix (Fin m) (Fin m) ℤ) (i j : Fin m) :
(X * back_identity_matrix m) i j = X i j.rev- 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 3
- bordered_goethals_seidel_matrix_entriesIf a, b, c, d : Fin m → ℤ take only the values 1 and -1, every entry of the bordered Goethals-Seidel matrix built from their circulants is…
- 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.
- 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
The $(i, j)$-th entry of the product with the back-identity matrix is by definition the sum $\sum_x X_{i, x} R_{x, j}$, where $R_{x, j} = 1$ if $j = x.\text{rev}$ and $0$ otherwise. Using `Finset.sum_eq_single`, the proof reduces the sum to the single summand at $x = j.\text{rev}$. Because index reversal on `Fin m` is an involution ($j.\text{rev}.\text{rev} = j$), any index $k \neq j.\text{rev}$ has $j \neq k.\text{rev}$, so all other terms vanish and the only non-zero term evaluates to $X_{i, j.\text{rev}}$.
The matrix product entry $(X * R)_{i, j}$ expands to the sum $\sum_x (\text{if } j = x.\text{rev} \text{ then } X_{i, x} \text{ else } 0)$.
By the definition of matrix multiplication (`Matrix.mul_apply`), the $(i, j)$-th entry is $\sum_x X_{i, x} R_{x, j}$. Substituting the formula for the back-identity matrix (`back_identity_matrix_apply`), distributing multiplication over the if-then-else condition (`mul_ite`), and simplifying with $X_{i, x} \cdot 1 = X_{i, x}$ (`mul_one`) and $X_{i, x} \cdot 0 = 0$ (`mul_zero`), each summand becomes $X_{i, x}$ when $j = x.\text{rev}$ and $0$ otherwise.
uses
Matrix.mul_apply,back_identity_matrix_apply,mul_ite,mul_one,mul_zerosimp only [Matrix.mul_apply, back_identity_matrix_apply, mul_ite, mul_one, mul_zero]The summation over all column indices reduces to the single term at index $x = j.\text{rev}$.
Applying `Finset.sum_eq_single` at the index $j.\text{rev}$ reduces the sum to its value at $x = j.\text{rev}$. This sets up the main equality that this single term equals $X_{i, j.\text{rev}}$, along with two side conditions: that all other summands are zero, and that $j.\text{rev}$ belongs to the universal index set.
uses
Finset.sum_eq_singlerw [Finset.sum_eq_single j.rev]The summand at index $x = j.\text{rev}$ evaluates to $X_{i, j.\text{rev}}$.
At $x = j.\text{rev}$, the condition $j = x.\text{rev}$ becomes $j = j.\text{rev}.\text{rev}$. Since reversing an index twice is the identity ($j.\text{rev}.\text{rev} = j$), the condition holds, and the if-then-else expression evaluates to $X_{i, j.\text{rev}}$, which matches the right-hand side.
· simpFor every index $k \neq j.\text{rev}$, the summand is zero.
Given an index $k$ with $k \neq j.\text{rev}$, we show the conditional `if j = k.rev then X i k else 0` evaluates to $0$ using `if_neg`. To establish $\neg(j = k.\text{rev})$, assume for contradiction that $j = k.\text{rev}$. Reversing both sides yields $j.\text{rev} = k.\text{rev}.\text{rev} = k$ by `Fin.rev_rev`, which directly contradicts the assumption $k \neq j.\text{rev}$.
uses
if_neg,Fin.rev_rev· intro k _ hk rw [if_neg] intro h exact hk (by rw [h, Fin.rev_rev])
The case where $j.\text{rev}$ is not in the index set is vacuously false.
Because the sum is taken over all elements of the finite type (`Finset.univ`), the index $j.\text{rev}$ is necessarily present. The hypothesis $j.\text{rev} \notin \text{Finset.univ}$ is false, so the goal is dismissed.
· simp
Matrix.mul_apply- The $(i, k)$-th entry of the matrix product $M * N$ is given by the sum $\sum_j M_{i, j} N_{j, k}$.
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.
mul_ite- Multiplication distributes from the left over an if-then-else conditional: $a * (\text{if } P \text{ then } b \text{ else } c) = \text{if } P \text{ then } a * b \text{ else } a * c$.
mul_one- Multiplying an element by $1$ on the right leaves it unchanged: $a * 1 = a$.
mul_zero- Multiplying an element by $0$ on the right yields zero: $a * 0 = 0$.
Finset.sum_eq_single- A finite sum $\sum_{x \in s} f(x)$ reduces to the single term $f(a)$ if all terms with $x \neq a$ vanish and $a \in s$.
if_neg- If a proposition $c$ is false ($\neg c$), then $\text{if } c \text{ then } t \text{ else } e$ evaluates to $e$.
Fin.rev_rev- Reversing a `Fin` index twice yields the original index: $i.\text{rev}.\text{rev} = i$.
- The lemma `Finset.sum_eq_single` produces a side condition for the case where the selected index is not in the summation set; here that case is vacuously false because the sum is over the universal set `Finset.univ`.
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 mul_back_identity_matrix_apply {m : ℕ} (X : Matrix (Fin m) (Fin m) ℤ) (i j : Fin m) : (X * back_identity_matrix m) i j = X i j.rev := by simp only [Matrix.mul_apply, back_identity_matrix_apply, mul_ite, mul_one, mul_zero] rw [Finset.sum_eq_single j.rev] · simp · intro k _ hk rw [if_neg] intro h exact hk (by rw [h, Fin.rev_rev]) · simp