AFTD Auto-Formalizing Theoretical Domains

back_identity_matrix_apply

theoremverified

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

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

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

    line 3

    uses Matrix.of_apply, Fin.ext_iff, Fin.val_rev

      simp only [back_identity_matrix, Matrix.of_apply, Fin.ext_iff, Fin.val_rev]
  2. 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)$).

    lines 4–5

    uses propext

      congr 1
      apply propext
  3. 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.

    line 6

      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.

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