Spectral radius concentration for inhomogeneous random matrices with independent entries Yi HAN Abstract . Let A A be a square random matrix of size n n , with mean zero, independent but not identically distributed entries, with variance profile S S . When entries are i.i.d. with unit variance, the spectral radius of n − 1 / 2 A n^{-1/2}A converges to 1 1 whereas the operator norm converges to 2. Motivated by recent interest in inhomogeneous random matrices, in particular non-Hermitian random band matrices, we formulate general upper bounds for ρ ⁡ ( A ) \rho(A) , the spectral radius of A A , in terms of the variance S S . We prove (1) after suitable normalization ρ ⁡ ( A ) \rho(A) is bounded by 1 + ϵ 1+\epsilon up to the optimal sparsity σ ∗ ≫ ( log n ) − 1 / 2 \sigma_{*}\gg(\log n)^{-1/2} where σ ∗ \sigma_{*} is the largest standard deviation of an individual entry; (2) a small deviation inequality for ρ ⁡ ( A ) \rho(A) capturing fluctuation beyond the optimal scale σ ∗ − 1 \sigma_{*}^{-1} ; (3) a large deviation inequality for ρ ⁡ ( A ) \rho(A) with Gaussian entries and doubly stochastic variance; and (4) boundedness of ρ ⁡ ( A ) \rho(A) in certain heavy-tailed regimes with only 2 + ϵ 2+\epsilon finite moments and inhomogeneous variance profile S S . The proof relies heavily on the trace moment method. 1. Introduction Let A=(a_{ij}) be an n by n random matrix with independent, mean zero entries a_{ij} . Let S:=(\mathbb{E}[|a_{ij}|^{2}])_{i,j} denote the variance profile of A . The aim of this paper is to obtain high probability upper bounds for \rho(A) , the spectral radius of A , for a wide class of variance profiles S up to high precisions that capture both sparsity of the matrix A and fluctuations at the spectral edge at the almost optimal scale. The spectral radius \rho(A) for a random matrix has important practical implications. Consider a simplified model of a system of linear ODEs driven by a random matrix X (1.1) \frac{d}{dt}u_{t}=-gu_{t}+Xu_{t}, where g is a coupling constant, the spectral radius \rho(X) controls the long time behavior of its solutions with large real part. It has since played an important part in analyzing the interplay of ecological stability and complexity, originating from the seminal paper of May [ 41 ] , see also [ 2 ] . More recent applications concern neural networks [ 53 ] , [ 30 ] , [ 37 ] , [ 46 ] , [ 42 ] , [ 31 ] having a structured inhomogeneous variance profile S , which could be very sparse with large bulks of zero entries. In addition to the almost sure limit of \rho(X) , deriving finer asymptotics of \rho(X) around its deterministic limit for large n can possibly allow us to compute the solution to u_{t} ( 1.1 ) at much larger time scales at the critical coupling g=\sqrt{\rho(X)} , see [ 19 ] , [ 25 ] , [ 27 ] for computing asymptotics of ODE systems at the critical coupling. Note however that in [ 19 ] , [ 25 ] , [ 27 ] the variance profile S is uniformly bounded from below or uniformly primitive in the terminology of [ 25 ] , yet these non-degeneracy assumptions on S are not assumed throughout in this paper. The homogeneous case, i.e. when S=\frac{1}{n}\mathbf{1}\mathbf{1}^{t} where \mathbf{1} is the all-ones vector of dimension n , has been much studied in the literature. The convergence of \rho(A) to the deterministic limit 1 has been obtained under a fourth moment condition in [ 8 ] , see also [ 29 ] where the same result was proven under stronger moment assumptions. When A has Gaussian entries, the precise distribution of \rho(A) , namely: (1.2) \rho(A)=1+\sqrt{\frac{\gamma_{n}}{4n}}+\frac{\mathcal{G}_{n}}{\sqrt{4n\gamma_{n}}},\quad\gamma_{n}:=\log n-2\log\log n-\log 2\pi, where \mathcal{G}_{n} converges to a Gumbel variable, has been uncovered in [ 47 ] , [ 48 ] via the exact integrable structure of the Gaussian matrix. Recently [ 20 ] showed that the asymptotic expansion ( 1.2 ) is universal fora large class of random matrices with i.i.d. distributions. Sparse i.i.d. matrices also received significant recent attention. Take for example the adjacency matrix of Erdös-Renyi digraph where we set a_{ij}\sim\operatorname{Ber}(\frac{p_{n}}{n}) independently for each i,j . Despite the sparsity when p_{n}\ll n , the variance profile is still very homogeneous, and high trace method has been applied in [ 12 ] for p_{n}\gg\log n and the method of characteristic functions has been applied in [ 23 ] to determine the spectral outliers even for constant p_{n}\geq 1 . For p_{n}\geq n^{\epsilon} , finer edge statistics have been obtained in [ 35 ] . In this work we aim to get a unified understanding for \rho(A) without any non-degeneracy or flatness condition on the variance S . This is highly relevant for the theory of inhomogeneous structured random matrices (see [ 59 ] , [ 1 ] ) as previous works mostly consider only the largest singular value. In addition to the neural network models discussed before where sparsity and inhomogeneity are key model features, another guiding example is non-Hermitian random band matrices with large chunks of zero entries. Consider for example the block band matrix (1.3) A=\begin{pmatrix}D_{1}&U_{2}&&&T_{m}\\ T_{1}&D_{2}&U_{3}&&\\ &T_{2}&D_{3}&\ddots&\\ &&\ddots&\ddots&U_{m}\\ U_{1}&&&T_{m-1}&D_{m}\end{pmatrix} where each D_{i},T_{i},U_{i} are some b_{n}\times b_{n} matrix with i.i.d. entries. Another important model is the periodic band matrix (with bandwidth d_{n} ) where we set a_{ij}=0 for any \frac{d_{n}-1}{2}<|i-j|0 we have with high probability (1.8) \rho(A)\leq\rho(S)+n^{-1/2+\epsilon}. We will make a mild improvement to this bound in Theorem ( 1.7 ). From this result one may be tempted to bound \rho(A) by \rho(S) for an arbitrary variance S without assuming ( 1.7 ): this is clearly a too general statement which may not be provable without any structure on S . Instead, we introduce another terminology, the long time control of S by \sigma in Definition ( 1.3 ), which provides a much better control of \rho(A) when S is far from being doubly stochastic. Many other related results are proved along the lines. We summarize the main results of this paper into the following four categories: (1) In Theorem 1.1 we show that whenever \sigma_{*}\sqrt{\log n}\to 0 then \rho(A) can be bounded by \sigma(1+\epsilon) with high probability. This can be compared with ( 1.4 ) which shows in the same range of \sigma_{*} , we have \mathbb{E}\|A\|\leq 2(1+\epsilon)\sigma . That is, we remove the factor 2 on the bound of \rho(A) from the bound on \|A\| all the way down to the optimal scale \sigma_{*}\sqrt{\log n}\to 0 (optimality is shown in Theorem A.1 ). (2) In Theorem 1.6 we prove small deviation inequalities for \rho(A) with a precision close to the optimal scale as predicted in ( 1.2 ): we prove fluctuation up to the scale \sigma_{*}\log n and the bound is effective whenever \sigma_{*}\log n\to 0 . A better parameter is invented in Definition 1.3 to bound \rho(A) in leading order, replacing \sigma in ( 1.8 ) to better capture non-normal fluctuations. Further, when S satisfies ( 1.7 ) we prove in Theorem 1.7 a small deviation inequality that improves the scale of ( 1.8 ). (3) When the variance S is doubly stochastic and A has Gaussian entries, we prove in Theorem 1.10 a large deviation inequality for \rho(A) . This appears to be the first large deviation inequality for \rho(A) capturing the correct dependence on \sigma_{*} . (4) An important property of random matrix with i.i.d. entries [ 14 ] , [ 13 ] is that its spectral radius remains bounded even when the entries do not have a fourth moment. In Theorem 1.11 we generalize this to show, when \sigma_{*}=O(n^{-1/2}), then \rho(A) is also bounded by \sigma (or \rho(S) ) with high probability when entries of A are symmetric with only 2+\epsilon finite moments. In the following we state the main results of this paper, divided into four different categories. 1.1. Convergence of spectral radius under optimal sparsity The first result in this paper states that \rho(A) can be well controlled by (1+\epsilon)\sigma whenever \sigma_{*}\ll(\log n)^{-1/2} . Compared to ( 1.4 ) which shows \rho(A)\leq\|A\|\leq 2(1+\epsilon)\sigma whenever \sigma_{*}\ll(\log n)^{-1/2} , the main interest is we remove the factor 2 and capture non-commutativity at optimal sparsity. Theorem 1.1 . (Convergence of spectral radius) Let A=(b_{ij}g_{ij}) be an n\times n random matrix with independent entries. Assume that b_{ij} are some fixed scalars and g_{ij} are i.i.d. random variables that are either real Gaussian with distribution \mathcal{N}_{\mathbb{R}}(0,1) , or complex Gaussian with distribution \mathcal{N}_{\mathbb{C}}(0,1) . Denote by \sigma:=\max\left(\sup_{i\in[n]}\sum_{j=1}^{n}b_{ij}^{2},\sup_{j\in[n]}\sum_{i=1}^{n}b_{ij}^{2}\right),\quad\sigma_{*}=\sup_{i,j}b_{ij} and assume \sigma/\sigma_{*}\leq n . Then there is a universal constant C>0 such that, for any \epsilon>0 , we have the non-asymptotic bound \mathbb{E}[\rho(A)]\leq(1+\epsilon)(\sigma+\frac{6\sigma_{*}}{\sqrt{\log(1+\epsilon})}\sqrt{\log n})\left(1+C\frac{\sqrt{6\frac{\log n}{\log(1+\epsilon)}}}{\sqrt{(\frac{\sigma}{\sigma_{*}})^{2}+6\frac{\log n}{\log(1+\epsilon)}}}\right). In particular, when \sigma_{*}=o(\frac{1}{\sqrt{\log n}}) , then almost surely the outliers are absent: \mathbb{P}(\lim\sup_{n\to\infty}\rho(A)>\sigma)=0. More generally, all the statements are true whenever the distributions of g_{ij} satisfy (1) \mathbb{E}[g_{ij}]=0,\quad\mathbb{E}[|g_{ij}|^{2}]=1 , g_{ij} has a symmetric distribution: g_{ij}\overset{\text{law}}{\equiv}-g_{ij}. (2) (Sub-Gaussian tail) For each m\in\mathbb{N}_{+} , (1.9) \mathbb{E}[|g_{ij}|^{2m}]\leq(\text{const}\cdot m)^{m}. (3) When g_{ij} are complex-valued, we further require that the law of g_{ij} is rotational invariant, i.e. g_{ij} has the same distribution as e^{2\pi i\mathcal{U}}g_{ij} where \mathcal{U}\sim\operatorname{Unif}([0,1]) . Here we briefly elaborate on what we mean by outliers of A , and why we assume that the bulk of the eigenvalues should lie in the ball B(0,\sigma) in the complex plane. When A has i.i.d. entries, it is known [ 56 ] that the empirical spectral measure of A converges to the circular law, the uniform measure on B(0,\sigma) . For sparse i.i.d. matrices, the circular law was also proven in [ 49 ] , improving [ 61 ] and [ 11 ] . It is a well-known conjecture to prove that even when A has inhomogeneous entries, we also have convergence of the ESD of A to the circular law under reasonable assumptions. No general solution to this conjecture is known up to date, for lack of sufficient technical machinery to control \sigma_{min}(A) , the smallest singular value of A . However, it is still widely believed that the ESD converges to the circular law in the setting of Theorem 1.1 when the variance profile of A is doubly stochastic ( \sum_{j}b_{ij}^{2}=\sum_{i}b_{ij}^{2}=1 ) [ 57 ] , and thus we consider eigenvalues outside B(0,\sigma) as outlying eigenvalues. Of course, we conclude by mentioning that convergence of ESDs does not imply absence of outliers, although absence of outliers is much easier to prove than convergence of ESDs for non-Hermitian matrices. An associated problem with Theorem 1.1 is whether we can prove an analogous lower bound for \mathbb{E}[\rho(A)] of the form \mathbb{E}[\rho(A)]\geq c\sigma for some c>0 . Unfortunately we have not been able to do so, and to our best knowledge the only way to establish such a lower bound is to prove convergence of ESDs of A to a limiting measure (see the last paragraph). This is in stark contrast to the case of a symmetric (Hermitian) matrix B where by the trace moment method we have \|B\|\leq(\operatorname{tr}(B^{p}))^{\frac{1}{p}}\leq n^{\frac{1}{p}}\|B\| , so that the computation of \operatorname{tr}(B^{n}) automatically gives rise to a lower bound on \|B\| . Still, we claim that \sigma>0 is the natural parameter in Theorem 1.1 for \rho(A) because the circular law heuristic suggests so. We note that a similar result was proven in [ 12 ] , Theorem 2.11 which also captures the optimal scale on \sigma_{*} and does not require g_{ij} to have a symmetric law, but made a flatness assumption in [ 12 ] , equation (2.3) which rules out random band matrices ( 1.3 ) and all examples when the variance of some entry is \Omega(n^{-\epsilon}) for some \epsilon\in(0,\frac{1}{10}) . In other words, our method captures the most extreme case where the variance is concentrated on a few entries (band matrices, etc.), while the method in [ 12 ] is more useful for the random graph model where the variance profile is homogeneous. In Appendix A we show in Theorem A.1 that our assumption \sigma_{*}=o(\frac{1}{\sqrt{\log n}}) is sharp for convergence of \rho(A) by a diagonal Gaussian matrix example. 1.2. Small deviation bounds Theorem 1.1 captures convergence of \rho(A) under optimal sparsity, at the order O(1) , but does not capture the fluctuations at a smaller o(1) scale. Now we further develop small deviation inequalities for the spectral radius up to the almost optimal scale predicted by ( 1.2 ), represented in terms of \sigma_{*} . We consider slightly larger \sigma_{*} , and thus weaken the sub-Gaussian tail assumption by a sub-exponential tail, and remove the requirement that the random variables have a symmetric distribution. 1.2.1. Upper bound via row sums and long-time averages Definition 1.2 . (General matrix model) Let X=(x_{ij}) be a n\times n square matrix with independent entries, and each x_{ij} satisfies (1) \mathbb{E}[x_{ij}]=0,\quad\mathbb{E}[|x_{ij}|^{2}]=1 ; (2) (Sub-exponential tail) For a fixed constant independent of i,j\in[n] we have, for each m\in\mathbb{N}_{+} , (1.10) \mathbb{E}[|x_{ij}|^{m}]\leq(\text{const}\cdot m)^{m}. Let (b_{ij})_{i,j=1}^{n} be non-negative scalars, and define the inhomogeneous matrix A=(b_{ij}x_{ij})_{i,j=1}^{n}. Define the variance matrix S:=(b_{ij}^{2})_{i,j=1}^{n} and define the sparsity parameter \sigma_{*}=\sigma_{*}(A)=\sup_{i,j}b_{ij}. We introduce a parameter, in place of \sigma ( 1.6 ), that controls the spectral radius: Definition 1.3 . (Long-time control) Let S be an n\times n square matrix with non-negative entries. We say S is long-time controlled by a parameter \sigma>0 [ \sigma can be n -dependent but we assume \sigma=O(1) ] if there exists a fixed (independent of n ) constant C=C(\sigma)>0 such that \sup_{i}\sum_{j=1}^{n}[S^{k}]_{ij}\leq C\sigma^{2k},\quad\sup_{i}\sum_{j=1}^{n}[(S^{*})^{k}]_{ij}\leq C\sigma^{2k},\quad\text{ for all }k\geq 1, where [S^{k}]_{ij} denotes the (i,j) -th entry of the product matrix S^{k} , and S^{*} is the transpose of the matrix S . The notion of Definition 1.3 is more flexible than the \ell^{2} norm of columns and rows of S , as shown in the following most simple example: Example 1.4 . (Doubly stochastic) When A has doubly stochastic variance profile, so that (1.11) \sum_{j=1}^{n}b_{ij}^{2}\leq 1\quad\text{for all }i\in[n];\quad\sum_{i=1}^{n}b_{ij}^{2}\leq 1\quad\text{for all }j\in[n], S is long-time controlled by 1, as we can simply take \sigma=1 and C=1 in Definition ( 1.3 ). Example 1.5 . (Heterogeneous block matrix) Consider two independent n\times n random matrices T_{1},T_{2} with mean zero, unit variance sub-Gaussian entries. Fix \lambda_{1},\lambda_{2}>0 and consider the (2n\times 2n) matrix T:=n^{-1/2}\begin{pmatrix}0&\lambda_{1}T_{1}\\ \lambda_{2}T_{2}&0\end{pmatrix}. The largest \ell^{2} norm of any row (or column) of the variance profile of T is \max(\lambda_{1},\lambda_{2}) , but it is easy to see the variance profile of T is long-time controlled by \sqrt{\lambda_{1}\lambda_{2}} , so we expect to control \rho(T) by \sqrt{\lambda_{1}\lambda_{2}} , which is much smaller than \sup(\lambda_{1},\lambda_{2}) when \lambda_{1},\lambda_{2} are not close. A further example is deferred to B.1 . These examples illustrate that the long-term control in Definition 1.3 can better capture \rho(A) than \sigma in ( 1.6 ). The underlying reason is that for a non-Hermitian random matrix A , its spectral radius \rho(A) is less sensitive to the maximum \ell^{2} norm of each single row, compared to the operator norm \|A\| . Our main theorem in this direction can be stated as: Theorem 1.6 . (Small deviations) In the setting of Definition 1.2 and 1.3 , let \underline{\sigma}>0 be such that S is long-time controlled by \underline{\sigma} . Assume that \sigma_{*}\ll(\log n)^{-1} , then we have the following estimate: for any t>0 we have \mathbb{P}\left(\rho(A)\geq\underline{\sigma}(1+t\sigma_{*})\right)\leq C_{0}ne^{-Ct}, where C_{0},C>0 are two positive constants depending only on the sub-exponential moments of x_{ij} in Definition 1.2 and the constant C(\underline{\sigma}) in Definition 1.3 . In particular, whenever A satisfy Definition 1.2 (so that x_{ij} has sub-exponential tails and not necessarily symmetric distribution), and \sigma_{*}\ll(\log n)^{-1} , then \mathbb{P}(\lim\sup_{n\to\infty}\rho(A)\leq\underline{\sigma})=1. Theorem 1.6 captures the fluctuation of \rho(A) on an almost optimal scale. Taking, for example, \underline{\sigma}=1 and \sigma_{*}=n^{-1/2} , then Theorem 1.6 implies with high probability \rho(A)\leq 1+\frac{(\log n)^{1+c}}{\sqrt{n}} for any c>0 and the possibility that \rho(A)\geq 1+n^{-d} is O(ne^{-n^{1/2-d}}) for any 00 we have \mathbb{P}\left(\rho(A)\geq\sqrt{\rho(S)}+\frac{t}{\sqrt{n}})\right)\leq C_{0}n^{2}e^{-C_{1}t}, where C_{0},C_{1}>0 are two constants depending only on sub-exponential moments of x_{ij} in Definition 1.2 and the constants c,C in equation ( 1.12 ). In particular, we show that \rho(A)\leq\sqrt{\rho(S)}+\frac{(\log n)^{1+c}}{\sqrt{n}} with high probability for any c>0 . Similar results were first proven in [ 3 ] which shows that \rho(A)\leq\sqrt{\rho(S)}+n^{\epsilon-1/2} with probability at least 1-c_{D,\epsilon}/n^{D} for any D\in\mathbb{N}_{+} . In [ 3 ] it was only assumed that the entries have finite moments of all order, whereas we assume x_{ij} has sub-exponential tails. Under this assumption we improve the bound in [ 3 ] in two directions: first we reach a much smaller scale close to \sqrt{\log n/n} as predicted by ( 1.2 ), and second we have a super-polynomial bound e^{-n^{\epsilon}} for the error of small deviation by taking t=n^{\epsilon} , improving the polynomial bound [ 3 ] . The assumption 1.12 plays a crucial role in the proof. Adapting the proof argument a bit, 1.12 could possibly be weakened to n^{-1-\tau}\leq b_{ij}^{2}\leq n^{-1+\tau} for some sufficiently small \tau>0 , though we do not pursue this improvement in this paper. 1.2.3. Suppressed fluctuations: Examples Whereas Theorem 1.6 provides high precision small-deviation estimates when S has a good structure, we may have vastly overestimated the fluctuation (and even the spectral radius itself) when the matrix has large chunks of zero dispersed in a particular pattern. This is illustrated by the following important examples that arises in the study of product matrix process and product circular law. Theorem 1.8 . For each integer n let p_{n}\in[1,n] be an integer dividing n , with n=p_{n}q_{n} . Let X_{1},\cdots,X_{p_{n}} be independent q_{n}\times q_{n} random matrices with i.i.d. entries having distribution \frac{1}{\sqrt{q_{n}}}\xi , with \mathbb{E}[\xi]=0 and \mathbb{E}[|\xi|^{2}]=1 (we do not need \xi to have higher than two moments). Consider the following n\times n matrix \mathcal{L} (1.13) \mathcal{L}=\begin{pmatrix}&X_{2}&&&\\ &&X_{3}&&\\ &&&\ddots&\\ &&&&X_{p_{n}}\\ X_{1}&&&&\end{pmatrix}. Then for any q_{n}\log q_{n}\ll n , for any \epsilon>0 , with high probability we have \rho(\mathcal{L})\leq 1+\epsilon for n large. We also have a small deviation bound: for any t>0 , \mathbb{P}(\rho(\mathcal{L})\geq 1+\frac{t}{p_{n}})\leq q_{n}e^{-2t}. Note that both claims are true if p_{n} is so large that q_{n}=o(\log n) : in this case \sigma_{*}(\mathcal{L})\gg(\log n)^{-1/2} , so that Theorem 1.1 and 1.6 are not applicable. But even in this case, we have \rho(\mathcal{L})\to 1 and \rho(\mathcal{L})\leq 1+n^{-1+\epsilon} with high probability for any \epsilon>0 : this scale of fluctuation is much smaller than the Gaussian matrix ( 1.2 ). The matrix model ( 1.8 ) plays a fundamental role in the study of spectrum and outlier of product random matrices, see for example [ 44 ] , [ 24 ] , [ 33 ] , [ 34 ] . For large p_{n}\gg\sqrt{n} the system exhibits an ergodic behavior, and in particular for q_{n}=2 , a law of large numbers is proved for spectral radius of product matrices with only a second moment assumption [ 7 ] . Example 1.9 . (Nilpotent matrices) Another important example where Theorem 1.1 and 1.6 are less precise is when the variance profile S of A is itself a nilpotent matrix. For example we can take S the square matrix with entry one all along its upper diagonal and zero elsewhere. Then A itself is nilpotent and \rho(A)=0: this can be checked via computing high moments of A , even if Theorem 1.1 and 1.6 are not designed to detect such degenerate circumstances. It is hard to formulate general conditions capturing pedagogically defined matrices with large chunks of zero, and the focus of the current paper is more leaning on inhomogeneous non-Hermitian matrices having a near mean-field structure. Thus we do not develop this direction further and illustrate suppressed fluctuations just via the example in Theorem 1.8 . 1.3. Large deviation estimates of spectral radius An important result in high dimensional probability states that the operator norm of a random matrix with sub-Gaussian entries concentrates around a fixed value with sub-Gaussian tails of deviation. More precisely, (see [ 60 ] , Theorem 4.3.5) Let A be an m\times n random matrix with independent mean zero sub-Gaussian entries, then for any t>0 , \|A\|\leq CK(\sqrt{m}+\sqrt{n}+t) with probability at least 1-2\exp(-t^{2}) . Much more refined sub-Gaussian concentration inequalities have since been derived, see [ 58 ] , [ 9 ] and references therein. When A has Gaussian entries, the operator norm \|A\| is a Gaussian process where powerful dimension free techniques are available, see for example [ 10 ] , [ 9 ] . In contrast, little seems to be known for sub-Gaussian concentration of \rho(A) , the spectral radius of an i.i.d. random matrix. Observe that using \rho(A)\leq\|A\| and that large deviation inequalities for \|A\| are well-known, the interest in proving large deviation of \rho(A) mainly lies in the range \rho(A)\leq t\leq\|A\| . The spectral radius does not admit a variational characterization, hence the standard arguments for the operator norm are not applicable. Via computing very high moments as in the proof of Theorem 1.1 , we can derive large deviation estimates for \rho(A) , but which may be suboptimal in the power of \sigma_{*} . We propose an alternative method in the special case when X has a doubly stochastic variance profile and has Gaussian entries, with optimal dependence on \sigma_{*} . Theorem 1.10 . (Spectral radius sub-Gaussian concentration) Let A=(a_{ij}) be an n\times n random matrix with independent mean zero entries, the variance profile S=(s_{ij})=(\mathbb{E}[|a_{ij}|^{2}])_{i,j} is doubly stochastic . Assume that A has jointly Gaussian entries and \sqrt{\sigma_{*}}(\log n)^{\frac{3}{4}}\to 0 as n\to\infty , then for any t>0 , whenever \sqrt{\sigma_{*}}(\log n)^{\frac{3}{4}}\leq\frac{t^{1.5}}{500} we have \mathbb{P}(\rho(A)\geq 1+t)\leq(1+t^{-3})e^{-C_{0}\frac{\min\{t^{2},t^{3}\}}{\sigma_{*}^{2}}} where C_{0} is some universal constant. At this point, the reader may be bothered as to why we need Theorem 1.10 after all. For the Gaussian case, we may expect the following simple argument to work: we have the computation \mathbb{E}\rho(A) in Theorem 1.1 and since the entries are Gaussian we expect \rho(A) to concentrate around \mathbb{E}\rho(A) . This argument works pretty well when one controls the operator norm \|A\| (see [ 10 ] ) but does not seem to work for the spectral radius \rho(A) because, in general, the spectral radius \rho(A) is not a Lipschitz continuous function of all the entries of A , unlike the operator norm. Thus, one cannot directly apply Gaussian concentration of measure to \rho(A) . Instead, we will consider the resolvent of the Hermitization of A and use a concentration of measure argument for the resolvent to deduce the result. Compared to the Hermitian case (see for example [ 16 ] , [ 10 ] ), we have reached the expected (sharp) dependence of the large deviation on \sigma_{*}^{-2} . To see why \exp(-t^{2}/\sigma_{*}^{2}) is expected to the asymptotics for the large deviation probability, suppose (only as a heuristic argument) that we can regard \rho(A) as a 1-Lipschitz continuous function of each of its entries, then the fact that the entries are scaled by a factor \sigma_{*} would imply a Gaussian large deviation probability \exp(-t^{2}/\sigma_{*}^{2}) . However, we do not have a proof that this large deviation probability \exp(-t^{2}/\sigma_{*}^{2}) is the sharpest one for all models. Compared to this optimal estimate, we need a higher power t^{3} instead of t^{2} for t small, and we have an additional entropy cost factor (1+t^{-3}) contributing for some t . These additional factors all arise from the proof technique and may be removed via other methods, but these additional factors are tame enough for large n and do not contribute significantly to practical applications. The extension of Theorem 1.10 to general subGaussian distributions should be possible, but the current method yields suboptimal dependence on t and \sigma_{*} in the resulting estimate, so we do not pursue it here. The restriction of a doubly stochastic variance profile is made so that the matrix Dyson equation can easily be solved. For an arbitrary variance profile, the matrix Dyson equation ( 4.5 ) may not be explicitly solvable, which makes quantitative results much harder to get. 1.4. Upper bound in the heavy-tailed case In the main theorems of this paper we have considered random matrices with sub-Gaussian, or sub-exponential entries. In this last section we show the theme of this work continues to hold in the heavy-tailed case, when entries of A have only 2+\epsilon moments. The fact that \rho(A) is bounded without fourth moment assumption is a peculiar feature for non-Hermitian matrices uncovered in [ 14 ] , [ 13 ] . So far this fact is proven only for the i.i.d. case, and in the next theorem we show the parameters \sigma and \rho(S) can still be a good upper bound for \rho(A) in this case without a fourth moment. Theorem 1.11 . Let A=(b_{ij}x_{ij}) be an n\times n random matrix where (x_{ij}) are i.i.d. with distribution \xi such that \xi is symmetric \xi\overset{\text{law}}{\equiv}-\xi , \mathbb{E}[\xi]=0,\mathbb{E}[|\xi|^{2}]=1 and \mathbb{E}[|\xi|^{2+\epsilon}]<\infty for a given \epsilon>0 . Denote by S=(s_{ij})=(b_{ij}^{2}) . Assume that the entries of S are uniformly upper bounded: we can find a constant C>0 such that (1.14) s_{ij}\leq\frac{C}{n}\text{ for each }i,j\in[n]. Then the spectral radius \rho(A) can be well-controlled in the following cases (1) (Row/ column sum) Let \sigma be defined as in ( 1.6 ). Then with probability 1-o(1) , \limsup_{n\to\infty}\rho(A)\leq\sigma. (2) (Spectral radius) Assume moreover that S has a lower bound: for some fixed c>0 , s_{ij}\geq\frac{c}{n}\text{ for each }i,j\in[n]. Then for any \epsilon>0 , we have with probability 1-o(1) , \rho(A)\leq\sqrt{\rho(S)}+\epsilon. The proof will essentially be an adaptation of the moment method in [ 14 ] . In case (1), it is not clear if we can replace \sigma by the long-time control bound in Definition ( 1.3 ). In case (2), we should be able to prove a two-sided inequality, that is, we also have \rho(A)\geq\sqrt{\rho(s)}-\epsilon , via showing an inhomogeneous circular law holds for the ESD of A (see [ 4 ] , [ 21 ] , [ 22 ] ) and that the limiting law is supported on B(0,\sqrt{\rho(S)}) . The proof of this step is standard by now (only the 2+\epsilon moment condition needs to be taken care of) and is omitted. The uniform upper bound ( 1.14 ) plays a fundamental role and cannot be removed. As entries of X only have 2+\epsilon finite moments, if ( 1.14 ) were replaced by a weaker assumption, we can easily construct a band matrix in which the diagonal entries are with high probability unbounded, while the rest of the matrix (with diagonal entries removed) has a bounded spectral radius. This is likely to produce a matrix with unbounded spectral radius; for more details of this band matrix example, see Example B.2 . That is, a weakening of ( 1.14 ) should be followed by a strengthening of the moment assumption on \xi , but proving such am interpolation result is beyond the scope of this work. 1.5. Methods and further discussions To prove most theorems in this paper (except Theorem 1.10 ) we use the method of moments to bound the spectral radius of A , and this idea dates back to the earliest works [ 29 ] , [ 8 ] and the more recent ones [ 14 ] , [ 12 ] . The basic idea is very easy to illustrate: if \lambda is an eigenvalue of A then \lambda^{p} is an eigenvalue of A^{p} for any p , so that we have |\lambda|\leq\|A^{p}\|^{\frac{1}{p}} and the problem boils down to computing upper bounds of \mathbb{E}[\|A^{p}\|]^{\frac{1}{p}} . The accuracy of estimates on \rho(A) depends on the range on which p can simultaneously grow with n . Compared to previous works, the key novelty of this paper is to improve the range of p where such a bound can be proven. The idea of using high moment computations and a compression argument to bound the operator norm of an inhomogeneous random matrix dates back to [ 26 ] , [ 10 ] , and we adapt them to this non-Hermitian setting. In contrast to the situation there, the high moment computations \mathbb{E}[\|A^{p}\|] for a Gaussian model A does not seem available, and this will occupy the bulk of Section 2 of this paper. For Theorem 1.1 , we need to consider any p=O(n) in computing \mathbb{E}[\|A^{p}\|]^{\frac{1}{p}} . This is in general very difficult, and we will take ideas from computing non-backtracking paths and precise topological enumeration of all possible paths, which is first done in [ 28 ] for Wigner and Wishart matrices. The independent assumption on A essentially guarantees the paths are non-backtracking, so many computations in [ 28 ] can be used here. For Theorem 1.6 , we need to consider any p\ll\sqrt{n} in bounding \mathbb{E}[\|A^{p}]\| . We do not consider any larger scale of p here because typically \rho(A)\geq\sigma+n^{-1/2} by ( 1.2 ). The upper bound of \mathbb{E}[\|A\|^{p}] is reminiscent of the Dyck path enumerations in proving edge universality for Wigner matrices in [ 50 ] , [ 51 ] , [ 54 ] , and we will take inspirations for these works to prove Theorem 1.6 . In this range p\ll\sqrt{n} , the main contribution to \mathbb{E}\|A\|^{p} comes from double edges without self-intersection, and this is why only the long-time control in Definition 1.3 contributes to the first order limit of \rho(A) . Theorem 1.10 will follow from using the machinery of [ 9 ] and a covering argument, leading to an entropy cost (1+t^{-3}) . Theorem 1.11 will follow from adapting the high moment computations from [ 14 ] . The high moment method in this paper requires \mathbb{E}[A]=0 . Recently, [ 18 ] proposed a method to prove absence of outliers for A having nonzero expectation and a general variance profile satisfying 1.12 . 2. Moments expansion in the homogeneous case To bound the spectral radius we will develop moments expansion of \mathbb{E}[\operatorname{tr}(A^{\ell}(A^{*})^{\ell})] for moderately large \ell up to \ell=o(\sqrt{n}) and \ell=o(n) . Unlike Wigner and Wishart matrices, such estimates cannot easily be found in the literature even in the special case where A is the Ginibre ensemble. In [ 29 ] a computation was done up to \ell=n^{c} for some fixed small c>0 and in [ 12 ] a computation up to \ell=n^{\frac{1}{3}-\epsilon} , but they are not enough for our purpose. Therefore we have to do moment computation by ourselves even in the Gaussian case. We will present in this section the computations when the variance profile is homogeneous, and then adapt the computations to inhomogeneous variance profiles in Section 3 . The computations do not use the Gaussian structure and works for general distributions. At this point we may wonder if, using Wick formula, we can significantly simplify the computation of \mathbb{E}[\operatorname{tr}(A^{\ell}(A^{*})^{\ell})] for the Gaussian case. Relevant computations for the mixed moments of complex Ginibre ensembles can be found in references in [ 17 ] . In particular, it is well-known that certain mixed moments of the complex Ginibre ensemble converge to the Fuss-Catalan numbers [ 32 ] [ 38 ] . However, these results are computed in the regime when the matrix size n grows to infinity but \ell is fixed. When \ell is growing with n , it is not clear if the use of Wick formula leads to any simplification in the combinatorial argument: we have to enumerate all the pairings of vertices of a chain of length 2\ell where two different pairings share the same vertex, and it is unclear how to correctly enumerate such pairings especially near the critical case \ell=n^{1/2-\epsilon} . This section is purely technical and can be skipped for a first reading. In Section 3 , references will be made on the results and notations stated in this section. We will carry out two different types of moment computations. In Section 2.1 , which is the preparation for proving Theorem 1.6 and 1.7 , we will compute moments up to \ell=o(n^{\frac{1}{2}}) to derive small deviation estimates. The choice of \ell is because the spectral edge of a Ginibre matrix satisfies the three terms expansion ( 1.2 ). It turns out that in the regime \ell=o(n^{\frac{1}{2}}) the combinatorics in the trace expansion \mathbb{E}[\operatorname{tr}(A^{\ell}(A^{*})^{\ell})] is relatively simple, and the only dominant contribution comes from simple paths with no self-intersection. We will partly follow and make considerable adaptations to the moment computation in [ 50 ] for Wigner matrices up to \ell=o(n^{\frac{1}{2}}) . In Section 2.2 , which is the preparation for proving Theorem 1.1 , we compute moments up to \ell=O(n) . Motivated by [ 28 ] , the combinatorics involved is much more difficult but still tractable by the graph counting techniques. 2.1. Moment estimate I To highlight the main ideas we first do computation for the complex Ginibre case in Lemma 2.1 , then the sub-exponential symmetric case in Theorem 2.2 , and finally remove the symmetric distribution assumption in Theorem 2.3 . The underlying theme is the same despite increased generality. Lemma 2.1 . Assume that A is the complex Ginibre ensemble, i.e. V=\frac{1}{n}\mathbf{1}\mathbf{1}^{t} and entries of X are i.i.d. with law \mathcal{N}_{\mathbb{C}}(0,1) . Then whenever p\ll\sqrt{n} , we have \mathbb{E}\operatorname{Tr}[A^{p}(A^{*})^{p}]=n(1+o(1)). Proof. The property we use about the distribution \xi\sim\mathcal{N}_{\mathbb{C}}(0,1) is its rotational invariance, so that for any m,n\in\mathbb{N}_{+} , \mathbb{E}[\xi^{m}\overline{\xi}^{n}]=0 unless m=n . Breakdown the expectation computation: classifying vertices by the number of visits by the first half. We have the expansion \mathbb{E}\operatorname{tr}(A^{p}(A^{*})^{p})=\frac{1}{n^{p}}\sum_{i_{0},\cdots,i_{p}=1}^{n}\sum_{j_{0},\cdots,j_{p-2}=1}^{n}\mathbb{E}[x_{i_{0}i_{1}}x_{i_{1}i_{2}}\cdots x_{i_{p-1}i_{p}}\bar{x}_{j_{p-2}i_{p}}\bar{x}_{j_{p-3}j_{p-2}}\cdots\bar{x}_{i_{0}j_{0}}]. From the above property of complex Gaussian distribution, we see that once (i_{0},\cdots,i_{p}) are fixed, then (j_{0},\cdots,j_{p-2}) must be chosen from (i_{0},\cdots,i_{p}) and no other possibility is allowed. This is because if some additional index is chosen then we have a term \bar{x}_{i_{s}j_{s}}^{m_{s}} in the expectation with no corresponding pairs of x_{i_{s}j_{s}} , so the expectation must vanish. Likewise, each directed edge (i_{0},i_{1}),\cdots,(i_{p-1},{i_{p}}) counting multiplicity must be traveled by the \bar{x} elements in exactly the same number of times as they are traveled by the x elements. Therefore we only need to enumerate over the first half of the paths, and we later show how the contributions from the second half of paths can be bounded from the first half. We first fix the initial i_{0}\in[n] and then consider paths P=(i_{1},\cdots,i_{p}) and we let n_{k} be the number of indices in [n] that are visited k times by P . Clearly we have \sum_{k\geq 0}n_{k}=n and \sum_{k\geq 0}kn_{k}=p (note that P has p indices, and each vertex visited k times by P should appear in i_{1},\cdots,i_{p} with multiplicity k , hence the equality). We let \mathcal{P}_{k}\subset[n] denote the set of vertices visited k times by P , for each k . Contribution from the dominant part. We claim that the dominant contribution comes from paths where n_{1}=p and n_{k}=0 for all k\geq 2 . Once such a path is chosen, so that P has no self-intersection, there is a unique choice of j_{p-2},\cdots,j_{1} so as to have a nonzero expectation: we must take j_{p-2}=i_{p-1},\cdots,j_{0}=i_{1} . The contribution of all such terms to \mathbb{E}\operatorname{tr}(A^{p}(A^{*})^{p}) is at most (2.1) \frac{1}{n^{p}}\cdot n\cdot(n-1)\cdots(n-p)=n(1+o(1)), where we simply need to choose p different indices from [n] , in addition to the initial vertex i_{0} , and we also use p\ll\sqrt{n} . Other contributions: Determining the second half of path from the first half . Then we show contributions from terms with nonzero n_{k},k\geq 2 is negligible. The procedure is to first choose the initial i_{0} and then choose the path P . Once P is chosen proceed as follows: we set up a procedure which, for every 1\leq s\leq p-2 suppose that j_{s} is chosen, outputs a choice of j_{s-1} . We first show how we determine j_{p-2} from i_{p} : if i_{p} is visited only once in P by x_{i_{p-1}i_{p}} then we must take j_{p-2}=i_{p-1} with no other option, and we have a |x_{i_{p-1}i_{p}}|^{2} term in the expectation. If i_{p} is visited more than once in P , say it is visited k times, then we choose any of these k visits and set j_{p-2} to be the vertex in P immediately to the left of this visit (the restriction of complex Ginibre ensembles forces that j_{p-2} must be exactly one of those k preimages to guarantee a nonzero expectation). In this scenario |x_{i_{p-1}j_{p-2}}| may appear at most 2k times in the expansion of \mathbb{E}[A^{p}(A^{*})^{p}] . This determines the choice of j_{p-2} , and from this we can determine the choice of j_{p-3} depending on the number of times j_{p-2} appears in P , and then determine j_{p-4} , all the way up until we determine j_{0} . We are faced with the global constraint that each directed edge in P must be traveled the same number of times by the elements with complex conjugate, the \bar{x}_{ij} ’s. In the above procedure, the determination of j_{p-s-1} from j_{p-s} is not unique, but if j_{p-s} is visited by P for k times, then there is at most k possible values for j_{p-s-1} . Thus for a fixed first half of path P , the total number of choices of the second half is at most \prod_{k=2}^{p}k^{kn_{k}} . We prove this upper bound as follows: Proving the upper bound for the number of choices for the second half of the path. To justify the upper bound in the last paragraph, we can carry out an inductive proof: let P^{\prime} denote the second half of the path, and suppose we have known the first x\leq p vertices of P^{\prime} , so we know P\cup(P^{\prime})_{[1,x]} where the latter is the restriction of P^{\prime} on the first x vertices. By the constraint of complex Gaussians, we have determined the exact vertices that P^{\prime}_{[x+1,p]} should visit, and the exact number of times each vertex should be visited (but have not determined the order where they are visited). Now we denote, for each k , n_{k}^{\prime} (and n_{k}^{\prime\prime} ) be the number of indices of (P^{\prime})_{[1,x]} (and respectively (P^{\prime})_{[x+1,p]} ) that lie in the subset \mathcal{P}_{k} , counting the multiplicity of each appearance. Note that by the previous paragraph, n_{k},n_{k}^{\prime\prime} are uniquely determined by (P^{\prime})_{[1,x]} and not by the choice of (P^{\prime})_{[x+1,p]} . Then we have kn_{k}=n_{k}^{\prime}+n_{k}^{\prime\prime} : be careful that in the definition of n_{k} we only count indices in [n] without the number of visits, but in defining n_{k}^{\prime} and n_{k}^{\prime\prime} we count each single visit, and thus there is an overall multiplicity k for each index in \mathcal{P}_{k} . For the known path (P^{\prime})_{[1,x]} we claim the number of possible choices for (P^{\prime})_{[x+1,p]} is at most \prod_{k=2}^{p}k^{n_{k}^{\prime\prime}} . This claim is clearly true for x=p-2 , and when the claim is true for x , it is not hard to prove it is true for x-1 by determining the possible next vertex once P^{\prime}_{x-1} is chosen, see the next paragraph: Indeed, if we use n_{k}^{\prime}(x) and n_{k}^{\prime\prime}(x) to denote the numbers n_{k}^{\prime},n_{k}^{\prime\prime} with respect to P^{\prime}_{[1,x]} , then assume that we are given (P^{\prime})_{[1,x-1]} , and the last vertex P^{\prime}_{x-1}\in\mathcal{P}_{k_{0}} for some k_{0} , then there are at most k_{0} choices for the vertex P^{\prime}_{x} , and, for each admissible choice of P_{x}^{\prime} (to be explained later), we must have n_{l}^{\prime\prime}(x)=n_{l}^{\prime\prime}(x-1) for all l\neq k_{0} and n_{k_{0}}^{\prime\prime}(x)=n_{k_{0}}^{\prime\prime}(x-1)-1 . Then by indiction hypothesis, the contribution of (P^{\prime})_{[x+1,p]} for each fixed admissible P_{x}^{\prime} is at most \prod_{k=2}^{p}k^{n_{k}^{\prime\prime}(x-1)-\mathbf{1}_{k=k_{0}}} . Multiplying by k_{0} verifies the indiction hypothesis for x-1 . Then we inductively prove this upper bound for the whole path P^{\prime} , since when x=0 we have n_{k}^{\prime\prime}=kn_{k} . Finally, we explain what admissible means in the previous paragraph. Although for a given P^{\prime}_{x-1} we may have at most k_{0} possible choices of P_{x}^{\prime} , not all of them will make a non-vanishing contribution to the contribution: we have to make sure the constraint on complex Ginibre matrices is satisfied, so that the edges of P^{\prime} should be an exact repetition of the edges of P . As such, we only consider those P_{x}^{\prime} such that the remaining paths can be constructed to satisfy this condition, and thus we can check that n_{l}^{\prime\prime}(x)=n_{l}(x)-1_{l=k_{0}} for each such choice of P_{x}^{\prime} . Combining all the upper bounds. For each choice of n_{1},n_{2},n_{3},\cdots n_{p} the total contribution to \mathbb{E}[\operatorname{tr}(A^{p}(A^{*})^{p}] by subpaths with free index i_{0} and first half part P has index n_{0},\cdots,n_{p} is bounded by (2.2) n\frac{1}{n^{p}}\frac{n!}{n_{0}!n_{1}!\cdots n_{p}!}\frac{p!}{\prod_{k=2}^{p}(k!)^{n_{k}}}\prod_{k=2}^{p}k^{kn_{k}}\prod_{k=2}^{p}(\text{const}\cdot k)^{kn_{k}}. The construction here is highly reminiscent of [ 50 ] in the Wigner case. The leading factor n is the choice of i_{0}\in[n] . The factor \frac{n!}{(n_{0}!\cdots n_{p}!)} arises from dividing n integers into subsets of sizes n_{0},\cdots,n_{p} . The factor \frac{p!}{\prod_{k=2}^{p}(k!)^{n_{k}}} is the number of ways to write down all such paths P of length p with fixed n_{0},\cdots,n_{p} and fixed vertex groups that appear in P : indeed we have p!/\prod_{k=1}^{p}(kn_{k})! ways to divide the path length p into subsets of size kn_{k} , k=1,\cdots,p , and we have (kn_{k})!/(k!)^{n_{k}} ways to write down entries in each class P_{k} . The factor k^{kn_{k}} is explained in the above paragraph. Finally, the last exponential factor (\text{const}\cdot k)^{kn_{k}} bounds the subGaussian moments from paths visited multiple times, by assumption ( 1.9 ). Indeed the estimate ( 2.2 ) is very loose and involves a lot of overcounting, but it is good enough in the sub-Gaussian case. We will refine them in Theorem 2.2 for the sub-exponential case. Upper bound estimate for the summation. Using \frac{n!}{n^{p}n_{0}!}\leq\frac{n(n-1)\cdots(n-n_{0}+1)}{n^{p}}\leq n^{n-n_{0}-p}=n^{-\sum_{k=2}^{p}(k-1)n_{k}} , using also p!\leq(n_{1})!p^{p-n_{1}} and p-n_{1}=\sum_{k\geq 2}kn_{k} , we can bound the right hand side of ( 2.2 ) by \displaystyle n\cdot n^{-\sum_{k\geq 2}(k-1)n_{k}}\frac{1}{n_{2}!\cdots n_{p}!}\frac{p^{\sum_{k\geq 2}kn_{k}}}{\prod_{k=2}^{s}(ke^{-1})^{kn_{k}}}\prod_{k=2}^{p}(2\text{const}\cdot k^{2})^{kn_{k}} \displaystyle\leq n\prod_{k=2}^{p}\frac{1}{n_{k}!}\left[\frac{(2e\cdot\text{const}\cdot k\cdot p)^{k}}{n^{k-1}}\right]^{n_{k}}. Taking the summation over all 0<\sum_{k\geq 2}kn_{k}\leq p , we see that the total sum is bounded by n\left[\exp\left(\sum_{k=2}^{p}\frac{(2e\cdot\text{const}\cdot k\cdot p)^{k}}{n^{k-1}}\right)-1\right]. For any p\ll n^{\frac{1}{2}} we have \begin{aligned} \sum_{k=2}^{p}\frac{(kp)^{k}}{n^{k-1}}&=\sum_{k=0}^{p+2}\frac{((k+2)p)^{k+2}}{n^{k+1}}\leq\frac{p^{2}}{n}(4+\sum_{k=1}^{p+2}\frac{(k+2)^{2}((k+2)p)^{k}}{n^{k}})\\ &\leq\frac{p^{2}}{n}(4+\sum_{k=1}^{p+2}(\frac{\text{const}\cdot p^{2}}{n})^{k})=\frac{p^{2}}{n}\cdot(3+\frac{1}{1-\text{const}\cdot p^{2}/n})=o(1),\end{aligned}, where for the first inequality in the second line we use k\leq p+2 and \log_{k}k+2\leq 2 . Thus we verified the contribution from summations with \sum_{k\geq 2}kn_{k}\geq 1 is negligible. The last computation highlights why p\sim\sqrt{n} is the threshold value for the proof. ∎ Exactly the same limit holds in the sub-exponential case with a symmetric law. Theorem 2.2 . Let X satisfy the assumptions in Definition 1.2 , and we assume further that the distribution of x_{ij} is symmetric. We assume V=\frac{1}{n}\mathbf{1}\mathbf{1}^{t} . Then whenever p\ll\sqrt{n} , \mathbb{E}\left[\operatorname{Tr}(A^{p}(A^{*})^{p})\right]=n(1+o(1)). We can also find constants C_{0},C_{1}>0 depending only on the constant in the sub-exponential moments x_{ij} ( 1.10 ) such that whenever p^{2}\leq C_{0}n , we have \mathbb{E}\left[\operatorname{Tr}(A^{p}(A^{*})^{p})\right]\leq C_{1}n. Proof. We follow most parts of the proof of Lemma 2.1 , but now x_{ij} are not rotationally symmetric. We do still assume x_{ij} has a symmetric distribution, so that (2.3) \mathbb{E}[x_{ij}^{m}\overline{x}_{ij}^{n}]\neq 0\text{ only if }m+n\text{ is even}. Consider a typical term (we use a different parametrization from Lemma 2.1 ) (2.4) x_{i_{0}i_{1}}x_{i_{1}i_{2}}\cdots x_{i_{p-1}i_{p}}\bar{x}_{i_{p+1}i_{p}}\cdots\bar{x}_{i_{0}i_{2p-1}} in the expansion \operatorname{Tr}(A^{p}(A^{*})^{p}) with free indices i_{0},\cdots,i_{2p-1} to be summed over [n]^{2p} . In this proof, we call the first half of the path associated to the product in ( 2.4 ) to be the subset with indices i_{0},i_{1},\cdots,i_{p} and we call the second half of the path to be the subset with indices i_{p+1},\cdots,i_{2p-1},i_{0} . Classifying each visit by the parity of visit times. We make labeling construction similar to the first step of the proof of Lemma 2.1 (but instead of labeling only the first half of the visit, we label the visit of the whole path with a counting mod 2). We say that the index i_{t} , 1\leq t\leq p is an odd index if there are an even number of terms in ( 2.4 ) to the left of x_{i_{t-1}i_{t}} that equals x_{i_{t-1}i_{t}} . We say an index i_{t} , p+1\leq t\leq 2p-1 is an odd index if there are an even number of terms to the left of \bar{x}_{i_{t}i_{t-1}} that equals x_{i_{t}i_{t-1}} or \bar{x}_{i_{t}i_{t-1}} . Here we use x and \bar{x} as abstract variables rather than the value they may take. This definition is stated to count the number of times a directed edge i_{t-1}\mapsto i_{t} appears in the generated path ( 2.4 ) before and until instance i_{t} . Likewise, we say i_{t} , 1\leq t\leq p (resp. p+1\leq t\leq 2p-1 ) is an even index if an odd number of terms to the left of x_{i_{t-1}i_{t}} (resp. \bar{x}_{i_{t}i_{t-1}} ) equals x_{i_{t-1}i_{t}} (resp. equals x_{i_{t}i_{t-1}} or \bar{x}_{i_{t}i_{t-1}} ). Evidently, if i_{1},\cdots,i_{t} are mutually distinct up to time t , then i_{t} is an odd element. Finally, we say the last instance i_{0} in the path expansion ( 2.4 ) is odd if to the left of the term \bar{x}_{i_{0}i_{2p-1}} there are an even number of terms that equal \bar{x}_{i_{0}i_{2p-1}} or x_{i_{0}i_{2p-1}} , and we say i_{0} is even otherwise. This definition of odd and even index is very similar to that in [ 50 ] , Definition 1 and 2 but with the crucial difference that we consider directed edges (as the entries are i.i.d.) whereas [ 50 ] considers undirected edge: this leads to an overall difference of a factor of 2. For this term ( 2.4 ) to have nonzero expectation, each term x_{i_{s}i_{s+1}} must be coupled with x_{i_{s}i_{s+1}} or its complex conjugate, and the total number that x_{i_{s}i_{s+1}} and its conjugate appears must be even, due to ( 2.3 ). Thus the directed path generated by ( 2.4 ) must be an even closed path, and the last appearance of i_{0} in ( 2.4 ) must be an even index. Altogether, there are p odd indices and p even indices among i_{0},\cdots,i_{2p-1} (we do not consider the first appearance of i_{0} in ( 2.4 )). We can reconstruct an even closed path as follows. Step 1: Assignment of vertices of the path with the correct multiplicity (parts of the path with odd visit times) . We choose p indices from [n] (with repetition) such that n_{1} of them appears once (we denote this set by \mathcal{P}_{1} ), n_{2} of them appears twice (denoted by \mathcal{P}_{2} ), n_{k} of them appears k times (denoted by \mathcal{P}_{k} ), etc. Then \sum_{i=0}^{p}n_{i}=n and \sum_{i=1}^{p}in_{i}=p . Then we give an ordering \mathcal{L} of \cup_{i\geq 1}i\mathcal{P}_{i} to decide the order they appear in [p] , where we use the notation i\mathcal{P}_{i} to denote the multiset in which every element of \mathcal{P}_{i} appears i times. These p vertices are candidates for the odd instances in the path ( 2.4 ) , with overall combinatorial factor n\frac{n!}{n_{0}!n_{1}!\cdots n_{p}!}\frac{p!}{\prod_{k=2}^{p}(k!)^{n_{k}}}. Step 2: inserting even paths to the already constructed odd paths I: the first half . In the previous step, we have essentially constructed half of the path, having the edges that are visited an odd number of times. The next step is to insert new edges in the path that correspond to visits a number of times. We introduce an algorithm to insert these edges of the visit at even number of times. Before proceeding, we highlight how this proof mirrors the proof of Lemma 2.1 : here we introduce subsets \mathcal{P}_{1},\mathcal{P}_{2},\cdots : These subsets play a similar role as the subsets introduced in the proof of Lemma 2.1 with the same notation. The remaining steps are to insert the edges that are visited at the even number of times to the already constructed part, and to show that this leads to an overall combinatorial factor of at most \prod_{k\geq 2}(\text{const}\cdot k)^{kn_{k}} . We have to design a much more involved algorithm to insert in the edges visited at the even number instances and verify this combinatorial upper bound: this algorithm is much more sophisticated than the one in Lemma 2.1 and is presented as follows. By Step 1, we first select i_{1},\cdots,i_{p} to be the vertices selected in Step 1 in the order specified in Step 1, and we assign that all the index i_{1},\cdots,i_{p} are odd index. Then we start a scanning and insertion procedure as follows. We start to scan from the second index i_{1} which must be odd and we do nothing with it. (a) Suppose we have scanned the path up to index i_{t} (1\leq tp will not happen since \bar{x}_{i_{l}i_{i-1}} does not pair with \bar{x}_{i_{t}i_{t-1}} by independence, unless i_{t-1}=i_{l-1} . The latter case corresponds to a self-loop which is constructed in Step 2. In case (a2) then i_{t} is an odd index, and we do nothing but move on to scan the next index in the path (there must be un-scanned elements remaining). Then if (b) i_{t}\in\cup_{i\geq 2}\mathcal{P}_{i} , say for example i_{t}\in\mathcal{P}_{k} , then we can either assign i_{t+1} to be odd or even. If(b1) we assign i_{t+1} to be odd (this must be the case if i_{t} is not the last index in the current path), then we do no insertion and simply move on to i_{t+1} . Or, (b2) we assign i_{t+1} to be even, then \bar{x}_{i_{t+1}i_{t}} is a repetition of elements appearing before it, then there are k choices of i_{t+1} , ad we insert this value to the path with label i_{t+1} and increase the label of indices after i_{t} . Then we proceed to scan the next element. In Step 2 and 3 we have designed two scanning and insertion procedures, and both steps lead to additional combinatorial factors. The important take-away of our construction is that the scanning procedure in Step 2 amounts to the construction of repeated loops that are either both in the first, or second, half of the path whereas the scanning procedure in Step 3 amounts to the pairings of two elements with one in the first half, and the other in the second half, of the path. We have assigned the even vertices in \cup_{k\geq 2}\mathcal{P}_{k} a label \{0,1\} to determine whether they are used in Step 2 or Step 3, and regardless of this label, every even vertex in \cup_{k\geq 2}\mathcal{P}_{k} contribute a factor of 2k by the number of choice for possible returns. Combining all the combinatorial factors. Combining Steps 2 and 3, we have introduced the following combinatorial factor: at each odd instance in \cup_{k\geq 2}\mathcal{P}_{k} , we have two choices to determine whether the next index is odd or even. For an even index there are k choices of return (and there are kn_{k} vertices in \mathcal{P}_{k} with even index in the path) while for an odd index there is no additional choice. Thus the total combinatorial factor is \prod_{k\geq 2}(8k)^{kn_{k}}. Explanation of this combinatorial factor. We now explain how this \prod_{k\geq 2}(\text{const}\cdot k)^{kn_{k}} factor arises: the reasoning here is much the same as the paragraph “ proving the upper bound for the number of choices for the second half of the path” in the proof of Lemma 2.1 , so we only give a sketch here. The essential reason is that not all the methods of the choice of the next vertex starting from a vertex in \cup_{k\geq 2}\mathcal{P}_{k} is allowed: only those choices that obey the overall constraint that each such edges appear 2k times is contributing to the expectation. Then one can prove by induction, as in Lemma 2.1 , that we get this quantity \prod_{k\geq 2}(8k)^{kn_{k}} for the possible ways to insert the even edges. Now we bound \mathbb{E}[\operatorname{Tr}(A^{p}(A^{*})^{p})] via this path reconstruction procedure. Again the dominant contribution comes from the case where n_{1}=p and n_{k}=0 for any k\geq 2 , and the contribution of this term is as in ( 2.1 ). For general n_{1},n_{2},\cdots n_{k} the contribution is bounded by (2.5) n\frac{1}{n^{p}}\frac{n!}{n_{0}!n_{1}!\cdots n_{p}!}\frac{p!}{\prod_{k=2}^{p}(k!)^{n_{k}}}\prod_{k=2}^{p}(2k)^{kn_{k}}\prod_{k=2}^{s}(\text{const}\cdot k)^{kn_{k}}\cdot 4^{\sum_{k\geq 2}kn_{k}}. To explain each term, we first divide n into subsets of size n_{1},\cdots,n_{p} , and choose the number of ways in which elements appear in the first half of this product term up to index p . At this point we assume all the indices thus appeared up to time p are odd indices, but we have freedom to switch indices in \mathcal{P}_{2},\mathcal{P}_{3},\cdots to even indices: this leads to the factor 4^{\sum_{k\geq 2}kn_{k}}. The term (2k)^{kn_{k}} again represents the choice of the next index if the current index lies in \mathcal{P}_{t},t\geq 2 and is an even index. The term (\text{const}\cdot k)^{kn_{k}} are the sub-Gaussian moments. Sub-exponential entries in place of subgaussian entries. An important observation is that ( 2.5 ) is true even if x_{ij} has only sub-exponential moments ( 1.10 ): this is an observation made already in [ 51 ] , Lemma 1. The reason is that the factor k^{kn_{k}} comes from choosing the vertices of return in every visit to a point in \cup_{k\geq 2}\mathcal{P}_{k} , and if an edge e=(e_{i},e_{j}) is chosen for return for \ell\geq 2 times, this would contribute to the sub-exponential moment of x_{ij} by a factor (\text{const}\cdot\ell)^{2\ell} , but in this case we need to divide by a factor \ell! as the choice of a returning edge from these \ell identical edges are identical. (In other words, the number of possible returns and the factor in the sub-exponential moments cannot be too large simultaneously). Then the same reasoning as in [ 51 ] , Lemma 1 shows ( 2.2 ) is true under the weaker sub-exponential moment condition ( 1.10 ), which we assume henceforth. More concretely, we are enumerating over all even closed paths \mathcal{P} of length 2p . Let (i,j) be any directed edge in \mathcal{P} , we denote by 2l((i,j)) the number of occurrence of this directed edge in \mathcal{P} , then under the sub-exponential moment condition we need to bound, accounting for the \ell! overcounting: \prod_{(i,j)}^{\prime}(\text{const}\cdot l(i,j))^{2l(i,j)}\frac{1}{l((i,j))!}\text{ in place of }\prod_{(i,j)}^{\prime}(\text{const}\cdot l(i,j))^{l(i,j)} where \prod^{\prime} is the product over all edges with l(i,j)>1 , and the right hand side is the sub-Gaussian bound without dividing the overcounting. As the left hand side is bounded by the right by a suitable choice of constants, we see that switching to sub-exponential tails does not affect the upper bound ( 2.5 ). Final bound. Taking the summation over all indices such that \sum_{k\geq 2}kn_{k}>0 , we get (as in the proof of Lemma 2.1 , with only change of constants) that the sum is bounded by (2.6) n\left[\exp\left(\sum_{k=2}^{p}\frac{(32e\cdot\text{const}\cdot k\cdot p)^{k}}{n^{k-1}}\right)-1\right], which is bounded by n\frac{p^{2}}{n}\frac{\text{const}}{1-\text{const}\cdot p^{2}/n} and thus is n\cdot O(1) whenever p^{2}\leq C_{0}n for some constant C_{0} depending on the sub-exponential moments of x_{ij} , and is o(n) for p\ll n^{\frac{1}{2}}. ∎ Next we show that we can remove the assumption that x_{ij} has a symmetric distribution in Theorem 2.2 . Theorem 2.3 . Theorem 2.2 is valid without assuming that x_{ij} has a symmetric distribution. The proof of Theorem 2.3 follows somewhat standard arguments, but is too lengthy to be presented here so we defer the proof to Appendix C . The idea is to show that contributions to the expectation from non-even paths can be bounded via considering adding odd edges to even paths, and we show such even paths with added odd edges has negligible contribution. Motivated by [ 45 ] in the Wigner case, the key component of the proof is a method to construct non-even paths from even paths. 2.2. Moment estimate II In this section we outline necessary moment computations for the proof of Theorem 1.1 . In contrast to Theorem 2.2 considering moments p\ll\sqrt{n} , we now work with much higher moments p\sim n and new combinatorial ingredients are necessary. This type of results was first obtained for Wigner matrices in [ 28 ] via refined combinatorial techniques. In [ 28 ] , equation (I.5.6) they prove that Theorem 2.4 . Let W_{n}=(w_{ij}) be an n\times n Wigner matrix with entry distribution satisfying assumptions (1),(2) of Theorem 1.1 . In the complex-valued case we assume further that \mathbb{E}[w_{ij}^{2}]=0 for each i\neq j . Then we can find C>0 such that for any k\in\mathbb{N}_{+} , \mathbb{E}\left[\operatorname{Tr}\left(\frac{W_{n}}{2\sqrt{n-2}}\right)^{k}\right]\leq C\frac{n}{k\sqrt{k}}e^{C\frac{k^{3}}{n^{2}}}. We note that for Gaussian random matrices, one can use the theory of Gaussian processes to derive a similar bound as in Theorem 2.4 without too much difficulty; see [ 10 ] , Lemma 2.2. In the non-Hermitian setting, there are no results similar to Theorem 2.4 concerning traces of high powers, to the author’s best knowledge. For Gaussian matrices (the complex/real Ginibre ensemble), the situation does not appear to be simpler, as the spectral radius of a Gaussian matrix is not a Gaussian process (in contrast to the spectral norm) and the considered quantity ( 2.7 ) does not admit a closed form expression in terms of integrable formulas of real/complex Ginibre ensemble. We will derive the necessary moment bounds by ourselves, adapting the combinatorial tools in [ 28 ] to the non-Hermitian setting. The main result is Theorem 2.5 . Let G_{n}=(\frac{1}{\sqrt{n}}g_{ij}) be an n\times n matrix with independent entries, where g_{ij} are i.i.d. random variables satisfying assumptions (1),(2),(3) of Theorem 1.1 . Then we can find C>0 depending only on the constant in equation ( 1.9 ) such that for any k\in\mathbb{N}_{+},k\leq n (2.7) \mathbb{E}[\operatorname{Tr}G_{n}^{k}(G_{n}^{*})^{k}]\leq Ck^{2}n^{6}e^{C[\frac{k^{3/2}}{n^{1/2}}+\frac{k^{2}}{n}]}. The leading factor n^{6} is possibly unnecessary, but this does not lead to any suboptimality in the proof of Theorem 1.1 . This is because we will set k\gg\log n , so that n^{\frac{6}{k}}\to 1. 2.2.1. Recap of combinatorial terminologies Our proof of Theorem 2.5 uses many combinatorial terminologies from [ 28 ] . We outline these combinatorial constructions. In our combinatorial construction we differentiate between two cases: the real case \beta=1 and the complex case \beta=2 . The estimates are slightly different in both cases. Fix n\in\mathbb{N}_{+} . Consider a path p_{2k}=u_{0}u_{1}\cdots u_{2k} on \{1,2,\cdots,n\} satisfying (1) u_{j}\neq u_{j-1} (no self-loops) for each j ; (2) u_{j}\neq u_{j-2} (non-backtracking) for each j ; (3) u_{0}=u_{2k} (closed path); (4) (a) In the real case for any u\neq v\in[n] , the number of j\in[2k] such that u_{j}=u,u_{j+1}=v and the number of j\in[2k] such that u_{j}=v,u_{j+1}=u are equal mod 2. (b) In the complex case for any u\neq v , the number of j such that u_{j}=u,u_{j+1}=v equals the number of j such that u_{j}=v,u_{j+1}=u . Definition 2.6 . (Directed multigraphs and matching) From this path p_{2k} we construct a directed multigraph G=(V,E_{\text{dir}}) where V\subset\{1,\cdots,n\} consists of all vertices u_{j},0\leq j\leq 2k , and E_{\text{dir}} is the collection of all directed edges u_{j-1}\to u_{j} (counting multiplicity). We define a matching of p_{2k} as an involution of \{0,1,\cdots,2k-1\} that satisfies (i) in the real case, an edge (u,v) is matched to (u,v) or (v,u) ; or (ii) in the complex case, each edge (u,v) is matched to (v,u) . In Definition 2.6 , we use the multigraph G to encode the path p_{2k} . To have a heuristic understanding of our definition of matchings (a.k.a., pairings), simply note that these pairings will arise when we apply Wick formula for Gaussian matrices: the number of matchings is exactly the combinatorial factor of the number of pairings showing up in Wick formula. We call a path p_{2k} with a matching as a matched path. To effectively estimate the number of matched paths, in [ 28 ] the authors introduced an algorithm of combinatorial reduction, to reduce a matched path to the following simpler object: Definition 2.7 . [ 28 ] For \beta=1,2 , we define a diagram of class \beta as an undirected multigraph \bar{G}=(\bar{V},\bar{E}) combined with a circuit \bar{p}=\bar{u}_{0}\bar{u}_{1}\cdots\bar{u}_{0} on \bar{G} satisfying that (1) \bar{p} is not backtracking, meaning that \bar{u}_{j}\neq\bar{u}_{j-2} for each j . (2) For any edge (\bar{u},\bar{v})\in\bar{E} , in the real case the number of j with \bar{u}_{j}=\bar{u},\bar{u}_{j+1}=\bar{v} plus the number of j with \bar{u}_{j}=\bar{v},\bar{u}_{j+1}=\bar{u} equals 2; and in the complex case both quantities are one. (3) The degree of \bar{u}_{0} in \bar{G} is 1 and the degree of any other vertices is 3 . Finally, we add a weight function \bar{w}:\bar{E}\to\{-1,0,1,2,\cdots\} defined in the graph \bar{G} . As noted in [ 52 ] , Remark 2.4, \bar{G} is a multigraph where the coinciding edges are distinguished, so the circuit is not uniquely defined by the vertices through which it passes. The algorithm of reducing matched paths to diagrams is as follows: Proposition 2.8 . ( [ 28 ] , Claim II.1.4) There exists a mapping from the set of matched paths p_{2k} to a diagram (\bar{G},\bar{p},\bar{w}) . By [ 28 ] , for each weighted diagram (\bar{G},\bar{p},\bar{w}) there are no more than n^{|\bar{V}|+\sum_{\bar{e}}\bar{w}(\bar{e})} matched paths that are mapped to this weighted diagram (\bar{G},\bar{p},\bar{w}) . The final step is to find an upper bound for the number of diagrams. In [ 28 ] , Section II.2, an algorithm was designed for this purpose: Proposition 2.9 . ( [ 28 ] , Section II.2) There exist an automaton generating all possible diagrams. In the complex case \beta=2 , each diagram is generated in s steps for some s\in\mathbb{N} , and for a diagram generated in s steps the diagram has |\bar{E}|=3s-1 edges and |\bar{V}|=2s vertices. In the real case \beta=1 , each diagram can be generated in some s\in\mathbb{N} steps with |\bar{E}|=3s-1 edges and |\bar{V}|=2s vertices. In [ 28 ] , The number of diagrams with parameter \beta\in\{1,2\} and generated in s steps has cardinality D_{\beta}(s) which satisfy, for some universal constant C>0 , (2.8) (s/C)^{s}\leq D_{\beta}(s)\leq(Cs)^{s}. 2.2.2. An illustrative explanation for the proof of Theorem 2.5 We outline how the proof of Theorem 2.4 from [ 28 ] can be adapted to the proof of Theorem 2.5 , at a non-rigorous level. Only the main ideas are highlighted here and the details are presented later. The key estimate in the proof of Theorem 2.4 is in [ 28 ] , Theorem I.5.3, which states that: Let U_{n} denote the n -th Chebyshev polynomial U_{n}(\cos\theta)=\frac{\sin((n+1)\theta)}{\sin\theta} , then \mathbb{E}[\operatorname{Tr}U_{k}(\frac{W_{n}}{2\sqrt{n-2}})]\leq Ck\exp(Ck^{3/2}/n^{1/2}). It can be shown that the composition by Chebyshev polynomial essentially amounts to counting only the non-backtracking paths in the trace expansion of (W_{n})^{k} . Also note that U_{k}(x)\sim(2x)^{k} when x is large, which cancels a factor 2 in the denominator of \frac{W_{n}}{2\sqrt{n-2}} . In the non-Hermitian case, because the non-backtracking condition on path p_{2k} is automatically imposed on the expansion \operatorname{Tr}(G_{n}^{k}(G_{n}^{*})^{k}) thanks to independence of entries of G_{n} , one expects the same computation should also generalize. There do exist paths that are backtracking and contribute to the expectation, but the contribution of these backtracking paths will be negligible compared to the non-backtracking paths, as we shall prove later. 2.2.3. The proof of of Theorem 2.5 Proof of Theorem 2.5 , the real case \beta=1 . Fix i,j\in[n] . Let P be a path from i to j of length k , that is, the path P can be denoted by P:i=p_{0}\mapsto p_{1}\mapsto\cdots\mapsto p_{k}=j . For this path P we can define its weight w(P) by w(P)=\prod_{t=0}^{k-1}g_{p_{t}p_{t+1}}, and we denote by \bar{w}(P) the complex conjugate of w(P) . We can expand the trace via \operatorname{Tr}\left(G_{n}^{k}(G_{n}^{*})^{k}\right)=\sum_{i,j}\sum_{P_{1},P_{2}:i\mapsto j}w(P_{1})\bar{w}(P_{2}), where P_{1},P_{2} are directed paths from i to j of length k . Step 1: Reduction to path counting. We can construct from the paths (P_{1},P_{2}) a path P of length 2k+2 as follows: we start from i , then follow P_{1} to vertex j , then take the edge (j\mapsto i) , then follow P_{2} to get to vertex j again, and finally return to vertex i via edge (j,i) . For fixed i,j this defines a unique mapping from pairs of paths (P_{1},P_{2}) from i to j of length k , and a cycle of length 2k+2 rooted at edge (j,i) (we say the path of length 2k+2 is rooted at (j,i) if the k+1 -th and the 2k+2 -th step of the path both take the edge j\to i ). Let \mathcal{P}_{(j,i)}(2k+2) denote the set of even rooted paths of length 2k+2 rooted at (j,i) , where a rooted path is called an even rooted path if each directed edge has an even multiplicity. Since g_{ij} are symmetric random variables, to get a nonzero expectation for \mathbb{E}[w(P_{1})\bar{w}(P_{2})] , the resulting path P of length 2k+2 must have each edge an even multiplicity. Then (2.9) \mathbb{E}\left[\operatorname{Tr}\left(G_{n}^{k}(G_{n}^{*})^{k}\right)\right]=\sum_{i,j}\sum_{P\in\mathcal{P}_{(i,j)}(2k+2)}\frac{1}{n^{k}}\mathbb{E}[W_{r}(P)], where for an even rooted path P=(p_{0},p_{1},\cdots,p_{2k+2}) of length 2k+2 and root (j,i), we define W_{r}(P)=\prod_{t=0}^{k-1}g_{p_{t}p_{t+1}}\cdot\prod_{t=k+1}^{2k}\bar{g}_{p_{t}p_{t+1}}, note that we have taken complex conjugates in the second part of the path and we have omitted elements g_{p_{k}p_{k+1}} and g_{p_{2k+1}p_{2k+2}} in the product defining W_{r}(P) . We take a decomposition of \mathcal{P}_{(i,j)}(2k+2) into two subsets \mathcal{P}_{(i,j)}(2k+2)=\mathcal{P}^{1}_{(i,j)}(2k+2)\cup\mathcal{P}^{2}_{(i,j)}(2k+2) where \mathcal{P}^{1}_{(i,j)}(2k+2) consists of paths that are non-backtracking and has no edges (e,e) in it (so that p_{i}\neq p_{i+1},p_{i+2} for each i=0,1,\cdots,2k .) Let \mathcal{P}^{2}_{(i,j)}(2k+2) consist of other paths that do not satisfy these conditions. The collection of paths in \mathcal{P}^{1}_{(i,j)}(2k+2) make the primary contribution to the expectation in ( 2.9 ), which we now estimate. Step 2: Non-backtracking paths via Wick formula in the Gaussian case. First we assume that g_{ij} are standard real Gaussian variables, then by Wick formula, (2.10) \sum_{P\in\mathcal{P}^{1}_{(i,j)}(2k+2)}\mathbb{E}[W_{r}(P)]\leq\Omega_{(i,j)}(2k+2), where \Omega_{(i,j)}(2k+2) is the number of doubled matched paths (a path whose each directed edge has even multiplicity and where a matching has been assigned to this path, see Definition 2.6 ) P of length 2k+2 , containing the edge (j,i) , satisfying (a) p_{i}\neq p_{i+1} for each i, (b) p_{i}\neq p_{i+2} for each i , (c) p_{0}=p_{2k+2} . and (d) are matched in the following sense: each edge (u,v) is matched either to (u,v) or to (v,u) . Since the entries g_{ij} are symmetric, for the expectation to be non-vanishing we require that (e) for any u,v , the number of times each edge (u,v) and (v,u) appear in P are equal mod 2. These five constraints are the same as the definition of matched paths in Definition 2.6 . We give more explanation to the validity of ( 2.10 ) for why it corresponds to paths with a matching: by Wick formula ( [ 43 ] , Theorem 22.3 for the real case and Remark 22.5 for the complex case) the expectation of W_{r}(P) is given by numbers of pairings without pairing the roots: the (k,k+1) and (2k+1,2k+2) -th edge of P . These two edges j\to i can be further paired together resulting in the counting \Omega_{(i,j)}(2k+2) : note that for this quantity \Omega_{(i,j)}(2k+2) we not only count the number of paths, but also count the number of possible matchings associated to this path. This gives rise to Wick formula computations. Step 3: Counting non-backtracking paths. In the real case \beta=1 , we can estimate the quantity \Omega_{(i,j)}(2k) for each k\in\mathbb{N} just as in [ 28 ] . 2 2 2 For future use, the fact that such path should go through (j,i) is not very important and we shall ignore this restriction: this leads to an overcounting of at most n^{2} . By Proposition 2.8 and 2.9 , each such matched path is mapped to a weighted diagram (\bar{V},\bar{E},\bar{p}) in s steps for some 1\leq s\leq k , with |\bar{V}|=2s , |\bar{E}|=3s-1 , and with a set of weight functions \bar{w}(e) satisfying that \sum_{\bar{e}}\bar{w}(\bar{e})=k-|\bar{E}|=k-3s+1 . The number of diagrams (\bar{V},\bar{E},\bar{p}) generated in s steps is denoted by D_{\beta}(s) , which satisfies the upper bound ( 2.8 ). The number of ways to assign the weights \bar{w} on this path is \binom{k+3s-2}{3s-2} and the number of ways to choose vertices is n^{2s+k-3s+1}=n^{k-s+1} . Therefore (2.11) \displaystyle\Omega_{(i,j)}(2k) \displaystyle\leq\sum_{1\leq s\leq k}D_{\beta}(s)n^{k-s+1}\frac{(k+3s-2)^{3s-2}}{(3s-2)!} \displaystyle\leq\sum_{1\leq s\leq k}C^{s}s^{s}n^{k-s+1}\frac{(k+3s-2)^{3s-2}}{(3s-2)!} \displaystyle\leq kn^{k}\sum_{s\geq 1}\frac{(C_{1}k^{3}/n)^{s-1}}{(2(s-1))!}\leq kn^{k}\exp(C_{2}k^{3/2}/n^{1/2}), where C_{1},C_{2}>0 are some universal constants. Plugging in this upper bound for \Omega_{(i,j)}(2k) into ( 2.10 ) and summing over i,j , we get an upper bound for the trace moment with a magnitude almost as large as the one claimed in Theorem 2.5 . We are now left with the task to show that the contribution from the remaining paths that do not belong to \Omega_{(i,j)}(2k+2) , has at most the same magnitude. Before proceeding with this task, we first show that the above computation works also for non-Gaussian distribution with only a minor modification: Step 3.1: non-Gaussian distribution. The same estimate also holds (with a different constant C_{2}>0 ) when g_{ij} are general sub-Gaussian random variables satisfying assumptions (1),(2),(3) in Theorem 1.1 . Here we follow the ideas of [ 28 ] , Section III.2. Instead of using Wick formula we use the sub-Gaussian moment bound ( 1.9 ) which leads to a product of (\text{const}\cdot k)^{k} terms, and these terms are absorbed in the s^{s} factor. More precisely, for a constant C>0 we consider the quantity \Omega_{(i,j)}^{C}(2k):=\sum_{P\in\Omega_{(i,j)}(2k)}C^{k-|E(P)|} where |E(P)| is the number of distinct edges in P and we are summing over matched paths P . Using the sub-Gaussian moment condition and elementary combinatorics, we can find some C_{3}>0 depending on the sub-Gaussian moment in ( 1.9 ) such that \sum_{P\in\mathcal{P}^{1}_{(i,j)}(2k+2)}\mathbb{E}[W_{r}(P)]\leq\Omega_{(i,j)}^{C_{3}}(2k+2). To derive this inequality we do not use the Wick formula, but directly evaluate the expectation counting the multiplicity of each entry g_{ij} . There is a (k/c)^{k} factor coming from the sub-Gaussian moment ( 1.9 ) but this factor is absorbed in the number of pairings, modulo a constant left out from each repeated edge. The number of repeated edges for a path P of length k is k-|E(P)| , hence the computation. We now let b be the number of edges \bar{e} such that \bar{w}(\bar{e})=-1 , where we recall \bar{w} is the weight function defined on a diagram of class \beta=1 generated from P . Then for a path P of length 2k+2, |k+1-E(P)|\leq b . Therefore \displaystyle\sum_{P\in\mathcal{P}^{1}_{(i,j)}(2k+2)}\mathbb{E}[W_{r}(P)] \displaystyle\leq\sum_{1\leq s\leq k+1}D_{1}(s)n^{k-s+1}\sum_{b\geq 0}(C_{3})^{b}\binom{k+3s-2}{3s-2-b}\binom{3s-1}{b} \displaystyle\leq\sum_{1\leq s\leq k+1}C^{s-1}s^{s}n^{k+2-s}\binom{k+3s-1}{3s-2}\sum_{b\geq 0}\frac{(C_{4}s/k)^{b}}{b!} for some constant C_{4}>0 depending on C_{3} . Since \sum_{b\geq 0}\frac{(C_{4}s/k)^{b}}{b!}=O(1) , we can bound the other terms as in ( 2.11 ) and conclude that, for some C_{5}>0 depending only on the sub-Gaussian constant of g_{ij} that \sum_{P\in\mathcal{P}^{1}_{(i,j)}(2k+2)}\mathbb{E}[W_{r}(P)]\leq C_{5}(k+1)n^{k+1}\exp(C_{5}k^{3/2}/n^{1/2}). Step 4: Counting backtracking paths. The remaining task is to bound the contribution from paths not counted in Step 3 , which by definition are those that are either not backtracking or has two adjacent vertices that are equal. We will manually remove the backtracking parts and parts where adjacent indices are equal, and reduce the count of these paths to a path of shorter length. Recall that we construct, from two paths P_{1},P_{2}:i\to j of length k , a path P of length 2k+2 via first going through P_{1} , then the edge j\to i , then P_{2} , then j\to i . The path P may be backtracking, but since the entries g_{ij} are i.i.d., for \mathbb{E}[W_{r}(P)]\neq 0 , we must have that for each backtrack p_{i-1}\mapsto p_{i}\mapsto p_{i+1}=p_{i-1} , unless p_{i-1}=p_{i}=p_{i+1} , we must not match (p_{i-1},p_{i}) with (p_{i},p_{i+1}) , but we match these two directed edges with other edges in the path P . Reduction to only one type of backtracking. There are two possible cases where this backtrack will be matched with other elements of P occurring later. Case (A), we can find some j>i such that there is another backtracking p_{j-1}\mapsto p_{j}\mapsto p_{j+1}=p_{j-1} and (p_{i-1},p_{i})=(p_{j-1},p_{j}) or (p_{j},p_{j-1}) . This is the most generic case of backtracking. Case (B), we can find some j\neq k with j,k>i such that (p_{i-1},p_{i})=(p_{j-1},p_{j}) , (p_{i},p_{i+1})=(p_{k-1},p_{k}) . This case is more exotic, as we cannot simultaneously remove the two edges p_{i-1}\mapsto p_{i}\mapsto p_{i+1} and p_{j-1}\mapsto p_{j},p_{k-1}\mapsto p_{k} as the remaining path is disconnected, but we can convert case (B) into case (A) as follows. For such a path P of length 2k+2 in case (B), we identify the two vertices of the edge p_{j-1}\mapsto p_{j} and collapse this edge to one single vertex, and do the same operation to the edge p_{k-1}\mapsto p_{k} , so we get a unique closed even path \tilde{P} of length 2k-2 , with two backtracks attached to it that are matched to each other, which is case (A). Therefore, we only need to bound backtracking of class (A), from which we can bound contributions in case (B). Decomposing a backtracking path into forests. Now we bound contributions from case (A). We adapt the arguments from [ 28 ] , Section III.3. For a closed even path P of length 2k+2 not belonging to case (B), we can (for some integer m\in\mathbb{N} ) decompose P as the union of a closed even path q_{2(k+1-m)}:=\mathfrak{C}(P) with no backtracking and no self loops, a forest f_{2m}=\mathfrak{F}(P) and the remaining self-loops. By assumption of the path P not being in case (B), each leaf of f_{2m} should appear at another place on P . The contribution from q_{2(k+1-m)} is well-understood in the previous steps, and in the following we study the structure of each connected component of f_{2m} in detail. From [ 28 ] , Definition III.3.1 we define the notion of a tree diagram (abbreviated as t -diagram) to be a rooted planar binary tree. We assign a weight function \bar{w} to this t -diagram which takes values in \{-1,0,1,2,\cdots\} on each edge of the tree. By [ 28 ] , Lemma III.3.2 (which follows from elementary combinatorial counting), the cardinality D^{t}(\ell) of t -diagrams with \ell leaves is bounded by 4^{\ell} . As each leaf of f_{2m} should appear somewhere else on P , we suppose that, for some 0\leq\ell_{1}\leq\ell/2 , we have \ell_{1}\leq\ell/2 coinciding pairs of leaves and the remaining \ell-2\ell_{1} leaves coincide with some other vertices of P which are not leaves. Then we upper bound the number of ways to form a weighted t -diagram t_{m^{\prime}} for some m^{\prime}\in\mathbb{N} . The total number of trees with \ell leaves is bounded by, using k\leq n and \ell\leq k , \sum_{0\leq\ell_{1}\leq\ell/2}\binom{\ell}{2\ell_{1}}k^{\ell-2\ell_{1}}n^{2\ell_{1}}n^{m^{\prime}-2\ell}\frac{(2\ell_{1})!}{2^{\ell_{1}}\ell_{1}!}\leq n^{m^{\prime}-\ell}(C\ell)^{\ell}, where the first binomial coefficient gives the choice of coinciding pairs of leaves; the last binomial factor the number of ways to pair these coinciding leaves; the power of k is the number of ways these leaves coincide with other vertices of P , and the two powers of n are the way to choose these vertices from [n] . This t -diagram t_{m}^{\prime} with \ell leaves has 2\ell-1 edges. In order for the summation of weights on the t -diagram to not exceed 2m^{\prime} , the count of ways to assign the weight on the t -diagram is bounded by, for some universal constant C_{6}>0 , \binom{2m^{\prime}+2\ell-1+2\ell-2}{2\ell-2}\leq(C_{6}m^{\prime}/\ell)^{2\ell-2}. Finally we take the summation over \ell as follows: the number of t -diagrams t_{m^{\prime}} is at most \sum_{\ell\geq 1}(C_{6}m^{\prime}/\ell)^{2\ell-2}(C\ell)^{\ell}n^{m^{\prime}-\ell}\leq n^{m^{\prime}-1}\exp(C_{7}(m^{\prime})^{2}/n). A more careful computation as in Step 3.1 allows us to upper bound the weight coming from the forest f_{2m} , which we omit for simplicity. Total contribution from forests: summing everything up. Now we consider all the connected components of f_{2m} . Then the contributions from all t -tuples of trees of m_{i} edges each, with t\in\mathbb{N}_{+} and m_{1}+\cdots+m_{t}=m , is upper bounded by \sum_{m_{1}+\cdots+m_{t}=m}\prod_{j=1}^{t}n^{m_{j}-1}\exp(C_{7}(m_{j})^{2}/n)\leq n^{m-t}\exp(C_{7}m^{2}/n)\binom{m-1}{t-1}. Finally, the total contribution is bounded as follows: summing over t first and then over m , \sum_{1\leq t\leq m,t,m\in\mathbb{N}}n^{m-t}\binom{k+1-m+1}{t}n^{k+1-m}\binom{m-1}{t-1}\exp(C_{7}m^{2}/n)\Sigma_{1}(2(k+1-m)) where \Sigma_{1}(2(k+1-m)) is the contribution from non-backtracking paths computed in Step 3.1 . Note that for each fixed 1\leq m\leq k+1 , n^{-t}\binom{k-m+2}{t}\binom{m-1}{t-1}\leq(\frac{2km}{n})^{t}\cdot\frac{1}{t!}, which is summable over t . Then we may simply deduce that the total contribution of case (A) is bounded by (k+1)^{2}n^{k+1}\exp(C_{8}k^{2}/n+C_{8}k^{3/2}/n^{1/2}). Summing over i,j , the upper bound has the same magnitude as the one claimed in ( 2.7 ). As discussed previously, the contribution from case (B) can be bounded by that from case (A), up to a change of constant, say, for example, replacing (C\ell)^{\ell} by (2C\ell)^{\ell} . The remaining computations follow the same line. Self-loops. Finally, when there is a self-loop, then each self-loop must also appear an even number of times for us to get a non-zero expectation. Say, the self-loop repeats 2k times, then we remove the self-loops, resulting in a path with no self-loops. This leads to a loss of n^{k} free vertices to choose form for this path. The subgaussian moment generated from the self loop is (Ck)^{k} . This leads to a factor (Ck/n)^{k} to the overall contribution. It suffices to count the multiplicity of all self-loops and remove these loops. ∎ Proof of Theorem 2.5 , the complex case \beta=2 . . We essentially follow the proof in the real case, but take a different method to form a path P from P_{1},P_{2} in Step 1 . Suppose we are given two paths P_{1},P_{2}:i\mapsto j of length k each, then we form a path P of length 2k+12 via the following procedure. Select four distinct vertices T_{1},T_{2},T_{3},T_{4}\in[n] , we follow the path P_{1} until it gets to j , then follow j\mapsto T_{1}\mapsto T_{2}\mapsto j\mapsto T_{3}\mapsto T_{4}\mapsto j\mapsto T_{2}\mapsto T_{1}\mapsto j\mapsto T_{4}\mapsto T_{3}\mapsto j , and then follow path P_{2} reversed in order, from j back to i . This defines a unique map of paths: (P_{1},P_{2})\mapsto P . The matching on P is defined such that (u,v) is matched only to (v,u) but not (u,v) itself: this is consistent with the definition of \beta=2 matching in [ 28 ] and consistent with the assumption \mathbb{E}[g_{ij}^{2}]=0 . We further require that the k+1 to k+12 -th steps of P are (uniquely) matched to itself: these are the steps we just appended to the original path. Then by definition, P has no backtracking in the k+1 -th to k+12 -th steps, and by independence of entries of g_{ij} , for any possible backtracking of P of the form p_{i-1}\mapsto p_{i}\mapsto p_{i+1}=p_{i-1} , we cannot match (p_{i-1},p_{i}) with (p_{i},p_{i+1}) (unless p_{i-1}=p_{i}=p_{i+1} ) so they both have to be matched with other paths in P . Then we are back to almost the same setting as in the real case \beta=1 , only that we have a path of length 2k+12 and we use the \beta=2 automaton in [ 28 ] . We just need to enumerate all closed even paths P of length 2k+12 , matched in the \beta=2 type (so that for any two u,v\in[n] , the edge (u,v) is traveled in P the same number of times as the edge (v,u) ), and such that all backtracking parts in P are not matched to itself. The rest of the proof is the same and omitted. ∎ 3. Convergence and small deviation: the inhomogeneous case 3.1. Convergence of spectral radius under optimal sparsity In this section we prove Theorem 1.1 . The proof uses in a crucial way the moment computations in Theorem 2.5 and an idea of comparison, dating back to [ 10 ] , Proposition 2.1. Proof of Theorem 1.1 , the real case \beta=1 . For this proof we need some notations of paths and cycles from [ 10 ] . We essentially follow verbatim the steps in [ 10 ] although certain constructions are slightly different: in particular the meaning of n_{i}(\mathbf{u}) and \mathcal{S}_{2p} in the following are different from those in [ 10 ] . Given a path \mathbf{u}=(u_{1},u_{2},\cdots,u_{2p})\in[n]^{2p} of length 2p , we identify it with a cycle \mathbf{u}=(u_{1},\cdots,u_{2p},u_{1})\in[n]^{2p+1} . We denote by \mathcal{S}(\mathbf{u}) the shape of \mathbf{u} obtained by reordering the vertices via the order of first appearance. (For example, the cycle 7\mapsto 3\mapsto 5\mapsto 4\mapsto 3\mapsto 5\mapsto 4\mapsto 3\mapsto 7 has its shape 1\mapsto 2\mapsto 3\mapsto 4\mapsto 2\mapsto 3\mapsto 4\mapsto 2\mapsto 1 ). We say \mathbf{u} is a pair-admissible even cycle if the following two statements (1) and (2) hold: (1) for each directed edge (u_{i}\mapsto u_{i+1}) , 1\leq i\leq p , (3.1) \#|j\leq p:(u_{j},u_{j+1})=(u_{i},u_{i+1})|=\#|j\geq p+1:(u_{j+1},u_{j})=(u_{i},u_{i+1})|\mod 2, we then say the edge u_{i}\mapsto u_{i+1} is equivalent to the edges in these two sets (edges ( u_{j},u_{j+1}) in the first set and (u_{j+1},u_{j}) in the second), and we define the multiplicity of (u_{i}\mapsto u_{i+1}) to be the sum of the cardinality of the two sets in ( 3.1 ). (2) And for each directed edge (u_{i}\mapsto u_{i+1}) , p+1\leq i\leq 2p , (3.2) \#|j\leq p:(u_{j+1},u_{j})=(u_{i},u_{i+1})|=\#|j\geq p+1:(u_{j},u_{j+1})=(u_{i},u_{i+1})|\mod 2, we then say the edge u_{i}\mapsto u_{i+1} is equivalent to the edges in these two sets (edges ( u_{j+1},u_{j}) in the first set and (u_{j},u_{j+1}) in the second), and we define the multiplicity of (u_{i}\mapsto u_{i+1}) to be the sum of the cardinality of the two sets in ( 3.2 ). (In the above, by (a,b)=(c,d) we mean a=c,b=d , and we set u_{2p+1}=u_{1} ). In other words, we require that \mathbf{u} can be paired according to the independent entries of A taking into account the direction of edges, and we have reversed the order of edges in the second half of \mathbf{u} . This definition is designed for the non-Hermitian case, while in the symmetric case we only need \mathbf{u} be an even cycle without recording the direction an edge is visited [ 10 ] . Define \mathcal{S}_{2p}:=\{\mathcal{S}(u):u\text{ is a pair-admissible even cycle of length }2p\}. Let n_{i}(\mathbf{u}) be the number of directed edges with multiplicity i in the path \mathbf{u} , then n_{i}(\mathbf{u})=n_{i}(\mathcal{S}(\mathbf{u})) . We denote, for each initial vertex u\in[n] and each shape \mathbf{s}\in\mathcal{S}_{2p} , the following set of collections of path with shape \mathbf{s} and initial vertex u : \Gamma_{\mathbf{s},u}:=\{\mathbf{u}\in[n]^{2p}:\mathcal{S}(\mathbf{u})=\mathbf{s},u_{1}=u\}. As we compute the trace \operatorname{Tr}(A^{p}(A^{*})^{p}), we are summing over paths P_{1},P_{2}:i\mapsto j , and we merge P_{1},P_{2} into a cycle as follows: we first start from i and go through P_{1} , then we go through P_{2} in the reversed direction ( j\mapsto i ). Then we have (3.3) \mathbb{E}[\operatorname{Tr}(A^{p}(A^{*})^{p})]=\sum_{u\in[n]}\sum_{\mathbf{s}\in\mathcal{S}_{2p}}\prod_{i\geq 1}\mathbb{E}[g^{i}]^{n_{i}(\mathbf{s})}\sum_{\mathbf{u}\in\Gamma_{\mathbf{s},u}}b_{u_{1}u_{2}}\cdots b_{u_{p-1}u_{p}}b^{*}_{u_{p}u_{p+1}}\cdots b^{*}_{u_{2p}u_{1}}, where we use the notation (b^{*})_{ij}=b_{ji} for all i,j\in[n] . Here g is a copy of the i.i.d. entries g_{ij} given in Theorem 1.1 . As we are in the real case \beta=1, we have g=\overline{g}. For a shape \mathbf{s}=(s_{1},\cdots,s_{2p}) , denote by m(\mathbf{s})=\max_{i}s_{i} the total number of distinct vertices in it. (As the shape is independent of the labeling, we shall set s_{1}=1 , and the next visit to a new vertex will have label 2, a further visit to a new vertex has label 3, etc. so \max_{i}s_{i} is the total number of distinct vertices). Let i_{k}:=\inf\{j\geq 1:s_{j}=k\} for all 1\leq k\leq m(\mathbf{s}) , so i_{k} is the time when the k -th new vertex is first visited along the path. As the cycles are even, (u_{i_{k-1}},u_{i_{k}}) should be visited at least twice along the whole path, but (u_{i_{k}-1},u_{i_{k}}) should also be distinct from (u_{i_{\ell}-1},u_{i_{\ell}})_{\ellp , and where v_{s_{i_{2}}-1}=u . That is, we have proven (3.4) \mathbb{E}[\operatorname{Tr}(A^{p}(A^{*})^{p})]\leq n\sum_{\mathbf{s}\in\mathcal{S}_{2p}}\sigma^{2(m(\mathbf{s})-1))}\prod_{i\geq 1}\mathbb{E}[g^{i}]^{n_{i}(\mathbf{s})}. The case of a homogeneous variance can be easily computed. Let Y_{r} be an r\times r square matrix with i.i.d. entries following the same law as g_{ij} , then for any r>p , (3.5) \mathbb{E}\operatorname{Tr}[Y_{r}^{p}(Y_{r}^{*})^{p}]=r\sum_{\mathbf{s}\in\mathcal{S}_{2p}}(r-1)\cdots(r-m(\mathbf{s})+1)\prod_{i\geq 1}\mathbb{E}[g^{i}]^{n_{i}(\mathbf{s})}. This computation follows as the cycle \mathbf{u} with a given shape \mathbf{s(u)} is determined solely by its m(\mathbf{s}) free vertices. Taking r=\lceil\sigma^{2}\rceil+p , from the elementary inequality and p\geq m(\mathbf{s}) , (r-1)(r-2)\cdots(r-m(\mathbf{s})+1)\geq\sigma^{2(m(\mathbf{s})-1)}. Comparing ( 3.4 ) and ( 3.5 ) and substituting the value r=\lceil\sigma^{2}+p\rceil into ( 3.5 ), we immediately deduce that, by ( 3.4 ) and ( 3.5 ), \mathbb{E}\left[\operatorname{Tr}(A^{p}(A^{*})^{p})\right]\leq\frac{n}{\lceil\sigma^{2}\rceil+p}\mathbb{E}\operatorname{Tr}\left[Y_{\lceil\sigma^{2}\rceil+p}^{p}(Y_{\lceil\sigma^{2}\rceil+p}^{*})^{p}\right]. Now we complete the proof of Theorem 1.1 . Applying Theorem 2.5 , we get \displaystyle\mathbb{E}[\rho(A)] \displaystyle\leq\mathbb{E}[\operatorname{Tr}|A^{p}(A^{*})^{p}\|]^{\frac{1}{2p}}\leq n^{\frac{1}{2p}}\mathbb{E}\operatorname{Tr}\left[Y_{\lceil\sigma^{2}\rceil+p}^{p}(Y_{\lceil\sigma^{2}\rceil+p}^{*})^{p}\right]^{\frac{1}{2p}} \displaystyle\leq n^{\frac{1}{2p}}(\lceil\sigma^{2}+p\rceil)^{\frac{6}{2p}}\exp(C\frac{p^{1/2}}{(\lceil\sigma^{2}\rceil+p)^{1/2}})(\lceil\sigma^{2}+p\rceil)^{\frac{1}{2}}. Now we take p=\alpha\log n for some \alpha>0 . By our assumption \sigma^{2}/\sigma_{*}^{2}\gg\log n, and the normalization \sigma_{*}=1 , we have \sigma^{2}+p\leq n+p and \mathbb{E}[\rho(A)]\leq(C(n+p))^{\frac{7}{2\alpha\log n}}p^{\frac{2}{p}}(\sigma+2\sqrt{\alpha\log n)}\exp(C\frac{\sqrt{\alpha\log n}}{\sqrt{\sigma^{2}+\alpha\log n}}). That is, for any \epsilon>0 , we choose \alpha such that (2Cn)^{\frac{4}{\alpha\log n}}\leq\sqrt{1+\epsilon} , p^{\frac{2}{p}}\leq\sqrt{1+\epsilon} and get \mathbb{E}[\rho(A)]\leq(1+\epsilon)(\sigma+\frac{6\sigma_{*}}{\sqrt{\log(1+\epsilon})}\sqrt{\log n})\exp\left(C\frac{\sqrt{6\frac{\log n}{\log(1+\epsilon)}}}{\sqrt{(\frac{\sigma}{\sigma_{*}})^{2}+6\frac{\log n}{\log(1+\epsilon)}}}\right). Absence of outliers We can finally derive the tail bounds for \rho(A) via Markov’s inequality. First suppose that \frac{\sigma}{\sigma_{*}}\gg\sqrt{\log n} , and we again normalize by setting \sigma_{*}=1 , then for any \delta>0 , \displaystyle\mathbb{P}(\rho(A)\geq(1+\delta)\sigma) \displaystyle\leq\mathbb{P}(\operatorname{Tr}(A^{p}(A^{*})^{p})\geq(1+\delta)^{2p}\sigma^{2p}) \displaystyle\leq Cn^{6}(1+\delta)^{-2p}\sigma^{-2p}(\sigma^{2}+p)^{p+2}\exp\left(C\frac{p^{1/2}}{(\lceil\sigma^{2}\rceil+p)^{1/2}}\right)^{p}. By our choice p=\alpha\log n and the assumption \sigma^{2}\gg\log n , it is easy to see the right hand side is summable in n . Hence by Borel-Cantelli lemma we have almost surely \rho(A)\leq(1+\delta)\sigma for all n sufficiently large. In the regime where C_{1}\sqrt{\log n}\leq\frac{\sigma}{\sigma_{*}}\leq C_{2}\sqrt{\log n} , again using Markov’s inequality we can show there exists a constant {D}=D(C_{1},C_{2})>0 depending on C_{1},C_{2} such that \mathbb{P}(\lim\sup_{n\to\infty}\rho(A)\geq D(\sigma+\sqrt{\log n}\sigma_{*}))=0. This statement can however be alternatively deduced from the elementary fact that \rho(A)\leq\|A\| and the non-asymptotic bound on \|A\| proved in [ 10 ] . ∎ Proof of Theorem 1.1 , the complex case \beta=2 . The proof is essentially identical to the real \beta=1 case, but the extra assumption that g_{ij}\sim g_{ij}\mathcal{U} for \mathcal{U} the uniform distribution on the unit circle ensures that if a term \prod_{i\in 2\mathbb{N}_{+}}\mathbb{E}[(gg^{*})^{i/2}]^{n_{i}(\mathbf{s})} is nonzero (since n_{i}(\mathbf{s}) must be even in the complex case to get a nonzero expectation), then it must be a positive real number so the comparison procedure in the proof of real \beta=1 case still applies here. The details are omitted. ∎ 3.2. Small deviation bounds via long-time control In this section we prove Theorem 1.6 . The main idea is to closely follow the proof of Theorem 2.2 , 2.3 , but replace the coefficients \frac{1}{\sqrt{n}} there by coefficients b_{ij} . The magnitude of \sigma_{*} determines the largest range of p where moment estimates are valid. We first prove Theorem 1.6 when the distribution of x_{ij} are symmetric. Proof of Theorem 1.6 , symmetric distribution. We use frequently the notations in the proof of Theorem 2.2 . We compute the high trace moments \mathbb{E}[\operatorname{Tr}[A^{p}(A^{*})^{p}] . For a typical term (3.6) x_{i_{0}i_{i}}b_{i_{0}i_{1}}x_{i_{1}i_{2}}b_{i_{1}i_{2}}\cdots\bar{x}_{i_{p+1}i_{p}}b_{i_{p+1}i_{p}}\cdots\bar{x}_{i_{0}i_{2p-1}}b_{i_{0}i_{2p-1}} in the expansion, we claim that the leading contribution comes from vertices with distinct i_{0},\cdots,i_{p} . Let Z_{1}(p) be the sum of terms in \operatorname{Tr}[A^{p}(A^{*})^{p}] of the form ( 3.6 ) such that \operatorname{Card}|i_{0},i_{1},\cdots,i_{p}|=p+1 . We estimate its contribution by (3.7) \displaystyle\mathbb{E}[Z_{1}(p)] \displaystyle\leq\sum_{i_{0},\cdots,i_{p}}b_{i_{0}i_{1}}^{2}\cdots b_{i_{p}i_{p+1}}^{2} \displaystyle\leq\sum_{i_{0}=1}^{n}\sum_{i_{1},\cdots,i_{p-1}}b^{2}_{i_{0}i_{1}}\cdots b^{2}_{i_{p-2}i_{p-1}}\sum_{i_{p}}b^{2}_{i_{p-1}i_{p}}\leq\cdots\leq Cn\sigma^{2p}, where we first fix i_{0},\cdots,i_{p-1} and sum over i_{p} , then fix i_{0},\cdots,i_{p-2} and sum over i_{p-1} , etc. We use that each x_{i_{s}j_{s}} must appear exactly twice in the expansion, so that \{i_{1},\cdots,i_{p-1}\}=\{i_{p+1},\cdots,i_{2p-1}\} and that the entries b_{ij} need to be squared, and we finally use that S is long-time controlled by \sigma , see Definition 1.3 . Then we show the remaining terms, summed together, is also O(n\sigma^{2p}) provided p is not too large. We follow the main steps of the proof of Theorem 2.2 , As in Step 1 of the proof of Theorem 2.2 , we consider a sum of terms ( 3.6 ) over all possible p indices i_{1},\cdots,i_{p} from [n] such that n_{1} of these indices appear once, n_{2} of them appear twice, and n_{k} of them appear k times. An ordering of their appearance in [p] is also determined. Then as in Step 2 and Step 3 of the proof of Theorem 2.2 , we construct the whole path P from i_{1},\cdots,i_{p} . Assume that such a configuration has been fixed (the vertices are not yet chosen), and we first consider the product of coefficients along the path. (3.8) b_{i_{0}i_{1}}b_{i_{1}i_{2}}\cdots b_{i_{p-1}i_{p}}b_{i_{p+1}i_{p}}\cdots b_{i_{0}i_{2p-1}}. By symmetry of entry distribution, to have a nonzero expectation, each b_{ij} should appear an even number of times in this product. Since there are 2(\sum_{k\geq 2}kn_{k}) vertices appearing four times or more and n_{1} vertices appearing twice, we can decompose the product ( 3.8 ) into the product of entries of S , along J+1\geq 2 (possibly disconnected) paths P^{0},P^{1},\cdots,P^{J} , with J=\sum_{k\geq 2}(k-1)n_{k} . The method of summing over coefficients. The precise method to decompose the product ( 3.8 ) is as follows. Recall the notation \mathcal{P}_{k} introduced in the proof of Theorem 2.2 . For a given path P and each k we can alternatively understand the multiset \mathcal{P}_{k} associated to P as the collection of vertices in the path P where the path visits 2k times. Also, each point in \mathcal{P}_{k} is repeated with multiplicity k in the multiset \mathcal{P}_{k} . (Note: for a path i_{0},\cdots,i_{p},\cdots,i_{2p-1} we regard the middle value i_{p} as visited twice). Starting from i_{0} and walk through the path, at the first instance when we arrive at some index i_{t_{1}}=x\in\cup_{k\geq 2}\mathcal{P}_{k} the second time, then we stop the path P^{1} at x with x the last index of P^{1} . (If no such t_{1}

0 . Now we can conclude the proof of Theorem 1.6 via the method of moments. Recalling that \sigma=O(1) , we have, for any t>0 , \displaystyle\mathbb{P}(\rho(A)\geq\sigma(1+t\sigma_{*})) \displaystyle\leq\mathbb{P}(\operatorname{Tr}(A^{p}(A^{*})^{p})\geq\sigma^{2p}(1+t\sigma_{*})^{2p}) \displaystyle\leq C_{0}n(1+t\sigma_{*})^{-2p}\leq C_{0}ne^{-C\sigma t} where we take p=\lfloor\frac{C\sigma}{\sigma_{*}}\rfloor and C>0 is a sufficiently small constant defined in the previous paragraph, depending on \sigma and the sub-exponential distribution of x_{ij} . The constant C_{0}>0 is another fixed constant depending only on \sigma and the sub-exponential tail ( 1.10 ) of x_{ij} . ∎ The case of nonsymmetrically distributed entries can be handled in exactly the same way, where we modify the proof of Theorem 2.3 in Appendix C . Proof of Theorem 1.6 , non-symmetric distribution. Checking the proof of Theorem 2.3 in Appendix C , we only need to show that contributions of uneven paths (paths with at least one edge traveled an odd number of times) can be bounded by O(n\sigma^{2p}) . This is easy: since each b_{ij} is bounded by \sigma_{*} , we simply replace each factor n^{-\frac{1}{2}} of the additional edge weight contribution in the proof of Theorem 2.3 by the factor \sigma_{*} , and choose p\leq C^{\prime}\sigma_{*}^{-1} for another fixed constant C^{\prime}>0 . The remaining computations are analogous. ∎ 3.3. Small deviation bounds via spectral radius The proof is very similar to that of Theorem 1.6 , but we take a different method to estimate the coefficient matrix S . Proof of Theorem 1.7 . As in the proof of Theorem 1.6 , we first assume that the entries x_{ij} have a symmetric distribution. The idea of the proof is essentially the same as the proof of Theorem 1.6 , but we need to take a different estimate on the variance profile S . After a rescaling we may assume for simplicity that \rho(S)\geq 1 . From the standard linear algebraic relation \operatorname{Tr}(S^{k})\leq n\rho(S)^{k} we expand \sum_{i_{0},\cdots,i_{k}\in[n]}s_{i_{0}i_{1}}s_{i_{1}i_{2}}\cdots s_{i_{k-1}i_{k}}s_{i_{k}i_{0}}\leq n\rho(S)^{k+1}. From the assumption s_{i_{k}i_{0}}\geq\frac{c}{n} , we get an obvious upper bound (3.11) S(k):=\sum_{i_{0},\cdots,i_{k}\in[n]}s_{i_{0}i_{1}}s_{i_{1}i_{2}}\cdots s_{i_{k-1}i_{k}}\leq c^{-1}n^{2}\rho(S)^{k+1}. This bound on S(k) already gives the contribution to \mathbb{E}[\operatorname{Tr}(A^{k}(A^{*})^{k})] generated by even closed paths with no self intersection, and the contribution is O(n^{2}\rho(S)^{p+1}) as one may compute similarly to ( 3.7 ). For general paths with self intersection, we may decompose the path into J+1 sub-paths P^{1},\cdots,P^{J+1} as in the proof of Theorem 1.6 . Then we need to bound, for any fixed 1\leq r\leq J+1 and such that the path P^{r} has length m_{r} , the following summation (3.12) \sum_{p_{s}^{r}\in[n],1\leq s\leq m_{r}-1\forall r,P_{0}^{1},p_{m_{J+1}}^{J+1}\in[n]}\prod_{r=1}^{J+1}\prod_{s=0}^{m_{r}-1}b^{2}_{P_{s}^{r}P_{s+1}^{r}}, (that is, we sum over the possible choices of the vertices of each path P^{j} with the initial vertex and last vertex removed, and also sum over the first vertex of P^{1} and the last vertex of P^{J+1} ), under two constraints: (1) We require that the endpoint of P^{r},1\leq r\leq J satisfy that P_{m_{r}}^{r}=P_{m_{t}(s)}^{t} for some fixed t\leq r and for some fixed m_{t}(s)\in[0,m_{t})\cap\mathbb{N} . This is because by the way we construct the paths P^{1},\cdots,P^{J+1} , the endpoint of P^{r} is either some point in \cup_{k\geq 2}\mathcal{P}_{k} which is not the first visit, (and the first visit must be contained in the previously constructed paths), or the endpoint is a vertex of a previously existed directed edge, which also is contained in previously constructed paths. (2) A previously fixed correspondence between the starting point P^{r}_{0} of the path P^{r},r=2,\cdots,J+1 with \cup_{k\geq 2}(k-1)\mathcal{P}_{k} (which is the multiset spanned by each element in \mathcal{P}_{k} repeated k-1 times). Both constraints are determined by the shape \mathbf{s} of the path. We will now show that ( 3.12 ) can be bounded by a factor of the form n^{-J}S(p-J) , where S(\cdot) was defined in ( 3.11 ) , and such that this bound is independent from the specific form of the constraints imposed. To see this, we take an iterative exploration of the paths by first revealing vertices in P^{1} , then vertices in P^{2} , then P^{3} , etc. Note that P_{{m_{r}-1}}^{r} is a free vertex to be chosen in [n] and P_{{1}}^{r+1} is also a free vertex to choose, but the value of P_{m_{r}}^{r} and P^{r+1}_{0} have already been fixed. By the two-sided bound ( 1.12 ) on the variance s_{ij} , we have (3.13) b^{2}_{P^{r}_{m_{r}-1},P^{r}_{m_{r}}}b^{2}_{P^{r+1}_{0},P^{r+1}_{1}}\in[\frac{c^{2}}{Cn},\frac{C^{2}}{cn}]b^{2}_{P^{r}_{m_{r}-1},P^{r+1}_{1}}. This reduction removes one constraint previously set, but keeps the number of free vertices unchanged and brings about an additional n^{-1} factor. This procedure can be applied altogether J times, at the instance when we switch from paths P^{j} to P^{j+1} for each j . This leads to a reduction of J edges. After the reduction we have (3.14) \eqref{summationidentity2}\leq(\frac{\text{const}}{n})^{\sum_{k\geq 2}(k-1)n_{k}}S(p-J). Therefore in this case the contribution of all terms with specified n_{0},n_{1},\cdots,n_{p} to the trace expansion \mathbb{E}[\operatorname{Tr}(A^{p}(A^{*})^{p})] is upper bounded by (3.15) n^{2}\rho(S)^{p+1}(\frac{\text{const}}{n})^{\sum_{k\geq 2}(k-1)n_{k}}\frac{p!}{\prod_{k=2}^{p}(k!)^{n_{k}}}\prod_{k=2}^{p}(2k)^{kn_{k}}\prod_{k=2}^{p}(\text{const}\cdot k)^{kn_{k}}\cdot 4^{\sum_{k\geq 2}kn_{k}}. The summation over all n_{0},\cdots,n_{p} with \sum_{k\geq 2}kn_{k}>0 is bounded by n^{2}\rho(S)^{p+1}\left(\exp\left(\sum_{k\geq 2}\frac{(\text{const}k\cdot p)^{k}}{n^{k-1}}\right)-1\right) which is O(1)n^{2}\rho(S)^{p+1} whenever p\leq C_{0}\sqrt{n} for some fixed C_{0}>0 sufficiently small. Finally, the contribution of terms with n_{0}=n-p,n_{1}=p,n_{2}=\cdots=0 is bounded by c^{-1}n^{2}\rho(S)^{p+1}. Combining the above, we can finish the proof of the small deviation estimate via a standard application of Markov’s inequality, which parallels the argument in the proof of Theorem 1.6 and is thus omitted. Last we consider the case when x_{ij} does not have a symmetric law. For this we just need to follow the proof of Theorem 2.3 , where we replace the edge weight from n^{-1/2} to Cn^{-1/2} . There is also a change when we are in case (B) or (C) of the proof of Theorem 2.3 , when the path with an odd edge is generated from at least two even closed paths and some additional odd edges. For the contribution of coefficients from these even closed paths, we may just follow the computation in ( 3.12 ) to stick together the contribution from two disjoint paths into contribution along one single path, as in ( 3.14 ), and finally conclude via this estimate. ∎ 3.4. Suppressed fluctuations: proofs This section is devoted to the proof of Theorem 1.8 . The idea is again to compute the trace of high powers of \mathcal{L} . Proof of Theorem 1.8 . Expanding the trace power of \mathbb{E}[\operatorname{Tr}(\mathcal{L}^{p_{n}}(\mathcal{L}^{*})^{p_{n}})] , thanks to the special structure of \mathcal{L} , any monomial in the expansion should be of the form X^{1}_{i_{0}i_{1}}X^{2}_{i_{1}i_{2}}\cdots X^{p_{n}}_{i_{p_{n}-1}i_{p_{n}}}\bar{X}^{p_{n}}_{i_{p_{n}+1}i_{p_{n}}}\cdots\bar{X}^{1}_{i_{0}i_{2p_{n}-1}}, where we use the notation X^{i}_{j,k} to denote the (j,k) -th element of the matrix X^{i} . Since entries of \mathcal{L} are independent with zero mean, for this term to have nonzero expectation we need each X^{r}_{i_{r-1}i_{r}} to appear at least twice in the product. But as we consider exactly p_{n} moments, this guarantees each element must appear exactly twice and therefore i_{p_{n}+r}=i_{p_{n}-r} for all r=1,2,\cdots,p_{n}-1 . Summing over all possibilities of i_{1},\cdots,i_{p_{n}} , we get \mathbb{E}[\operatorname{Tr}\left(\mathcal{L}^{P_{n}}(\mathcal{L}^{*})^{p_{n}}\right)]\leq q_{n}. Thus by Markov’s inequality, whenever p_{n} is large enough, for any t>0 \displaystyle\mathbb{P}(\rho(\mathcal{L})\geq 1+\frac{t}{p_{n}}) \displaystyle\leq(1+\frac{t}{p_{n}})^{-2p_{n}}\mathbb{E}[\|\mathcal{L}^{p_{n}}\|^{2}] \displaystyle\leq(1+\frac{t}{p_{n}})^{-2p_{n}}\mathbb{E}[\operatorname{Tr}(\mathcal{L}^{p_{n}}(\mathcal{L}^{*})^{p_{n}}\|)]\leq e^{-2t}q_{n}. This proves claim (2) of Theorem 1.8 . For claim (1), it suffices to take e^{-2\frac{n}{q_{n}}}q_{n}\ll 1 to ensure \rho(\mathcal{L})\leq 1+o(1) with high probability: this is the same as q_{n}\log q_{n}\ll n . ∎ 4. Large deviation of spectral radius In this section we prove Theorem 1.10 . Instead of using the moments computation, we will use the free probability framework of [ 9 ] . The basic idea is, to show that \rho(A)\leq 1+t , we first recall that \|A\|\leq 4 with very high probability, then we find small balls B_{i}=B(\rho_{i},\epsilon_{i}) to cover \{z\in\mathbb{C}:1+t\leq|z|\leq 4\} and show that \sigma_{min}(A-\rho_{i}I)>0 with very high probability for each i . Finally we take a union bound over all such balls B_{i} . Before outlining the proof we recall some free probability notations from [ 9 ] . Consider a Gaussian random matrix M\in\mathcal{M}_{n}(\mathbb{C}) that can be written in the form M=A_{0}+\sum_{i=1}^{m}A_{i}g_{i} where A_{0},A_{1},\cdots,A_{m}\in\mathcal{M}_{n}(\mathbb{C}) are fixed and g_{1},\cdots,g_{m} are an independent family of standard real Gaussian random variables. The idea is to show that the spectrum of the finite dimensional object M is close to the spectrum of a limiting object, denoted M_{\text{free}} , that lives in an infinite dimensional space. To properly define this limiting object M_{\text{free}} , we need to introduce some notations in free probability theory. A comprehensive introduction to free probability can be found in [ 43 ] . Consider a unital C^{*} algebra (\mathcal{A},\tau) and a family of free semicircular elements s_{1},\cdots,s_{m} on (\mathcal{A},\tau) , where (\mathcal{A},\tau) is the space where the the infinite dimensional objects lie in, and the semicircular elements s_{i} can be thought as the limiting objects of GOE/GUE matrices in free probability theory. Then the free probability model M_{\text{free}} of M is defined on the C^{*} algebra (\mathcal{A}\otimes\mathcal{M}_{n}(\mathbb{C}),\tau\otimes\operatorname{tr}) as (4.1) M_{\text{free}}=A_{0}\otimes 1+\sum_{i=1}^{m}A_{i}\otimes s_{i}. Note that the definition of M_{\text{free}} and M applies to non-Hermitian matrices as well. For a random matrix M with general (non-Gaussian) entries, we can consider its Gaussian model M^{\text{gauss}} which is the Gaussian random matrix with the same mean and covariance profile as M , where the covariance profile is the following n^{2}\times n^{2} matrix (\operatorname{Cov}M)_{ij,kl}:=\mathbb{E}[(M-\mathbb{E}M)_{ij}\overline{(M-\mathbb{E}M)_{kl}}], and define its free probability version M_{\text{free}} as the free model associated with M^{\text{gauss}} . While there are several ways to write out M_{\text{free}} in terms of entries of M , they are equivalent in the following computations. For a self-adjoint operator M we denote by \operatorname{Sp}(M)\subset\mathbb{R} the spectrum of M . The main result in [ 9 ] implies that, under appropriate conditions on the coefficients of M , the spectrum \operatorname{Sp}(M) can be well captured by \operatorname{Sp}(M_{\text{free}}) . We will not use the most general notation of [ 9 ] but adapt [ 9 ] , Theorem 2.1 to the setting of Theorem 1.10 . Proposition 4.1 . Let A be a random matrix with Gaussian entries defined in Theorem 1.10 . For any z\in\mathbb{C}, we define \mathcal{Y}_{z}:=\begin{pmatrix}0&A+z\mathbf{1}\\ A^{*}+\bar{z}\mathbf{1}&0\end{pmatrix},\quad\mathcal{Y}_{\text{free},z}:=\begin{pmatrix}0&A_{\text{free}}+z\mathbf{1}\\ (A^{*})_{\text{free}}+\bar{z}\mathbf{1}&0\end{pmatrix}. Then for some universal constant C>0 , we have for all t>0 and z\in\mathbb{C} , \mathbb{P}\left(\operatorname{Sp}(\mathcal{Y}_{z})\subset\operatorname{Sp}(\mathcal{Y}_{\text{free},z})+C\{\sigma_{*}t+\sqrt{\sigma_{*}}(\log n)^{\frac{3}{4}}\}[-1,1]\right)\geq 1-e^{-t^{2}}. Proof. We shall use notations \sigma(A),\sigma_{*}(A),\widetilde{v}(A) from [ 9 ] . The claim follows from applying [ 9 ] , Theorem 2.1 with \sigma_{*}(A)=\sigma_{*} and \tilde{v}(A)\leq C\sqrt{\sigma_{*}} , and the fact that the assumptions in Theorem 1.10 implies \sigma(A)\leq 3 . ∎ Proof of Theorem 1.10 . We divide the proof into three regimes, that t<\frac{1}{3},t\in[\frac{1}{3},3] and t>3 . The large t regime. We can check that, say, \|A_{\text{free}}\|\leq 4 via Lehner’s formula [ 40 ] or Pisier’s formula (see [ 9 ] , Lemma 2.5), so that for any t\geq 3 , by [ 9 ] , Corollary 2.2, (4.2) \mathbb{P}(\rho(A)\geq t+1)\leq\mathbb{P}(\|A\|\geq t+1)\leq e^{-C_{0}\frac{(t-2)^{2}}{\sigma_{*}^{2}}}\leq e^{-C_{0}\frac{t^{2}}{\sigma_{*}^{2}}}, where C_{0}>0 is a universal constant that changes from line to line. More specifically, the parameter \sigma_{*} in this paper coincides with the parameter \sigma_{*}(X) in [ 9 ] by [ 9 ] , Lemma 3.1, and we also use the assumption (\log n)^{\frac{3}{4}}\sqrt{\sigma_{*}}\to 0 . The small t regime. Then we consider 0\leq t\leq\frac{1}{3} . Consider a finite covering of \{z\in\mathbb{C}:1+\frac{t}{4}\leq|z|\leq 4\} by finitely many balls of radius \frac{t^{1.5}}{400} : (B_{i})_{i\in\mathcal{A}}=(B(\rho_{i},\frac{t^{1.5}}{400}))_{i\in\mathcal{A}}, where \mathcal{A} is a finite index set and 1+\frac{t}{4}\leq|\rho_{i}|\leq 4 for each i . In the following, for any z\in\mathbb{C} denote A_{z}:=A-z\mathbf{1} , where \mathbf{1} is the identity matrix. Then we define A_{\text{free},z} as the free probability model associated to A_{z} as defined in ( 4.1 ). We claim that (4.3) \sigma_{min}(A_{\text{free},\rho_{i}})\geq\frac{t^{1.5}}{100}\text{ for every }i\in\mathcal{A}. [The reason why we choose t^{1.5} instead of t , and hence get the exponent \exp(-t^{3}/\sigma_{*}^{2}) instead of \exp(-t^{2}/\sigma_{*}^{2}) , all arise from this estimate.] Once this is shown, we have that whenever n satisfies \sqrt{\sigma_{*}}(\log n)^{\frac{3}{4}}\leq\frac{t^{1.5}}{500} , we can find a universal C_{0}>0 such that \displaystyle\mathbb{P}(A\text{ has an eigenvalue in }B_{i}) \displaystyle\leq\mathbb{P}(\sigma_{min}(A_{\rho_{i}})\leq\frac{t^{1.5}}{200}) \displaystyle\leq\mathbb{P}(|\sigma_{min}(A_{\rho_{i}})-\sigma_{min}(A_{\text{free},\rho_{i}})|\geq\frac{t^{1.5}}{200}) \displaystyle\leq e^{-C_{0}\frac{t^{3}}{\sigma_{*}^{2}}} where the last inequality follows from Proposition 4.1 (1) and our assumption on the smallness of \sigma_{*} . The first inequality follows from the fact that \sigma_{min}(A_{z}) is Lipschitz continuous in z , i.e. for any \lambda\in B_{i} we have \sigma_{min}(A_{\lambda})\geq\sigma_{min}(A_{\rho_{i}})-|\rho_{i}-\lambda| , so that A has eigenvalue \lambda\in B_{i} implies \sigma_{min}(A_{\rho_{i}})\leq\frac{t^{1.5}}{200}. Then we complete the proof via a union bound: (4.4) \displaystyle\mathbb{P}(\rho(A)\geq t+1) \displaystyle\leq\mathbb{P}(\|A\|\geq t+1)1_{t\geq 4}+\sum_{i\in\mathcal{A}}\mathbb{P}(A\text{ has an eigenvalue in }B_{i}) \displaystyle\leq(1+|\mathcal{A}|)e^{-C_{0}\frac{t^{3}}{\sigma_{*}^{2}}}\leq C_{0}(1+t^{-3})e^{-C_{0}\frac{t^{3}}{\sigma_{*}^{2}}} where we can bound the entropy cost by |\mathcal{A}|\leq C_{0}t^{-3} for some universal constant C_{0} , and this C_{0} can be absorbed into the constant C_{0} in the exponential term. This completes the proof of Theorem 1.10 in the Gaussian case, for all t\leq\frac{1}{3} . In fact, the value \frac{1}{3} here is arbitrary, not used in the above computation (but used in the proof of ( 4.3 )), and can be changed to any other small constant in (0,1) . Intermediate range of t . When \frac{1}{3}\leq t\leq 3 , we can find a covering of by finitely many balls of radius \frac{1}{6} and use the same argument. The entropy cost of covering is absorbed in the universal constant C_{0} . Verification for the claim on least singular values. We finally prove ( 4.3 ). A similar computation has been done in [ 33 ] but here we need a much more precise version. Define the resolvent of the free operator G_{\text{free},z}(v):=((\tau\otimes\operatorname{id})\mathcal{Y}_{\text{free,z}}-v\mathbf{1})^{-1}) for every v\in\mathbb{C}_{+}:=\{z\in\mathbb{C}:\Im z>0\} . We first assume that \mathbb{E}[a_{ii}^{2}]=0 for each i\in[n] . Then we solve the matrix Dyson equation for G_{\text{free},z} . By our assumption, G_{\text{free},z}(v) solves, by [ 33 ] , Section 3.1, the self consistency equation (4.5) \mathbb{E}[\mathcal{Y}_{0}G_{\text{free},z}(v)\mathcal{Y}_{0}]+G_{\text{free},z}(v)^{-1}+\begin{pmatrix}vI_{n}\quad zI_{n}\\ \bar{z}I_{n}\quad vI_{n}\end{pmatrix}=0. The existence of a unique solution to ( 4.5 ) such that \operatorname{Im}G_{\text{free},z}(v)>0 is proven in [ 36 ] , and we claim that the solution is necessarily given by G_{\text{free},z}(v)=\begin{pmatrix}a(z,v)\mathbf{1}&b(z,v)\mathbf{1}\\ \bar{b}(z,v)\mathbf{1}&a(z,v)\mathbf{1}\end{pmatrix}, where a(z,v),b(z,v) are scalar functions of (z,v) . To see this, plugging this expression back into the self-consistency equation ( 4.5 ) and multiplying by \mathcal{G}_{\text{free},z}(v) to the left, we see that we are reduced to the following 2\times 2 system of scalar equations: (4.6) \begin{pmatrix}a&b\\ \bar{b}&a\end{pmatrix}\cdot\begin{pmatrix}a&0\\ 0&a\end{pmatrix}+\begin{pmatrix}1&0\\ 0&1\end{pmatrix}+\begin{pmatrix}a&b\\ \bar{b}&a\end{pmatrix}\cdot\begin{pmatrix}v&z\\ \bar{z}&v\end{pmatrix}=0. Solving the self-consistency equation ( 4.6 ) we get b=\frac{-az}{a+v}. Taking this further back to ( 4.6 ) we get a cubic equation for a=a(z,v) : (4.7) -\frac{1}{a}=a+v-\frac{|z|^{2}}{a+v}. To determine the support of \mathcal{Y}_{z} , we will fix |z|>1 , take \Im v\to 0 although we do not set \Re v\to 0 . By a well-known criterion (see implication (vi)-(v) in Lemma D.1 of [ 5 ] ), we have (4.8) \{t\in\mathbb{R}:\lim_{\eta\downarrow 0}\Im a(z,t+i\eta)=0\}\subset\mathbb{C}\setminus\operatorname{Sp}(\mathcal{Y}_{\text{free},z}). Now we fix \tau:=|z|^{2}>1 and rewrite the cubic equation ( 4.7 ) as (4.9) \tau-1-v^{2}=a^{2}+2av+\frac{v}{a}. We now assume v is real and v\in[-\frac{1}{3},\frac{1}{3}] , and formulate a condition on v which guarantees all three solutions to a are real. By continuous dependence of solutions on the coefficients (or solution formula for cubic polynomials), we have that if \Re v satisfies the given condition, then \Im a(z,v)\to 0 whenever \Im v\to 0 . We can reformulate this implication as follows: (4.10) \{v\in\mathbb{R}:\text{all three solutions $a(z,v)$ to \eqref{equationsolvedbya} are real\lx@text@rbrace}\subset\mathcal{C}\setminus\operatorname{Sp}(\mathcal{Y}_{\text{free},z}). Consider the function with real entries f(x)=x^{2}+2vx+\frac{v}{x}, computing f^{\prime}(x)=0 yields 2x+2v-\frac{v}{x^{2}}=0 . We assume, say, |v|<\frac{1}{3} , then whenever |x|>2|v|^{1/3} or |x|<\frac{|v|^{1/3}}{4} then f^{\prime}(x)\neq 0 , so all critical points of f lie in \{\theta v^{1/3}:\frac{1}{4}\leq|\theta|\leq 2\} . Drawing the plots of f we see that all the local minima of f are smaller than 9|v|^{2/3} , so that for any \zeta>9|v|^{2/3} , the line y=\zeta has three intersection points with the plot of f for fixed v . Thus whenever \zeta>9|v|^{2/3} , the equation f(x)=\zeta has three real solutions for this fixed value of v . (Note that we are checking the inclusion ( 4.10 ) for each fixed v\in\mathbb{R} , and thus although f depends on v , we may fix v and plot the function f for this value of v ). Thus by the inclusion ( 4.8 ) one has \{t\in\mathbb{R}:|t|\leq\frac{1}{3},\quad 1+t^{2}+9|t|^{2/3}\leq|z|^{2}\}\subset\mathbb{C}\setminus\operatorname{Sp}(\mathcal{Y}_{\text{free},z}). That is, \sigma_{min}(\mathcal{Y}_{\text{free},z})\geq\min\left(\frac{1}{3},\left(\frac{|z|^{2}-1}{10}\right)^{3/2}\right). This bound is worse than the bound \sigma_{min}(\mathcal{Y}_{\text{free},z})\geq|z|-1 that one may expect, but is nonetheless workable. This estimate verifies ( 4.3 ) for t\leq\frac{1}{3} . ∎ 5. The heavy-tailed case This section is devoted to the proof of Theorem 1.11 . We will use critically the arguments in [ 14 ] , and take a further averaging step and careful counting. We begin with some graph-theoretic notations from [ 14 ] . For each n\in\mathbb{N}_{+} let [n]:=\{1,2,\cdots,n\} . A directed graph on [n] is G=(V,E) with V\subset[n] the vertices set and E\subset[n]\times[n] the set of directed edges. Edges in E can appear multiple times, and we say G is a multi digraph . For each m\in\mathbb{N}_{+} , a path P of length m is some sequence P=(i_{1},\cdots,i_{m+1})\in[n]^{m+1} , and we say P is closed if it has coinciding start and end vertices, i.e., i_{1}=i_{m+1} . Each path P generates a multigraph G_{P}=(V,E) where (i,j)\in E with multiplicity n if the directed edge (i,j) appears n times in P . Given a multi digraph, we call it a double cycle if the graph is formed by repeating a cycle twice. For a path P , we call it an even path if every adjacent pair (i\to j) appears an even number of times. A multi digraph generated by an even path (by the method described in the last paragraph) is called an even digraph . Two multi-digraphs G=(V,E) , G^{\prime}=(V^{\prime},E^{\prime}) on [n] are isomorphic if there is a bijection f:V\to V^{\prime} such that (i,j)\in E if and only if (f(i),f(j))\in E^{\prime} , and the two edges have the same multiplicity in G,G^{\prime} respectively. A rooted digraph is a digraph G=(V,E,\rho) where \rho\in E is a distinguished directed edge. Two rooted digraphs G=(V,E,\rho),G^{\prime}=(V^{\prime},E^{\prime},\rho^{\prime}) are isomorphic if there is an isomorphism preserving the multiplicity of edges and mapping \rho to \rho^{\prime} . Given an even digraph G=(V,E), we define its weight associated to the random matrix A in Theorem 1.11 as p(G):=\prod_{(i,j)\in E}|x_{ij}|^{n_{i,j}}, where n_{ij}\geq 2 is the multiplicity of edge (i,j)\in E . For a given unlabeled even digraph \mathcal{U} , we denote by \{G:G\sim\mathcal{U}\} the equivalence class of even digraphs to \mathcal{U} , where the equivalence relation is modulo the isomorphism relation defined in the previous paragraph. We define the following statistical quantity, for each h\in\mathbb{N}_{+} : (5.1) \mathcal{S}_{h}(\mathcal{U}):=\frac{2^{h}|\{G\sim\mathcal{U}:p(G)\geq 2^{h}\}|}{|\{G:G\sim\mathcal{U}\}|} and (5.2) \mathcal{S}(\mathcal{U}):=\max(1,\max_{h\geq 0}\mathcal{S}_{h}(\mathcal{U})). For rooted even digraphs G=(V,E,\rho) we similarly define p_{r}(G)=\prod_{(i,j)\in E}|x_{ij}|^{n_{ij}-2\mathbf{1}_{(i,j)=\rho}}. In the definition of p(G),p_{r}(G) we have not included the coefficients \{b_{ij}\}_{1\leq i,j\leq n} . Let \mathcal{C}_{m} denote a double cycle with 2m edges on [n] , and let \mathcal{C}_{m}^{*} denote a rooted double cycle with 2m edges on [n] . Recall the following lemma on cycle statistics from [ 14 ] , Lemma 3.1. For each k\geq 1 define \mathcal{A}_{k}:=\mathcal{A}_{k}^{1}\cap\mathcal{A}_{k}^{2}\cap\mathcal{A}_{k}^{3} , with \mathcal{A}_{k}^{1}:=\cap_{m=1}^{k}\left\{\sum_{h=0}^{\infty}\mathcal{S}_{h}(\mathcal{C}_{m})\leq k^{2}\right\}, \mathcal{A}_{k}^{2}:=\cap_{m=1}^{k}\left\{\sum_{h=0}^{\infty}\mathcal{S}_{h}(\mathcal{C}_{m}^{*})\leq k^{2}\right\}, \mathcal{A}_{k}^{3}:=\cap_{m=1}^{k}\left\{\sum_{h=0}^{\infty}2^{h\epsilon/2}\mathcal{S}_{h}(\mathcal{C}_{m})\leq k^{2}B^{m}\right\}. Lemma 5.1 . ( [ 14 ] , Lemma 3.1) For every k\geq 1 we have \mathbb{P}(\mathcal{A}_{k})\geq 1-\frac{6}{k} . Proposition 5.2 . (Main estimate, ( [ 14 ] , Proposition 3.3) Consider n^{\epsilon/16}\geq 5ek^{2} and an unlabeled rooted even graph \mathcal{U} having 2k edges and x vertices. Set y_{x}:=\max\left(0,k-x-\frac{4k\log B}{\epsilon\log n}\right), then on the event \mathcal{A}_{k} , \mathcal{S}(\mathcal{U})\leq n^{k-x-\epsilon y_{x}/16}k^{2}(3ek^{2})^{\frac{4k\log B}{\epsilon\log n}}. We also need a few combinatorial counting estimates. Lemma 5.3 . Let \mathcal{UG}(k,\ell) be the isomorphism class of unlabeled rooted digraphs with k vertices and 2\ell edges. Then |\mathcal{UG}(k,\ell)|\leq k^{2(k-\ell)+1}. Proof. This is essentially [ 14 ] , Lemma 2.3 but we do not label the vertices in [n] . ∎ Lemma 5.4 . [ [ 14 ] , Lemma 2.2] Given G=(V,E) an even digraph, |E|=2k , |V|=\ell . There are at most \ell(4k-4\ell)! number of paths that generate G . Now we are ready to prove Theorem 1.11 . We follow the lines of [ 14 ] to a large extent, yet the main novelty of our proof compared to [ 14 ] is that we add an additional permutation \pi to the indices of A_{n} in the estimate ( 5.3 ) to take a further averaging, which is helpful when \{b_{ij}\} do not have the same value. Proof of Theorem 1.11 , (1). We work on the event \mathcal{B} where |x_{ij}|\leq n^{2} for all (i,j)\in[n]^{2} . By Markov, \mathbb{P}(\mathcal{B})\geq 1-1/n^{2} . Let \mathcal{E}_{k}:=\mathcal{A}_{k}\cap\mathcal{B} , then \mathbb{P}(\mathcal{E}_{k})\geq 1-n^{-2}-6k^{-1} . Averaging over a random permutation for heavy-tail entries. At this point we need to take one more averaging procedure. let \pi\in S(n) be uniformly chosen permutation of [n] , and denote by \pi A the matrix with entries (b_{ij}x_{\pi(i),\pi(j)})_{i,j\in[n]} , that is, we permute the entries of \{x_{ij}\} via a uniformly chosen permutation \pi but keep the coefficients b_{ij} fixed at location (i,j) . Since x_{ij} are i.i.d. entries we have A\overset{\text{law}}{\equiv}\pi A for any \pi\in S_{n} . Moreover, from the definition of \mathcal{E}_{k} we readily see that \mathcal{E}_{k} is invariant under \pi , that is, A\in\mathcal{E}_{k} if and only if \pi A\in\mathcal{E}_{k} . We use \mathbb{E}_{\pi} to denote the expectation taken with respect to a uniformly chosen \pi\in S_{n} . For an arbitrary path P_{1}=(i_{0},i_{1},\cdots,i_{r})\in[n]^{r} , the permutation \pi naturally acts on P_{1} and maps it to \pi P_{1}=(\pi(i_{0}),\pi(i_{1}),\cdots,\pi(i_{r-1}),\pi(i_{r})) , so that \pi P_{1} permutes the coordinates of P_{1} . For this path P_{1} , we define its weight as w(P_{1})=\prod_{t=1}^{r}x_{i_{t-1}i_{t}}. Then w(\pi P_{1}) is the weight of the path \pi P_{1} . From this, we estimate the conditional moment of \rho(A_{n}) via (5.3) \displaystyle\mathbb{E}[\rho(A_{n})^{2k-2}\mid\mathcal{E}_{k}] \displaystyle=\mathbb{E}_{\pi}\mathbb{E}[\rho(\pi A_{n})^{2k-2}\mid\mathcal{E}_{k}] \displaystyle\leq\sum_{i,j}\sum_{P_{1},P_{2}:i\mapsto j}\mathbb{E}_{\pi}[\mathbb{E}[w(\pi P_{1})\bar{w}(\pi P_{2})V(P_{1})\bar{V}(P_{2})\mid\mathcal{E}_{k}]], where the sum is over paths P_{1},P_{2} from i to j with length k-1 and V(P_{1}),V(P_{2}) denote the product of entries of b_{ij} along path P_{1} (resp. P_{2} ): that is, for P_{1} is (i_{0},i_{1},\cdots,i_{r}) , then V(P_{1}):=\prod_{t=1}^{r}b_{i_{t-1},i_{t}}. Reduction to even digraphs . Conditioning on \mathcal{E}_{k} destroys independence of x_{ij} ’s, but the sign of each x_{ij} remain independent Bernoulli distributions because x_{ij} has a symmetric distribution. Thus \mathbb{E}[w(\pi P_{1})\bar{w}(\pi P_{2})|\mathcal{E}_{k}]=0 unless each edge in \pi P_{1}\cup\pi P_{2} has even multiplicity (equivalently, each edge in P_{1}\cup P_{2} has even multiplicity). Let P be the closed path starting from i , going through P_{1} , then take edge (j\mapsto i) , then follow P_{2} , and end again with (j\mapsto i) , so that P is even closed of length 2k . We use the notation V_{r}(P) to denote the product of entries of b_{ij} along the path P but the multiple of entries on the root edge r is reduced by multiplicity two: This is because we set (i,j) the root and it contributes to no increase in the moments. Recall that for a path P , G_{P} denotes the multigraph generated by P (see the beginning of Section 5 ). Then we use the notation V_{r}(G_{P}) to denote the product of entries b_{ij} with (i,j) ranging over directed edges in G_{P} , but the root is counted with multiplicity reduced by two. By injectivity of (P_{1},P_{2})\to P , we get (5.4) \mathbb{E}[\rho(A_{n})^{2k-2}|\mathcal{E}_{k}]\leq\sum_{P}\mathbb{E}_{\pi}\left[\mathbb{E}[p_{r}(\pi G_{p})V_{r}(G_{p})]|\mathcal{E}_{k}\right], with the summation over all even closed paths of length 2k : P=(i_{1},\cdots,i_{2k+1}) with (i_{k},i_{k+1}) the root. Via Lemma 5.3 and 5.4 the right hand side of ( 5.4 ) is bounded by (5.5) k\sum_{x=1}^{k}(4k)^{4(k-x)}\sum_{G\in\mathcal{G}_{n}(k,x)}\mathbb{E}_{\pi}[\mathbb{E}[|p_{r}(\pi G)V_{r}(G)|\mid\mathcal{E}_{k}]], with \mathcal{G}_{n}(k,x) the set of rooted even directed graphs on [n] having 2k edges and x vertices. Upper bound the weights on heavy-tail edges. On the event \mathcal{E}_{k} we have \operatorname{p}_{r}(G)\leq n^{4k-4} , so setting H:=\lfloor 4k\log_{2}n\rfloor we have (5.6) p_{r}(G)\leq 1+2\sum_{h=0}^{H}2^{h}1_{p_{r}(G)\geq 2^{h}}\text{ on }\mathcal{E}_{k}. For any fixed G\in\mathcal{G}_{n}(k,x) we have on the event \mathcal{E}_{k} , \mathbb{E}_{\pi}[\mathbb{E}[p_{r}(\pi G)]|\mathcal{E}_{k}]\leq 3H\mathcal{S}(G)\leq 3Hn^{k-x}n^{-\epsilon y_{x}/16}k^{2}(3ek^{2})^{\frac{4k\log B}{\epsilon\log n}}, where the first equality is because \{\pi G,\pi\in S_{n}\} exhausts all even digraphs on [n] that are isomorphic to G , and we recall the definition of \mathcal{S}(\mathcal{U}) and \mathcal{S}_{h}(\mathcal{U}) from ( 5.1 ), ( 5.2 ): these two quantities are the average over the weights on paths isomorphic to the given path, and our expectation taken over \pi also generates the uniform measure over the isomorphism class and thus gives \mathcal{S}(\mathcal{U}) . The second inequality follows from Proposition 5.2 . Contributions from the coefficients \{b_{ij}\} . Next we compute \sum_{G\in\mathcal{G}_{n}(k,x)}V_{r}(G) : this is the major technical ingredient in the current proof that we add upon to the proof in [ 14 ] . For each G\in\mathcal{G}_{n}(k,x) we choose a doubled path P spanning G (the choice of this path does not affect weight counting), where as each edge in P is doubled, we can replace P by a (possibly disconnected) path \bar{P} starting from the same starting point of P but where each edge visited at the even number of times is removed (so only edges visited for the first, third, fifth, etc. times are kept). Although \bar{P} may be disconnected, it is uniquely determined by P (we denote this by P\mapsto\bar{P} ) and has x vertices and k edges. By Lemma 5.3 , the isomorphism class of \bar{P} has cardinality bounded by k^{2(k-x)+1} . Fix a candidate \bar{P} . We first assume \bar{P} has no multiple edges (so the original path P has no edges visited four times or more, and obviously these paths make the dominant contribution), and consider each connected component of \bar{P} separately. Evidently if k=x then \bar{P} is simply a directed path with no self-intersection. Let \bar{P} be 1\mapsto 2\mapsto\cdots s_{1}=k_{1}\mapsto k_{1}+1\cdots\mapsto s_{2}=k_{2}\mapsto\cdots k be a representation of P where s_{1} is the first self-intersection of \bar{P} so that s_{1} equals one of 1,\cdots,s_{1}-1 (denoted t_{1} ) and s_{2} is the second self-intersection so s_{2}=t_{2} for some t_{2}1 , \mathbb{P}(\lim\inf_{n\to\infty}\rho(E)\geq a)=1. (2) If d_{n}=O({\log n}) , then we have \mathbb{P}(\lim\inf_{n\to\infty}\rho(E)>1)=1. The proof of Theorem A.1 will rely on the following estimate on the complex Ginibre ensemble which has explicit eigenvalue correlation functions: Proposition A.2 . Let G_{n}=(g_{ij}) be sampled from the n -dimensional complex Ginibre ensemble, i.e. G has independent entries, g_{ij}\sim\frac{1}{\sqrt{n}}\xi and \xi\sim\mathcal{N}_{\mathbb{C}}(0,1) . Then (1) For any a>1 we can find a constant p_{a}>0 such that whenever n is sufficiently large, \mathbb{P}(\rho(G_{n})\geq a)\geq\exp(-p_{a}n). (2) For any small \epsilon>0 we can find some a_{\epsilon}>1 such that whenever n is sufficiently large, \mathbb{P}(\rho(G_{n})\geq a_{\epsilon})\geq\exp(-\epsilon n). Proof. We use the exact eigenvalue density function of complex Ginibre ensemble to deduce, by [ 47 ] , equation (3), for any a>0 : (A.1) \mathbb{P}(\rho(G_{n})\leq a)=\prod_{k=0}^{n-1}\mathbb{P}\left[\frac{1}{n}\sum_{\ell=1}^{n-k}X_{\ell}\leq a^{2}\right], where \{X_{k}\} is a given sequence of independent rate one exponential random variables. To prove part (1), for k\geq\frac{n}{2} we trivially upper bound the probability of each factor on the right-hand side of ( A.1 ) by 1 . For 0\leq k\leq\frac{n}{2} , we bound \mathbb{P}\left[\frac{1}{n}\sum_{\ell=1}^{n-k}X_{\ell}\leq a^{2}\right]\leq\mathbb{P}\left[\frac{1}{n-k}\sum_{\ell=1}^{n-k}X_{\ell}\leq 2a^{2}\right] We will apply Cramér’s theorem in large deviations to the sum \bar{S}_{n-k}:=\frac{1}{n-k}\sum_{\ell=1}^{n-k}X_{\ell}, where Cramér’s theorem (see for example [ 55 ] or any standard large deviation textbook) shows that, for any x>1 we can find c_{x}=x-1-\log x>0 such that \displaystyle\lim_{n\to\infty}\frac{1}{n}\log\mathbb{P}(\bar{S}_{n}\geq x) \displaystyle=-\sup_{t\geq 0}\{tx-\log\mathbb{E}[\exp(tX_{1})]\}=-c_{x}<0. That is, whenever n sufficiently large we may assume \frac{1}{n}\log\mathbb{P}(\bar{S}_{n}\geq x)\geq-2c_{x} . That is, whenever n sufficiently large, \displaystyle\mathbb{P}(\rho(G_{n})\leq a) \displaystyle\leq\prod_{k=0}^{\frac{n}{2}}\mathbb{P}[\bar{S}_{n-k}\leq 2a^{2}] \displaystyle\leq\prod_{k=0}^{\frac{n}{2}}(1-e^{-2c_{2a^{2}}(n-k)})\leq(1-e^{-2c_{2a^{2}}n})^{\frac{n}{2}}\leq 1-C_{0}ne^{-2c_{2a^{2}}n} for some universal constant C_{0} . This completes the prof of part (1). The proof of part (2) is similar, except that we need to keep track of the constants more carefully. For the given \epsilon>0 we find a constant a_{\epsilon}>1 such that c_{a_{\epsilon}^{2}}=(a_{\epsilon})^{2}-1-\log((a_{\epsilon})^{2})<\frac{\epsilon}{10}. Let \theta_{\epsilon}:=1-(\frac{1+a_{\epsilon}}{2a_{\epsilon}})^{2} . Then for k\geq\theta_{\epsilon}n , we bound each term on the right hand side of ( A.1 ) simply by 1 . For the smaller k , we bound as follows: using equation ( A.1 ), whenever n is sufficiently large, \displaystyle\mathbb{P}(\rho(G_{n})\leq\frac{1+a_{\epsilon}}{2}) \displaystyle\leq\prod_{k=0}^{\theta_{\epsilon}n}\mathbb{P}[\bar{S}_{n-k}\leq(a_{\epsilon})^{2}]\leq\prod_{k=0}^{\theta_{\epsilon}n}(1-e^{-2c_{a_{\epsilon}^{2}}(n-k)}) \displaystyle\leq(1-e^{-\frac{\epsilon}{5}n})^{\theta_{\epsilon}n}\leq 1-C_{0}\theta_{\epsilon}ne^{-\frac{\epsilon}{5}n} for some universal C_{0}>0 . This completes the proof of part (2): it suffices to replace \epsilon by \frac{\epsilon}{5} and a_{\epsilon} by \frac{1+a_{\epsilon}}{2} . ∎ Now we can conclude the proof of Theorem A.1 . Proof of Theorem A.1 . As E is block diagonal, we have, whenever n is sufficiently large and using Proposition A.2 (1), for any a>0 : \begin{aligned} \mathbb{P}((\rho(E)\leq a))&=\prod_{i=1}^{\frac{n}{d_{n}}}\mathbb{P}(\rho(E_{i})\leq a)\end{aligned}. First assume we are in case (1), i.e., d_{n}=o(\log n) , then we have p_{a}d_{n}\leq\frac{\log n}{2} for any constant p_{a}>0 whenever n is large. Then \mathbb{P}(\rho(E)\leq a)\leq(1-n^{-1/2})^{\frac{n}{d_{n}}}\leq e^{-n^{1/4}}. Case (1) then follows from applying Borel-Cantelli lemma. Then we assume we are in case (2), so that d_{n}\leq C\log n for some C>0 . Choose \epsilon>0 small enough so that C\epsilon\leq\frac{1}{4} , then by Proposition A.2 (2), we can find some a_{\epsilon}>1 such that \mathbb{P}(\rho(E)\leq a_{\epsilon})\leq(1-n^{-1/2})^{\frac{n}{d_{n}}}\leq e^{-n^{1/4}}. The claim again follows from Borel-Cantelli lemma. ∎ Appendix B Further examples In this section we outline some further examples left out in the main text, to illustrate how the long-time control in Definition 1.3 can improve upon the quantity \sigma in capturing \rho(A) , both on the O(1) scale and on the small-deviation scale. The following example is notably more general than that in Example 1.5 . Example B.1 . (Perturbed band matrix: improved upper bound for spectral radius) Fix c\in(0,1) . Consider an n\times n matrix S^{\prime}:=S+\Lambda , where S=\frac{1}{\lfloor n^{c}\rfloor}\operatorname{Adj}(G) and \operatorname{Adj}(G) is the adjacency matrix of a \lfloor n^{c}\rfloor -regular directed graph G on n vertices. Let \Lambda be an n\times n matrix with nonnegative entries, having at most n^{d} (d\leq c) nonzero entries \Lambda_{1},\cdots,\Lambda_{n^{d}}, and we assume 0<\Lambda_{i}\leq Dn^{-c} for some fixed constant D>0 and for each i=1,\cdots,n^{d} . Then the largest row sum of S satisfies \sup_{i}\sum_{j}[S^{\prime}]_{ij}\leq 1+Dn^{-d-c}, and equality holds with the largest row sum equal to 1+Dn^{d-c}\leq 1+D in the extreme case where each \Lambda_{i} lies on the same row and \Lambda_{i}=Dn^{-c} for each i . Let us assume that all the entries \Lambda_{i} lie on the 1-th row of S^{\prime} , and that none of the \Lambda_{i} ’s lie on the diagonal entry of S^{\prime} . In this case, we have the computation: for any fixed i_{0}\in[n]\setminus\{1\} : (B.1) \displaystyle\sum_{i_{1},\cdots,i_{k}\in[n]} \displaystyle(S^{\prime})_{i_{0}i_{1}}(S^{\prime})_{i_{1}i_{2}}\cdots(S^{\prime})_{i_{k-1}i_{k}} \displaystyle\leq\sum_{i=0}^{k}C_{k}^{i}(Dn^{-c})^{i}n^{-c(k-i)}(n^{c})^{k-2i}n^{di}\leq(1+Dn^{d-2c})^{k}. where the label i labels the number of terms in the expansion of (S^{\prime})^{k} coming from entries in \Lambda , C_{k}^{i} is the combinatorial factor of the choice in [k] for terms come from \Lambda . The term n^{di} arises as there are at most n^{d} elements in \Lambda , so we have at most n^{d} choices of column label for an element from \Lambda . Finally the (n^{c})^{k-2i} factor arises because we have fixed i elements from \Lambda , but the fact that each \Lambda_{i} lies on the same row and none of the \Lambda_{i} is on the diagonal imply that they cannot be consecutive terms in the product of (S^{\prime})^{k} , so we have already fixed 2i free vertices. (The assumption that i_{0}\neq 1 ensures that all terms from \Lambda^{\prime} appear as the form (S^{\prime})_{i_{r}i_{r+1}} for some r\geq 1 , so we have a loss of two free vertices.). Thus, there are only k-2i remaining free vertices to be chosen, each having at most n^{c} choices thanks to the regular digraph structure imposed on S . This also implies i\leq k/2 , but we still take the sum over i\leq k as each term is non-negative. From this computation, and the fact that none of the \Lambda_{i} lies on the diagonal, we see that (B.2) \sum_{i_{1}\cdots,i_{k}\in[n]}(S^{\prime})_{1i_{1}}\cdots(S^{\prime})_{i_{k-1}i_{k}}\leq(1+Dn^{d-c})(1+Dn^{d-2c})^{k-1}\leq(1+D)(1+Dn^{d-2c})^{k-1}. A similar computation also applies to the long-time control of (S^{t})^{k} . From the above computations ( B.1 ), ( B.2 ) we see that 1+Dn^{d-2c} , instead of 1+Dn^{d-c} , should be the better estimate for \rho(X) . When d=c , by taking D large we create a family of variance profiles with arbitrarily large row sum but still \rho(X)\leq 1+o(1) thanks to Theorem 1.6 , as well as a small deviation estimate \rho(X)\leq(1+Dn^{-c})(1+\frac{\log n}{n^{c/2}}) with very high probability. When d0 , and A=(a_{ij}) where a_{ij}\sim\frac{1}{\sqrt{d_{n}}}g for a standard Gaussian variable g whenever 0<|i-j|d_{n} , and a_{ii}=\frac{1}{\sqrt{d_{n}}}\xi , where \xi is a symmetric, mean 0, variance 1 random variable with \mathbb{P}(|\xi|^{\frac{1-c}{2}}\geq t)\sim t^{-1} . Denote by A_{o} the matrix from A setting all diagonal entries 0, and A_{d} the diagonal part of A . By the main result of this paper, we have \rho(A_{o})\leq 1+o(1) with high probability. However, we also have \|A_{d}\|>1 with non-vanishing probability, and since A_{d} is diagonal, the eigenvalues of A_{d} away from [-1,1] can be proven to converge to a Poisson process in the large n limit. We can write A=A_{o}+A_{d} and regard A as a (growing) rank perturbation of the matrix A_{o} . Recently [ 33 ] characterized the outliers of perturbed non-Hermitian band matrices, and (although that result does not immediately apply here as A_{d} has growing rank, we expect an analogous result can be proven with additional effort), we can formally deduce that outlying eigenvalues of A_{0}+A_{d} correspond with eigenvalues of A_{d} outside [-1,1] , and hence with non-vanishing probability, \rho(A)\to 1+o(1) does not hold. Appendix C Non-symmetric entry distributions In this section we prove Theorem 2.3 on non-symmetric distributions. The notations and constructions in the proof will be used repeatedly in the proof of Theorem 1.6 for non-symmetric entry distributions. Proof of Theorem 2.3 . We again consider the summation of monomial expansions \mathbb{E}[x_{i_{0}i_{1}}x_{i_{1}i_{2}}\cdots x_{i_{p-1}i_{p}}\bar{x}_{i_{p+1}i_{p}}\cdots\bar{x}_{i_{0}i_{2p-1}}] over a closed path \mathcal{P}=(i_{0},i_{1},i_{2},\cdots i_{p},i_{p+1},\cdots i_{2p-1},i_{0}) of length 2p . Since x_{ij} are centered each directed edge (i,j) must exist at least twice in \mathcal{P} in the sense specified in the proof of Theorem 2.2 , but as x_{ij} may not be symmetric, the edge i\mapsto j can appear an odd number of times: if this is the case then we call this edge an odd directed edge. Since 2p is even, the number of odd directed edges must be even. We will adapt the argument in [ 45 ] for Wigner matrices, to define a gluing procedure which takes as an input a path \mathcal{P} with length 2p and 2\ell odd edges, and outputs a math \mathcal{P}^{\prime} of length 2p-2\ell having the same set of edges as \mathcal{P} except that the last time of occurrence of each odd edge in \mathcal{P} is removed. Thus each directed edge in \mathcal{P}^{\prime} is traveled an even number of times, but \mathcal{P} is not necessarily a closed path: it can be disjoint union of connected paths. For such an input math \mathcal{P} , the moment of the last occurrence of the odd edge is a subset of \{1,2,\cdots,2p\} , which can be written in a union of J ( 1\leq J\leq 2\ell ) disjoint intervals on \mathbb{Z} . Then the set of odd edges is split into J subsequences S_{i},i=1,\cdots,J . We denote by e_{i} ( f_{i} ) the left (right) endpoints of S_{i} and f_{0}=e_{J+1}=i_{0} with i_{0} the initial point of \mathcal{P} . Finally, for i=0,\cdots,J let \mathcal{P}_{i} be the subpath starting at f_{i} and ending at e_{i+1} . From these subpaths \mathcal{P}_{i} we construct a graph G with vertices \{e_{i},f_{i}:i=0,\cdots,J\} , where an edge is present from v_{i} to v_{j} if there is a path \mathcal{P}_{k} admitting v_{i},v_{j} as endpoints. We denote \mathcal{L}:=\{e_{i},f_{i};0\leq i\leq J\} . Let I^{\prime}\leq J be the number of connected components of G . From this graph we can reconstruct the paths as follows: first read \mathcal{P}_{0} until we reach the endpoint e_{1} , then choose a subpath \mathcal{P}_{i_{1}} with e_{1} as endpoint: we read \mathcal{P}_{i_{1}} in the forward direction if e_{1} is the left endpoint of \mathcal{P}_{i_{1}} and in the backward direction otherwise. Then we find \mathcal{P}_{i_{2}} whose endpoint coincides with the right endpoint of \mathcal{P}_{0}\cup\mathcal{P}_{i_{1}} , until the constructed subpath \mathcal{P}_{0}\cup\mathcal{P}_{i_{1}}\cdots\cup\mathcal{P}_{i_{k}} is a closed path. Then if i_{0} is the endpoint of some \mathcal{P}_{j} which hasn’t been glued we glue \mathcal{P}_{j} in the direction where i_{0} is the starting point, and restart the gluing procedure. After this, we find the first path \mathcal{P}_{i} not glued before (whose left end point must have occurred in \mathcal{P}_{0}\cup\cdots\cup\mathcal{P}_{i_{k}} ), and we continue the gluing procedure starting from \mathcal{P}_{i} . This produces a sequence of I_{0}\geq I^{\prime} closed paths \widetilde{W}_{i},0\leq i\leq I_{0}-1 with origins v_{i_{j}}\in\mathcal{L},j=1,\cdots,I_{0}-1,v_{i_{0}}=i_{0}. Then we reconstruct the path \mathcal{P}^{\prime} from the paths \widetilde{W}_{i} : we can order the \widetilde{W}_{i} in an arbitrary way so long as we start from \mathcal{P}_{0}, read all the edges with origin v_{1} and concatenate them to get the path W_{1} , etc. Then we get a sequence of paths W_{1},\cdots,W_{I-1} and finally define \mathcal{P}^{\prime} by concatenating the paths W_{i},0\leq i\leq I-1 , where \mathcal{P}^{\prime} is possibly disconnected. The order of reading W_{i}^{\prime}s in \mathcal{P}^{\prime} will not be relevant: what matters is that the origin of W_{i} is a marked vertex of \mathcal{P}^{\prime} and pairwise distinct. Then there are three possible cases for the path \mathcal{P} : (A), the gluing yields a genuine closed even path \mathcal{P}^{\prime} (a closed path where each directed edge is traveled an even number of times); (B), the gluing yields a sequence of I\geq 2 closed even paths with respective origins \{i_{0},v_{i},1\leq i\leq I-1\}, each v_{i} an odd index of \mathcal{P}^{\prime} (recall the proof of Theorem 2.2 for definition of an odd index, which is an analogue of marked vertex in [ 45 ] ); or (C) the gluing yields I\geq 2 paths, with some of them having an odd directed edge. We now estimate the contribution of case (A) and (B), and show that case (C) is controlled by case (B) or (A). For this we need to recall the insertion procedure defined in [ 45 ] , Section 3.1. First consider the simple case (A), and assume given a closed even path \mathcal{P}^{\prime} of length 2m=2p-2\ell , so we know edges in \mathcal{P}^{\prime} and the orders they are read. First we choose J vertices with at most C_{2m}^{J} choices. This splits \mathcal{P}^{\prime} into J+1 subpaths \mathcal{R}_{i},0\leq i\leq J . \mathcal{R}_{i} and \mathcal{P}_{i} differ only by the order they are read (and possibly the directions they are read): so the number of ways to construct \mathcal{P}_{i} from \mathcal{R}_{i} is J!2^{J} . We find the number of ways to write 2\ell as the sum of J positive integers, which is the way we assign the unreturned edges S_{i} , giving a factor C_{2\ell}^{J} . Finally, take an ordered collection of 2\ell-J edges from the edges in \mathcal{P}^{\prime} : this is given in \frac{(2m)!}{(2m-2\ell+J)!} methods: we only need 2\ell-J instead of 2\ell edges as the endpoints of each S_{i} are known a priori. Finally we need to take into account the weight \mathbb{E}\left[\prod_{j=0}^{p-1}\frac{x_{i_{j}i_{j+1}}}{\sqrt{n}}\prod_{j=p}^{2p-1}\frac{\overline{x}_{i_{j+1}i_{j}}}{\sqrt{n}}\right] , which evaluated along path \mathcal{P} will differ from that along \mathcal{P}^{\prime} by a factor depending on the sub-exponential moments of x_{ij} . This contribution cannot be bounded separately but has to be bounded taken account of weights on the double path \mathcal{P}^{\prime} . As the gluing procedure adds multiplicity at most one to the edges in \mathcal{P}^{\prime} , we only need to replace in equation ( 2.2 ) each term (\text{const}\cdot k)^{k} by (\text{const}\cdot k)^{k+1} to account for the additional weight, where the constant in the equation may change from line to line. In the worst case scenario we would have to consider (recall m=p-\ell , and \sum_{k\geq 1}kn_{k}=m ) (C.1) \hat{T}_{m}(n_{1},\cdots,n_{p}):=n\frac{1}{n^{m}}\frac{n!}{n_{0}!n_{1}!\cdots n_{p}!}\frac{m!}{\prod_{k=2}^{m}(k!)^{n_{k}}}\prod_{k=2}^{p}(2k)^{kn_{k}}\prod_{k=2}^{s}(\text{const}\cdot k)^{(k+1)n_{k}}\cdot 4^{\sum_{k\geq 2}kn_{k}}, which amounts to increasing the multiplicity of each edge in \mathcal{P}^{\prime} by one. Via a similar computation as in ( 2.6 ) we have \sum_{k=2}^{p}\frac{(\text{const}\cdot p)^{k}k^{k+1}}{n^{k-1}}\leq\frac{1}{4} whenever p\leq C_{0}\sqrt{n} for some fixed small constant C_{0}>0 depending only on the sub-exponential moments of x_{ij} . We get the following estimate, where C_{1}<\frac{1}{4} : \sum_{\sum_{k\geq 2}n_{k}>0}\widehat{T}_{m}(n_{1},\cdots,n_{p})\leq C_{1}n,\quad\widehat{T}_{m}(m,0,\cdots,0)\leq C_{1}n, and that \widehat{T}_{m}:=\sum_{n_{1},\cdots,n_{k}\geq 0:\hskip 8.19447pt\sum_{k\geq 0}n_{k}=n,\hskip 8.19447pt\sum_{k\geq 0}kn_{k}=m}\widehat{T}_{m}(n_{1},n_{2},\cdots,n_{p})\leq 2C_{1}n. Combining with the gluing procedure, we see that the contribution by paths \mathcal{P} with I=1 , \ell>0 is given by \displaystyle\sum_{\ell=1}^{m}\widehat{T}_{p-\ell}\sum_{J=1}^{2\ell}C_{2p-2\ell}^{J}J!2^{J}C_{2\ell}^{J}\frac{(2p-2\ell)!}{(2p-4\ell+J)!}n^{-\ell} \displaystyle\leq 2C_{1}n\cdot\sum_{\ell=1}^{p-1}\left(\frac{\text{const}(p-\ell)}{\sqrt{n}}\right)^{2\ell}\leq 4C1C_{0}^{2}n provided that p\leq C_{0}\sqrt{n} . Thus contributions of \mathcal{P} of class (A) is O(n) . For paths \mathcal{P} of class (B), we follow the ideas of [ 45 ] , Section 3.1.2. Assume the closed even paths corresponding to the I\geq 2 clusters have lengths 2s_{i},i=1,\cdots,I-1 . Each s_{i}>0 and \sum_{i=0}^{I-1}2s_{i}=2p-2\ell . Again we write these closed even paths by W_{i},i=0,\cdots,I-1 . The first closed even path makes a contribution computable by Theorem 2.2 . As previously noted, the starting points of W_{1},\cdots,W_{i-1} are odd indices of \mathcal{P}^{\prime} , so that their origins can be chosen in C_{2p-2\ell}^{I-1} ways and the order of choice is irrelevant to the insertion procedure. Then we need to choose J-(I-1) vertices from vertices in \mathcal{P}^{\prime} : they give the endpoints of the odd edges S_{1},\cdots,S_{J} and the number of choice is \binom{2p-2\ell-I+1}{J-I+1} . The choice of all these J vertices splits the path into subpaths \mathcal{R}_{i},i=1,\cdots,J and \mathcal{P}_{i} differ from \mathcal{R}_{i} only by ordering and directions. The contribution of such paths is upper bounded by (C.2) \displaystyle\sum_{\ell=1}^{p-1}\sum_{J=1}^{2\ell}2^{J}J!\binom{2\ell}{J}\frac{(2p-2\ell)!}{(2p-4\ell+J)!}n^{-\ell}\sum_{I=2}^{J}\binom{2p-2\ell}{I-1}\binom{2p-2\ell-I+1}{J-I+1} \displaystyle\times\sum_{s_{0},\cdots,s_{I-1}:\sum_{i}s_{i}=2p-2\ell}n\prod_{i=0}^{\ell-1}(\frac{\widehat{T}_{n}}{n}), where we consider \frac{\widehat{T}}{n} because the origin of the path has been fixed. In the above computation we assume the W_{i} ’s do not share an edge (if they share an edge, then we have one fewer vertex resulting in a factor n^{-1} , which compensates the higher moment factor k we gain, so all such contributions are negligible). Noting that \binom{2p-2\ell}{I-1}\binom{2p-2\ell-I+1}{J-I+1}\leq 2^{J}\binom{2p-2\ell}{J}, we see that ( C.2 ) is O(n) , so contributions from case (B) is O(n) . Finally consider case (C). For this we need an additional gluing procedure that can be found in the beginning of [ 45 ] , Section 2.2. Denote by \widetilde{i} the smallest index such that W_{\widetilde{i}} has an odd edge, and \widetilde{e} (resp. t_{\widetilde{e}} ) the first occurrence (resp. the instance of first occurrence) of an odd edge in W_{\widetilde{i}} . Let \widetilde{j} be the first instant where W_{\widetilde{j}} also has the edge \widetilde{e} , and t^{\prime}_{\widetilde{e}} is the instance of first appearance of \widetilde{e} in W_{\widetilde{j}} . If the selected occurrence of \widetilde{e} has opposite directions in W_{\widetilde{i}},W_{\widetilde{j}} , then we can glue the two paths to define W_{\tilde{i}}\vee W_{\widetilde{j}} via first reading the t_{\widetilde{e}}-1 edges of W_{\widetilde{i}} , switch to W_{\widetilde{j}} , read edges of W_{\widetilde{j}} from the instant t_{\widetilde{e}}+1 until end of W_{\widetilde{j}} . Then we restart at the origin of W_{\widetilde{j}} until (not including) the occurrence of \widetilde{e} , switch to W_{\widetilde{i}} , and read its edges until the end. The formed path W_{\tilde{i}}\vee W_{\widetilde{j}} is obtained via removing occurrence of \widetilde{e} twice. If the occurrence of \widetilde{e} has same direction then we proceed similarly with the gluing, but we read edges in W_{\widetilde{e}} in reverse direction. We continue the procedure until we end up with I-I_{1} closed even paths, and I_{1} iterations of the gluing procedure result in a loss of 2I_{1} occurrences of edges. The final length of the path \mathcal{P}^{\prime} is 2p-2\ell-2I_{1}. Let D_{j},j=0,\cdots,I-I_{1}-1 denote the closed even paths thus defined, so it has total length 2p-2\ell-2I_{1} . To reconstruct the paths we record (i) the I_{1} moments we remove the I_{1} marked edges; (ii) the length and (iii) origins of all these I_{1} paths when the switch occurs. The number of preimages, times the multiplicative factor K/\sqrt{n} contributed by the erased edges, is bounded by (for sufficiently small C_{0}>0 ) \binom{2p}{I_{1}}\times(\frac{\text{const}\times s^{2}}{n})^{I_{1}}\leq 10^{-2}\binom{2p}{I_{1}},\quad s\leq C_{0}\sqrt{n}, and this is enough to show the contribution from case (C) is bounded by contribution from case (A) or case (B). More precisely, assume that I-I_{1}>1 and we reduce to case (B) (reduction to case (A) when I-I_{1}=1 is analogous). Suppose that D_{i} is obtained by gluing I_{i}^{\prime}+1 paths, we only need to bound (C.3) \displaystyle\sum_{\ell=1}^{p-1}\sum_{J=1}^{2\ell}2^{J}J!\binom{2\ell}{J}(\frac{\text{const}}{n})^{\ell}\frac{(2p-2\ell)!}{(2p-4\ell+J)!}\sum_{I=2}^{J}\binom{2p-2\ell-I+1}{J-I+1}\sum_{I_{1}=1}^{I-1}\binom{2p-2\ell}{I-I_{1}-1} \displaystyle\times\sum_{\sum_{i}s_{i}^{\prime}=2p-2\ell-2I_{1}}n\prod_{i=0}^{I-I_{1}-1}\binom{2s_{i}^{\prime}}{I_{i}^{\prime}}\frac{\widehat{T}_{2s_{i}^{\prime}}}{n}(\frac{s_{i}^{2}}{n})^{I_{i}^{\prime}}. This expression comes from replacing the terms \binom{2p-2\ell}{I-1} in expressions in case (B) (or (A)) ( C.2 ) by the left hand side of the following expression \binom{2p-2\ell}{I-I_{1}-1}\sum_{I_{0}^{\prime},I_{1}^{\prime},\cdots}\prod_{i=0}^{I-I_{1}-1}(\frac{s_{i}^{2}}{n})^{I_{1}^{\prime}}\binom{2s_{i}^{\prime}}{I_{i}^{\prime}}\leq\binom{2p-2\ell}{I-1}(\frac{p^{2}}{n})^{I_{1}}\text{const}^{\ell}, we see that whenever we choose C_{0}>0 sufficiently small, then for all p\leq C_{0}\sqrt{n} , the contribution from case (C) as in the expression ( C.3 ) is bounded by a constant multiple of the contribution from case (A) or (B). This completes the proof of the theorem. ∎ Funding The author is supported by a Simons Foundation Grant (601948, DJ)