AFTD Auto-Formalizing Theoretical Domains

back_identity_matrix_mul_self

theoremverified

The back-identity matrix is an involution: R R = I.

Statement

theorem back_identity_matrix_mul_self (m : ℕ) :
    back_identity_matrix m * back_identity_matrix m = 1
Source
sanity lemma for back_identity_matrix; serves arXiv:2610.27175 Theorem 5
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • back_identity_matrix_mul_applyLeft multiplication by the back-identity matrix reverses the rows: (R X) i j = X (m - 1 - i) j.
Used by 2

The proof, explained

The proof proceeds entrywise. Multiplying on the left by the back-identity matrix reverses the rows of a matrix, so the (i, j) entry of the squared back-identity matrix is 1 when j = (i.rev).rev and 0 otherwise. Because index reversal on Fin m is an involution ((i.rev).rev = i), the condition j = (i.rev).rev is logically equivalent to i = j, which matches the entries of the identity matrix.

  1. The matrix equality reduces entrywise to showing that (if j = (i.rev).rev then 1 else 0) = (if i = j then 1 else 0) for all indices i, j.

    By matrix extensionality (`ext i j`), two matrices are equal if their corresponding entries match at all indices i and j. Multiplying on the left by the back-identity matrix reverses rows (`back_identity_matrix_mul_apply`), so the (i, j) entry of R² is R_{i.rev, j}, which evaluates to `if j = (i.rev).rev then 1 else 0` via `back_identity_matrix_apply`. On the right-hand side, the (i, j) entry of the identity matrix is `if i = j then 1 else 0` (`Matrix.one_apply`).

    lines 3–4

    uses back_identity_matrix_mul_apply, back_identity_matrix_apply, Matrix.one_apply

      ext i j
      rw [back_identity_matrix_mul_apply, back_identity_matrix_apply, Matrix.one_apply]
  2. It suffices to show that the conditions j = (i.rev).rev and i = j are logically equivalent: j = (i.rev).rev ↔ i = j.

    Since both sides are of the form `if P then 1 else 0`, congruence (`congr 1`) reduces the equality of entries to equality of the propositions (j = (i.rev).rev) = (i = j). Propositional extensionality (`propext`) turns this into a logical equivalence (↔), which is then split into forward and reverse implications (`constructor`).

    lines 5–7

    uses propext

      congr 1
      apply propext
      constructor
  3. If j = (i.rev).rev, then i = j.

    Assuming j = (i.rev).rev, substituting this equality into the goal i = j gives i = (i.rev).rev. Since index reversal is an involution (`Fin.rev_rev`), (i.rev).rev simplifies to i, leaving i = i which holds by reflexivity.

    line 8

    uses Fin.rev_rev

      · intro h; rw [h, Fin.rev_rev]
  4. If i = j, then j = (i.rev).rev.

    Assuming i = j, substituting i for j gives i = (i.rev).rev. Applying `Fin.rev_rev` simplifies (i.rev).rev to i, leaving i = i, which holds by reflexivity.

    line 9

    uses Fin.rev_rev

      · intro h; rw [h, Fin.rev_rev]
back_identity_matrix_mul_apply
Multiplying any matrix X on the left by the back-identity matrix reverses its rows: (R X)_{i, j} = X_{i.rev, j}.
back_identity_matrix_apply
The (i, j) entry of the back-identity matrix is 1 when j = i.rev and 0 otherwise.
Matrix.one_apply
The (i, j) entry of the identity matrix is 1 when i = j and 0 otherwise.
propext
Two propositions are equal if and only if they are logically equivalent (propositional extensionality).
Fin.rev_rev
Reversing a finite index twice yields the original index: (i.rev).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 back_identity_matrix_mul_self (m : ℕ) :    back_identity_matrix m * back_identity_matrix m = 1 := by  ext i j  rw [back_identity_matrix_mul_apply, back_identity_matrix_apply, Matrix.one_apply]  congr 1  apply propext  constructor  · intro h; rw [h, Fin.rev_rev]  · intro h; rw [h, Fin.rev_rev]
See it in the graphDiscuss this resultChallenge it