AFTD Auto-Formalizing Theoretical Domains

mul_back_identity_matrix_apply

theoremverified

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

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

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

    line 3

    uses Matrix.mul_apply, back_identity_matrix_apply, mul_ite, mul_one, mul_zero

      simp only [Matrix.mul_apply, back_identity_matrix_apply, mul_ite, mul_one, mul_zero]
  2. 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.

    line 4

    uses Finset.sum_eq_single

      rw [Finset.sum_eq_single j.rev]
  3. 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.

    line 5

      · simp
  4. For 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}$.

    lines 6–9

    uses if_neg, Fin.rev_rev

      · intro k _ hk
        rw [if_neg]
        intro h
        exact hk (by rw [h, Fin.rev_rev])
  5. 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.

    line 10

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

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