Marchenko–Pastur law and sample-covariance edge bounds

First fix a deterministic complex symmetric matrix $A$. Since $A_{ji}=A_{ij}$, ${\xi }^{\mathsf{T}}A\xi -\mathrm{tr}A={\sum }_i{A}_{ii}({\xi }_i^2-1)+2{\sum }_{i<j}{A}_{ij}{\xi }_i{\xi }_j\mathrm{.}$ The diagonal summands have mean zero. Distinct diagonal summands are uncorrelated; a diagonal summand and an off-diagonal summand are uncorrelated because at least one independent centered coordinate occurs to the first power; and two off-diagonal summands are uncorrelated unless their unordered index pairs coincide. Therefore $\mathbb{E}{\mid {\xi }^{\mathsf{T}}A\xi -\mathrm{tr}A\mid }^2=({\mu }_4-1){\sum }_i\mathrm{\mid }{A}_{ii}{\mathrm{\mid }}^2+4{\sum }_{i<j}\mathrm{\mid }{A}_{ij}{\mathrm{\mid }}^2\le C_{{\mu }_4}{\sum }_{i,j}\mathrm{\mid }{A}_{ij}{\mathrm{\mid }}^2\mathrm{.}$ Here ${\mu }_4\ge 1$ follows from $\mathbb{E}{\xi }_i^2=1$ and Cauchy–Schwarz.

By [F2], the joint law of $(\xi ,A)$ is the product of its marginal laws. The integrand is integrable: $\mathrm{\mid }{\xi }^{\mathsf{T}}A\xi -\mathrm{tr}A{\mathrm{\mid }}^2\le 2\mathrm{\parallel }A{\mathrm{\parallel }}_F^2\mathrm{\parallel }\xi {\mathrm{\parallel }}_2^4+2d\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$, and $\mathbb{E}\mathrm{\parallel }\xi {\mathrm{\parallel }}_2^4<\mathrm{\infty }$ because $d$ is finite and $\mathbb{E}{\xi }_i^4<\mathrm{\infty }$. Thus [F3] permits integration of the deterministic inequality in step 1.1 against the law of $A$, giving the asserted bound.

By [F1], write $B=U\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)U^{\mathsf{T}}$ with ${\lambda }_j\ge 0$. Thus $R$ exists, is normal, and $x^{\mathsf{T}}Rx={\sum }_j\frac{(U^{\mathsf{T}}x{)}_j^2}{{\lambda }_j-z},\mathrm{Im}(x^{\mathsf{T}}Rx)=\eta {\sum }_j\frac{(U^{\mathsf{T}}x{)}_j^2}{({\lambda }_j-u{)}^2+{\eta }^2}\mathrm{.}$ If $x\mathrm{\ne }0$, this imaginary part is strictly positive, so $1+x^{\mathsf{T}}Rx\mathrm{\ne }0$; if $x=0$, the denominator is $1$.

Direct multiplication verifies $(B+x{x}^{\mathsf{T}}-zI)(R-\frac{Rx{x}^{\mathsf{T}}R}{1+x^{\mathsf{T}}Rx})=I\mathrm{.}$ Since $B+x{x}^{\mathsf{T}}$ is also real symmetric and $z\mathrm{\notin }\mathbb{R}$, its resolvent exists; hence the displayed expression is $R_x$.

Taking traces in step 2.1 gives $\mathrm{tr}(R_x-R)=-\frac{x^{\mathsf{T}}{R}^{2}x}{1+x^{\mathsf{T}}Rx}\mathrm{.}$ In the eigenbasis of [F1], $\mathrm{\mid }{x}^{\mathsf{T}}{R}^{2}x\mathrm{\mid }\le {\sum }_j\frac{(U^{\mathsf{T}}x{)}_j^2}{({\lambda }_j-u{)}^2+{\eta }^2}=\frac{\mathrm{Im}(x^{\mathsf{T}}Rx)}{\eta }\mathrm{.}$ Also $\mathrm{\mid }1+x^{\mathsf{T}}Rx\mathrm{\mid }\ge \mathrm{Im}(x^{\mathsf{T}}Rx)$ when $x\mathrm{\ne }0$; for $x=0$ the trace difference is zero. Combining these inequalities proves the stated $1\mathrm{/}\eta$ bound.

