Kernel matrix is a covariance function How to prove that the kernel matrix is actually a covariance matrix?
 A: Just to expand the answer by Dougal. A rigorous deduction in feature space with (potentially) infinite dimension is a bit involved. The fact is a direct consequence of the Mercel theorem: let be $X$ a compact domain, and suppose that the operator,
$$
T_{\kappa}(.) = \int_{X}\kappa(.,x)f(x)dx
$$
is positive, i.e.
$$
T_{\kappa}(f(z)) = \int_{X}\kappa(z,x)f(x)f(z)dxdz \geq 0
$$
for all $f \in L_{2}(X)$. Then there is a set of orthonormal functions, $\left\{ \phi_{i}(x) \right\}_{i=1}^{\infty}$, such that,
$$
\kappa (x,z) \sum_{i=1}^{\infty}\phi_{i}(x)\phi_{i}(z)
$$
and $\sum_{i=1}^{\infty} ||\phi_{i}(x)||^{2}$ is convergent.
A covariance function has the form,
$$
\kappa (x,z) = \int_{F} f(x)f(z)q(f)df
$$
where $q$ is a distribution of probability, and $F$ is the function space with the dot product given by,
$$
<a,b> = \int_{F}a(f)b(f)q(f)df
$$
This resembles closely the form given by the Mercer theorem (notice that in a function space, functions are points). We can regard it as a kernel if we define the feature mapping to be $x \rightarrow f(x)$, where $f$ is some function. It is easy to see that this kernel is positive.
Now, the goal is to see that we can express any kernel,
$$
\kappa (x,z) \sum_{i=1}^{\infty}\phi_{i}(x)\phi_{i}(z)
$$
as a covariance kernel of the form,
$$
\kappa (x,z) = \int_{F} f(x)f(z)q(f)df
$$
for some probability distribution $q$.
If we take $F = L_{2}(X)$ and $q$ to be the Gaussian prior, so that every function is expressed as,
$$
f(x) = \sum_{i=1}^{\infty}u_{i}\phi_{i}(x)
$$
where $u_{i} \sim N(0,1)$, and $\phi_{i}$ are the orthonormal functions in which your kernel is decomposed, then we have that,
$$
\int_{L_{2}(X)}\int f(x)f(z)q(f)df = \lim_{n \to \infty} \sum_{i,j=1}^{n}\phi_{i}(x)\phi_{i}(z)\int u_{i}u_{j}\prod_{k=1}^{n}\frac{1}{\sqrt{2\pi}}\exp (\frac{-u_{k}^{2}}{2})du_{k} \\ = \lim_{n \to \infty} \sum_{i,j=1}^{n}\phi_{i}(x)\phi_{i}(z)\delta_{ij} = 
\sum_{i=1}^{\infty}\phi_{i}(x)\phi_{i}(z) = \kappa (x,z)
$$
Any book on kernel methods describe all these technicalities in detail.
A: (I'm answering in full despite this being self-study, because it's been so long, but there might as well be an answer if people search this....)
A matrix is a valid kernel matrix if and only if it's positive semidefinite (Mercer's theorem).
A matrix is a valid covariance if and only if it's positive semidefinite:


*

*Suppose the covariance matrix $\Sigma$ for some random vector $X$ is not psd. Then there exists some $v$ such that $v^T \Sigma v < 0$. But $\mathrm{Var}(v^T X) = v^T \Sigma v < 0$, which contradicts the definition of variance.

*Let $\Sigma$ be a psd matrix. Then there is some $C$ with $C^T C = \Sigma$ (e.g. the Cholesky decomposition, if $\Sigma$ is full-rank). But then if $X \sim N(0, I)$, $\mathrm{Cov}(C X) = \Sigma$.
So any kernel matrix is a valid covariance matrix, and vice versa.
