Eigenvalues of sums of random matrices
Say I have a sum of random Hermitian matrices
. I’d like to know what the
-th eigenvalue of
tends to look like. In the case that the
are positive-semidefinite, the upper and lower Chernoff tail bounds in User Friendly Tail Bounds bound the relative deviation of
from
and
from
respectively, so you might expect that
tends to look like
. However, it’s easy to see that this isn’t the case, even for
and
: assume
has all eigenvalues equal to
. Then it seems that an instance of
is likely to have
and
. More formally, we expect the same results from Jensen's inequality.
To illustrate my point graphically, I took
to be the first
rows of an
Fourier matrix; let
refer to the
-th column of
, and take
where
are i.i.d Bernoulli(
) random variables. Then the eigenvalues of
are the squares of the singular values of a matrix you get by tossing out each of the columns of
independently with probability
. On average, the singular values of this column subsampled version of
are all
, but you can see that empirically the extreme singular values do not cluster around
(indicated by the red lines).
It seems that whatever
clusters around is comparable to
from the bounds in User Friendly, but it’s not clear that one can’t do much better.
Possibly relevant posts:
- Full rankedness of random submatrices of orthogonal matrices (5/26/2010)
- The gist of the Laplace transform method for bounding eigenvalues of random matrices (8/27/2010)
- One direction in Khintchine’s inequality for Rademacher sums (9/26/2008)

be conformal matrices, then it’s clear that the matrix
are scalars in the open unit disc. In that case, we are looking at the matrix
. By the Schur Product Theorem (which states that the Hadamard product of two positive semidefinite matrices is positive semidefinite), we see that the matrix is positive semidefinite.
norm of a PSD matrix
?
,
so that
, and the spectral spread of the graph is given by the Ky-fan two norm. So whatever we know about Ky Fan norms can be used.
of norms:
is a norm
is the convex indicator function of a set.
The spectral and trace norms are trace dual, so we have
are also symmetric. It follows that we can achieve the maximum over
to be 0 zero when
is negative, and 1 otherwise. Recalling that
is the inclusion operator between
norm, and
, the space of symmetric matrices with the Ky Fan 2-norm, then
I doubt this will ever be a useful observation
norm
then
for
You can compute these using induction and integration by parts. By Markov’s inequality and Stirling’s approximation,
the quantity in the parentheses is monotonic:
is sufficiently large that the quantity in the parentheses is negative for some
, then we can optimize the approximate tail bound by setting
, then the root is given by the Lambert W function:
:
? Just eyeballing it, it looks like asymptotically, the moment bound gives you an exponential tail bound with a worse constant. If true, that’s pretty amazing!
denote the spectrum of an invertible matrix. Here’s the question: if
is contained in the upper open half plane and
is a projection matrix, then is
contained in the upper closed half plane?
, and blue are in the spectrum of
when
is a contour surrounding the spectrum of
for
on the cut plane
by the formula
is positive then
algebras? ( I’m only interested in the matrix case, but general theory is better than none)

for some
Here’s a proof:
and
where
is an
matrix with orthonormal columns, given by the SVD of 
is block diagonal in the basis given by
: