Find the smallest eigenvalue of $G=[ \exp(-(x_i-x_j )^2]_{i,j}$ for ${\bf x}=[x_1,\dots,x_n]$ 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.
 A: 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}} $$
A: 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}$.
