Linear Systems and Eigenvalue Problems — Problem 37 (Subspace injection properties of sparse random matrices)

Definitions and mathematical statement

The source uses $n$ for the ambient dimension and $r$ for the subspace dimension. Its stated asymptotic hypothesis is \[ r\leq \mathcal{O}\!\left(\frac{n}{\log n}\right). \] This indicates an upper bound by a constant multiple of $n/\log n$, but the constant, its permitted dependencies, and the precise joint asymptotic regime for $n$ and $r$ are not specified.

For context, if the intended setting is linear over a field $K$, a linear map $S:E\to F$ is injective on a subspace $V\subseteq E$ when \[ \forall v,w\in V,\quad Sv=Sw\Longrightarrow v=w, \qquad\text{equivalently}\qquad V\cap\ker S=\{0\}. \] This defines ordinary subspace injectivity only. The source record does not specify the field, the distribution and construction of a SparseStack embedding, or the definition of an oblivious subspace injection (OSI), including the role of its parameter $\alpha$.

Source assertion to prove or disprove, pending these definitions. Under the stated relation between $r$ and $n$, can SparseStack parameters be chosen with \[ \zeta=\mathcal{O}(1),\qquad k=\mathcal{O}(r),\qquad \alpha=\alpha_0\ \text{constant}, \] so that the embedding has the OSI property with parameter $\alpha_0$? More specifically, do \[ \zeta=4,\qquad k=2r \] suffice for that property for all sufficiently large $r$, subject to the same dimension hypothesis?

The general question and its specific parameter question are retained separately. Their precise probabilistic quantifiers, admissible parameter ranges, uniformity in the subspace and dimensions, and constant dependencies cannot be recovered from this record. In particular, ordinary injectivity as defined above must not be substituted for the undefined OSI property. These missing qualifications prevent a fully specified mathematical conjecture.

Short English statement

Under the source's restriction $r\leq\mathcal{O}(n/\log n)$, the question asks whether SparseStack embeddings with bounded $\zeta$ and $k=\mathcal{O}(r)$ have the OSI property for constant $\alpha$, and specifically whether $\zeta=4$, $k=2r$ suffice for all sufficiently large $r$. The SparseStack construction and OSI definition are missing, so this remains a qualified statement requiring source consultation and human mathematical review.

Sources

• Local UnsolvedMath registry: permanent ID $800528$, exact source problem code catalogue entry, title "Linear Systems and Eigenvalue Problems --- Problem 37 (Subspace injection properties of sparse random matrices)." Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Supplied attribution: Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 37. Supplied source URL: https://arxiv.org/abs/2602.05394. The record attributes the problem to Amsel, Baumann et al., with proposed year 2026.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. This is supplied provenance, not an assertion that the source was independently visited or verified for this draft.
• The registry labels the problem open. This is a supplied status label, not an independently verified literature assessment. The supplied context is "Subspace injection properties of sparse random matrices."