back_identity_matrix_transpose
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
- goethals_seidel_array_mul_transposeFor circulant integer matrices A, B, C, D of order m > 0 and R the back-identity matrix, the Goethals-Seidel array M satisfies M Mᵀ =…
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.
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`.
uses
Matrix.transpose_apply,back_identity_matrix_applyext i j simp only [Matrix.transpose_apply, back_identity_matrix_apply]
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 (↔).
uses
propextcongr 1 apply propext
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.
uses
Fin.rev_revconstructor <;> 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
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_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]