2
$\begingroup$

We say that a matrix $M\in\mathbb{R}^{n\times n}$ is a distance matrix on a metric space $(X,d)$, if there exist $x_1,\cdots,x_n \in X$ such that $M=[d(x_i,x_j)]_{n\times n}$.

Question. For which metric spaces are the properties of distance matrices investigated?

Improve this question
$\endgroup$
4
  • $\begingroup$ The obvious answer is "all of them", by the characterization that you just gave. So that must not be what you mean, but in that case I am not sure what you are asking. $\endgroup$
    – Nik Weaver
    Jul 5, 2014 at 14:26
  • $\begingroup$ @NikWeaver: I mean that "For which metric spaces does there exist a practical criteria that characterize all distance matrices?". I'll edit my question. $\endgroup$
    – Mahdi
    Jul 5, 2014 at 14:56
  • 1
    $\begingroup$ Mahdi, what I think Nik is trying to say is that any symmetric positive matrix with zeros on the diagonal whose entries obey the triangle inequality is a covered by the scope of your question. $\endgroup$
    – Vidit Nanda
    Jul 5, 2014 at 16:27
  • 4
    $\begingroup$ I think OP is asking for analogues of Schoenberg's (?) theorem which characterizes matrices of mutual distances between k-tuples of points in Euclidean spaces. It is not a bad question, for instance, the similar problem for hyperbolic spaces is open (to the best of my knowledge). The only general result I know is for triples of points (n=3) in the category of path-metric spaces. $\endgroup$
    – Misha
    Jul 5, 2014 at 18:18

1 Answer 1

Reset to default
4
$\begingroup$

The first paper to read is "Metric spaces and positive definite functions" by Schoenberg. (I first learned about this from Igor Rivin many years ago.) It follows from his main result + Corollary 1 that a (say, finite) metric space $(M,d)$ embeds isometrically in a Hilbert space if and only if the "distance matrix" of $(M,d)$ is conditionally negative definite. (Schoenberg first proves it for the matrix of square distances, but then Corollary 1 allows to get rid of squares.)

One can ask the same question about other spaces, like the separable infinite-dimensional real-hyperbolic space. In this setting, there are 4-point conditions on the matrix of distances (coming from negative curvature); but these conditions are insufficient and the problem is open. On the other hand, if one asks for an isometric embedding in the "universal metric tree" of Dyubina/Erschler and Polterovich, then the necessary and sufficient condition is known: It is equivalent to $0$-hyperbolicity of $(M,d)$, which is a combination of triangle inequalities and some 4-point conditions on the distance matrix.

On yet another hand, if one relaxes isometric to quasi-isometric embeddings but considers maps to real-hyperbolic spaces, then the problem was solved (for domains which are "reasonable" Gromov-hyperbolic spaces) by a deep theorem of M.Bonk and O.Schramm in the paper "Embeddings of Gromov hyperbolic spaces".

Lastly, I proved some time ago a general theorem about metric matrix for geodesic metric spaces $(M,d)$: Every triple of distances (subject to triangle inequalities) is realized by a geodesic triangle in $(M,d)$ if and only if $M$ is not quasi-isometric to point, half-line and the line. See here. This settles the question in the case $n=3$ for a reasonable class of metric spaces $(M,d)$.

Improve this answer
$\endgroup$

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.