back_identity_matrix_apply
Entry (i, j) of the back-identity matrix is 1 when j is the reversal m - 1 - i of i and 0 otherwise.
Statement
theorem back_identity_matrix_apply (m : ℕ) (i j : Fin m) : back_identity_matrix m i j = if j = i.rev then 1 else 0
- Source
- sanity lemma for back_identity_matrix; serves bordered_goethals_seidel_is_hadamard
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 4
- back_identity_matrix_mul_selfThe back-identity matrix is an involution: R R = I.
- mul_back_identity_matrix_applyRight multiplication by the back-identity matrix reverses the columns: (X R) i j = X i (m - 1 - j).
- back_identity_matrix_mul_applyLeft multiplication by the back-identity matrix reverses the rows: (R X) i j = X (m - 1 - i) j.
- back_identity_matrix_transposeThe back-identity matrix is symmetric: Rᵀ = R.
The proof, explained
The proof unfolds the definition of the back-identity matrix and expresses the reversal condition $j = i.\text{rev}$ in terms of the underlying natural numbers. Congruence and propositional extensionality reduce the resulting equality of conditional expressions to the logical equivalence of their branching conditions, $i + j + 1 = m \leftrightarrow j = m - (i + 1)$. This equivalence is then settled by linear natural-number arithmetic using the bounds $i, j < m$.
The matrix equality simplifies to $( \text{if } i + j + 1 = m \text{ then } 1 \text{ else } 0 ) = ( \text{if } j = m - (i + 1) \text{ then } 1 \text{ else } 0 )$.
Unfolding the definition of `back_identity_matrix` and evaluating the matrix application with `Matrix.of_apply` reduces the left-hand side to `if i + j + 1 = m then 1 else 0`. On the right-hand side, `Fin.ext_iff` converts the equality $j = i.\text{rev}$ in $\text{Fin } m$ to an equality of natural numbers, and `Fin.val_rev` replaces the value of $i.\text{rev}$ with $m - (i + 1)$.
uses
Matrix.of_apply,Fin.ext_iff,Fin.val_revsimp only [back_identity_matrix, Matrix.of_apply, Fin.ext_iff, Fin.val_rev]It suffices to show that the conditions $i + j + 1 = m$ and $j = m - (i + 1)$ are logically equivalent.
Both sides are conditional expressions returning $1$ when true and $0$ when false. By congruence (`congr 1`), equality of the expressions reduces to equality of their branching conditions as propositions. Propositional extensionality (`propext`) then converts the equality of these two propositions into a logical equivalence ($i + j + 1 = m \leftrightarrow j = m - (i + 1)$).
uses
propextcongr 1 apply propext
The equivalence $i + j + 1 = m \leftrightarrow j = m - (i + 1)$ holds for all $i, j < m$.
Since $i$ and $j$ are elements of $\text{Fin } m$, their numerical values satisfy $i < m$ and $j < m$, so $i + 1 \le m$. Under these bounds, the two linear equations are equivalent over the natural numbers, and the `omega` tactic dispatches the equivalence.
omega
Matrix.of_apply- The entry at $(i, j)$ of a matrix constructed as $\text{Matrix.of } f$ is given by evaluating $f(i, j)$.
Fin.ext_iff- Two finite indices in $\text{Fin } n$ are equal if and only if their underlying natural numbers are equal.
Fin.val_rev- The underlying natural number of the reversed index $i.\text{rev} \in \text{Fin } n$ equals $n - (i + 1)$.
propext- Propositional extensionality: two propositions are equal if and only if they are logically equivalent.
- The linear arithmetic tactic `omega` automatically uses the implicit bounds $i < m$ and $j < m$ from the type $i, j : \text{Fin } m$ to justify the equivalence involving natural number subtraction.
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_apply (m : ℕ) (i j : Fin m) : back_identity_matrix m i j = if j = i.rev then 1 else 0 := by simp only [back_identity_matrix, Matrix.of_apply, Fin.ext_iff, Fin.val_rev] congr 1 apply propext omega