<p>To get the obvious out of the way first, to show that the $n\times n$ matrix $M$ is PSD, it is enough to show that it is the Gram matrix of $n$ vectors, i.e. $m_{ij} = \langle u_i, u_j\rangle$ where $u_1, \ldots, u_n \in \mathbb{R}^n$. (This is a "sum of squares" proof of positive semi-definiteness, because it shows that the bi-linear form $x^T M x$ can be written as a sum of squares of linear functions of $x$.  I am wondering if you meant something more sophisticated by "sum of squares".)</p>

<p>You get a useful class of PSD matrices from <em>positive definite functions</em>. A function $f: \mathbb{R}^d \to \mathbb{R}$ is positive definite if for all sequences $u_1, \ldots, u_n \in \mathbb{R}^d$, the $n\times n$ matrix $M$ defined by $m_{ij} = f(u_i - u_j)$ is PSD. It is not very hard to see that if $f$ is the Fourier transform of a finite measure, then $f$ is positive definite. I.e. it is sufficient that there is a finite Borel measure $\mu$  on $\mathbb{R}^d$ such that for all $x$
$$
f(x) = \int{e^{i\langle x, y\rangle} d\mu(y)}.
$$
A classical theorem of Bochner shows that this condition is necessary as well.</p>

<p>A special class of positive definite functions are the functions $f(x) = g(\|x\|_2)$, for which the matrix $M$ becomes $m_{ij} = g(\|u_i - u_j\|_2)$. Another classical result of Schoenberg shows that such an $f$ is positive definite if and only if there exists a finite Borel measure $\mu$ on $[0, \infty)$ so that for every $t \geq 0$
$$
g(t) = \int_{0}^\infty{e^{-t^2s}d\mu(s)}.
$$</p>

<p>The original motivation for Schoenberg's theorem was to determine what functions $g$ have the property that for any $u_1, \ldots, u_n \in \mathbb{R}^d$, the metric space with metric $d(u_i, u_j) = g(\|u_i - u_j\|_2)$ embeds isometrically into Euclidean space.</p>

<p>This <a href="http://djalil.chafai.net/blog/2013/02/09/a-probabilistic-proof-of-the-schoenberg-theorem/" rel="nofollow">blog post</a> has a simple proof of Schoenberg's theorem and many links.</p>

CC BY-SA 3.0
2014-12-09T05:43:58.183Z
2014-12-09T05:50:16.983Z
2014-12-09T05:50:16.983Z
Sasho Nikolov
<ol>
<li><p>Diagonally dominant matrices are known to be positive semidefinite (PSD). What are some other families of (symmetric) matrices which are known to be PSD?</p></li>
<li><p>Given an <em>arbitrary</em> matrix A, the positivstellensatz or 'sum of squares' machinery can be used as a tool towards showing that A is PSD. What are other simpler methods/tools that can be used towards proving that a matrix is PSD?</p></li>
</ol>

CC BY-SA 3.0
2014-12-09T06:26:12.197Z
Note that $A$ is PSD iff $(A+A^T)/2$ is PSD, since $x^T A x = x^T\frac{A+A^T}{2} x$. So in (2) you can assume that $A$ is symmetric.
Yuval Filmus
CC BY-SA 3.0
2014-12-09T07:27:56.780Z
This seems to be two discrete questions and should be asked as such.
David Richerby
<matrices>
Proving PSD-ness of matrices
Anand Louis
# Proving PSD-ness of matrices

(Asked by: username_0 on 2014-12-08)

1. Diagonally dominant matrices are known to be positive semidefinite (PSD). What are some other families of (symmetric) matrices which are known to be PSD?
2. Given an *arbitrary* matrix A, the positivstellensatz or 'sum of squares' machinery can be used as a tool towards showing that A is PSD. What are other simpler methods/tools that can be used towards proving that a matrix is PSD?

**Tags:** matrices
> **Comments:**
> **username_1**: Note that $A$ is PSD iff $(A+A^T)/2$ is PSD, since $x^T A x = x^T\frac{A+A^T}{2} x$. So in (2) you can assume that $A$ is symmetric.  
> **username_2**: This seems to be two discrete questions and should be asked as such.  

---

## 1 answers

### Answer by username_3 on 2014-12-09. Score: 3 | Accepted answer

To get the obvious out of the way first, to show that the $n\times n$ matrix $M$ is PSD, it is enough to show that it is the Gram matrix of $n$ vectors, i.e. $m\_{ij} = \langle u\_i, u\_j\rangle$ where $u\_1, \ldots, u\_n \in \mathbb{R}^n$. (This is a "sum of squares" proof of positive semi-definiteness, because it shows that the bi-linear form $x^T M x$ can be written as a sum of squares of linear functions of $x$. I am wondering if you meant something more sophisticated by "sum of squares".)

You get a useful class of PSD matrices from *positive definite functions*. A function $f: \mathbb{R}^d \to \mathbb{R}$ is positive definite if for all sequences $u\_1, \ldots, u\_n \in \mathbb{R}^d$, the $n\times n$ matrix $M$ defined by $m\_{ij} = f(u\_i - u\_j)$ is PSD. It is not very hard to see that if $f$ is the Fourier transform of a finite measure, then $f$ is positive definite. I.e. it is sufficient that there is a finite Borel measure $\mu$ on $\mathbb{R}^d$ such that for all $x$
$$
f(x) = \int{e^{i\langle x, y\rangle} d\mu(y)}.
$$
A classical theorem of Bochner shows that this condition is necessary as well.

A special class of positive definite functions are the functions $f(x) = g(\|x\|\_2)$, for which the matrix $M$ becomes $m\_{ij} = g(\|u\_i - u\_j\|\_2)$. Another classical result of Schoenberg shows that such an $f$ is positive definite if and only if there exists a finite Borel measure $\mu$ on $[0, \infty)$ so that for every $t \geq 0$
$$
g(t) = \int\_{0}^\infty{e^{-t^2s}d\mu(s)}.
$$

The original motivation for Schoenberg's theorem was to determine what functions $g$ have the property that for any $u\_1, \ldots, u\_n \in \mathbb{R}^d$, the metric space with metric $d(u\_i, u\_j) = g(\|u\_i - u\_j\|\_2)$ embeds isometrically into Euclidean space.

This [blog post](http://djalil.chafai.net/blog/2013/02/09/a-probabilistic-proof-of-the-schoenberg-theorem/) has a simple proof of Schoenberg's theorem and many links.


---

