

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


