AFTD Auto-Formalizing Theoretical Domains

back_identity_matrix_transpose

theoremverified

The back-identity matrix is symmetric: Rᵀ = R.

Statement

theorem back_identity_matrix_transpose (m : ℕ) :
    (back_identity_matrix m).transpose = back_identity_matrix m
Source
sanity lemma for back_identity_matrix; serves 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 1

The proof, explained

To show that the back-identity matrix is symmetric (Rᵀ = R), we compare entries at an arbitrary position (i, j). Unfolding the definitions of transposition and the back-identity matrix reduces entry equality to the condition that i = j.rev if and only if j = i.rev. This equivalence follows directly from the fact that index reversal on Fin m is an involution, so substituting either equality into the other yields an identity.

  1. For all indices i, j ∈ Fin m, the entry equality (if i = j.rev then 1 else 0) = (if j = i.rev then 1 else 0) suffices to establish that Rᵀ = R.

    By matrix extensionality (`ext i j`), two matrices are equal if their corresponding entries are equal at every coordinate pair (i, j). Applying `Matrix.transpose_apply` to the left-hand side transforms the (i, j)-th entry of Rᵀ into R j i. Then `back_identity_matrix_apply` evaluates R j i as `if i = j.rev then 1 else 0` and R i j as `if j = i.rev then 1 else 0`.

    lines 3–4

    uses Matrix.transpose_apply, back_identity_matrix_apply

      ext i j
      simp only [Matrix.transpose_apply, back_identity_matrix_apply]
  2. It suffices to prove the logical equivalence i = j.rev ↔ j = i.rev.

    Because both sides of the equation are conditional expressions with identical branches (1 and 0), congruence (`congr 1`) reduces their equality to the equality of their boolean conditions, (i = j.rev) = (j = i.rev). Propositional extensionality (`propext`) then turns this equality of propositions into an equivalence (↔).

    lines 5–6

    uses propext

      congr 1
      apply propext
  3. The equivalence i = j.rev ↔ j = i.rev holds.

    We prove both directions of the equivalence (`constructor`). In the forward direction, assuming i = j.rev (`intro h`), rewriting the target j = i.rev with h yields j = (j.rev).rev. Since index reversal in Fin m is an involution (`Fin.rev_rev`), this simplifies to j = j, which holds by reflexivity. The backward direction is completely symmetric: assuming j = i.rev, rewriting produces i = (i.rev).rev = i.

    line 7

    uses Fin.rev_rev

      constructor <;> intro h <;> rw [h, Fin.rev_rev]
Matrix.transpose_apply
The (i, j)-th entry of a transposed matrix Mᵀ equals the (j, i)-th entry of M: Mᵀ i j = M j i.
back_identity_matrix_apply
The (i, j)-th entry of the back-identity matrix of size m is 1 if j = i.rev and 0 otherwise.
propext
Propositional extensionality: two propositions are equal if and only if they are logically equivalent.
Fin.rev_rev
Reversing an index in Fin n 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_transpose (m : ℕ) :    (back_identity_matrix m).transpose = back_identity_matrix m := by  ext i j  simp only [Matrix.transpose_apply, back_identity_matrix_apply]  congr 1  apply propext  constructor <;> intro h <;> rw [h, Fin.rev_rev]
See it in the graphDiscuss this resultChallenge it