The circular law for random matrices

Introduction

Let $X_{jk},1\leq j,k<\infty$, be complex random variables with $\mathbf{E}X_{jk}=0$ and $\mathbf{E}|X_{jk}|^{2}=1$. For a fixed $n\geq 1$, denote by $\lambda_{1},\ldots,\lambda_{n}$ the eigenvalues of the $n\times n$ matrix

and define its empirical spectral distribution function by

The main result of our paper is the following:

Let $\varphi(x)$ denote the function $(\ln(1+|x|))^{19+\eta}$, $\eta>0$, arbitrary, small and fixed. Let $X_{jk},j,k\in\mathbf{N}$, denote independent complex random variables with

Then $\mathbf{E}G_{n}(x,y)$ converges weakly to the distribution function $G(x,y)$ as $n\to\infty$.

We shall prove the same result for the following class of sparse matrices. Let $\varepsilon_{jk}$, $j,k=1,\ldots,n$, denote a triangular array of Bernoulli random variables (taking values $0,1$ only) which are independent in aggregate and independent of $(X_{jk})_{j,k=1}^{n}$ with common success probability $p_{n}:=\Pr\{\varepsilon_{jk}=1\}$ depending on $n$. Consider the sequence of matrices $\mathbf{X}^{(\varepsilon)}=\frac{1}{\sqrt{np_{n}}}(\varepsilon_{jk}X_{jk})_{j,k=1}^{n}$. Let $\lambda_{1}^{(\varepsilon)},\ldots,\lambda_{n}^{(\varepsilon)}$ denote the (complex) eigenvalues of the matrix $\mathbf{X}^{(\varepsilon)}$ and denote by $G_{n}^{(\varepsilon)}(x,y)$ the empirical spectral distribution function of the matrix $\mathbf{X}^{(\varepsilon)}$, that is,

For $\eta>0$ define $\varphi(x)=(\ln(1+|x|))^{19+\eta}$. Let $X_{jk},j,k\in\mathbf{N}$, denote independent complex random variables with

Assume that there is a $\theta\in(0,1]$ such that $p_{n}^{-1}=\mathcal{O}(n^{1-\theta})$ as $n\to\infty$. Then $\mathbf{E}G_{n}^{(\varepsilon)}(x,y)$ converges weakly to the distribution function $G(x,y)$ as $n\to\infty$.

The crucial problem of the proofs of Theorems 1.1 and 1.2 is to bound the smallest singular values $s_{n}(z)$, respectively, $s_{n}^{(\varepsilon)}(z)$ of the shifted matrices $\mathbf{X}-z\mathbf{I}$, respectively, $\mathbf{X}^{(\varepsilon)}-z\mathbf{I}$. (See also Zei04 , page 1561.) These bounds are based on the results obtained by Rudelson and Vershynin in RV . In a previous version of this paper GT07 we have used the corresponding results of Rudelson rud06 proving the circular law in the case of i.i.d. sub-Gaussian random variables. In fact, the results in GT07 actually imply the circular law for i.i.d. random variables with $\sup_{j,k}\mathbf{E}|X_{jk}|^{4}\leq\varkappa_{4}<\infty$ in view of the fact (explicitly stated by Rudelson in rud06 ) that in his results the sub-Gaussian condition is needed for the proof of $\Pr\{\|\mathbf{X}\|>K\}\leq C\exp\{-cn\}$ only. Restricting oneself to the set $\Omega_{n}(z)=\{s_{n}(z)\leq cn^{-3};\|\mathbf{X}\|\leq K\}$ for the investigation of the smallest singular values, the inequality $\Pr\{\Omega_{n}(z)^{c}\}\leq cn^{-1/2}$ follows from the results of Rudelson rud06 without the assumption of sub-Gaussian tails for the matrix $\mathbf{X}$. A similar result has been proved by Pan and Zhou in PanZhou2007 based on results of Rudelson and Vershynin RV and Bai and Silverstein Bainn .

The strong circular law assuming moment condition of order larger than $2$ only and comparable sparsity assumptions was proved independently by Tao and Vu in TaoVu2007 based on their results in TaoVu2007a in connection with the multivariate Littlewood Offord problem.

The approach in this paper though is based on the fruitful idea of Rudelson and Vershynin to characterize the vectors leading to small singular values of matrices with independent entries via “compressible” and “incompressible” vectors (see RV , Section 3.2, page 15). For the approximation of the distribution of singular values of $\mathbf{X}-z\mathbf{I}$ we use a scheme different from the approach used in Bai Bai1997 .

The investigation of the convergence the spectral distribution functions of real or complex (nonsymmetric and non-Hermitian) random matrices with independent entries has a long history. Ginibre’s ginibre , in 1965, studied the real, complex and quaternion matrices with i.i.d. Gaussian entries. He derived the joint density for the distribution of eigenvalues of matrix. Applying Ginibre’s formula, Mehta Me , in 1967, determined the density of the expected spectral distribution function of random matrices with Gaussian entries with independent real and imaginary parts and deduced the circle law. Pastur suggested in 1973 the circular law for the general case (see Pastur1973 , page 64). Using the Ginibre results, Edelman edelman , in 1997, proved the circular law for the matrices with i.i.d. Gaussian real entries. Rider proved in Rider2003 and Rider2006 results about the spectral radius and about linear statistics of eigenvalues of non-Hermitian matrices with Gaussian entries.

