# Positive definiteness of Grammian with respect to Gaussian process' covariance function

A Gaussian process indexed by $T \subseteq \mathbb{R}^d$ is a collection of random variables $\{ X_t : t \in T\}$, for which each finite subset is distributed as a multivariate Gaussian.

Let $G$ be a sample path of a Gaussian process having mean zero and covariance function $K$, where $K: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}, K(t,s)=\operatorname{Cov}(X_s,X_t)$. Let $(x_1,...,x_n)$ be a finite sequence of points where $x_i \in \mathbb{R}^d$ and let $M$ denote the Gram matrix $$M(x_1,...,x_n) = \begin{pmatrix} K(x_1,x_1) & \cdots & K(x_1,x_n) \\ \vdots & \ddots & \vdots \\ K(x_n,x_1) & \cdots & K(x_n,x_n) \end{pmatrix} .$$

Is matrix $M$ positive definite (and therefore invertible) for any choice of covariance function $K$? If so, why?

UPDATE:

What if the points $(x_1,...,x_n)$ are distinct? Does that guarantee that Grammian M is positive definite?

For us to have a Gaussian Process, our covariance function $k(x_i,x_j)$ itself has to be positive semi-definite which is defined as so:
A symmetric function $k:\mathcal{X}\times \mathcal{X} \rightarrow \mathbb{R}$ is a positive definite kernel on $\mathcal{X}$ if $$\sum_i^n \sum_j^n k(x_i,x_j)c_ic_j \geq 0$$ holds for any $n \in \mathbb{N}$, $x_1, ..., x_n \in \mathcal{X}$ and $c_1, ..., c_n \in \mathbb{R}$.
Thus, since the definition of the Gram matrix is $M_{ij} = k(x_i,x_j)$ as you write, and the definition of a positive semi-definite matrix is $x^\top Mx \geq f, \forall x \in \mathcal{X}$, we only have to rewrite this quadratic form $$x^\top Mx = \sum_i^n \sum_j^n M_{ij}x_i x_j = \sum_i^n \sum_j^n k(x_i,x_j)x_i x_j$$ to see that $M$ is a positive semi-definite matrix (since $x_1, ..., x_n \in \mathbb{R}$).
• Yes! A positive definite kernel function only implies a positive semi-definite Gram matrix. Having said that, your eigenvalues will often all be positive (i.e. positive definite matrix), depending on your data. But yes, you could have 0's as well. Furthermore, note that you can run into numerical trouble trying to invert your Gram matrix, the solution to which is to add a small value $\delta$ to the daigonal. – Daniel Svendsen Jul 19 '18 at 15:17
• One more question. What if the points $(x_1,...,x_n)$ are distinct? Does that guarantee that Grammian M is positive definite? – Metod Jazbec Jul 19 '18 at 17:49