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
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.