Girko Girko1984a , in 1984, investigated the circular law for general matrices with independent entries assuming that the distribution of the entries has densities. As pointed out by Bai Bai1997 , Girko’s proof had serious gaps. Bai in Bai1997 gave a proof of the circular law for random matrices with independent entries assuming that the entries had bounded densities and finite sixth moments. His result does not cover the case of the Wigner ensemble and in particular ensembles of matrices with Rademacher entries. These ensembles are of some interest in various applications (see, e.g., Timm2004 ). Girko’s Girko1984a approach using families of spectra of Hermitian matrices for a characterization of the circular law based on the so-called V-transform was fruitful for all later work. See, for example, Girko’s Lemma 1 in Bai1997 . In fact, Girko Girko1984a was the first who used the logarithmic potential to prove the circular law. We shall outline his approach using logarithmic potential theory. Let $\xi$ denote a random variable uniformly distributed over the unit disc and independent of the matrix $\mathbf{X}$. For any $r>0$, consider the matrix

where $\mathbf{I}$ denotes the identity matrix of order $n$. Let $\mu_{n}^{(r)}$ (resp., $\mu_{n}$) be empirical spectral measure of matrix $\mathbf{X}(r)$ (resp., $\mathbf{X}$) defined on the complex plane as empirical measure of the set of eigenvalues of matrix. We define a logarithmic potential of the expected spectral measure $\mathbf{E}\mu_{n}^{(r)}(ds,dt)$ as

where $\lambda_{1},\ldots,\lambda_{n}$ are the eigenvalues of the matrix $\mathbf{X}$. Note that the expected spectral measure $\mathbf{E}\mu_{n}^{(r)}$ is the convolution of the measure $\mathbf{E}\mu_{n}$ and the uniform distribution on the disc of radius $r$ (see Lemma .4 in the Appendix for details).

Assume that the sequence $\mathbf{E}\mu_{n}^{(r)}$ converges weakly to a measure $\mu$ as $n\to\infty$ and $r\to 0$. Then

Let $J$ be a random variable which is uniformly distributed on the set $\{1,\ldots,n\}$ and independent of the matrix $\mathbf{X}$. We may represent the measure $\mathbf{E}\mu_{n}^{(r)}$ as the distribution of a random variable $\lambda_{J}+r\xi$ where $\lambda_{J}$ and $\xi$ are independent. Computing the characteristic function of this measure and passing first to the limit with respect to $n\to\infty$ and then with respect to $r\to 0$ (see also Lemma .5 in the Appendix), we conclude the result.

Now we may fix $r>0$ and consider the measures $\mathbf{E}\mu_{n}^{(r)}$. They have bounded densities. Assume that the measures $\mathbf{E}\mu_{n}$ have supports in a fixed compact set and that $\mathbf{E}\mu_{n}$ converges weakly to a measure $\mu$. Applying Theorem 6.9 (Lower envelope theorem) from saff , page 73 (see also Section 3.8 in the Appendix), we obtain that under these assumptions

Applying Theorem 1.2 in saff , page 84, we get

Let $s_{1}(\mathbf{X})\geq\cdots\geq s_{n}(\mathbf{X})$ denote the singular values of the matrix $\mathbf{X}$.

Since $\mathbf{E}\frac{1}{n}\operatorname{Tr}\mathbf{X}\mathbf{X}^{*}=1$ the sequence of measures $\mathbf{E}\mu_{n}$ is weakly relatively compact. These results imply that for any $\eta>0$ we may restrict the measures $\mathbf{E}\mu_{n}$ to some compact set $K_{\eta}$ such that $\sup_{n}\mathbf{E}\mu_{n}(K_{\eta}^{(c)})<\eta$. Moreover, Lemma .2 implies the existence of a compact $K$ such that$\lim_{n\to\infty}\sup_{n}\mathbf{E}\mu_{n}(K^{(c)})=0$. If we take some subsequence of the sequence of restricted measures $\mathbf{E}\mu_{n}$ which converges to some measure $\mu$, then$\liminf_{n\to\infty}U_{\mu_{n}}^{(r)}(z)=U_{\mu}^{(r)}(z)$, $r>0$, and $\lim_{r\to 0}U_{\mu}^{(r)}(z)=U_{\mu}(z)$. If we prove that $\liminf_{n\to\infty}U_{\mu_{n}}^{(r)}(z)$ exists and $U_{\mu}(z)$ is equal to the logarithmic potential corresponding the uniform distribution on the unit disc [see Section 3, equality (68)], then the sequence of measures $\mathbf{E}\mu_{n}$ weakly converges to the uniform distribution on the unit disc. Moreover, it is enough to prove that for some sequence $r=r(n)\to 0$, $\lim_{n\to\infty}U_{\mu_{n}}^{(r)}(z)=U_{\mu}(z)$.

Furthermore, let $s_{1}^{(\varepsilon)}(z,r)\geq\cdots\geq s_{n}^{(\varepsilon)}(z,r)$ denote the singular values of matrix $\mathbf{X}^{(\varepsilon)}(z,r)=\mathbf{X}^{(\varepsilon)}(r)-z\mathbf{I}$. We shall investigate the logarithmic potential $U_{\mu_{n}}^{(r)}(z)$. Using elementary properties of singular values (see, e.g., Goh69 , Lemma 3.3, page 35), we may represent the function $U_{\mu_{n}}^{(r)}(z)$ as follows:

