clopen.solutions

A square-root-logarithmic threshold for sparse rectangular injectivity

Recorded by the registry's curators from GitHub; the authors did not submit it here.

Sidney Holden

Let $A_k$ have $k$ rows and $k/100$ independent columns. Each column has
exactly $s_k$ uniformly located nonzero entries, with independent signs and
magnitude $s_k^{-1/2}$. We prove the sequence criterion
$$\exists a > 0:\ \Pr\{\sigma_{\min}(A_k) \ge a\} \longrightarrow 1 \quad\Longleftrightarrow\quad \liminf_{k \to \infty} \frac{s_k^2}{\log k} > 0.$$
Below this scale, a reservoir of columns supplies local cancellation trees.
Above it, columns with too many high-occupancy neighbors have uniformly bounded
local interaction. Removing their row neighborhoods yields a well-conditioned
bulk; a disjoint-row construction then recovers the exceptional columns through
a block-triangular estimate. The sole non-elementary input is the published
nonbacktracking trace-moment estimate of Dumitriu and Zhu. A termwise moment
comparison extends that input to fixed column sparsity and support-dependent
pruning.

Claims

SOLUTION CLAIMED OP-00209 — Sharp sparsity threshold for injectivity of a random sparse rectangular matrix
Full resolution · fidelity not yet established

Files and sources

Paper
OpenProblemsInNLA @ eb7c9d6, TR-08/solution.pdf ↗
Posted on GitHub
13 September 2026

No verification run is on record for this version.