# Is the matrix $(max(0,1-|x_i-x_j|))$ positive semi-definite?

$x_1, ..., x_n \in \mathbb{R}$

Prove that $(max(0,1-|x_i-x_j|))_{i,j}$ is a positive semi-definite matrix.

Classic methods don't seem to work...

• Do you mean that its entries are non-negative or that the matrix is positive definite? – Omnomnomnom Mar 3 '15 at 20:01
• Positive semi-definite. – Arnaud Mar 3 '15 at 20:01
• I am wondering if, more generally, $\left(1-d\left(x_i,x_j\right)\right)_{i,j}$ is a positive-definite matrix whenever $x_1,x_2,\ldots,x_n$ are $n$ elements of a metric space $M$ with a distance function $d$. – darij grinberg Mar 3 '15 at 20:02