where $\nu_{n}^{(\varepsilon)}(\cdot,z,r)$ denotes the expected spectral measure of the matrix$\mathbf{H}_{n}^{(\varepsilon)}(z,r)=(\mathbf{X}^{(\varepsilon)}(r)-z\mathbf{I})(\mathbf{X}^{(\varepsilon)}(r)-z\mathbf{I})^{*}$, which is the expectation of the counting measure of the set of eigenvalues of the matrix $\mathbf{H}_{n}^{(\varepsilon)}(z,r)$.

In Section 2 we investigate convergence of the measure $\nu_{n}^{(\varepsilon)}(\cdot,z):=\break\nu^{(\varepsilon)}(\cdot,z,0)$. In Section 3 we study the properties of the limit measures $\nu(\cdot,z)$. But the crucial problem for the proof of the circular law is the so-called “regularization of the potential.” We solve this problem using bounds for the minimal singular values of the matrices $\mathbf{X}^{(\varepsilon)}(z):=\mathbf{X}^{(\varepsilon)}-z\mathbf{I}$ based on techniques developed in Rudelson rud06 and Rudelson and Vershynin RV . The bounds of minimal singular values of matrices $\mathbf{X}^{(\varepsilon)}$ are given in Section 4 and in the Appendix, Theorem 1.2. In Section 5 we give the proof of the main theorem. In the Appendix we combine precise statements of relevant results from potential theory and some auxiliary inequalities for the resolvent matrices.

In the what follows we shall denote by $C$ and $c$ or $\alpha,\beta,\delta,\rho,\eta$ (without indices) some general absolute constant which may be changed from line to line. To specify a constant we shall use subindices. By $I_{A}$ we shall denote the indicator of an event $A$. For any matrix $\mathbf{G}$ we denote the Frobenius norm by $\|\mathbf{G}\|_{2}$, and we denote by $\|\mathbf{G}\|$ the operator norm.

Denote by $F_{n}^{(\varepsilon)}(x,z)$ the distribution function of the measure $\nu_{n}^{(\varepsilon)}(\cdot,z)$, that is,

where $s_{1}^{(\varepsilon)}(z)\geq\cdots\geq s_{n}^{(\varepsilon)}(z)\geq 0$ denote the singular values of the matrix $\mathbf{X}^{(\varepsilon)}(z)=\mathbf{X}^{(\varepsilon)}-z\mathbf{I}$. For a positive random variable $\xi$ and a Rademacher random variable (r.v.) $\kappa$ consider the transformed r.v. $\widetilde{\xi}=\kappa\sqrt{\xi}$. If $\zeta$ has distribution function ${F}_{n}^{(\varepsilon)}(x,z)$, the variable $\widetilde{\zeta}$ has distribution function $\widetilde{F}_{n}^{(\varepsilon)}(x,z)$, given by

for all real $x$. Note that this induces a one-to-one corresponds between the respective measures $\nu_{n}^{(\varepsilon)}(\cdot,z)$ and ${\widetilde{\nu}}_{n}^{(\varepsilon)}(\cdot,z)$. The limit distribution function of ${F}_{n}^{(\varepsilon)}(x,z)$ as $n\to\infty$, is denoted by $F(\cdot,z)$. The corresponding symmetrization $\widetilde{F}(x,z)$ is the limit of $\widetilde{F}_{n}^{(\varepsilon)}(x,z)$ as $n\to\infty$. We have

Denote by $s_{n}^{(\varepsilon)}(\alpha,z)$ [resp., $s(\alpha,z)$] and $S_{n}^{(\varepsilon)}(x,z)$ [resp., $S(x,z)$] the Stieltjes transforms of the measures $\nu_{n}^{(\varepsilon)}(\cdot,z)$ [resp., $\nu(\cdot,z)$] and $\widetilde{\nu}_{n}^{(\varepsilon)}(\cdot,z)$ [resp., $\widetilde{\nu}(\cdot,z)$] correspondingly. Then we have

As shown in Bai Bai1997 , the measure $\nu(\cdot,z)$ has a density $p(x,z)$ with bounded support. More precisely, $p(x,z)\leq C\max\{1,\frac{1}{\sqrt{x}}\}$. Thus the measure $\widetilde{\nu}(\cdot,z)$ has bounded support and bounded density $\widetilde{p}(x,z)=|x|p(x^{2},z)$.

Let $\mathbf{E}X_{jk}=0$, $\mathbf{E}|X_{jk}|^{2}=1$. Assume for some function $\varphi(x)>0$ such that $\varphi(x)\to\infty$ as $x\to\infty$ and such that the function $x/\varphi(x)$ is nondecreasing we have

Let $\mathbf{E}X_{jk}=0$, $\mathbf{E}|X_{jk}|^{2}=1$, and

To bound the distance between the distribution functions$\widetilde{F}_{n}^{(\varepsilon)}(x,z)$ and $\widetilde{F}(x,z)$ we investigate the distance between their the Stieltjes transforms. Introduce the Hermitian $2n\times 2n$ matrix

where $\mathbf{O}_{n}$ denotes $n\times n$ matrix with zero entries. Using the inverse of the partial matrix (see, e.g., HoJohn91 , Chapter 08, page 18) it follows that, for $\alpha=u+iv$, $v>0$,

