Gaussian Kernels, Why are they full rank? I'd like to ask why a Gaussian Kernel's Gram Matrix is of full rank. Lots of texts and articles always write about assuming this is the case, and refer me to an unavailable research article online, but I haven't been able to find a single source that sheds light on why this is the case.
 A: Let $K:X\times X\rightarrow\mathbb{R}$ be a kernel function on the set $X$. Then $K$ is positive definite if and only if the functions $K_x:=K(\cdot,x)$ are linearly independent. In particular for every finite set $\{x_1,\ldots ,x_n\}\subseteq X$ the matrix $K(x_i,x_j)$ then has full rank.
Thus in your case you have to show that the functions $e^{-\| x-x_k\|^2}$, $k=1,\ldots ,n$, are linearly independent over $\mathbb{R}$.
A linear relation
$
\sum\limits_{k=1}^n a_k e^{-||x-x_k||^2} =0,\; a_k\in\mathbb{R},
$
can be rewritten in the form
$
0=\sum\limits_{k=1}^n (a_k e^{-||x_k||^2}) e^{-||x||^2} e^{2\langle x,x_k\rangle}=\sum\limits_{k=1}^n b_k e^{-||x||^2} e^{2\langle x,x_k\rangle},
$
where $b_k:=a_k e^{-||x_k||^2}$. Then:
$
\sum\limits_{k=1}^n b_k e^{2\langle x,x_k\rangle}=0,
$
and since this equation holds for all $x\in\mathbb{R}^m$ one gets the homogenous system
$
\sum\limits_{k=1}^n b_k e^{2\langle jx,x_k\rangle}=0,\;j=0,\ldots ,n-1.
$
For fixed $x$ is this is a Vandermonde system of equations for the $b_k$. Consequently $b_k=0$ and thus $a_k=0$ for all $k$ as desired.
