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?
Thanks!
–Gabriel
Best Answer
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.