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

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_{jne 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-Dsqrt{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)^2le g_{12}^2+g_{13}^2+g_{23}^2le 2D^2+D^8,$$ so $lambdage 1-Dsqrt{2+D^6}$.

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_{jneq i} |G_{ij}|$. Here, we have $G_{ii}=1$ for all $i$ and we can bound the radii as:

$$ r_i = sum_{jneq i} |G_{ij}| = sum_{jneq i} e^{-(x_i-x_j)^2} le sum_{jneq 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, jneq i}^n e^{-{(x_i-x_j)^2}} $$