where $\mathbf{X}^{(\varepsilon)}(z)=\mathbf{X}^{(\varepsilon)}-z\mathbf{I}$ and $\mathbf{I}_{2n}$ denotes the unit matrix of order $2n$. By definition of $S_{n}^{(\varepsilon)}(\alpha,z)$, we have

Set $\mathbf{R}(\alpha,z):=(R_{j,k}(\alpha,z))_{j,k=1}^{2n}=(\mathbf{W}-\alpha\mathbf{I}_{2n})^{-1}$. It is easy to check that

With this notation we rewrite equality (2) as follows:

In what follows we shall use a simple resolvent equality. For two matrices $\mathbf{U}$ and $\mathbf{V}$ let $\mathbf{R}_{U}=(\mathbf{U}-\alpha\mathbf{I})^{-1}$, $\mathbf{R}_{U+V}=(\mathbf{U}+\mathbf{V}-\alpha\mathbf{I})^{-1}$, then

Using this representation and the resolvent equality, we get

Here, and in what follows, we omit the arguments $\alpha$ and $z$ in the notation of resolvent matrices. For any vector $\mathbf{a}$, let $\mathbf{a}^{T}$ denote the transposed vector $\mathbf{a}$. Applying the resolvent equality again, we obtain

Applying this notation to equality (2) and taking into account that $X_{jk}$ and $\mathbf{R}^{(jk)}$ are independent, we get

From (2) it follows immediately that for any $p,q=1,\ldots,2n$, $j,k=1,\ldots,n$,

Since ${\sum_{m,l=1}^{n}}|R_{m,l}|^{2}\leq n/v^{2}$ and ${\sum_{m,l=1}^{n}}|R^{(jk)}_{m,l}|^{2}\leq n/v^{2}$, equality (2) implies

By definition (2) of $\mathbf{T}^{(j,k)}$, applying standard resolvent properties, we obtain the following bounds, for any $z=u+iv,v>0$,

For the proof of this inequality see Lemma .3 in the Appendix. Using the last inequalities we obtain, that for $v>0$

Since $\frac{1}{n}\sum_{j=1}^{n}R_{jj}=\frac{1}{n}\sum_{k=1}^{n}R_{k+n,k+n}=\frac{1}{2n}\operatorname{Tr}\mathbf{R}(\alpha,z)$, we obtain

Note that for any Hermitian random matrix $\mathbf{W}$ with independent entries on and above the diagonal we have

The proof of this inequality is easy and due to a martingale-type expansion already used by Girko. Inequalities (24) and (25) together imply that for $v>0$

Denote by $r(\alpha,z)$ some generic function with $|r(\alpha,z)|\leq 1$ which may vary from line to line. We may now rewrite equality (2) as follows:

We now investigate the functions $T(\alpha,z)=\frac{1}{n}\mathbf{E}\operatorname{Tr}\mathbf{B}$ and $V(\alpha,z)=\frac{1}{n}\mathbf{E}\operatorname{Tr}\mathbf{D}$. Since the arguments for both functions are similar we provide it for the first one only. By definition of the matrix $\mathbf{B}$, we have

Using the resolvent equality (2) and Lemma .3, we get, for $v>c\times\break\varphi(\sqrt{np_{n}})/n$

Inequalities (28) and (29) together imply, for $v>c\varphi(\sqrt{np_{n}})/n$,

where $\widetilde{\delta}_{n}(\alpha,z)=\theta\frac{C\varkappa r(\alpha,z)}{\varphi(\sqrt{np_{n}})v^{3}}$.

Furthermore, we prove the following simple lemma.

Let $\alpha=u+iv$, $v>0$. Let $S(\alpha,z)$ satisfy the equation

and $\operatorname{Im}\{S(\alpha,z)\}>0$. Then the inequality

For $\alpha=u+iv$ with $v>0$, the Stieltjes transform $S(\alpha,z)$ satisfies the following equation:

Comparing the imaginary parts of both sides of this equation, we get

Since $v>0$ and $\operatorname{Im}\{\alpha+S(\alpha,z)\}>0$, it follows that

Equality (40) and the last remark together imply

To compare the functions $S(\alpha,z)$ and $S_{n}(\alpha,z)$ we prove:

Repeating the arguments of Lemma 2.2 completes the proof.

The next lemma provides a bound for the distance between the Stieltjes transforms $S(\alpha,z)$ and $S_{n}^{(\varepsilon)}(\alpha,z)$.

Note that $S(\alpha,z)$ and $S_{n}^{(\varepsilon)}(\alpha,z)$ satisfy the equations

respectively. These equations together imply

Applying inequality $|ab|\leq\frac{1}{2}{(a^{2}+b^{2})}$, we get

The last inequality and Lemmas 2.2 and 2.3 together imply

To bound the distance between the distribution function $F_{n}(x,z)$ and the distribution function $F(x,z)$ corresponding the Stieltjes transforms $S_{n}(\alpha,z)$ and $S(\alpha,z)$ we use Corollary 2.3 from GT03 . In the next lemma we give an integral bound for the distance between the Stieltjes transforms $S(\alpha,z)$ and $S_{n}^{(\varepsilon)}(\alpha,z)$.

For $v\geq v_{0}(n)=c(\varphi(\sqrt{np_{n}}))^{-1/6}$ the inequality

It follows from here that $|\widehat{\delta}_{n}(\alpha,z)|\leq\frac{C}{v^{5}\varphi(\sqrt{np_{n}})}$ and

