Smallest eigenvalue of a tricky random matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:43:25Z http://mathoverflow.net/feeds/question/45982 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45982/smallest-eigenvalue-of-a-tricky-random-matrix Smallest eigenvalue of a tricky random matrix suVRit 2010-11-13T22:06:05Z 2010-11-14T21:29:05Z <p>While experimenting with positive-definite functions, I was led to the following:</p> <p>Let $n$ be a positive integer, and let $x_1,\ldots,x_n$ be sampled from a zero-mean, unit variance gaussian. Consider the (positive-definite) matrix $$M_{ij}=\frac{1}{1+|x_i-x_j|}.$$ Now I wish to know:</p> <blockquote> <p>How do I obtain an estimate for the smallest eigenvalue $\lambda_n$ of $M$?</p> </blockquote> <p>Preliminary experiments (see plot; x-axis: $n$, y-axis: $\lambda_n$) suggest that $\lambda_n \approx 1/n^2$, but how do I prove that or perhaps a more accurate result?</p> <p><img src="http://img251.imageshack.us/img251/1075/smallesteig.png" alt="you should see plot here"></p> http://mathoverflow.net/questions/45982/smallest-eigenvalue-of-a-tricky-random-matrix/46070#46070 Answer by Terry Tao for Smallest eigenvalue of a tricky random matrix Terry Tao 2010-11-14T21:12:08Z 2010-11-14T21:29:05Z <p>I think I can get an upper bound of $O(1/n^2)$ by exhibiting a vector $v$ of magnitude comparable to $1$ which gets mapped to a vector of magnitude $O(1/n^2)$. The basic idea is to exploit the birthday paradox to find (with high probability) two indices $i \neq i'$ such that $x_i-x_{i'} = O(1/n^2)$. It should also be possible to then find another additional index $i''$ such that $x_{i''} = x_i + O(1/n)$.</p> <p>Now look at the $i^{th}$ and $(i')^{th}$ rows, which have components $1/(1+|x_i-x_j|)$ and $1/(1+|x_{i'}-x_j|)$. These rows differ by $O(n^{-2})$ in each coefficient. This already gives an upper bound of $O(n^{-3/2})$ for the smallest eigenvalue, but one can do better by using Taylor expansion to note that the difference between the two components is $(x_i-x_{i'}) \hbox{sgn}( x_i-x_j ) / (1 + |x_i-x_j|)^2 + O(n^{-4})$ except when $x_j$ is very close to $x_i$, at which point we only have the crude bound of $O(n^{-2})$. Similarly, the difference between the $i''$ and $i$ rows is something like $(x_i-x_{i''}) \hbox{sgn}( x_i-x_j ) / (1 + |x_i-x_j|)^2 + O(n^{-4})$ except when $x_j$ is too close to $x_i$. So we can use a multiple of the second difference to mostly cancel off the first difference, and end up with a linear combination of three rows in which most entries have size $O(n^{-4})$ and only about $O(1)$ entries have size $O(n^{-2})$. This seems to give an upper bound of $O(n^{-2})$ for the least eigenvalue (or least singular value), though I have not fully checked the details.</p> <p>To get a matching lower bound is trickier. One may have to move to a Fourier representation of the matrix as this would more readily capture the positive definiteness of the matrix (as suggested by Bochner's theorem).</p>