An upper bound on the smallest singular value of dense random combinatorial matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914470913114112 |
|---|---|
| author | Li, Dongbin Litvak, Alexander E. Yu, Tingzhou |
| author_facet | Li, Dongbin Litvak, Alexander E. Yu, Tingzhou |
| contents | Let $M$ be an $n\times n$ random matrix with entries in $\{0, 1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{0, 1\}^n$ containing exactly $d$ ones, with $d=pn$ for some fixed constant $p\in (0,1/2]$. A recent result of Tran states that the smallest singular value $s_n(M)$ is bounded below by $c_p n^{-1/2}$ with high probability. In this note, we establish a complementary upper bound for $s_n(M)$, proving that \[
\forall \varepsilon >0 \qquad \mathbb{P}\left(s_n(M)\le \frac{\sqrt{d}}{\varepsilon^2 n}\right)\ge 1-C_p\left(\varepsilon+\frac{1}{\sqrt{d}}\right), \]where $C_p$ is a positive constant depending only on $p$. This result confirms that the least singular value $s_n(M)$ of dense random combinatorial matrices is typically of the order $n^{-1/2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_12233 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An upper bound on the smallest singular value of dense random combinatorial matrices Li, Dongbin Litvak, Alexander E. Yu, Tingzhou Probability 60B20, 15B52, 46B06, 60C05, 05C80, 46B09 Let $M$ be an $n\times n$ random matrix with entries in $\{0, 1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{0, 1\}^n$ containing exactly $d$ ones, with $d=pn$ for some fixed constant $p\in (0,1/2]$. A recent result of Tran states that the smallest singular value $s_n(M)$ is bounded below by $c_p n^{-1/2}$ with high probability. In this note, we establish a complementary upper bound for $s_n(M)$, proving that \[ \forall \varepsilon >0 \qquad \mathbb{P}\left(s_n(M)\le \frac{\sqrt{d}}{\varepsilon^2 n}\right)\ge 1-C_p\left(\varepsilon+\frac{1}{\sqrt{d}}\right), \]where $C_p$ is a positive constant depending only on $p$. This result confirms that the least singular value $s_n(M)$ of dense random combinatorial matrices is typically of the order $n^{-1/2}$. |
| title | An upper bound on the smallest singular value of dense random combinatorial matrices |
| topic | Probability 60B20, 15B52, 46B06, 60C05, 05C80, 46B09 |
| url | https://arxiv.org/abs/2604.12233 |