If $C\le 0$ the claim is vacuous. Suppose $C>0$, set $v=E{Z}_{11}^2$ and fix $\epsilon >0$. For a dyadic integer $m=2^{\mathrm{\ell }}$ put $N=2m$, $I=\lceil 2Cm\rceil$, $x=\epsilon m$, $r=4$ and $y=x\mathrm{/}r$. For one row write $Z_j=Z_{ij}$ and $W_j=Z_j{\mathbf{1}}_{\{Z_j\le y\}}$. These variables are independent with $E{W}_j=-E[Z_j{\mathbf{1}}_{\{Z_j>y\}}]\le 0$ and $E{W}_j^2\le v$. For $t>0$ and $w\le y$, $e^{tw}\le 1+tw+(e^{ty}-1-ty)w^2\mathrm{/}{y}^2$: the function $(e^u-1-u)\mathrm{/}{u}^2={\int }_0^1(1-s)e^{su}ds$, extended continuously at zero, is increasing in $u$. Consequently $E{e}^{t{W}_j}\le \exp \{v(e^{ty}-1-ty)\mathrm{/}{y}^2\}$.

Set $\psi =v(e^{ty}-1-ty)\mathrm{/}{y}^2\ge 0$. Independence shows that $M_k=\exp (t{\sum }_{j\le k}{W}_j-k\psi )$ has conditional expected next value at most $M_k$. If $\tau$ is the first $k\le N$ with ${\sum }_{j\le k}{W}_j\ge x$, stopping this finite sequence at $\tau$ or $N$ preserves the expectation bound $1$: condition each increment and observe that the indicator of not having stopped is determined by the preceding variables. On a crossing its stopped value is at least $e^{tx-N\psi }$. Nonnegativity therefore gives $P({\max }_{k\le N}{\sum }_{j\le k}{W}_j\ge x)\le e^{-tx+N\psi }$. This proves the needed maximal bound directly.

If $v=0$, every $Z_j=0$ almost surely and the conclusion follows. Otherwise choose $t>0$ by $e^{ty}=1+xy\mathrm{/}(Nv)$. Then $N\psi \le x\mathrm{/}y=r$, so the preceding probability is at most $e^r(Nv\mathrm{/}(xy){)}^r\le K{m}^{-r}$, with $K$ depending only on $v,\epsilon$. On the event that all $Z_j\le y$, the original and truncated partial sums agree; the complement has probability at most $NP(Z_{11}>y)$. Thus the positive original maximal tail is at most $NP(Z_{11}>y)+K{m}^{-r}$. Apply the same argument to $-Z_j$ for the negative tail and use a union bound over the $I$ rows. The result is $P({\max }_{i\le I,k\le N}\mid {\sum }_{j\le k}{Z}_{ij}\mid \ge \epsilon m)\le K_C{m}^{2}P(\mathrm{\mid }{Z}_{11}\mathrm{\mid }>\epsilon m\mathrm{/}4)+K_C^{\mathrm{\prime }}{m}^{1-r}\mathrm{.}$

The right-hand side is summable over dyadic $m$: for every $a>0$, ${\sum }_{\mathrm{\ell }}{2}^{2\mathrm{\ell }}P(\mathrm{\mid }{Z}_{11}\mathrm{\mid }>a{2}^{\mathrm{\ell }})\le K_{a}E\mathrm{\mid }{Z}_{11}{\mathrm{\mid }}^2<\mathrm{\infty }$, by summing the finite geometric progression ${\sum }_{\mathrm{\ell }:a{2}^{\mathrm{\ell }}<\mathrm{\mid }{Z}_{11}\mathrm{\mid }}{2}^{2\mathrm{\ell }}$ under expectation. Also ${\sum }_{\mathrm{\ell }}{2}^{(1-r)\mathrm{\ell }}<\mathrm{\infty }$. First Borel–Cantelli gives the displayed maximal estimate eventually on each dyadic block. Whenever $m\le n\le 2m$, every $i\le Cn$ and $k\le n$ occurs in the corresponding block; division by $n\ge m$ bounds the desired ratio by $\epsilon$ eventually. Intersecting over positive rational $\epsilon$ proves convergence to zero. Exchanging the two coordinates preserves the iid law and gives the column version.

