Why this matrix is not a distance matrix?

Question

While working on this topic, I came across the following matrix $$D=\begin{pmatrix} 0&1&1&2\\ 1&0&\sqrt 2&1\\ 1&\sqrt 2&0&1\\ 2&1&1&0 \end{pmatrix}$$ This matrix comes from the following: $$D_{ij}=D_{ji}=\sqrt{K_{ii}+K_{jj}-2|K_{ij}|},$$ where $K=XX^\top$ and $X=\begin{pmatrix}-1&-1\\1&0\\0&1\\1&-1\end{pmatrix}$.

Now, my question is: why $D$ is not a distance matrix ? It's obviously not a distance matrix, as its square has more than one positive eigenvalue. But at the same time:

1. It is symmetric
2. $D_{ij}=0 \iff i=j$
3. The triangle inequality is obviously satisfied, since $D_{ij}\le 2 \le D_{ik}+D_{kj}$.

So, what's going on here ?

Answer 1

The kernel is only positive semi-definite if the metric is Euclidean. And indeed, the distances in your matrix are not achievable in that case. But consider the following points in $\mathbb{R}^2$, equipped with the metric obtained from the maximum norm, $d(x,y) = max(|x_1-y_1|,|x_2-y_2|)$:

• $p_1=(0,0)$,
• $p_2=(1,\frac{\sqrt{2}}{2})$,
• $p_3=(1,-\frac{\sqrt{2}}{2})$,
• $p_4=(2,0)$.

These do achieve $d(p_i,p_j) = D_{ij}$.