How to prove that a kernel is positive definite? For example, how to prove
$\forall(x,y)\in R^N\times R^N,K(x,y) = \displaystyle\frac{1}{1+\frac{||x - y||^2}{{\sigma}^2}}\\$
where $\sigma > 0$ is a parameter, is positive definite? I have tried to construct the target kernel base on some negative definite kernel, such as the square distance $||x-y||^2$, but doesn't seems to work.
 A: Schoenberg (Ann. of Math. 39 (1938), 811-841) observed that if $f(t)$ is a completely monotonic function, then the radial kernel $K(x,y)=f(\|x-y\|^2)$ is positive definite on any Hilbert space. Since 
$$ f(t):=\frac{1}{1+\frac{t}{\sigma^2}} $$ is completely monotonic, the result follows.
Added. Schoenberg's proof relies on the Hausdorff-Bernstein-Widder theorem and the fact that the Gaussian kernel $\exp(-\|x-y\|^2)$ is positive definite. Using these two facts, the proof is immediate. 
For a modern account, see Theorem 7.13 in Wendland: Scattered Data Approximation (Cambridge University Press, 2005).
A: Here is a simple trick that relies only on elementary ideas.
First, we use the observation that for $t>0$
\begin{equation*}
  \exp(-t\|x-y\|^2) = \exp(-t\|x\|^2)\exp(2t\langle x, y\rangle)\exp(-t\|y\|^2),
\end{equation*}
which is clearly positive definite (use $\langle x,y\rangle^k$ is pd for $k\ge0$).
Now, just use the integral
\begin{equation*}
  \frac{1}{1+\|x-y\|^2} = \int_0^\infty e^{-t(1+\|x-y\|^2)}dt,
\end{equation*}
which is basically just a nonnegative sum of positive definite functions, hence itself positive definite.