First replace $\xi$ by any bounded centered real iid entry $\eta$, of variance $v\ge 0$. For a fixed integer $k\ge 1$, set $T_{n,k}=\frac{1}{n}\mathrm{Tr}{\left(\frac{Y_n{Y}_n^T}{n}\right)}^k=\frac{1}{n^{k+1}}{\sum }_{i_1,\dots ,i_k\le n}{\sum }_{j_1,\dots ,j_k\le p_n}{\prod }_{\mathrm{\ell }=1}^k{\eta }_{i_{\mathrm{\ell }}{j}_{\mathrm{\ell }}}{\eta }_{i_{\mathrm{\ell }+1}{j}_{\mathrm{\ell }}},i_{k+1}=i_1\mathrm{.}$

Each summand is a length-$2k$ closed alternating walk on a bipartite graph: row labels and column labels are disjoint vertex types, and each distinct pair $(i,j)$ is an edge. Its graph is connected. An edge occurring once makes its expectation zero, by centering and independence. Every surviving walk therefore has at most $k$ distinct edges and at most $k+1$ vertices. There are finitely many equality patterns of the $2k$ vertex positions, with a bound depending only on $k$. A pattern with $r$ row and $s$ column vertices has exactly $(n{)}_r(p_n{)}_s$ injective labelings, and its summand expectations are uniformly bounded. Consequently, every pattern with $r+s\le k$ contributes $O(n^{-1})$ after normalization.

A pattern with $k+1$ vertices has exactly $k$ edges, its graph is a tree, and every edge is traversed exactly twice. The closed walk traverses each tree edge once in each direction. The order in which it first enters the children of each vertex makes this tree a rooted ordered tree, rooted at a row vertex. Conversely the contour walk of every such ordered tree supplies exactly one canonical equality pattern. This is a bijection: on a tree an edge cannot be left behind before its whole descendant excursion is completed, since that would force a third traversal. If the tree has $s$ odd-depth (column) vertices, its limiting labeling weight is ${\gamma }^s$, and its expectation is $v^k$.

For completeness, the tree count can be extracted without any random-matrix theorem. Let $R(z)$ count ordered trees rooted at a row, with an edge contributing $z$ and each column vertex contributing $\gamma$. Let $C(z)$ count column-rooted trees with the same weights, including the root-column weight. The ordered list of subtrees gives, as formal power series, $R=\frac{1}{1-zC},C=\frac{\gamma }{1-zR}\mathrm{.}$

Writing $H=R-1$, these equations give $C=\gamma +H$ and $H=z(1+H)(\gamma +H)\mathrm{.}$

The formal coefficient identity for $H=z\mathrm{\Phi }(H)$ is $[z^k]H=\frac{1}{k}[u^{k-1}]\mathrm{\Phi }(u{)}^k\mathrm{.}$

One direct verification uses formal residues: substitute $z=u\mathrm{/}\mathrm{\Phi }(u)$ into $\mathrm{Res}H(z)z^{-k-1}dz$. The resulting residue is $\mathrm{Res}(u^{-k}{\mathrm{\Phi }}^k-u^{-k+1}{\mathrm{\Phi }}^{k-1}{\mathrm{\Phi }}^{\mathrm{\prime }})du$; the second coefficient is $(k-1)\mathrm{/}k$ times the first, by differentiating ${\mathrm{\Phi }}^k$. This proves the identity, including $k=1$. Applying it gives ${\mu }_k(\gamma )=[z^k]H={\sum }_{s=1}^k\frac{1}{k}\left(\genfrac{}{}{0px}{}{k}{s}\right)\left(\genfrac{}{}{0px}{}{k}{s-1}\right){\gamma }^s\mathrm{.}$