for $v\geq c(\varphi(\sqrt{np_{n}}))^{-1/6}$. Lemma 2.4 implies that it is enough to prove the inequality

where $\gamma_{n}=\frac{C}{v^{6}\varphi(\sqrt{np_{n}})}$. By definition of $\widehat{\delta}(\alpha,z)$, we have

Furthermore, representation (35) implies that

It follows from relation (32) that for $v>c(\varphi(\sqrt{np_{n}}))^{-1/6}$,

The last two inequalities together imply that for sufficiently large $n$ and $v>c(\varphi(\sqrt{np_{n}}))^{-1/6}$,

Inequalities (47), (45) and the definition of $\widehat{\delta}_{n}(\alpha,z)$ together imply

If we choose $v$ such that $\frac{C\varkappa}{v^{4}\varphi(\sqrt{np_{n}})}<\frac{1}{2}$ we obtain

In Section 3 we show that the measure $\widetilde{\nu}(\cdot,z)$ has bounded support and bounded density for any $z$. To bound the distance between the distribution functions $\widetilde{F}_{n}^{(\varepsilon)}(x,z)$ and $\widetilde{F}(x,z)$ we may apply Corollary 3.2 from GT03 (see also Lemma .6 in the Appendix). We take $V=1$ and $v_{0}=C(\varphi(\sqrt{np_{n}}))^{-1/6}$. Then Lemmas 2.2 and 2.3 together imply

Properties of the measure ν~​(⋅,z)~𝜈⋅𝑧\widetilde{\nu}(\cdot,z)

In this section we investigate the properties of the measure $\widetilde{\nu}(\cdot,z)$. At first note that there exists a solution $S(\alpha,z)$ of the equation

Set $y=S(x,z)+x$ and consider equation (41) on the real line

It is straightforward to check that $\sqrt{3(1-|z|^{2})}\leq|x_{1}|$ and $x_{2}^{2}<0$ for $|z|<1$ and $x_{2}^{2}=0$ for $|z|=1$, and $x_{2}^{2}>0$ for $|z|>1$.

In the case $|z|\leq 1$ equation (57) has one real root for $|x|\leq|x_{1}|$ and three real roots for $|x|>|x_{1}|$. In the case $|z|>1$ equation (57) has one real root for $|x_{2}|\leq x\leq|x_{1}|$ and three real roots for $|x|\leq|x_{2}|$ or for $|x|\geq|x_{1}|$.

This implies that, for $|z|\leq 1$ and for

equation (57) has one real root. Furthermore, direct calculations show that

Solving the equation $L(y_{1})L(y_{2})=0$ with respect to $x$, we get for $|z|\leq 1$ and $\sqrt{3(1-|z|^{2})}\leq|x|\leq|x_{1}|$

and for $|z|\leq 1$ and $|x|>\sqrt{\frac{20+8|z|^{2}}{8}+\frac{(1+8|z|^{2})^{3/2}-1}{8|z|^{2}}}$

These relations imply that for $|z|\leq 1$ the function $L(y)$ has three real roots for $|x|\geq|x_{1}|$ and one real root for $|x|<|x_{1}|$.

Consider the case $|z|>1$ now. In this case $y_{1,2}$ are real for all $x$ and $x_{2}^{2}>0$. Note that

for $|x|\leq|x_{2}|$ and for $|x|\geq|x_{1}|$ and

for $|x_{2}|<x<|x_{1}|$. These implies that for $|z|>1$ and for $|x_{2}|<x<|x_{1}|$ the function $L(y)$ has one real root and for $|x|\leq|x_{2}|$ or for $|x|\geq|x_{1}|$ the function $L(y)$ has three real roots. The lemma is proved.

From Lemma 3.1 it follows that the measure $\widetilde{\nu}(x,z)$ has a density $p(x,z)=\lim_{v\to 0}\operatorname{Im}{S(\alpha,z)}$ and:

for $|z|\leq 1$, if $|x|\geq x_{1}$, then $p(x,z)=0$;

for $|z|\geq 1$, if $|x|\geq x_{1}$ or $|x|\leq x_{2}$, then $p(x,z)=0$;

It is well known that for $z=s+it$ the logarithmic potential of uniform distribution on the unit disc is

According to Lemma 4.4 in Bai Bai1997 , we have, for $z=s+it$,

According to Remark 3.1, we have, for $|z|\geq 1$,

Comparing equalities (63) and (61) and using relation (65), we obtain

The smallest singular value

Let $\mathbf{X}^{(\varepsilon)}=\frac{1}{\sqrt{np_{n}}}(\varepsilon_{jk}X_{jk})_{j,k=1}^{n}$ be an $n\times n$ matrix with independent entries $\varepsilon_{jk}X_{jk}$, $j,k=1,\ldots,n$. Assume that $\mathbf{E}X_{jk}=0$ and $\mathbf{E}X_{jk}^{2}=1$ and let $\varepsilon_{jk}$ denote Bernoulli random variables with $p_{n}=\Pr\{\varepsilon_{jk}=1\}$, $j,k=1,\ldots,n$. Denote by $s_{1}^{(\varepsilon)}(z)\geq\cdots\geq s_{n}^{(\varepsilon)}(z)$ the singular values of the matrix $\mathbf{X}^{(\varepsilon)}(z):=\mathbf{X}^{(\varepsilon)}-z\mathbf{I}$. In this section we prove a bound for the minimal singular value of the matrices $\mathbf{X}^{(\varepsilon)}(z)$. We prove the following result.

