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

Question

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?

Answer 1

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}$).