Thus $E{T}_{n,k}⟶v^k{\mu }_k(\gamma )\mathrm{.}$ This explicitly counts all leading patterns, and the argument above bounds all nonleading patterns. It does not assume a spectral limit.

For a label assignment $w$, let $M_w$ be its walk monomial and $Z_w=M_w-E{M}_w$. Expand the fourth centered moment as a sum of $E(Z_{w_1}{Z}_{w_2}{Z}_{w_3}{Z}_{w_4})$, with normalization $n^{-4k-4}$.

Join two of the four walks when their sets of matrix entries share an edge. A walk isolated in this graph is independent of the other three monomials, so its centered factor makes the expectation zero. Therefore every surviving configuration has at most two clusters of walks. Each cluster has a connected union graph because its walks are individually connected and consecutive walks in the cluster share an edge.

Moreover, no matrix-entry edge can occur just once in the total $8k$ factors. Indeed, if that edge occurs in $M_{w_t}$, then $E{M}_{w_t}=0$, so $Z_{w_t}=M_{w_t}$, and conditioning on all other entries makes the expectation zero. Thus a surviving configuration has at most $4k$ distinct edges. Its number of distinct vertices is at most the sum over its clusters of (edges plus one), hence at most $4k+2$. Sharing vertices between different edge-clusters only reduces this bound.

There are finitely many patterns at this fixed $k$. Bounded entries bound every centered product expectation by a constant depending only on $k$ and the entry bound. With $p_n=O(n)$, the count of labelings is $O(n^{4k+2})$. Therefore $E\mathrm{\mid }{T}_{n,k}-E{T}_{n,k}{\mathrm{\mid }}^4=O(n^{-2})\mathrm{.}$

Markov's inequality and the first Borel–Cantelli lemma show $T_{n,k}-E{T}_{n,k}\to 0$ almost surely. Intersecting over all integer $k\ge 1$ proves simultaneous fixed-degree trace convergence for bounded entries. Neither independence between different $n$ nor a monotone sequence $p_n$ was assumed.

Rectangular strong law. For every integrable iid nonnegative array $Z_{ij}$, $\frac{1}{n^2}{\sum }_{i\le n,j\le p_n}{Z}_{ij}⟶\gamma EZ\text{almost surely}\mathrm{.}$

To prove this, for each positive rational $t$ enumerate the cells of the nested rectangles $[m]\times [\lfloor tm\rfloor ]$ in their successive increments. This is an enumeration of the whole quadrant, so the ordinary one-dimensional iid strong law applies at the rectangle cardinalities. It gives the limit $tEZ$ after division by $m^2$. Intersect these probability-one events over rational $t$. Bracket $p_n\mathrm{/}n$ between rationals $t_{-}<\gamma <t_{+}$ and use nonnegativity, then let $t_{\pm }\to \gamma$. This proof accommodates arbitrary $p_n\mathrm{/}n\to \gamma$.

Singular-value comparison. For two real rectangular matrices $A,B$ of the same dimensions, pad their ordered singular-value lists with zeros to length $n$ when forming $A{A}^T,B{B}^T$. Then ${\sum }_{i=1}^n(s_i(A)-s_i(B){)}^2\le \mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2\mathrm{.}$ Here is an elementary proof of the underlying comparison. For symmetric matrices $U,V$ of dimension $d$ with ordered eigenvalues $\alpha ,\beta$, orthogonal diagonalization expresses $\mathrm{Tr}(UV)$ as ${\sum }_{ij}{\alpha }_i{\beta }_j{d}_{ij}$, where $d_{ij}$ is the square of an orthogonal overlap and its row and column sums are one. For descending real sequences, this sum is at most ${\sum }_i{\alpha }_i{\beta }_i$: set $c_i={\sum }_j{d}_{ij}{\beta }_j$; the sum of its first $r$ entries is at most the sum of the first $r$ entries of $\beta$, because the associated column weights lie in $[0,1]$ and sum to $r$. Summation by parts against descending $\alpha$, with equal total sums, proves the assertion. Expanding $\mathrm{Tr}(U-V{)}^2$ now bounds it below by ${\sum }_i({\alpha }_i-{\beta }_i{)}^2$. Apply this result to the symmetric dilations $\left(\begin{array}{cc}0& A\\ A^T& 0\end{array}\right),\left(\begin{array}{cc}0& B\\ B^T& 0\end{array}\right)\mathrm{.}$

