Let $a_i \in [-1,1]$ and define the $n\times n$-matrix $M$ by $$ M_{i,j} = \begin{cases} 1-|a_i - a_j|,& \text{if } a_ia_j>0 \\ 0, & \text{otherwise}. \end{cases} $$ $M$ is clearly symmetric with $1$s on the diagonal. Can we prove that it has a non-negative determinant ($\det(M) \ge 0$) or that it is PSD? I was unable to find a counter-example numerically.
If $a_i \in [0,1]$ for each $i$, the "otherwise" case would be of no effect and I can show that the matrix is PSD. However, I'm not sure how to deal with the general case above. Hints are also appreciated.
It is easy to see that when the $a_i$s are arranged in descending order, $M$ becomes a direct sum of three diagonal sub-blocks, where the middle sub-block is zero and each of the other two sub-blocks is a smaller $M$ constructed with those nonzero $a_i$s of the same signs. Therefore it suffices to consider only the case where $a_i>0$ for each $i$.
Then $M$ is positive semidefinite because it is congruent to a nonnegative diagonal matrix. To illustrate, suppose $n=3$ and $a_1\ge a_2\ge a_3>0$. Rename $a_1,a_2,a_3$ as $a,b,c$. Then $M=E+A$, where $E$ denotes the all-one matrix and $$ A=\pmatrix{0&b-a&c-a\\ b-a&0&c-b\\ c-a&c-b&0}. $$ Therefore \begin{align} B&:=P^TAP\\ &:=\pmatrix{1&-1\\ &1&-1\\ &&1} \pmatrix{0&b-a&c-a\\ b-a&0&c-b\\ c-a&c-b&0} \pmatrix{1\\ -1&1\\ &-1&1}\\ &=\pmatrix{a-b&b-a&b-a\\ b-c&b-c&c-b\\ c-a&c-b&0} \pmatrix{1\\ -1&1\\ &-1&1}\\ &=\pmatrix{2(a-b)&0&b-a\\ 0&2(b-c)&c-b\\ b-a&c-b&0},\\ C&:=Q^TBQ\\ &:=\pmatrix{1\\ &1\\ \frac12&\frac12&1} B\pmatrix{1&&\frac12\\ &1&\frac12\\ &&1}\\ &=\operatorname{diag}\left(2(a-b),2(b-c),0\right). \end{align} Hence $Q^TP^TMPQ=\operatorname{diag}\left(2(a-b),2(b-c),1\right)$. Similarly, for a larger $n$, if we enlarge $P$ and $Q$ appropriately, we get $$ Q^TP^TMPQ=\operatorname{diag}\left(2(a_1-a_2),2(a_2-a_3),\cdots,2(a_{n-1}-a_n),1\right). $$ Therefore $M$ is congruent to a nonnegative diagonal matrix and in turn it is positive semidefinite.