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?
$\begingroup$
$\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$– YCorCommented 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$– YCorCommented Jan 21, 2016 at 17:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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$.