Their eigenvalues are the singular values, their negatives, and the required zeros. Both sides acquire a factor two, proving the comparison.

For $k\ge 1$, the scalar factorization and Cauchy–Schwarz consequently give $\mid \frac{1}{n}{\sum }_i{s}_i^{2k}-\frac{1}{n}{\sum }_i{t}_i^{2k}\mid \le 2k{\left(\frac{\mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2}{n}\right)}^{1\mathrm{/}2}{[\frac{2}{n}{\sum }_i(s_i^{4k-2}+t_i^{4k-2})]}^{1\mathrm{/}2}\mathrm{.}$ Indeed $\mathrm{\mid }{s}^{2k}-t^{2k}\mathrm{\mid }\le 2k\mathrm{\mid }s-t\mathrm{\mid }(s^{2k-1}+t^{2k-1})$ for nonnegative $s,t$; squaring the last parenthesis is bounded by twice the sum of the squares. This inequality needs no operator-norm bound on $B$.

For integer $K\ge 1$, put $m_K=E[\xi {\mathbf{1}}_{\mathrm{\mid }\xi \mathrm{\mid }\le K}],{\eta }^{(K)}=\xi {\mathbf{1}}_{\mathrm{\mid }\xi \mathrm{\mid }\le K}-m_K,v_K=E({\eta }^{(K)}{)}^2\mathrm{.}$

Then $0\le v_K\le 1$ and $v_K\to 1$. The residual $r_K=\xi -{\eta }^{(K)}$ has second moment ${\delta }_K^2=E{r}_K^2=E[{\xi }^2{\mathbf{1}}_{\mathrm{\mid }\xi \mathrm{\mid }>K}]-m_K^2⟶0.$

Let $B_n^{(K)}$ be the normalized matrix of these bounded centered entries, constructed from the same original array. On one probability-one event, phases 1–2 give for every integer $K$ and every integer $j\ge 1$ $\frac{1}{n}\mathrm{Tr}(B_n^{(K)}{B}_n^{(K)T}{)}^j⟶v_K^j{\mu }_j(\gamma )\mathrm{.}$

The rectangular strong law, applied to $r_K^2$, also gives simultaneously in $K$ $\frac{1}{n}\mathrm{\parallel }{A}_n-B_n^{(K)}{\mathrm{\parallel }}_F^2⟶\gamma {\delta }_K^2\mathrm{.}$

Intersect this event with the original coarse-norm event. For each outcome in the intersection there is a finite $C$ such that $\mathrm{\parallel }{A}_n\mathrm{\parallel }\le C$ eventually. Thus the $s_i^{4k-2}$ average in the comparison inequality is at most $C^{4k-2}$. The $t_i^{4k-2}$ average converges to $v_K^{2k-1}{\mu }_{2k-1}(\gamma )\le {\mu }_{2k-1}(\gamma )$. Consequently ${\mathrm{lim\hspace{0.17em}sup}}_n\mid \frac{1}{n}\mathrm{Tr}{S}_n^k-v_K^k{\mu }_k(\gamma )\mid \le 2k\sqrt{\gamma }{\delta }_K\sqrt{2(C^{4k-2}+{\mu }_{2k-1}(\gamma ))}\mathrm{.}$

Let $K\to \mathrm{\infty }$. This proves, simultaneously for every fixed positive integer $k$, $\frac{1}{n}\mathrm{Tr}{S}_n^k⟶{\mu }_k(\gamma )\text{almost surely}\mathrm{.}$

In particular $n^{-1}\mathrm{Tr}{S}_n\to \gamma >0$, so eventually there is at least one positive eigenvalue. Every fixed polynomial with zero constant term has its normalized trace limit by linearity. There is no triangular truncation, hidden high-moment assumption, or appeal to an empirical-distribution limit.