Let $X_{jk},j,k\in\mathbf{N}$, be independent random complex variables with $\mathbf{E}X_{jk}=0$ and $\mathbf{E}|X_{jk}|^{2}=1$, which are uniformly integrable, that is,

Let $X_{jk}$ be i.i.d. random variables with $\mathbf{E}X_{jk}=0$ and $\mathbf{E}|X_{jk}|^{2}=1$. Then condition (69) holds.

Consider the event $A$ that there exists at least one row with zero entries only. Its probability is given by

Simple calculations show that if $np_{n}\leq\ln n$ for all $n\geq 1$, then

Hence in the case $np_{n}\leq\ln n$ and $np_{n}\to\infty$ we have no invertibility with positive probability.

The proof of Theorem 4.1 uses ideas of Rudelson and Vershynin RV , to classify with high probability vectors $\mathbf{x}$ in the $(n-1)$-dimensional unit sphere $\mathcal{S}^{n-1}$ such that $\|\mathbf{X}^{(\varepsilon)}(z)\mathbf{x}\|_{2}$ is extremely small into two classes, called compressible and incompressible vectors.

We develop our approach for shifted sparse and normalized matrices $\mathbf{X}^{(\varepsilon)}(z)$. The generalization to the case of complex sparse and shifted matrices $\mathbf{X}^{(\varepsilon)}(z)$ is straightforward. For details see, for example, the paper of Götze and Tikhomirov GT07 and the proof of the Lemma 4.1 below.

We may relax the condition $p_{n}^{-1}=\mathcal{O}(n^{1-\theta})$ to $p_{n}^{-1}=o(n/\break\ln^{2}{n})$. The quantity $B$ in Theorem 4.1 should be of order $\ln n$ in this case. See Remark 4.9 for details.

Let $\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathcal{S}^{n-1}$ be a fixed unit vector and $\mathbf{X}^{(\varepsilon)}(z)$ be a matrix as in Theorem 4.1. Then there exist some positive absolute constants $\gamma_{0}$ and $c_{0}$ such that for any $0<\tau\leq\gamma_{0}$

Recall that $\mathbf{E}X_{ij}=0$ and $\mathbf{E}|X_{ij}|^{2}=1$. Assume first that $X_{ij}$ are real independent r.v. with mean zero, and variance at least $1$. Let $X^{(\varepsilon)}_{ij}=X_{ij}\varepsilon_{ij}$ with independent Bernoulli variables which are independent of $X_{ij}$ in aggregate and let $z=0$. Assume also that $\mathbf{x}$ is a real vector. Then

Using $e^{-t^{2}/2}=\mathbf{E}\exp\{it\xi\}$, where $\xi$ is a standard Gaussian random variable, we obtain

where $\xi_{j}$, $j=1,\ldots,n$, denote i.i.d. standard Gaussian r.v.s and $\mathbf{E}_{Z}$ denotes expectation with respect to $Z$ conditional on all other r.v.s. For every $\alpha,x\in$ and $\rho\in(0,1)$ the following inequality holds:

(see Bickel , inequality (3.7)). Take $\alpha=\Pr\{|\xi_{j}|\leq C_{1}\}$ for some absolute positive constant $C_{1}$ which will be chosen later. Then it follows from (4) that

where $f_{jk}(u)=\mathbf{E}\exp\{iuX_{jk}\}$. Assuming (69), choose a constant $M>0$ such that

Since $1-\cos x\geq 11/24x^{2}$ for $|x|\leq 1$, conditioning on the event $|\xi_{j}|\leq C_{1}$, we get for $0<t\leq 1/(MC_{1})$

It follows from (4) for $0<t<1/{(MC_{1})}$ and for some constant $c>0$

This implies that conditionally on $|\xi_{j}|\leq C_{1}$ and for $0<t\leq 1/(MC_{1})$

Let $\Phi_{0}(x):=2\Phi(x)-1$, $x>0$, where $\Phi(x)$ denotes the standard Gaussian distribution function. It is straightforward to show that

We may choose $C_{1}$ large enough such that following inequalities hold:

for all $|t|\leq 1/(MC_{1})$. Inequalities (4), (77), (4), (86) together imply that for any $\beta\in(0,1)$

Without loss of generality we may take $C_{1}$ sufficiently large, such that $\alpha\geq 4/5$ and choose $\beta=2/5$. Then we obtain

For $\tau<\frac{\sqrt{c}}{\sqrt{60}}$ we conclude from here that for $|t|\leq 1/(MC_{1})$

Inequality (89) implies that inequality (73) holds with some positive constant $c_{0}>0$. This completes the proof in the real case.

Consider now the general case. Let $X_{jk}=\xi_{jk}+i\eta_{jk}$ with $i=\sqrt{-1}$ with $\mathbf{E}|X_{jk}|^{2}=1$ and $x_{k}=u_{k}+iv_{k}$ and $z=u+iv$. In this notation we have

For any $j=1,\ldots,n$ we introduce the set $A_{j}$ as follows:

It is straightforward to check that for any $k\notin A_{j}$

According to inequality (91), for any $j=1,\ldots,n$, there exists a set $B_{j}$ such that

Introduce the following random variables for any $j,k=1,\ldots,n$

Inequalities (95) and (96) together imply that one of the following two inequalities

