Before stating the problem, a bit of context is in order: although this open problem is about random matrices, it is motivated by work I am doing in the area of Theoretical Computer Science (see a paper here).

In this paper we describe an approximation algorithm for the little Grothendieck problem over the Orthogonal Group (since this post is about the conjecture itself and not the work that inspired it I don’t want to go into the Grothendieck problem — it is a really cool problem though, I’ll blog about it soon!). It turns out that the approximation ratio of this algorithm is guaranteed to be where is the average singular value of a Gaussian matrix.

Let me be more precise:

Definition 1 (of )Let be a random matrix withrealiid entries . Let denote the -th singular value of , then we define as

One can similarly define this quantity in the complex field (which also corresponds to an approximation ratio of a slight variation of the algorithm proposed in here, this will appear in an update of the paper soon)

Definition 2 (of )Let be a matrix withcomplexiid entries . Let denote the -th singular value of , then we define as

Broadly stated, the problem consists in understanding the sequences for and .

In the limit, the distribution of the eigenvalues is known. In fact, since that singular values of are the square-root of the eigenvalues of the Wishart matrix , one can easily obtain the limit distribution of the singular values by the Marchenko-Pastur distrubtion (the limit distribution of the eigenvalues of a Wishart matrix). Interestingly this does not depend on whether or , in both cases the distribution of the singular values converges to the quarter-circle distribution given by

This means that

Lemma 3For both and ,

It seems that understanding for finite is much more difficult. Nevertheless it is easy to compute since in that case, the singular value is simply the absolute value of a standard real gaussian random variable ,

This suggests that is growing with the dimension.

The surprise comes when we try to do the same thing for . Note that is the expected absolute value of a standard complex gaussian random variable, if we separate the real and imaginary part they are independent and each has variance so is the expected norm of a dimensional vector with real gaussian iid entries . The distribution of the norm of times this vector is given by a distribution with degrees of freedom, whose mean is given by . This means that

This motivates the surprising conjecture:

is monotonically increasing and is monotonically decreasing.

Conjecture

Both and can be written analitically in terms of (rather ugly, specially in the real case) integrals involving Laguerre polynomials. Althought these integrals can be computed, for each fixed , using, e.g., *Mathematica* and I have verified that the sequences are respectively increasing and decreasing for , I haven’t been able to prove the Conjecture. Any ideas?

## 3 thoughts on “A conjecture on the singular values of a Gaussian matrix”