Reversal of a row-major square matrix stream
ProvedTensorNP.Bilinear.reverse_row_major_squareLet be a nonnegative integer, let be a type, and let be a matrix with entries in . List its entries in row-major order, reading the columns of each row from left to right. Reversing this list gives the row-major list for the matrix defined by
The result includes the empty matrix. It is a reusable indexing fact for the graph-input encoder used in the tensor bilinear feasibility reduction: that encoder stores adjacency symbols in reverse order after scanning them.
Formalization Note. Row-major positions are represented by the standard equivalence between and , and finite-index reversal by Fin.rev.
Preamble
import Mathlib
Formal statement
theorem TensorNP.Bilinear.reverse_row_major_square {α : Type*} {v : ℕ} (m : Fin v → Fin v → α) :
(List.ofFn (fun k : Fin (v*v) ↦
m (finProdFinEquiv.symm k).1 (finProdFinEquiv.symm k).2)).reverse =
List.ofFn (fun k : Fin (v*v) ↦
m (finProdFinEquiv.symm k).1.rev (finProdFinEquiv.symm k).2.rev) := by sorrySource
Derived indexing lemma for the graphCode row-major adjacency layout in TensorNP.Eigen.Defs, https://prove2.me/api/v1/definitions/0e6f3434-ae26-4ae0-adad-a0f75e3b99d4; used in the reduction for Hillar and Lim, Most Tensor Problems Are NP-Hard, Theorem 3.7, p. 0:17, https://arxiv.org/abs/0911.1393 . This indexing lemma is an implementation consequence, not a claim that the paper explicitly states it.