# Smallest eigenvalue of a tricky random matrix

While experimenting with positive-definite functions, I was led to the following:

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:

How do I obtain an estimate for the smallest eigenvalue $\lambda_n$ of $M$?

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?

-
Do you mean $M_{ij}=\frac{1}{1+|x_i-x_j|}$? Because $M$ as you've defined doesn't seem to be a matrix. – Gilead Nov 13 '10 at 23:00
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)$.
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.
It's even easier than that: once you've found a pair of indices giving distance order $1/n^2$, they define a $2 \times 2$ matrix with an eigenvalue of order $1/n^2$, and then by interlacing of eigenvalues for Hermitian (or real symmetric) matrices the entire matrix has an eigenvalue no larger than that. – Tracy Hall Nov 15 '10 at 4:32
@Terry: thanks for the nice argument for an upper bound (and @Tracy, good point of invoking Cauchy's interlacing theorem to argue about the upper bound on the eigenvalues). As for the Fourier connection, indeed this matrix is generated by the posdef function $f(x)=1/(1+|x|)$. In fact, perhaps even more can be proved, because actually the said matrix is infinitely divisible. – Suvrit Nov 16 '10 at 8:53