A square matrix of rank at most has linearly dependent first columns
ProvedLatticePrepro.exists_dependence_of_rank_lecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a field, a natural number, and a square matrix over . If and , then the first columns of are linearly dependent: there is a nonzero vector with
In the soundness part of Theorem A.8 (the polynomial evaluation tables form a moment representation), this is applied to the Hankel matrix formed by the moment maps evaluated at an evaluation table , whose rank is small. The resulting dependence among its first columns is the linear recurrence from which Theorem A.7 reconstructs a sparse coefficient function.
Formalization Note: Rows and columns are indexed by Fin ℓ; a column index is embedded into by Fin.castLE.
Preamble
import Mathlib open Polynomial Matrix
Formal statement
theorem LatticePrepro.exists_dependence_of_rank_le {K : Type*} [Field K] {ℓ : ℕ} (A : Matrix (Fin ℓ) (Fin ℓ) K)
{t : ℕ} (ht : A.rank ≤ t) (htℓ : t + 1 ≤ ℓ) :
∃ c : Fin (t + 1) → K, c ≠ 0 ∧ ∀ i : Fin ℓ, ∑ j, c j * A i (Fin.castLE htℓ j) = 0 := by sorrySource
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), auxiliary lemma used in the proof of Theorem A.8 (\label{thm:moment-representation-construction}), where it supplies the column dependence required by Theorem A.7 (\label{thm:moment-hankel-reconstruction}); Lean: LatticePrepro/Basic/Matrix.lean, LatticePrepro.exists_dependence_of_rank_le