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?




1 Answer 1


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.

  • 2
    $\begingroup$ 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})}$? $\endgroup$
    – ght
    Mar 24, 2011 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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