6533b839fe1ef96bd12a6751
RESEARCH PRODUCT
The smallest singular value of a shifted $d$-regular random square matrix
Anna LytovaPierre YoussefNicole Tomczak-jaegermannKonstantin TikhomirovAlexander E. Litvaksubject
Statistics and ProbabilityIdentity matrixAdjacency matrices01 natural sciencesSquare matrixCombinatorics010104 statistics & probabilityMatrix (mathematics)Mathematics::Algebraic GeometryFOS: MathematicsMathematics - Combinatorics60B20 15B52 46B06 05C80Adjacency matrix0101 mathematicsCondition numberCondition numberMathematicsRandom graphsRandom graphLittlewood–Offord theorySingularity010102 general mathematicsProbability (math.PR)InvertibilityRegular graphsSingular valueSmallest singular valueAnti-concentrationSingular probabilitySparse matricesCombinatorics (math.CO)Statistics Probability and UncertaintyRandom matricesRandom matrixMathematics - ProbabilityAnalysisdescription
We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let $$C_1<d< c n/\log ^2 n$$ and let $$\mathcal {M}_{n,d}$$ be the set of all $$n\times n$$ square matrices with 0 / 1 entries, such that each row and each column of every matrix in $$\mathcal {M}_{n,d}$$ has exactly d ones. Let M be a random matrix uniformly distributed on $$\mathcal {M}_{n,d}$$ . Then the smallest singular value $$s_{n} (M)$$ of M is greater than $$n^{-6}$$ with probability at least $$1-C_2\log ^2 d/\sqrt{d}$$ , where c, $$C_1$$ , and $$C_2$$ are absolute positive constants independent of any other parameters. Analogous estimates are obtained for matrices of the form $$M-z\,\mathrm{Id}$$ , where $$\mathrm{Id}$$ is the identity matrix and z is a fixed complex number.
year | journal | country | edition | language |
---|---|---|---|---|
2017-07-09 |