OpenAlex ·
Sharp singularity asymptotics for discrete random matrices
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.39463
- Original
- Read it at the publisher
- Topics
Abstract
We resolve the Rademacher singularity conjecture: an $n\times n$ matrix with independent uniform $\{-1,1\}$ entries is singular with probability $(2+o(1))n^22^{-n}$. More generally, for an $n\times n$ matrix $M_n$ with independent entries uniform on a fixed set $S\subset\mathbb{R}$ of cardinality $q\ge2$, we prove $\mathbb{P}(s_n(M_n)\le z/\sqrt{n}) \le Cz+a_n(S)+C'n^{1+\varepsilon}q^{-n}$ for all $n\ge1$, $z\ge0$, and $\varepsilon>0$, with $C=C(S)$ and $C'=C'(S,\varepsilon)$. Here $s_n$ denotes the least singular value, and $a_n(S)$ is the sum of the probabilities of the events involving zero rows or columns and equal or opposite pairs of rows or columns.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Local decisions, diffusive influence, and lower bounds for graphical balanced allocation
Distribution-constrained maximum stopping of maximum type
MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
Stable and Online Algorithms for Random Matrix Discrepancy
Stochastic Knothe-Rosenblatt: Light-speed Calibration of Stochastic Local Volatility Models
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.