Is the determinant of this symmetric matrix non-negative? 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.
 A: 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.
