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 ?

  • $\begingroup$ Why can't it have more than 1 positive eigenvalue? $\endgroup$ Jul 10, 2015 at 9:54
  • $\begingroup$ 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. $\endgroup$ Jul 10, 2015 at 9:59
  • $\begingroup$ 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...$ $\endgroup$
    – davcha
    Jul 10, 2015 at 10:04
  • $\begingroup$ 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. $\endgroup$
    – davcha
    Jul 10, 2015 at 10:06
  • $\begingroup$ What is $K$...? $\endgroup$ Jul 10, 2015 at 10:08

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

  • $\begingroup$ So, basically, the data points are on a manifold. Is it possible to "unfold" this manifold ? $\endgroup$
    – davcha
    Jul 10, 2015 at 12:31
  • $\begingroup$ I'm not sure what you mean by "unfold". $\endgroup$ Jul 10, 2015 at 12:35
  • $\begingroup$ 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$. $\endgroup$
    – davcha
    Jul 10, 2015 at 12:39
  • $\begingroup$ Interesting question, but I'm not sure what can be done in this direction, sorry. $\endgroup$ Jul 10, 2015 at 12:44
  • $\begingroup$ Hi davcha, do you mean like to draw a map? To parametrize a curve or surface? $\endgroup$ Jul 11, 2015 at 19:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .