# Why this matrix is not a distance matrix?

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 ?

• Why can't it have more than 1 positive eigenvalue? Jul 10, 2015 at 9:54
• And what is diag supposed to mean? If working on a matrix it produces a vector with diagonal elements in it, no? You can't add a vector to a matrix. Jul 10, 2015 at 9:59
• Diag is a shortcut used in Matlab. Diag(K) is the column vector with entries equal to the diagonal of K. Sure you can't add vectors and matrix, I should have written $D_{ij} = K_{ii}^2+K_{jj}^2...$ Jul 10, 2015 at 10:04
• Also, distance matrices always have exactly one positive eigenvalue. If not, it means that $K$ is not positive semi definite, thus does not describe a metric. Jul 10, 2015 at 10:06
• What is $K$...? Jul 10, 2015 at 10:08

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}$.

• So, basically, the data points are on a manifold. Is it possible to "unfold" this manifold ? Jul 10, 2015 at 12:31
• I'm not sure what you mean by "unfold". Jul 10, 2015 at 12:35
• I know "unfold" is very vague. But, for example, you can obtain an Euclidean representation of a graph, that gives you the commute-time distance between nodes of this graph. In the example given by the matrix $D$, I don't really know what "unfold" would mean. I think I'm trying to figure what is the interpretation of the negative eigenvalues of the kernel associated with $D$. Jul 10, 2015 at 12:39
• Interesting question, but I'm not sure what can be done in this direction, sorry. Jul 10, 2015 at 12:44
• Hi davcha, do you mean like to draw a map? To parametrize a curve or surface? Jul 11, 2015 at 19:14