Universality
The semicircle law describes the limiting empirical distribution of eigenvalues of a normalized Wigner matrix. The limit depends on the entry variance, rather than the full entry distribution. We give two proofs for bounded entries, then remove boundedness by truncation. The first proof counts trace moments; the second derives an equation for the Stieltjes transform.
Let \(\{\xi_{ij}:i<j\}\) be iid complex random variables with \(\mathbb{E}\xi_{12}=0\) and \(\mathbb{E}|\xi_{12}|^2=1\). Set \(\xi_{ji}=\overline{\xi_{ij}}\). Independently, let the diagonal entries be iid real variables with finite second moment. Write \(M_n=(\xi_{ij})_{i,j\le n}\), \(H_n=M_n/\sqrt n\), and
This is a random probability measure. Its expectation is the deterministic probability measure defined by \((\mathbb{E}\mu_n)(B)=\mathbb{E}[\mu_n(B)]\), or equivalently by integration of bounded measurable test functions.
Theorem 1 (Semicircle law). Under these hypotheses, \(\mu_n\) converges weakly almost surely to
Precisely, on one event of probability one, \(\int f\,d\mu_n\to\int f\,d\mu_{\rm sc}\) for every bounded continuous function \(f:\mathbb R\to\mathbb R\).
Remark 2 (Geometric subsequences). Write \(F_n(x)=\mu_n(( -\infty,x])\). Cauchy interlacing, with all eigenvalues put at the same unnormalized threshold, gives for \(m<n\),
It suffices to prove almost-sure weak convergence along every sequence \(n_j=\lfloor(1+\epsilon)^j\rfloor\), for a countable collection \(\epsilon\downarrow0\). Indeed, for \(m\) between consecutive sizes, the displayed inequalities bound its cdf by the larger matrix's cdf, with a threshold perturbation of order \(|x|\epsilon\), a multiplicative error of order \(\epsilon\), and an additive error of order \(\epsilon\). Along each sequence the limiting cdf is continuous. First let \(j\to\infty\), then \(\epsilon\downarrow0\). Taking rational \(x\) first puts all these conclusions on one probability-one event. Convergence on one fixed geometric sequence alone would not suffice.
The interlacing assertion itself follows from Courant–Fischer. For an \(m\)-dimensional coordinate subspace \(V\subset\mathbb C^n\), the Rayleigh quotient of the principal minor is the restriction of the full quotient to \(V\). Restricting the maximizing subspaces gives \(\lambda_i(M_n)\ge\lambda_i(M_m)\); restricting the minimizing subspaces gives \(\lambda_i(M_m)\ge\lambda_{i+n-m}(M_n)\), in descending order. At a common unnormalized threshold the two eigenvalue counts therefore differ by a number between zero and \(n-m\). This is precisely the cdf comparison in Remark 2, after dividing by the appropriate matrix dimensions.
Remark 3 (Perturbations). For Hermitian matrices with ordered eigenvalues, the Hoffman–Wielandt inequality is
For completeness, diagonalize \(A\) and \(C=A+B\), with descending eigenvalues \(\alpha_i,\gamma_i\) and unit eigenvectors \(u_i,v_i\). The matrix \(p_{ij}=|u_i^*v_j|^2\) has nonnegative entries and all row and column sums one. Set \(q_i=\sum_jp_{ij}\gamma_j\). For every \(k\), the weights \(w_j=\sum_{i\le k}p_{ij}\) lie in \([0,1]\) and sum to \(k\); therefore \(\sum_{i\le k}q_i=\sum_jw_j\gamma_j\le\sum_{j\le k}\gamma_j\). Equality holds at \(k=n\). Summation by parts, with \(\alpha_k-\alpha_{k+1}\ge0\), now gives
Consequently \(\|A-C\|_F^2=\operatorname{Tr}A^2+\operatorname{Tr}C^2-2\operatorname{Tr}(AC)\ge\sum_i(\alpha_i-\gamma_i)^2\), proving the inequality. The square on the Frobenius norm is essential.
At most \(\|B\|_F^2/(n\epsilon^2)\) eigenvalues move by more than \(\epsilon\sqrt n\). Dividing this count by \(n\) gives
This estimate will transfer the law from bounded entries to entries having only a second moment.
First proof for bounded entries: moments. For each fixed integer \(k\ge0\),
For this part of the proof, assume a fixed finite bound on both the off-diagonal and diagonal entries. Constants in the moment estimates may depend on that bound and on the fixed degree \(k\), but not on \(n\). The case \(k=0\) is the identity \(m_0^{(n)}=1\).
View an index sequence as a closed walk on its distinct vertices, with an unordered edge for each matrix entry. An off-diagonal edge used exactly once makes the expectation zero, by independence and centering. If the walk uses \(v\) vertices, at least \(v-1\) distinct non-loop edges are needed, each at least twice in a surviving term. Thus \(v\le1+k/2\). For fixed \(k\), there are finitely many walk patterns, each contributing \(O_k(n^v)\) index choices and a bounded expectation.
If \(k=2r\), the only patterns with \(v=r+1\) are trees traversed exactly twice along each edge. A closed walk on a tree traverses each edge once in each direction, so its expectation is one, also for complex entries. The successive distances from the starting vertex form a Dyck path of length \(2r\), and conversely each such path gives one walk with vertices labeled in order of first appearance. There are \(C_r=(r+1)^{-1}\binom{2r}{r}\) such paths, by the reflection principle. Each has \(n(n-1)\cdots(n-r)\) labelings. All remaining patterns have at most \(r\) vertices. Consequently,
The Dyck-path count can be checked directly. Among all \(\binom{2r}{r}\) sequences of \(r\) upward and \(r\) downward steps, reflect the initial segment through the first visit to height \(-1\) for each path that goes below zero. This gives a bijection with paths having \(r+1\) upward and \(r-1\) downward steps. Hence the number that stay nonnegative is
In the tree walk, an upward step visits a new vertex; a downward step returns to its parent. An edge cannot be revisited after that return, because its two allowed traversals are already used. Thus the path determines the entire walk pattern, not just its sequence of distances.
The variance is \(O_k(n^{-1})\). To see this, expand it as a sum of covariances of two closed walks. Walks using disjoint unordered edges have zero covariance. If they share an edge, their union is connected. A nonzero covariance requires each non-loop edge in the union to occur at least twice in the combined \(2k\) steps, so the union has at most \(k+1\) vertices. Its contribution, after the normalization \(n^{-k-2}\), is \(O_k(n^{-1})\). This argument also permits diagonal entries, including nonzero diagonal means.
Chebyshev and Borel–Cantelli now give convergence of every moment along each geometric subsequence, simultaneously for all integer \(k\). On that event, the second moments are bounded, hence the spectral measures are tight. Along any weakly convergent further subsequence, bounded higher even moments make each lower power uniformly integrable, so its limiting moments are the values just computed.
The semicircle moments are zero in odd degree. In even degree, substituting \(x=2\sqrt u\) gives
These moments determine the measure. Indeed, \(C_r\le4^r\), so any measure with these moments assigns at most \((4/R^2)^r\) mass to \(\{|x|>R\}\). Letting \(r\to\infty\) for \(R>2\) shows it is supported on \([-2,2]\). Polynomial approximation on that compact interval then gives uniqueness. Every subsequential limit is therefore \(\mu_{\rm sc}\), and Remark 2 extends the result to all sizes. ◻
Second proof for bounded entries: resolvents. For \(z=a+ib\) with \(b>0\), set
Every such transform has positive imaginary part, absolute value at most \(1/b\), and derivative bounded by \(1/b^2\). Its imaginary part is \(\pi\) times convolution with the Poisson kernel \(P_b(x)=b/[\pi(x^2+b^2)]\).
Let \(H_n^{(i)}\) be the principal minor obtained by deleting row and column \(i\), retaining the normalization \(1/\sqrt n\), and let \(R_i=(H_n^{(i)}-zI)^{-1}\). Interlacing and integration by parts against \(g(x)=(x-z)^{-1}\) imply
The bound applies to the full complex transform. No change from \(\sqrt n\) to \(\sqrt{n-1}\) is made inside this comparison.
Here are the counting details behind the trace estimate and its rank-perturbation version. Write \(N_A(x)=\#\{i:\lambda_i(A)\le x\}\). For a principal minor, interlacing gives \(0\le N_A(x)-N_{A^{(i)}}(x)\le1\). Integration by parts against \(g\), whose limits at both infinities vanish, yields
For two matrices of the same size with \(\operatorname{rank}(A-C)\le r\), one has \(|N_A-N_C|\le r\). Indeed, intersect the spectral subspace of \(A\) for eigenvalues at most \(x\) with \(\ker(A-C)\); it loses at most \(r\) dimensions and the quotient of \(C\) there is also at most \(x\). Courant–Fischer gives \(N_C(x)\ge N_A(x)-r\); interchange the matrices for the other inequality. The same integral identity then bounds the trace difference by \(r\int|g'|\). Finally \(\int_{\mathbb R}|(x-a-ib)^{-2}|dx=\pi/b\).
Group the independent upper-triangular entries by their row index. Replacing one group changes the Hermitian matrix by rank at most two. The same cdf integration argument bounds the resulting change in \(s_n(z)\) by \(2\pi/(nb)\). Applying bounded differences to the real and imaginary parts yields, for fixed \(z\),
Thus \(s_n(z)-\mathbb{E}s_n(z)\to0\) almost surely, initially on a countable dense set of \(z\)'s. The derivative bound extends the conclusion to every point of the upper half-plane on the same event.
Write \(X_i\) for the unnormalized off-diagonal column removed with index \(i\). It is independent of \(R_i\), its entries are centered and independent, and \(\mathbb{E}X_iX_i^*=I\). Schur complementation gives
Bounded entries have uniformly bounded fourth moments. Expanding the quadratic form and pairing its centered terms gives, conditionally on \(R_i\),
For the inequality, diagonal terms contribute at most a constant times \(\sum_j|R_{jj}|^2\); among off-diagonal terms, independence leaves only the identical or reversed index pairs, bounded by a constant times \(\sum_{j,k}|R_{jk}|^2\). This avoids any unwarranted concentration claim for a general resolvent quadratic form.
More explicitly, write the centered quadratic form as
The first sum has second moment bounded by \(C\sum_j|R_{jj}|^2\), since its summands are independent and the fourth moments are uniformly bounded. Its cross terms with the second sum vanish by centering. In the squared modulus of the second sum, only identical or reversed pairs of indices survive. The first contribution is \(\sum_{j\ne k}|R_{jk}|^2\), while the absolute value of the second is at most \(\sum_{j\ne k}|R_{jk}R_{kj}|\le\sum_{j\ne k}|R_{jk}|^2\), using \(|\mathbb EX_j^2|\le1\). This proves the stated bound without requiring circularly symmetric complex entries. The resolvent spectral decomposition gives \(\operatorname{Tr}(RR^*)\le(n-1)/b^2\).
Set \(m_n(z)=\mathbb{E}s_n(z)\). The quadratic-form bound, interlacing, concentration, and the diagonal term show, uniformly in \(i\), that
For example, the four terms in this replacement can be bounded in \(L^1\) by
The third term is \(O(1/(\sqrt n\,b))\) by integrating the bounded-differences tail. All bounds are uniform in the deleted index \(i\); row/column exchangeability is unnecessary. Also \(\Im R_i=bR_iR_i^*\) is positive semidefinite, so \(\Im(X_i^*R_iX_i)\ge0\). Since \(\xi_{ii}\) is real, the exact Schur denominator has imaginary part at least \(b\). This justifies the inverse comparison even on rare events where a quadratic form is large.
Both denominators in the Schur formula and in \((z+m_n)^{-1}\) have imaginary part at least \(b\). The inverse map is therefore \(b^{-2}\)-Lipschitz on these values. Averaging the diagonal resolvent entries proves
Every convergent subsequence of these bounded complex numbers has a limit satisfying \(m=-1/(z+m)\) and \(\Im m\ge0\); the equation forces \(\Im m>0\). There is only one such root. Indeed, imaginary parts give \(|m|^2=\Im m/(b+\Im m)<1\), while two distinct roots of \(m^2+zm+1=0\) have product one. Hence
with the square-root branch chosen so that \(m(z)\sim-1/z\) at imaginary infinity. To identify this root with the semicircle transform without making an assumption about boundary inversion, use the deterministic density moments calculated above. For \(|z|>2\) in the upper half-plane, the uniformly convergent geometric expansion on \([-2,2]\) gives
A nonempty Dyck path has a unique first-return decomposition into an initial up step, a Dyck path, a down step, and another Dyck path. Consequently \(C_r=\sum_{j=0}^{r-1}C_jC_{r-1-j}\) and \(C_0=1\). The convergent generating function \(C(w)=\sum_r C_rw^r\) satisfies \(C=1+wC^2\). Thus this transform satisfies the same quadratic equation and has positive imaginary part, so it equals the unique root above. Analytic continuation extends equality throughout the upper half-plane. Lemma 4 below turns the almost-sure transform convergence into weak convergence. ◻
Removing boundedness. For large integers \(K\), let
where complex variance means \(\mathbb{E}|Z-\mathbb{E}Z|^2\). Its denominator tends to one and is positive for all sufficiently large \(K\). Use these variables above the diagonal and zero diagonal entries to form \(M_n^{(K)}\). The bounded-entry law applies to each \(K\). Moreover, by the strong law applied to an enumeration of the iid upper-triangular entries,
The diagonal contributes zero to this limit because \(n^{-1}\sum_{i\le n}\xi_{ii}^2\) converges to a finite mean. The right side tends to zero as \(K\to\infty\), by \(L^2\) truncation and normalization. Remark 3, first with \(n\to\infty\), then \(K\to\infty\), and finally \(\epsilon\downarrow0\), proves Theorem 1 under the stated second-moment assumptions. Countably many truncation levels and rational thresholds again give a single probability-one event.
The strong-law enumeration can be made explicit: list the upper-triangular variables column by column, so that all \(i<j\le n\) form the first \(n(n-1)/2\) terms. Their squared differences are iid integrable. The off-diagonal part of the normalized squared Frobenius norm equals
This identifies the normalization exactly. For any fixed \(\epsilon>0\), the limiting perturbation error in the cdf bound is at most \(\epsilon^{-2}\mathbb E|\xi-\xi^{(K)}|^2\). Send \(K\to\infty\) before sending \(\epsilon\to0\); continuity of the semicircle cdf then gives both limiting inequalities.
Lemma 4. For probability measures \(\mu_n,\mu\) on \(\mathbb R\), weak convergence \(\mu_n\Rightarrow\mu\) is equivalent to \(s_{\mu_n}(z)\to s_\mu(z)\) for every \(\Im z>0\).
Proof. The forward implication uses the bounded continuous test function \((x-z)^{-1}\). For the converse, first prove tightness; it is not automatic from Helly selection. For \(y>0\),
The corresponding integral for the probability measure \(\mu\) tends to one as \(y\to\infty\). Transform convergence therefore controls the tails of all sufficiently large \(n\); enlarging the compact interval handles the finitely many remaining measures. Thus the sequence is tight, and every subsequence has a weakly convergent further subsequence with a probability limit \(\nu\).
That limit has \(s_\nu=s_\mu\). Taking imaginary parts gives \(\nu*P_b=\mu*P_b\) for every \(b>0\). Integrating against a compactly supported continuous function and sending \(b\downarrow0\), using the Poisson approximate identity, shows \(\nu=\mu\). All subsequential limits coincide, proving weak convergence. The assumption that the limiting transform belongs to a probability measure is what prevents loss of mass at infinity. ◻
To justify the Poisson approximate identity used in Lemma 4, extend a compactly supported continuous test function \(\varphi\) to its bounded uniformly continuous function on \(\mathbb R\). For each \(\delta>0\),
First let \(b\downarrow0\), then \(\delta\downarrow0\). Fubini's theorem identifies integration against \(\nu*P_b\) with integration of \(P_b*\varphi\) against \(\nu\), so the uniform bound proves equality of the two measures on all such test functions.
A primary reference for the precise second-moment theorem is Terence Tao, 254A Notes 4, Theorem 1. Both proofs above are supplied in full; in particular, the resolvent argument uses the explicit conditional second-moment calculation given here.