Back to Search
Start Over
Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
- Source :
- Israel Journal of Mathematics. 242:461-500
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- An approximate Spielman-Teng theorem for the least singular value $s_n(M_n)$ of a random $n\times n$ square matrix $M_n$ is a statement of the following form: there exist constants $C,c >0$ such that for all $\eta \geq 0$, $\Pr(s_n(M_n) \leq \eta) \lesssim n^{C}\eta + \exp(-n^{c})$. The goal of this paper is to develop a simple and novel framework for proving such results for discrete random matrices. As an application, we prove an approximate Spielman-Teng theorem for $\{0,1\}$-valued matrices, each of whose rows is an independent vector with exactly $n/2$ zero components. This improves on previous work of Nguyen and Vu, and is the first such result in a `truly combinatorial' setting.<br />Comment: 28 pages; comments welcome!
- Subjects :
- General Mathematics
Probability (math.PR)
010102 general mathematics
Zero (complex analysis)
0102 computer and information sciences
01 natural sciences
Square matrix
Independent vector
Combinatorics
Singular value
010201 computation theory & mathematics
Simple (abstract algebra)
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Algebra over a field
Computer Science::Data Structures and Algorithms
Random matrix
Mathematics - Probability
Mathematics
Subjects
Details
- ISSN :
- 15658511 and 00212172
- Volume :
- 242
- Database :
- OpenAIRE
- Journal :
- Israel Journal of Mathematics
- Accession number :
- edsair.doi.dedup.....4d5227633761acd3d36b661c12f9f088