How to prove that the Gram matrix of the Gaussian kernel has full rank?

Question

I'm trying to prove that, given mutually different points $x_1,\dots,x_m$, the Gram matrix $G$ for the Gaussian kernel has $rank(G)=m$. If I can prove that the Gaussian kernel is strictly positive definite I could follow that all eigenvalues $\lambda_1,\dots,\lambda_m$ of $G$ are positive. Therefore, $det(G)=\Pi_{i=1}^m \lambda_i \neq 0$ which implies $rank(G)=m$. Is there an easy way to show that the Gaussian kernel is strictly positive definite? I've already searched on StackExchange but I couldn't find an explanation I could understand.

Thanks in advance!

EDIT: The definition of the Gram matrix is the following: Given a kernel $k$ and data $x_1,\dots,x_m \in X$, the $m \times m$ matrix $G=(g_{ij})$ with $g_{ij}=k(x_i,x_j)$ is called Gram matrix.

Answer 1

We are given $m$ distinct vectors $x_1,\ldots,x_m \in X$. We may assume your vector space $X$ is finite dimensional with dual $V$, by restricting to the linear span of the $x_r$ if needed.

Let $k(x,y)=\exp(-\|x-y\|^2) =\int_V \exp(i\langle v,x-y\rangle) g(v)dv$, where $g(v)$ is the Fourier transform of $\exp(-\|x\|^2)$. Note that $g(v)>0$ for almost all $v$.

For numbers $a_r\in\mathbb C$ let $Q=\sum_{r=k}^m\sum_{s=1}^m a_r \overline a_s k(x_r,x_s)$. It is easy to see that $Q=\int_V |P(v)|^2 g(v)dv$, where $P(v)=\sum_{r=1}^m a_r \exp(i \langle v,x_r\rangle)$. If the $a_r$ do not all vanish, $|P(v)|>0$ for almost all $v$. Then the integrand of $\int_V |P(v)|^2 g(v)dv$ is non-negative almost everywhere, and hence $Q>0$.