Set $c=1+\gamma$, $d=2\sqrt{\gamma }$, so $a=c-d$, $b=c+d$, and define on $(a,b)$ $w(x)=\frac{1}{2\pi }\sqrt{(b-x)(x-a)}\mathrm{.}$

We prove the exact positive-moment identity ${\mu }_k(\gamma )={\int }_a^b{x}^{k-1}w(x)dx(k\ge 1)\mathrm{.}$ This is only an identity for explicit numbers and integrals. No probability measure or spectral support theorem is asserted or used.

For real $z>0$ sufficiently small, substitute $x=c+d\cos \theta$. The generating function of the right-hand side is $z{\int }_a^b\frac{w(x)}{1-zx}dx=\frac{z{d}^2}{2\pi }{\int }_0^{\pi }\frac{{\sin }^2\theta }{1-cz-dz\cos \theta }d\theta \mathrm{.}$

For $u>\mathrm{\mid }v\mathrm{\mid }$, substitution $t=\tan (\theta \mathrm{/}2)$ directly gives ${\int }_0^{\pi }(u-v\cos \theta {)}^{-1}d\theta =\pi \mathrm{/}\sqrt{u^2-v^2}$. Polynomial division in $\cos \theta$ then gives ${\int }_0^{\pi }\frac{{\sin }^2\theta }{u-v\cos \theta }d\theta =\frac{\pi }{v^2}(u-\sqrt{u^2-v^2}),$ with its continuous value when $v=0$. Hence the generating function above equals $\frac{1-cz-\sqrt{(1-cz{)}^2-4\gamma z^2}}{2z}\mathrm{.}$

It is analytic near zero, vanishes there, and solves $H=z(1+H)(\gamma +H)$. The formal equation uniquely determines the coefficients recursively, so these coefficients equal the tree counts of phase 1. Expansion under the integral is justified by the uniformly convergent geometric series on $[a,b]$ for small $z$. This proves the identity, also when $a=0$.

Consequently, for every polynomial $P$ with $P(0)=0$, $\frac{1}{n}\mathrm{Tr}P(S_n)⟶{\int }_a^b\frac{P(x)}{x}w(x)dx\mathrm{.}$

At $a=0$, the quotient is the polynomial obtained by canceling the factor $x$, so there is no singularity to interpret.

Fix $L$ with $0<L<b$. For an integer $q\ge 0$ use $P_q(x)=x^{q+1}(x-L)$. Its trace limit is $I_q={\int }_a^b{x}^q(x-L)w(x)dx\mathrm{.}$

Choose $\max (a,L)<t<u<b$. The positive contribution from $[t,u]$ is at least $t^q(t-L){\int }_t^{u}w(x)dx$. The absolute negative contribution, supported in $[a,L]$ when that interval is nonempty, is at most $L^{q}L{\int }_a^{b}w(x)dx$. Since $t>L$ and $w>0$ on $(a,b)$, $I_q>0$ for some finite integer $q$ (and for all sufficiently large $q$). If $L\le a$, positivity follows directly.

If all eigenvalues of $S_n$ were at most $L$, every summand $P_q(\lambda )$ would be nonpositive, contradicting the eventually positive normalized trace. Thus ${\lambda }_{\max }(S_n)>L$ for all sufficiently large $n$. Intersecting over a countable sequence $L\uparrow b$ gives $\mathrm{lim\hspace{0.17em}inf}{\lambda }_{\max }\ge b$.

Fix $U>a$. If desired replace $U$ by a smaller number in $(a,b)$; proving the stronger bound for that smaller threshold proves the original bound. Thus assume $a<U<b$. Choose a fixed $B>b$ and use the polynomial $Q_q(x)=x(U-x)(B-x{)}^{2q},q\ge 0.$

For every $x\ge 0$, it vanishes at $0$, is nonpositive for $x\ge U$, and is positive for $0<x<U$ except at the irrelevant zero of the even factor. Its trace limit is $J_q={\int }_a^b(U-x)(B-x{)}^{2q}w(x)dx\mathrm{.}$

