Question

Suppose I uniformly sample matrices X from the Gaussian Unitary Ensemble (GUE) with variance \sigma^2. Consider the Ky-Fan d norm, i.e. the sum of the singular values, of X. Let's call this Z=||X||_1. What is the distribution of Z as a function of the dimension d and the variance \sigma^2? Really, all I want are estimates of the mean and a good tail bound, so maybe also the second moment.

Answer 1

Let's normalise the variance of the entries to be $1$. Then GUE asymptotically obeys the semicircular law, i.e., the eigenvalues (which equal the singular values, as GUE is Hermitian), after dividing by $\sqrt{n}$, are distributed according to the law $\frac{1}{2 \pi} (4 - x^2)^{1/2}_+ dx$. So the Schatten $1$-norm (Ky Fan norm) should asymptotically equal $\sqrt{n}$ times n times the integral

\begin{equation*} \int \frac{|x|}{2 \pi} (4 - x^2)^{1/2}_+ dx, \end{equation*}

which Wolfram alpha tells me is $8/3 \pi$. So the answer is $n^{3/2} ( 8 / 3 \pi + o(1) )$ with probability $1-o(1)$. Using an explicit convergence rate for GUE, one can probably replace the $o(1)$ with $O(n^{-c})$ for some explicit constant $c>0$.

Getting the variance may be within current technology - it's some integral of two-point correlations of GUE, which are known - but somewhat tedious. Higher moments should also (in principle) be computable. My guess is that the limiting distribution will be asymptotically gaussian, but I might be wrong about this (the central limit theorem doesn't apply directly because the eigenvalues are correlated with each other).

Answer 2

More precise results along the lines of Yemon Choi's answers are in two papers by Szarek: "Spaces with large distance to $l^\infty$ and random matrices", and "Condition number of random matrices".

Answer 3

I'm not at all expert on random matrix stuff, but until someone more qualified pops up, would you be interested in some crude estimates on Z in the $n \to \infty$ asymptotic? Or do you really want something sharper in each dimension?

EDIT/UPDATE: OK, here's my hand-wavy argument, it's been a while since I did any probability theory, so caveat lector and all that.

I'm going to use the GOE just because that's the one I know better and to save me worrying about stray scaling factors.

The idea is that for any $n \times n$ matrices $S$ and $T$ we always have

$\Vert S\Vert_1 \Vert T \Vert_{\rm op} \geq |{\rm tr}(ST)|$

where the subscript 1 denotes Ky-Fan/Schatten 1-norm and the subscript "op" denotes usual operator norm. In particular, if $S=T$ is self-adjoint then

$\Vert S\Vert_1 \geq || S ||_2^2\, /\, || S ||_{\rm op}$

Now when S is GOE(n,$\sigma^2$) then $n^{-2} \Vert S\Vert_2^2$ is strongly concentrated round its mean (which is $\sigma^2$) -- it's the average of a bunch of independent random variables so we could use variance estimates and Chebyshev, or probably some stronger exponential tail estimates.

Also, when S is GOE(n,$\sigma^2$) then $n^{-1/2} \Vert S\Vert_{\rm op}$ is strongly concentrated round $2\sigma$ - one can get exponential tail estimates, at least for an upper bound of $(2+\epsilon)\sigma$ for any positive $\epsilon$. I think this is folklore or a special case of Big Machinery, but as I said I have a more elementary proof, albeit one which is probably not original.

So, there is going to be a high probability (for $n$ large) that || S ||₂² is bigger than $(1-\epsilon)\sigma^2n^2$, and there is going to be a high probability (for $n$ large) that $\Vert S\Vert_{\rm op}$ is less than $(2+\epsilon)\sigma n^{1/2}$. On the intersection of these two events you're going to find that

$\Vert S\Vert_1 \geq (1-\epsilon)n^2\sigma^2 / (2+\epsilon)\sigma n^{1/2}$

which gives the lower bound I was claiming.

Answer 4

Some vaguer thoughts: one way to try and get an intuitive handle on these kinds of global question, is to think of the not-quite-correctly named Wigner theorem on convergence to the semicircle distribution. That is, we know that if we scale the variance by 1/n then one gets convergence of the empirical spectral measure (in various senses) to a continuous density supported on [-2,2]. So there are going to be enough 'big' eigenvalues to drive up the values of the Schatten norms, in particular the sum of their absolute values should naively be O(n). This was when we scaled the entries by 1/\sqrt{n}, so to get a limit of the 1-norm it looks like we need a n^{-3/2} scaling.