Consider $K$ vectors $x\_1,\dots,x\_K$ in $\mathbb{R}^N$. Define the $K\times K$ matrix $A$ whose $(i,j)$ entry is given as $$A\_{ij}=\exp(-\frac{||x\_i-x\_j||^2}{2})$$ Is this matrix Positive Semi-Definite?



Is this matrix positive semi-definite?
Yes, it is. We write $A\_{ij}=B\_{ij}C\_{ij}$, where 
$$B\_{ij}=e^{-\|x\_i\|^2/2}e^{-\|x\_j\|^2/2}; \quad C\_{ij}=e^{(x\_i,x\_j)}.$$
By Schur's theorem on elementwise product of positive definite matrices, it is enough to show that $B\_{ij}$ and $C\_{ij}$ are positive semidefinite. Positive definiteness of $B\_{ij}$ is obvious. Positive definiteness of $C\_{ij}$ follows from positive definiteness of the matrix $(x\_i,x\_j)$, Taylor expansion of the exponent and application of Schur's theorem to elementwise powers of the matrix $(x\_i,x\_j)$. 


