Random Matrices: Eigenvalue and Operator-Norm Bounds
To estimate a random matrix norm, we first express it as a supremum of scalar quantities. Linear algebra supplies the variational formulas; concentration and covering numbers then control the supremum. We develop these ingredients for eigenvalues and singular values, followed by a second approach that bounds the norm through traces of high powers.
Throughout, eigenvalues of an \(n\times n\) Hermitian matrix are ordered \(\lambda_1\ge\cdots\ge\lambda_n\). Thus \(\lambda_1\) is the largest eigenvalue and satisfies \(\lambda_1(A+B)\le\lambda_1(A)+\lambda_1(B)\); the smallest eigenvalue satisfies the reverse superadditivity inequality. The distinction matters in every variational formula below.
1. The Spectral Theorem
Theorem 1 (Spectral theorem). A self-adjoint operator \(T\) on an \(n\)-dimensional complex Hilbert space has an orthonormal basis of eigenvectors, with real eigenvalues.
Proof. The Rayleigh quotient \(v^*Tv\) is real for every unit vector and attains a maximum on the compact unit sphere. Let \(v\) be a maximizer, with value \(\lambda\). For any \(w\perp v\), differentiate the quotient at \((v+tw)/\|v+tw\|\), first with real \(t\), and then with \(w\) replaced by \(iw\). The two derivatives show \(\Re(w^*Tv)=\Im(w^*Tv)=0\). Hence \(Tv\) lies in the span of \(v\), and \(Tv=\lambda v\). Moreover \(v^*Tw=(Tv)^*w=0\) for every \(w\perp v\), so \(v^\perp\) is invariant under \(T\), and its restriction remains self-adjoint. Induction on dimension supplies an orthonormal eigenbasis there. The base cases of dimension zero and one are immediate. Each eigenvalue is real because \(v^*Tv\) is real. ◻
2. Minimax Formulation of Eigenvalues
Theorem 2 (Courant–Fischer). For \(1\le k\le n\),
Proof. Let \(u_1,\ldots,u_n\) be an eigenbasis in descending order. The space \(W_+=\operatorname{span}(u_1,\ldots,u_k)\) has minimum Rayleigh quotient \(\lambda_k\). Conversely, every \(k\)-dimensional space meets \(\operatorname{span}(u_k,\ldots,u_n)\) nontrivially, since their dimensions sum to \(n+1\). A unit vector in the intersection has quotient at most \(\lambda_k\), proving the first equality. For the second, \(W_-=\operatorname{span}(u_k,\ldots,u_n)\) has maximum \(\lambda_k\), and every space of dimension \(n-k+1\) meets \(\operatorname{span}(u_1,\ldots,u_k)\). A unit vector in that intersection has quotient at least \(\lambda_k\). Equivalently one can apply the first formula to \(-A\), remembering \(\lambda_j(-A)=-\lambda_{n-j+1}(A)\). ◻
3. Eigenvalue Inequalities
Weyl's inequality states that, if \(i+j-1\le n\),
Indeed, intersect the spectral subspaces of \(A\) with eigenvalues at most \(\lambda_i(A)\) and of \(B\) with eigenvalues at most \(\lambda_j(B)\). Their intersection has dimension at least \(n-i-j+2\), and every unit vector in it has \((A+B)\)-quotient at most the proposed bound. The minimum-over-subspaces formula proves it. Applying the result to negatives supplies the corresponding lower inequalities.
Ky Fan's inequality is
For a rank-\(k\) orthogonal projection \(P\), expand in an eigenbasis of \(A\): \(\operatorname{Tr}(PA)=\sum_i\lambda_i(A)p_i\), where \(p_i=\|Pu_i\|^2\in[0,1]\) and \(\sum_i p_i=k\). Moving weight toward the larger eigenvalues shows \(\sum_i\lambda_i(A)p_i\le\sum_{i\le k}\lambda_i(A)\); projection onto the top \(k\) eigenvectors attains equality. Thus
Apply this formula to \(A+B\) and bound the two trace terms separately. In particular \(k=1\) gives largest-eigenvalue subadditivity.
The variational formulas also give the perturbation bound
because \(-\|B\|_{\rm op}\le v^*Bv\le\|B\|_{\rm op}\) uniformly on the unit sphere. This proves continuity of all ordered eigenvalues and permits approximation in the next argument.
Lidskii's inequality extends the sum bound to any increasing index set \(1\le i_1<\cdots<i_k\le n\):
Here is a proof that includes eigenvalue crossings. First suppose \(A\) has distinct eigenvalues and consider \(C(t)=A+tB\), \(0\le t\le1\). The discriminant of its characteristic polynomial is a polynomial in \(t\), nonzero at zero; hence it vanishes only at finitely many parameters. Between them, every ordered eigenvalue is differentiable by the implicit function theorem. A differentiable local unit eigenvector can be chosen by applying the spectral projection
to a fixed vector with nonzero projection, then normalizing. Differentiating the eigenvector equation gives \(\lambda_i'(t)=u_i(t)^*Bu_i(t)\). The chosen \(k\) eigenvectors are orthonormal, so the projection trace formula bounds their derivative sum by \(\sum_{j\le k}\lambda_j(B)\). Integrate on each interval of simple spectrum and use continuity at the finitely many crossing points. Finally approximate a general \(A\) by Hermitian matrices with simple spectrum, obtained by perturbing its eigenvalues in an eigenbasis. The perturbation bound passes the inequality to the limit. For \(k=n\), equality follows directly from the trace.
4. Singular Value Decomposition
Proposition 3 (Singular value decomposition). For \(A:\mathbb C^p\to\mathbb C^n\), let \(r=\operatorname{rank}A\). There are orthonormal families \(u_1,\ldots,u_r\) in \(\mathbb C^p\), \(v_1,\ldots,v_r\) in \(\mathbb C^n\), and positive \(\sigma_1\ge\cdots\ge\sigma_r\), such that
In particular, \(A\) vanishes on the orthogonal complement of the span of all the \(u_j\), and \(\|A\|_{\rm op}=\sigma_1\) when \(r>0\), or zero when \(A=0\).
Proof. The matrix \(A^*A\) is Hermitian positive semidefinite. Choose an orthonormal eigenbasis, with positive eigenvalues \(\sigma_j^2\) for \(j\le r\), and put \(v_j=Au_j/\sigma_j\). Then
A zero eigenvalue gives \(\|Au\|^2=u^*A^*Au=0\); therefore the remaining domain eigenvectors lie in the kernel. Expanding any vector in this basis gives the displayed decomposition. Completing both orthonormal families gives the usual rectangular diagonal matrix form; its additional singular values, up to \(\min(n,p)\), are zero. In the adjoint relation the operator must be \(A^*\), since \(v_j\) belongs to the codomain. ◻
5. Statistics of Random Matrices
We first consider a \(d\times d\) matrix \(M\) whose entries are independent, centered, and bounded in modulus by one. They may be complex. This model does not impose Hermitian symmetry: the independence of rows used below would otherwise fail. Constants denoted by \(c,C,A_0\) are positive and universal.
Lemma 4. For every deterministic unit vector \(x\in\mathbb C^d\) and every \(A\ge A_0\),
For an arbitrary vector, replace the threshold by \(A\sqrt d\|x\|_2\), with the zero vector handled separately.
Proof. In a row sum \(Z=\sum_j\xi_jx_j\), each real part \(\Re(\xi_jx_j)\) is centered and lies in \([-|x_j|,|x_j|]\). Hoeffding's scalar exponential bound yields \(P(|\Re Z|>t)\le2e^{-t^2/2}\), because \(\sum_j|x_j|^2=1\). The same holds for the imaginary part. If \(|Z|>t\), one of these parts exceeds \(t/\sqrt2\); hence \(P(|Z|>t)\le4e^{-t^2/4}\). The tail integration identity now gives
The row sums \(Z_1,\ldots,Z_d\) are independent. Markov's inequality therefore gives
once \(A^2\ge16\log5\). This proves the claim, including its uniformity over deterministic unit vectors. ◻
Lemma 5 (Net bound). If \(\mathcal{N}\) is an \(\epsilon\)-net of the unit sphere, with \(0<\epsilon<1\), then every linear operator satisfies
A \(1/2\)-net of the complex unit sphere can be chosen with at most \(5^{2d}\) points.
Proof. For each unit \(x\), choose a net point \(y\) with \(\|x-y\|\le\epsilon\). The triangle inequality gives \(\|Mx\|\le\|My\|+\epsilon\|M\|_{\rm op}\). Take the supremum over \(x\) and rearrange. For the cardinality bound, identify \(\mathbb C^d\) with \(\mathbb R^{2d}\), and take a maximal set with pairwise distances greater than \(\epsilon\). The disjoint balls of radius \(\epsilon/2\) about its points lie in the ball of radius \(1+\epsilon/2\). Comparing volumes bounds its size by \((1+2/\epsilon)^{2d}\); maximality makes it an \(\epsilon\)-net. This uses the existence of a nearby net point for each \(x\), not closeness of every pair of sphere points. ◻
Remark 6. Apply Lemma 4 to the finitely many points of a \(1/2\)-net and use a union bound. For all sufficiently large \(A\),
The extra constant in the lower threshold for \(A\) absorbs the entropy term \(2d\log5\). Taking a supremum over the entire sphere inside a pointwise tail bound would not justify this step. Scaling handles uniformly bounded entries with another common bound.
Example 7 (The moment method). Now let \(M=(\xi_{ij})\) be Hermitian, with independent centered entries on and above the diagonal, \(\xi_{ji}=\overline{\xi_{ij}}\), \(\mathbb E|\xi_{ij}|^2\le1\), and \(|\xi_{ij}|\le K\) for a deterministic \(K\ge1\). Diagonal entries are real. The upper-triangular independence is the appropriate assumption for this model. For every positive integer \(q\), the spectral theorem gives
The trace is not the sum of the \(2q\)th powers of the diagonal entries. Matrix multiplication instead gives a sum over closed walks,
Regard each unordered pair as an edge, allowing a loop at a repeated vertex. An edge occurring exactly once makes the expectation zero, by centering and independence of different upper-triangular entries. A surviving length-four walk thus uses at most two distinct edges. Its graph is connected, so it has at most three vertices.
If two edges occur, each occurs twice. Independence and \(\mathbb E|\xi|^2\le1\) bound the absolute expected product by one, whether or not the two occurrences are conjugated. There are at most \(C d^3\) such walks: for each of the finitely many equality patterns among four indices, choose at most three labels. If only one edge occurs, there are at most \(C d^2\) walks, and their absolute expectation is at most
This includes diagonal loops. Therefore
For \(K=O(\sqrt d)\), this gives \(\|M\|_{\rm op}=O_P(d^{3/4})\). More explicitly, confidence \(1-\eta\) is obtained at a threshold \([C(d^3+d^2K^2)/\eta]^{1/4}\). The fourth-moment calculation is a coarse bound; sharper norm scales require control of higher trace moments or another argument. The independent-entry net proof above cannot be applied by treating the rows of a Hermitian matrix as independent. Higher moments and their closed-walk structure will also drive the semicircle-law proof in the next post.