holds. If (99) holds we shall bound the first term on the right-hand side of (4). In the other case we shall bound the second term. In what follows we may repeat the arguments leading to inequalities (4)–(84). Thus the lemma is proved.

For any $q_{n}\in(0,1)$ and $K>0$ to be chosen later we define $K_{n}:=Kn\sqrt{p_{n}}$, $\widehat{q}_{n}:=q_{n}/(\ln(2/p_{n})\ln K_{n})$ and $\widehat{p}_{n}:=p_{n}/(\ln(2/p_{n})\ln K_{n})$. Without loss of generality we shall assume that

Assume there exist an absolute constant $c>0$ and values $\gamma_{n},q_{n}\in(0,1)$ such that for any $\mathbf{x}\in\mathcal{C}\subset\mathcal{S}^{(n-1)}$

holds. Then there exists a constant $\delta_{0}>0$ depending on $K$ and $c$ only such that, for $k<\delta_{0}n\widehat{q}_{n}$,

Let $\eta>0$ to be chosen later. There exists an $\eta$-net $\mathcal{N}$ in $\mathcal{S}^{k-1}\cap\mathcal{C}$ of cardinality $|\mathcal{N}|\leq(\frac{3}{\eta})^{2k}$ (see, e.g., Lemma 3.4 in rud06 ). By condition (102), we have for $\tau\leq\gamma_{n}$

Let $V$ be the event that $\|\mathbf{X}^{(\varepsilon)}(z)\|\leq K_{n}$ and $\|\mathbf{X}^{(\varepsilon)}(z)\mathbf{y}\|_{2}\leq\frac{1}{2}\tau$ for some point $\mathbf{y}\in\mathcal{S}^{(k-1)}\cap\mathcal{C}$. Assume that $V$ occurs and choose a point $\mathbf{x}\in\mathcal{N}$ such that $\|\mathbf{y}-\mathbf{x}\|_{2}\leq\eta$. Then

Choosing $\delta_{0}=\frac{c}{80}$ and $\tau=\gamma_{n}$, we complete the proof.

Following Rudelson and Vershynin RV , we shall partition the unit sphere $\mathcal{S}^{(n-1)}$ into the two sets of so-called compressible and incompressible vectors, and we will show the invertibility of $\mathbf{X}$ on each set separately.

The sets of sparse, compressible and incompressible vectors depending on $\delta$ and $\rho$ will be denoted by

Let $\mathbf{X}^{(\varepsilon)}(z)$ be a random matrix as in Theorem 1.2, and let $K_{n}=Kn\sqrt{p_{n}}$ with a constant $K\geq 1$. Assume there exist an absolute constant $c>0$ and values $\gamma_{n},q_{n}\in(0,1)$ such that for any $\mathbf{x}\in\mathcal{C}\subset\mathcal{S}^{(n-1)}$

holds. Then there exist $\delta_{1},c_{1}$ that depend on $K$ and $c$ only, such that

At first we estimate the invertibility for sparse vectors. Let $k=[\delta_{1}n\widehat{q}_{n}]$ with some positive constant $\delta_{1}$ which will be chosen later. According to Proposition 4.6 for any $\delta_{1}\leq\delta_{0}$ and for any $\tau\leq\gamma_{n}/2$, we have the following inequality:

Using Stirling’s formula, we get for some absolute positive constant $C$

We may choose $\delta_{1}$ small enough that

Choose $\rho:=\gamma:=\gamma_{n}/4$. Let $V$ be the event that $\|\mathbf{X}^{(\varepsilon)}(z)\|\leq K_{n}$ and $\|\mathbf{X}^{(\varepsilon)}(z)\mathbf{y}\|_{2}\leq\gamma_{1}$ for some point $\mathbf{y}\in\mathit{Comp}(\delta_{1}\widehat{p}_{n},\rho K_{n}^{-1})$. Assume that $V$ occurs and choose a point $\mathbf{x}\in\mathit{Sparse}(\delta_{1}\widehat{p}_{n})$ such that $\|\mathbf{y}-\mathbf{x}\|_{2}\leq\rho K_{n}^{-1}$. Then

Let $\delta,\rho\in(0,1)$. Let $\mathbf{x}\in\mathit{Incomp}(\delta,\rho)$. Then there exists a set $\sigma(\mathbf{x})\subset\{1,\ldots,n\}$ of cardinality $|\sigma(\mathbf{x})|\geq\frac{1}{2}n\delta$ such that

which we shall call “spread set of $x$” henceforth.

See proof of Lemma 3.4 RV , page 16. For the reader’s convenience we repeat this proof here. Consider the subsets of $\{1,\ldots,n\}$ defined by

If $\mathbf{x}\in\mathit{Incomp}(\delta\widehat{p}_{n},\rho)$ then there exists a set $\sigma(\mathbf{x})$ with cardinality $|\sigma(\mathbf{x})|\geq\frac{1}{2}n\delta\widehat{p}_{n}$ such that

We shall now bound this concentration function and prove a tensorization lemma for incompressible vectors.

Let $\delta_{n}$ and $\rho_{n}$ be some functions of $n$ such that $\rho_{n},\delta_{n}\in(0,1)$. Let $\eta_{0}$ and $r_{0}$ as in Lemma .7. Let $\mathbf{x}\in\mathit{Incomp}(\delta_{n},\rho_{n})$. Then there exists positive constants $r_{1}$ and $r_{2}$ depending on $r_{0}$ such that for any $0<\eta\leq\eta_{0}$ we have

