The strong circular law: A combinatorial view

DOI10.1142/S2010326321500313MaRDI QIDQ5019008zbMATH OpenOpenAlexFDO

Authors Vishesh Jain

Publication date 27 December 2021

Published in Random Matrices: Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.11108

zbMATH Keywords

circular lawcomplex matricesleast singular value

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: Let $N_n$ be an $nimesn$ complex random matrix, each of whose entries is an independent copy of a centered complex random variable $z$ with finite non-zero variance $sigm{a}^2$. The strong circular law, proved by Tao and Vu, states that almost surely, as $noinfty$, the empirical spectral distribution of $N_n/(sigmasqrtn)$ converges to the uniform distribution on the unit disc in $mathbbC$. A crucial ingredient in the proof of Tao and Vu, which uses deep ideas from additive combinatorics, is controlling the lower tail of the least singular value of the random matrix $xI-N_n/(sigmasqrtn)$ (where $xinmathbbC$ is fixed) with failure probability that is inverse polynomial. In this paper, using a simple and novel approach (in particular, not using tools from additive combinatorics or any net arguments), we show that for any fixed matrix $M$ with operator norm at most $n^{0.51}$ and for all $etageq0$, ${\displaystyle }$Prleft(s_n(M+N_n) leq eta ight) lesssim n^{C}eta + exp(-n^{c}),${\displaystyle }$ where $s_n(M+N_n)$ is the least singular value of $M+N_n$ and $C,c$ are absolute constants. Our result is optimal up to the constants $C,c$ and the inverse exponential-type error rate improves upon the inverse polynomial error rate due to Tao and Vu. During the course of our proof, we extend the solution of the counting problem in inverse Littlewood-Offord theory, recently isolated by the author along with Ferber, Luh, and Samotij, from Rademacher variables to general complex random variables. This significantly improves on estimates for this problem obtained using the optimal inverse Littlewood-Offord theorem of Nguyen and Vu, and may be of independent interest.

Recommendations

• scientific article; zbMATH DE number 7103333
• The circular law for random regular digraphs
• The Strassen law of iterated logarithm for combinatorial assemblies
• On combinatorial strong law of large numbers and rank statistics
• Circular law for sparse random regular digraphs
• The circular law for random regular digraphs with random edge weights
• Circular law for the sum of random permutation matrices
• Strong law of large numbers in D-posets
• The law of iterated logarithm for combinatorial multisets

Cites work

• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Around the circular law
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Bounds on the concentration function in terms of the Diophantine approximation
• Circular law
• Circular law for the sum of random permutation matrices
• Complex random matrices have no real eigenvalues
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• No-gaps delocalization for general random matrices
• Norms of random matrices: local and global problems
• On the counting problem in inverse Littlewood-Offord theory
• On the Kolmogorov-Rogozin inequality for the concentration function
• Optimal inverse Littlewood-Offord theorems
• RANDOM MATRICES: THE CIRCULAR LAW
• Random matrices: universality of ESDs and the circular law
• Small ball probability, inverse theorems, and applications
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Smooth analysis of the condition number and the least singular value
• Spectral analysis of large dimensional random matrices
• The circular law for random regular digraphs with random edge weights
• The Littlewood-Offord problem and invertibility of random matrices

Cited in

(5)

• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Quantitative invertibility of random matrices: a combinatorial perspective
• Circular law for random block band matrices with genuinely sublinear bandwidth
• A note on the universality of ESDs of inhomogeneous random matrices
• Eigenvalue gaps of random perturbations of large matrices

This page was built for publication: The strong circular law: A combinatorial view

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5019008)