A Question on Random Matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:40:03Z http://mathoverflow.net/feeds/question/59296 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59296/a-question-on-random-matrices A Question on Random Matrices ght 2011-03-23T13:18:18Z 2012-04-09T02:53:38Z <p>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]$.</p> <p>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}).$ </p> <p>Any idea of what can work here? </p> <p>Thanks!</p> <p>--Gabriel</p> http://mathoverflow.net/questions/59296/a-question-on-random-matrices/59453#59453 Answer by fedja for A Question on Random Matrices fedja 2011-03-24T18:10:56Z 2011-03-24T18:10:56Z <p>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). </p> <p>I hope it makes sense but I'm in quite a hurry right now, so accept my apologies if I said some nonsense somewhere.</p>