Introduce $\sigma(\mathbf{x}):=\{k\in\{1,\ldots,n\}\dvtx\rho_{n}/{\sqrt{2n}}\leq|x_{k}|\leq 1/\sqrt{m/2}\}$. Since $\mathbf{x}\in\break\mathit{Incomp}(\delta_{n},\rho_{n})$ the cardinality of $\sigma(\mathbf{x})$ is at least $m/2$. Using that the concentration function of sum of independent random variables is less then concentration function of its summands, we obtain

According to Lemma .7 in the Appendix for any $\eta\leq\eta_{0}$, we have $Q(\eta)\leq r_{0}<1$. Assume that $mp_{n}\geq 1/3$. Then we have

If $mp_{n}\leq 1/3$ then $(1-p_{n})^{m}\leq 1-mp_{n}/3$ and

Let $\zeta_{1},\ldots,\zeta_{n}$ be independent nonnegative random variables. Assume that

for some positive $q_{n}\in(0,1)$ and $\lambda_{n}>0$. Then there exists positive absolute constants $K_{1}$ and $K_{2}$ such that

We repeat the proof of Lemma 4.4 in LPRT . Let $t=K_{1}\sqrt{q_{n}}\lambda_{n}$. For any $\tau>0$ we have

Choosing $\tau:=q_{n}/4$ and $K_{1}^{2}:=\frac{1}{4\ln 2}$, we get

Recall that we assume $p_{n}^{-1}=O(n^{1-\theta}),1\geq\theta>0$. For this fixed $\theta$ consider $L:=[\frac{1}{\theta}]$. Hence by definition $p_{n,l}:=(n\widehat{p}_{n})^{l}p_{n}\to 0,n\to\infty$ for $l=1,\ldots,L-1$ and $\limsup_{n\to\infty}(np_{n})^{L}p_{n}>0$. We put $p_{n,L}:=1$.

We shall assume that $n$ is large enough such that $(np_{n})^{L}p_{n}\geq q_{1}>0$ for some constant $q_{1}>0$. Starting with a decomposition of $\mathcal{C}_{0}:=\mathcal{S}^{(n-1)}$ into compressible vectors $\mathbf{x}$ in $\widehat{\mathcal{C}}_{1}:=\mathcal{C}_{0}\cap\mathit{Comp}(\delta_{1}p_{n,1},\rho_{n,1})$, where $p_{n,1}=\widehat{p}_{n}$, $\rho_{n,1}=\gamma_{0}/(4K_{n})$, and the constants $\gamma_{0}$ and $\delta_{1}$ are chosen as in Lemmas 4.1 and 4.2, respectively. Then Lemma 4.1 implies inequality (108) with $q_{n}$ replaced by $p_{n}$ and $\gamma_{n}$ replaced by $\gamma_{0}$. Hence, using Lemma 4.2, one obtains the claim for the subset of vectors $\widehat{\mathcal{C}}_{1}$. The remaining vectors $\mathbf{x}$ in $\mathcal{C}_{0}$ lie in $\mathcal{C}_{1}:=\mathit{Incomp}(\delta_{1}p_{n,1},\rho_{n,1})$. According to Lemmas 4.4, 4.5 inequality (108) holds again for these vectors but with new parameters $q_{n}=np_{n}\delta_{1}p_{n,1}$ and $\gamma_{n}=c\rho_{n,1}\sqrt{\delta_{1}p_{n,1}}$. Thus we may again subdivide the vectors in $\mathcal{C}_{1}$ into the vectors within distance $\rho_{n,2}$ from these sparse ones, that is, $\widehat{\mathcal{C}}_{2}:={\mathcal{C}}_{1}\cap\mathit{Comp}(\delta_{2}p_{n,2},\rho_{n,2})$ and the remaining ones, that is, ${\mathcal{C}}_{2}:={\mathcal{C}}_{1}\cap\mathit{Incomp}(\delta_{2}p_{n,2},\rho_{n,2})$. Iterating this procedure $L$ times we arrive at the incompressible set ${\mathcal{C}}_{L}$ of vectors $\mathbf{x}$ where Lemmas 4.4, 4.5 and Proposition 4.6 yield the required bound of order $\exp\{-\delta n\}$, for a sufficiently small absolute constant $\delta>0$.

Summarizing, we will determine iteratively constants $\delta_{l},\rho_{n,l}$, for $l=1,\ldots,L$ and the following sets of vectors:

The main bounds to carry out this procedure are given in the following Lemmas 4.6 and 4.7.

Let $\delta_{n},\rho_{n}\in(0,1)$ and let $\mathbf{x}\in\mathit{Incomp}(\delta_{n},\rho_{n})$ and $\mathbf{X}^{(\varepsilon)}(z)$ be a matrix as in Theorem 4.1. Then there exist some positive constants $c_{1}$ and $c_{2}$ depending on $K$, $r_{0}$, $\eta_{0}$ such that for any $0<\tau\leq\gamma_{n}$

where $a\wedge b$ denotes the minimum of $a$ and $b$.

Assume at first that $n\delta_{n}p_{n}\leq 1/3$. According to Lemma 4.4, we have, for any $j=1,\ldots,n$,

Applying Lemma 4.5 with $q_{n}=r_{1}\delta_{n}np_{n}$, we get