Theorem 4.1 of [this](http://projecteuclid.org/download/pdf_1/euclid.lnms/1215465631) 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?



Example distance metric that is not conditionally negative definite
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$.


