Find the smallest eigenvalue of $G=[ \exp(-(x_i-x_j )^2]_{i,j}$ for ${\bf x}=[x_1,\dots,x_n]$

Question

Consider a sequence $\{x_1,...,x_n \}$ such that $b=\max_i |x_i|$ and $d_{\min}=\min_{ij: i \neq j} |x_i-x_j|$. We assume that $b<\infty$ and $d_{\min}>0$.

Can we find a non-trivial lower bound on the smallest eigenvalue of $$G=[ \exp(-(x_i-x_j )^2)]_{i=1..n,j=1..n}$$

We want this lower bound to depend on some property of this sequence.

I was thinking of writing it as \begin{align} u^T G u =\sum_i \sum_j u_i u_j \exp(-(x_i-x_j )^2) \end{align} and showing a lower bound that holds for all $(u_i,u_j)$.

We have the following bounds on each entry $$\exp(-d_{\min}^2) \ge \exp(-(x_i-x_j )^2) \ge \exp(-4 b^2).$$ However, I don't know how to combine these two steps.

Note that we know that $G$ is positive definite. This follows since $\exp(-t^2)$ is a positive definite kernel.

Answer 1

This is a textbook example for applying the Gerschgorin circle theorem: The eigenvalues are located somewhere in the union of discs $D_{r_i}(G_{ii})$ of radius $r_i = \sum_{j\neq i} |G_{ij}|$. Here, we have $G_{ii}=1$ for all $i$ and we can bound the radii as:

$$ r_i = \sum_{j\neq i} |G_{ij}| = \sum_{j\neq i} e^{-(x_i-x_j)^2} \le \sum_{j\neq i} e^{-d_\min^2} = (n-1) e^{-d_\min^2} $$

Thus you have the lower bound $\lambda_\min(G) \ge 1 - (n-1) e^{-d_\min^2}$. Of course this bound is only useful if $d_\min$ is sufficiently large, i.e. if $d_\min > \sqrt{\log(n-1)}$

In the case when the $x$-values are known you can of course improve the bound towards

$$ \lambda_\min(G) \ge 1 - r_\max \qquad r_\max=\max_i \sum_{j=1, j\neq i}^n e^{-{(x_i-x_j)^2}} $$

Answer 2

Put $D=\exp(-d_{\min}^2)<1$. Let $\lambda_{\min}$ be the smallest eigenvalue of $G$. It turns out, that the simple bound $\lambda_{\min}\le 1-D$ by JimmyK4542 is rather tight, especially for small $n$ and big $d_{\min}$. Namely, we have $\lambda_{\min}\ge 1-E,$ where $$E=D+D+D^4+D^4+D^9+D^9+\dots$$ (the right-hand-side has $n-1$ summands).

Let’s prove this. Let $x’_1,\dots, x’_n$ be a permutation of the numbers $x_i$ such that $x’_1<x’_2<\dots<x’_n$. Then for each $i,j$ we have $|x’_i-x’_j|\le |i-j|d_{min}$, and so $$\exp(-(x’_i-x’_j)^2)\le \exp(-(i-j)^2 d_{\min}^2)=D^{(i-j)^2}.$$ This easily follows that for each $i$ $$S_i=\sum_{j\ne i} \exp(-(x_i-x_j)^2)\le E.$$ Thus if $\lambda<1-E$ then $G-\lambda I$ is a strictly diagonally dominant matrix, so it is non-singular by Levy–Desplanques theorem, that is $\lambda$ is not an eigenvalue of $G$.

Moreover, for $n=3$, $\lambda_{\min}\ge 1-D\sqrt{2+D^6}$. Indeed, let $G=\|g_{ij}\|$. Then

$$|G-\lambda I|=(1-\lambda)^3+2g_{12}g_{13}g_{23}-(1-\lambda)(g_{12}^2+g_{13}^2+g_{23}^2).$$

Thus if $\lambda<1$ and $|G-\lambda I|=0$ then $$(1-\lambda)^2\le g_{12}^2+g_{13}^2+g_{23}^2\le 2D^2+D^8,$$ so $\lambda\ge 1-D\sqrt{2+D^6}$.