An upper bound on the smallest singular value of dense signed random combinatorial matrices

@misc{shi2026upper,
  title = {{An upper bound on the smallest singular value of dense signed random combinatorial matrices}},
  author = {Yuxiao Shi and Zeyan Song and Kexin Yu and Tingzhou Yu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.33427},
  eprint = {2610.33427},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.33427},
}

TY  - UNPB
TI  - An upper bound on the smallest singular value of dense signed random combinatorial matrices
AU  - Yuxiao Shi
AU  - Zeyan Song
AU  - Kexin Yu
AU  - Tingzhou Yu
PY  - 2026
DA  - 2026/10/24
PB  - arXiv
DO  - 10.48550/arxiv.2610.33427
UR  - https://arxiv.org/abs/2610.33427
AB  - Let M_n be an n× n random matrix with entries in {−1, 0, 1}, where each row is independently and uniformly sampled from the set of all vectors in {−1, 0, 1}^n containing exactly d nonzero entries, with d=pn for some fixed constant p∈(0,1/2]. A recent result by one of the authors gives a lower bound of order n^−1/2 for the smallest singular value s_n(M_n) of this model with high probability. In this paper, we establish a matching upper bound for s_n(M_n). Specifically, there exists a constant C_p>0 depending only on p such that ∀ ε >0 ℙ ( s_n(M_n) ≤ √d/(ε^2 n) ) ≥ 1−C_p(ε + 1/√d). Consequently, in the dense regime, the smallest singular value s_n(M_n) of signed random combinatorial matrices is typically of order n^−1/2.
ER  -