AFTD Auto-Formalizing Theoretical Domains

back_identity_matrix_mul_apply

theoremverified

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

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

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

    line 3

    uses Matrix.mul_apply, back_identity_matrix_apply, ite_mul, one_mul, zero_mul

      simp only [Matrix.mul_apply, back_identity_matrix_apply, ite_mul, one_mul, zero_mul]
  2. 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}$.

    line 4

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

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