Theorem 4.1 of this paper says that there exist distance matrices that are not conditionally negative definite (CND). How do I construct an example of a distance matrix that is not CND? Do you know an example?

## 1 Answer

You need a finite metric space $(X,d)$ such that the same space with the square root of the distance $(X,\sqrt{d})$ is not isometrically embeddable into any Euclidean space. An example is given by the metric space defined as the 0-skeleton of the graph with vertices $A,B,C,D,E$, and edges $\{AB,AC,AD,BE,CE,DE\}$ (so all the other distances are 2).

Assume by contradiction that $(X,\sqrt{d})$ is embeddable into a Euclidean space. Denote by $a,b,c,d,e$ the images: then $ab,ac,ad,be,ce,de$ are 1 and the other distances are $\sqrt{2}$. The triangle $bcd$ is equilateral with edge $\sqrt{2}$. Each of $a,e$, along with $bcd$, forms a pyramid with base $bcd$ and other edges equal to $1$. So if $o$ is the center of $bcd$, we have, by basic 3-dimensional Euclidean geometry, $oa=oe=1/\sqrt{3}$. So $ae\le 2/\sqrt{3}$. But $ae=\sqrt{2}$ and this is a contradiction.

So the distance matrix $\begin{pmatrix}0 & 1 & 1 & 1 & 2\\1 & 0 & 2 & 2 & 1\\1 & 2 & 0 & 2 & 1\\1 & 2 & 2 & 0 & 1\\2 & 1 & 1 & 1 & 0\end{pmatrix}$ is not conditionally negative definite.

As far as I remember, a simple argument shows that no example exists in size $\le 4$.

distance matrixis a matrix obtained by pulling back the distance through a map $u$ from $X$ to any metric space $Y$ (thus defining $f^*u(x,x')=u(f(x),f(x'))$). This is the same as requiring the usual (semi)metric axioms. Aconditionally negative definite matrixis by definition a matrix obtained by pulling back thesquareof the distance through a map from $X$ to a Hilbert space. $\endgroup$