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

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.

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.

• Can you give a formula for a typical entry of $G$, please, so we can be absolutely sure we understand what you are asking? Jan 27, 2019 at 20:48
• @kimchilover I added the definition of the Gram matrix to the question. Jan 27, 2019 at 20:56

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$$.
• Note that you need the $x_{i}$ to be distinct. Any repeated values and you've lost linear independence. Jan 27, 2019 at 21:38
• @kimchilover Thanks for your answer! I did not have time to think about it until now and I'm not too familiar with Fourier transform. What do you mean with dual $V$? The space of linear functionals from $X$ to $\mathbb{R}$? And how do you get the equality to the integral over $V$? Sorry that I have so many questions. Feb 4, 2019 at 10:11
• One problem with this forum is that it's often hard to know the background one can assume in answering a question; sorry about that. For your problem in general, see en.wikipedia.org/wiki/Bochner%27s_theorem; for Fourier transforms see en.wikipedia.org/wiki/Fourier_transform (and for your problem, formula 206 in en.wikipedia.org/wiki/…). The business about "dual" is probably needless pedanticism; the integral over $V$ is covered by the Wikipedia article on FT. Feb 4, 2019 at 19:03
• @kimchilover Nice anwer! I wonder whether one can use this to get a quantitative bound, by which I $Q \ge \alpha \|a\|^2$, for some $\alpha>0$. I'm optimistic in the case the $x_i$'s a well-separated, in the sense that $\|x_i - x_j\| \ge c$ for all $(i,j)$ such that $i \ne j$ May 21, 2021 at 9:46