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 with real iid 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 with complex iid 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 3 For 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:
Conjecture is monotonically increasing and is monotonically decreasing.
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?