MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following $n\times n$ random matrix $V_{n}$ where the $(p,q)$ entry is given by $$ V_{n}(p,q):= \frac{1}{\sqrt{n}}\exp(2\pi i(p-1) x_{q}) $$ where $x_{1},x_{2},\ldots,x_{n}$ are iid random variables with uniform distribution on $[0,1]$.

It is not difficult to prove that $V_{n}^{*}V_{n}$ has the same eigenvalues as $X_{n}$ where $$ X_{n}(p,q)=\frac{\sin(n(x_p-x_q)/2)}{n\sin((x_p-x_q)/2)}. $$ This matrix is positive definite and invertible with probability one. The minimum eigenvalue, $\lambda_{1}(n)$, goes to zero as $n\to\infty$. I'm interested in the rate at which this eigenvalue goes to zero. Simulations suggest that $$ \mathbb{E}(\lambda_1(n))\sim \exp(-\alpha n), $$ the expected value decays exponentially. Using the Cauchy interlacing theorem I can only get the upper bound $O(\frac{1}{n^2}).$

Any idea of what can work here?



share|cite|improve this question
Why is this community wiki? – Andrey Rekalo Mar 23 '11 at 13:32
No Vandermonde matrix here. – Did Mar 23 '11 at 13:47
Do you mean $1/\sqrt{n} \exp(2 \pi i (p-1) x_q)$? That would be Vandermonde. – David Speyer Mar 23 '11 at 14:20
Yes, David. I corrected. – ght Mar 23 '11 at 14:28
up vote 12 down vote accepted

It is actually more like $e^{-\sqrt n}$. Let's look at the norm of the inverse matrix. The entries are $\pm\prod_{i:i\ne j}\frac 1{z_j-z_i}\sigma_m(z_1,\dots,z_{j-1},z_{j+1},\dots,z_n)$ where $z_k=e^{2\pi i x_k}$ is a random point on the unit circle and $\sigma_m$ is the $m$-th symmetric sum. Since $\log |Z-z_j|$ has zero mean and finite variance, you expect the first factor to be $e^{O(\sqrt n)}$ most of the time. The size of second factor is essentially the size of the random polynomial $\prod_i(z-z_i)$ on the unit circle. The typical value at one point is $e^{O(\sqrt n)}$ and we need about $n$ points to read the true maximum (plus we have $n$ rows to serve), so my educated guess (which I can try to convert into a proof if this subexponential dependence is of any value for you) would be $e^{-\alpha \sqrt{n\log n}}$ with some $\alpha$ (with high probability; the expectation may be a bit larger because there is a chance that the rare large values will still dominate).

I hope it makes sense but I'm in quite a hurry right now, so accept my apologies if I said some nonsense somewhere.

share|cite|improve this answer
Thanks Fedja. Can you explain why $\sigma_{m}(z_1,\ldots,z_{j-1},z_{j+1},\ldots,z_{n})$ has the size of the random polynomial $\prod_{i}(z-z_i)$ and why its typical value is $e^{O(\sqrt{n})}$? – ght Mar 24 '11 at 23:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.