0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ For the context, we think of a square matrix as a map $f:X\times X\to\mathbf{R}$ ($X$ being the index set). By definition, a distance matrix is 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. A conditionally negative definite matrix is by definition a matrix obtained by pulling back the square of the distance through a map from $X$ to a Hilbert space. $\endgroup$
    – YCor
    Jan 21, 2016 at 17:30
  • $\begingroup$ That there exist distance matrices that are not CND is predictable by the fact that there exist infinite groups with Kazhdan's Property T. Indeed, given such a group $G$ and a proper left-invariant distance $d$, $(G,d)$ cannot be CND since otherwise we would deduce a metrically proper isometric action of $G$ on a Hilbert space. This implies that there exists a finite subset of $G$ such that $(X,d)$ is not CND. But this is not explicit and it's natural to wonder about an explicit example. $\endgroup$
    – YCor
    Jan 21, 2016 at 17:34

1 Answer 1

4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.