Choose $a<t<u<U$. The positive contribution on $[t,u]$ is at least $(U-u)(B-u{)}^{2q}{\int }_t^{u}w(x)dx\mathrm{.}$

The absolute negative contribution on $[U,b]$ is at most $(b-U)(B-U{)}^{2q}{\int }_a^{b}w(x)dx\mathrm{.}$

Because $B-u>B-U>0$ and the positive interval has positive integral, $J_q>0$ for some finite integer $q$. If $S_n$ had no positive eigenvalue below $U$, all its eigenvalues would be either $0$ or at least $U$, and therefore $\mathrm{Tr}{Q}_q(S_n)\le 0$. The positive limiting trace excludes this for every sufficiently large $n$. Hence ${\lambda }_{\min }^{}(S_n)<U$ eventually. Let $U\downarrow a$ through a countable sequence to obtain $\mathrm{lim\hspace{0.17em}sup}{\lambda }_{\min }^{}\le a$.

For $\gamma =1$, $a=0$. The same argument chooses $0<t<u<U$ and proves an eventually positive eigenvalue below every prescribed $U>0$. The factor $x$ removes every exact zero eigenvalue, including arbitrary extra rank defects, so no rank theorem or lower-rank estimate is concealed in this case. Since eigenvalues are nonnegative, this also proves ${\lambda }_{\min }^{}\to 0$ in the square-aspect-ratio case.

The matrix $S(X)$ is symmetric because $(X^{\mathsf{T}}X{)}^{\mathsf{T}}=X^{\mathsf{T}}X$. For every $v\in {\mathbb{R}}^p$, $v^{\mathsf{T}}S(X)v=\frac{1}{n}\mathrm{\parallel }Xv{\mathrm{\parallel }}_2^2\ge 0.$ By [F2], its eigenvalues are real; if $S(X)v=\lambda v$ with $v\mathrm{\ne }0$, the displayed quadratic-form identity gives $\lambda \mathrm{\parallel }v{\mathrm{\parallel }}_2^2\ge 0$, hence $\lambda \ge 0$.

Apply [F3] to the finite list ${\lambda }_1(S(X)),\dots ,{\lambda }_p(S(X))$ in the Borel space $\mathbb{R}$. The resulting empirical measure is exactly [F1] and is a Borel probability measure. Step 1.1 shows it assigns no mass outside $[0,\mathrm{\infty })$.

Fix all vectors except $Y_{n,j}$. Replacing that vector by another vector $Y_{n,j}^{\mathrm{\prime }}$ changes $B_n$ by removing $Y_{n,j}{Y}_{n,j}^{\mathsf{T}}$ and adding $Y_{n,j}^{\mathrm{\prime }}(Y_{n,j}^{\mathrm{\prime }}{)}^{\mathsf{T}}$. Applying [F1] once to remove the first term and once to add the second shows that $\mathrm{tr}(B_n-zI{)}^{-1}$ changes by at most $2\mathrm{/}\eta$. Hence each of the real and imaginary parts of $M_n(z)$ has coordinate oscillation at most $c_j=2\mathrm{/}(d_n\eta )$.

Apply [F2] separately to $\mathrm{Re}{M}_n(z)$ and $\mathrm{Im}{M}_n(z)$. If a complex number has modulus greater than $t$, at least one of its real or imaginary parts has magnitude greater than $t\mathrm{/}\sqrt{2}$. The union bound therefore gives $\mathrm{Pr}\{\mathrm{\mid }{M}_n(z)-\mathbb{E}{M}_n(z)\mathrm{\mid }>t\}\le 4\exp (-\frac{t^2{d}_n^2{\eta }^2}{4n})\mathrm{.}$ This is the stated estimate.

Since $d_n\mathrm{/}n\to c>0$, for each fixed $t>0$ the exponent in step 2.1 is at most $-c_{t}n$ for all sufficiently large $n$, for some $c_t>0$. The probabilities are therefore summable.

Apply [F3] to the events in step 3.1 for each $t=1\mathrm{/}k$, $k\ge 1$, and intersect the resulting countable collection of probability-one events. On that event $M_n(z)-\mathbb{E}{M}_n(z)\to 0$.