If ${\bf M}_{ij} = \min\{x_i,x_j\}$, is ${\bf M}$ positive semidefinite

linear algebrapositive-semidefinitesymmetric matrices

Let $\{x_1,\ldots,x_n\}$ be a set of $n$ positive real numbers, and consider the $n\times n$ symmetric matrix $\bf M$ whose $(i,j)$-th element is ${\bf M}_{ij} = \min\{x_i, x_j\}$. Is ${\bf M}$ positive semidefinite? I believe it is, but haven't been able to find or construct a proof.

Best Answer

Hint. Suppose $0\le x_1\le x_2\le x_3$. Then $$ \pmatrix{x_1&x_1&x_1\\ x_1&x_2&x_2\\ x_1&x_2&x_3} =x_1\pmatrix{1&1&1\\ 1&1&1\\ 1&1&1} +(x_2-x_1)\pmatrix{0&0&0\\ 0&1&1\\ 0&1&1} +(x_3-x_2)\pmatrix{0&0&0\\ 0&0&0\\ 0&0&1}. $$