27
$\begingroup$

There have been a couple questions recently regarding metric spaces, which got me thinking a bit about representation theorems for finite metric spaces.

Suppose $X$ is a set equipped with a metric $d$. I had initially assumed there must be an $n$ such that $X$ embeds isometrically into $\mathbb{R}^n$, but the following example shows that this doesn't quite work:

Take for $X$ the vertex set of any graph, and let $d(x,y)$ be the length (in steps) of the shortest path connecting $x$ to $y$. Then for a minimal path connecting $x$ to $y$, the path must map to a straight line in $\mathbb{R}^n$. This is because $\mathbb{R}^n$ has the property that equality in the triangle inequality implies colinearity.

So take a graph such that $x$ and $y$ have $d(x,y) \geq 2$ and two minimal paths between them; a plain old square will do the trick. The two minimal paths must each get mapped to the same line in $\mathbb{R}^n$, so the map cannot be an isometry (nor even an embedding, for that matter).

This gives us one obstruction to representability: a finite metric space cannot be representable unless it satisfies the property $d(x,y) = d(x,z) + d(z,y) \wedge d(x,y) = d(x,z') + d(z',y) \wedge d(x,z) = d(x,z') \implies z = z'$. In the graph case this means "unique shortest paths"; I'm not clear if there is a snappy characterization like that in the general case.

Question #1: Is this the only obstruction to representability?

In a slightly different direction, you could get around the problem above by trying to represent the finite metric spaces on some surface instead of $\mathbb{R}^n$. This at least works in the graph case by replacing the points with little discs and the edges with very fat ribbons of length 1. Then compactifying the whole thing should give a surface into which the graph embeds isometrically. This suggests the answer to

Question #2a: Does every finite metric space have a representation on a surface?

is yes, as long as the answer to

Question #2b: Does every finite metric space have a global scaling which embeds $\epsilon$-isometrically into a graph?

is also yes. The $\epsilon$ is to take care of finite metric spaces with irrational distances.

Of course, there is also the important

Question #0: Is there some standard place I should have looked for all this?

$\endgroup$
4
  • 3
    $\begingroup$ This question was already answered: mathoverflow.net/questions/7794/… $\endgroup$ Jan 20, 2010 at 7:51
  • $\begingroup$ Ryan, I agree that the question you link to is closely related, but do you think the answers there really answer Matt's questions? If so, whose answers? $\endgroup$ Jan 20, 2010 at 14:53
  • $\begingroup$ Oh, Anton Petrunin's answer to this question tells me. $\endgroup$ Jan 20, 2010 at 14:56
  • $\begingroup$ I vaguely remember that Hilbert characterized spaces embeddable into Euclidean $\mathbb R$, he has introduced a related matrix. Possibly others had this result but certainly Hilbert had an input (eh, it had to be Hilbert :-) ). Wasn't there a classic monograph by Blumenthal(?) on the metric theory of metric spaces? $\endgroup$ Dec 29, 2015 at 6:13

8 Answers 8

24
$\begingroup$

Since the paper referred to by Hagen Knaf is published by Springer, it may not be available to one and all. The (publicly viewable) MathSciNet reference is: MR355836.

It's a very short paper (7 pages) and the main theorem is:

Theorem A metric space can be embedded in Euclidean n-space if and only if the metric space is flat and of dimension less than or equal to n.

Clearly, the two terms "flat" and "dimension" need expanding. To define these, Morgan considers simplices in the metric space; that is, an n-simplex is simply an ordered (n+1)-tuple of elements of the metric space. Given such an n-tuple, say $(x_0, \dots, x_n)$, Morgan defines $D(x_0,\dots,x_n)$ to be the determinant of the matrix whose $(i,j)$th entry is

$$ \frac{1}{2}\left(d(x_0,x_i)^2 + d(x_0,x_j)^2 - d(x_i,x_j)^2\right) $$

A metric space is flat if this is positive for all simplices. If it is flat, its dimension (if this exists) is the largest n for which there is an n-simplex with this quantity positive.

The argument (on a skim read) is quite cunning. Rather than go for a one-shot embedding, Morgan defines a map into $\mathbb{R}^n$ of the appropriate dimension and then uses that map to define an inner product on $\mathbb{R}^n$ with respect to which the map is an embedding. Standard linear algebra then completes the argument.

Now finite dimension, in this sense, is clearly very strong. It basically says that the metric is controlled by n points. The flatness condition says that those n points embed properly (and presumably rules out the examples in the question and the first answer). But then, that's probably to be expected since embeddability into Euclidean space is similarly a strong condition.

$\endgroup$
5
  • 1
    $\begingroup$ Hmm. I guess flat is non-negative determinants? $\endgroup$ Jan 20, 2010 at 12:46
  • 1
    $\begingroup$ Andrew: the matrix you mention (let's call it $N$) is closely related to the matrix $M$ in my answer. By an elementary manipulation, your $N$ is positive semidefinite iff my $M$ is conditionally negative semidefinite. In fact, Schoenberg used this equivalence in the 1935 paper that I cited. $\endgroup$ Jan 20, 2010 at 15:15
  • $\begingroup$ @Mariano: So I understand from the paper. @Tom: as a guess, then, Morgan's contribution was to extend from finite to arbitrary metric spaces. @Everyone else (since this attracted a vote against): My original intention was simply to leave a comment which made Hagen Knaf's answer a little more accessible, but then on reading the paper I decided that the result was simple enough to quote, hence the expansion of a comment into an answer. $\endgroup$ Jan 21, 2010 at 8:25
  • $\begingroup$ It sounds like this merely reproves the characterization of embeddability in terms of Cayley-Menger determinants ? $\endgroup$ Oct 14, 2010 at 20:08
  • $\begingroup$ By the way, important to note that the matrix is $n\times n$ (and not $(n+1)\times (n+1)$) :) $\endgroup$ Jun 20, 2023 at 22:22
15
$\begingroup$

Re question 1: I think the first person to characterize the finite metric speaces that embed in some Euclidean space was Schoenberg, in

I.J. Schoenberg, Remarks to Maurice Fréchet's article "Sur la définition axiomatique d'une classe d'espace distanciés vectoriellement applicable sur l'espace de Hilbert", Annals of Mathematics 36 (1935), 724--732.

There he shows that a finite metric space $\{a_0, \ldots, a_n\}$ can be embedded in some Euclidean space if and only if the matrix $M = (d(a_i, a_j)^2)$ of squared distances is conditionally negative semidefinite, that is, $$ \mathbf{x}^t M \mathbf{x} \leq 0 $$ whenever $\mathbf{x} = (x_0, \ldots, x_n) \in \mathbb{R}^{n + 1}$ with $\sum x_i = 0$.

In fact, Schoenberg's result is even sharper. For an $(n + 1)$-point space $A$ as above, the following are equivalent:

  • $A$ embeds isometrically in Hilbert space $L^2$
  • $A$ embeds isometrically in $\mathbb{R}^n$
  • the matrix $M$ of squared distances is conditionally negative semidefinite.

Incidentally, Fréchet and Schoenberg also showed that every finite metric space embeds in $(\mathbb{R}^n, d_\infty)$ for some $n$, where $d_\infty$ is the metric coming from the $\infty$-norm $\Vert\cdot\Vert_\infty$. The proof is pretty short and sweet.

$\endgroup$
0
8
$\begingroup$

For Question 1: What about $K_{1,3}$ (one vertex connected to 3 vertices) with the shortest path metric?

For the rest, there is this theorem by Bourgain (1985, "On lipschtitz embedding of finite metric spaces in Hilbert space") that says: Any n point metric space can be embedded in $\ell_2$ with distortion $O(\log n)$.

Finally, "Low Distortion Embeddings of Finite Metric Spaces" (Piotr Indyk, Jiri Matousek) is expository on lots of such results and then there are more papers here (including the article)

$\endgroup$
1
  • 1
    $\begingroup$ You answer a different question, but I agree --- your question is more interesting :) $\endgroup$ Jan 21, 2010 at 0:27
6
$\begingroup$

There is a related question here (with an answer similar to Andrew's --- it answers question #1).

Question #2a: NO, say take 4 points p,x,y,z such that |px|=|py|=|pz|=1 and $|xy|=|yz|=|zx|=2$.

Question #2b: YES, there is a trivial embedding into metric graph, which can be approximated arbitrary well by graph with fixed length of edges.

Question #0: Some related questions appear when one plays with definition of Alexandrov space, check also Gromov's CAT(κ)-Spaces: Construction and Concentration Link

$\endgroup$
7
  • $\begingroup$ I don't see that your proposed counterexample for Q2a quite works; can't you put the tripod on a disc of radius 1 and build mountain ranges into each triangular wedge to penalize paths through that region? Geodesics should then all pass near the center, giving the right distances. $\endgroup$ Jan 20, 2010 at 19:33
  • $\begingroup$ By surface (I thought you mean) a Riemannian 2-manifold. In this case, the 4-point space can not be embedded since geodesic do not bifurcate... $\endgroup$ Jan 20, 2010 at 20:50
  • $\begingroup$ Yes, but there is no reason that the geodesic connecting $x$ to $y$ must go through $p$ as far as I can tell. $\endgroup$ Jan 20, 2010 at 20:59
  • $\begingroup$ Since $|xy|=|xp|+|py|$, there is a geodesic $[xy]$ which pass through $p$. The same way, there is a geodesic $[xz]$ which pass through $p$. That can not happen... $\endgroup$ Jan 20, 2010 at 21:25
  • $\begingroup$ It is not true that $|xy| = |xp| + |py|$ implies a geodesic $[xy]$ through $p$. For example, there could be a minimal length geodesic $xy$ which is far away from (say, non-homotopic to) the path $xp \cup py$. $\endgroup$ Jan 20, 2010 at 22:20
3
$\begingroup$

The problem under which conditions a finite metric space $(X,d)$ can be embedded isometrically into Euclidean space $\mathbb{R}^n$ is answered in the article

C.L. Morgan, EMBEDDING METRIC SPACES IN EUCLIDEAN SPACE, Journal of Geometry. Vol. 5/1 1974

The answer is too technical to write it down here, but if I remember it well, the article can be found in the Web.

$\endgroup$
1
  • 2
    $\begingroup$ How could it be too technical to write it down here? $\endgroup$ Jan 20, 2010 at 11:10
3
$\begingroup$

It's probably worth pointing out that (unlike for $L_2$) any finite metric space can be embedded into a finite-dimensional $L_\infty$ space with no distortion. Simply map each of the $n$ points of the metric space to the $n$-dimensional vector of distances from all points. (For a closely related construction, see the tight span.)

$\endgroup$
4
  • $\begingroup$ It was already pointed out by Tom Leinster. Also, this construction has a name "Kuratowski embedding". $\endgroup$ Jan 21, 2010 at 0:01
  • $\begingroup$ @AntonPetrunin, wasn't it "Kuratowski-Wojdysławski embedding"? They certainly published a joint paper on the given topic. $\endgroup$ Dec 29, 2015 at 6:07
  • $\begingroup$ @WłodzimierzHolsztyński Check en.wikipedia.org/wiki/Kuratowski_embedding --- you will see that it is fair to call it "Fréchet embedding". In general it is very wrong to call theorems by name of their authors, it is always better to use some short description as for example "non-squizing theorem". $\endgroup$ Dec 29, 2015 at 12:40
  • $\begingroup$ Do you happen to have a reference for the Kuratowski–Wojdysławski paper? It should probably be cited from the Wikipedia article. $\endgroup$ Dec 29, 2015 at 18:58
3
$\begingroup$

For Question 0 :

For isometric embedding a standard reference is

Deza, M.; Laurent, M. (1997), Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer, MR1460488, ISBN 354061611X

For approximate embeddings a beautiful exposition from Matouseks' book:

Lectures on Discrete Geometry. Jiri Matousek. Year of Publication: 2002. ISBN:0387953744

$\endgroup$
2
$\begingroup$

I will just quote from the introduction of Johnson and Kambites' paper "Idempotent tropical matrices and finite metric spaces" in giving a cheating answer that exploits the tropical--versus the usual--structure of $\mathbb{R}$:

"every finite semimetric on $n$ points can be embedded into tropical $n$-space."

Here, a semimetric is a function satisfying all the distance axioms except symmetry (so in particular, a metric is also a semimetric).

$\endgroup$
3
  • 1
    $\begingroup$ This is just the Kuratowski embedding or $L_\infty$ embedding alluded to in Tom Leinster's and David Eppstein's comments. (In enriched category theory terms this is the Yoneda embedding.) I would say that there is nothing specifically tropical being used here. $\endgroup$ Apr 3, 2013 at 9:41
  • $\begingroup$ @Matt (1) At some point I observed that an unweighted graph is isometrically embeddable into a strictly convex Banach space iff it is a clique or a path. You can find this and more on this in my book "Metric embeddings". Possibly one can prove something of this type for weighted graphs. $\endgroup$ Jul 29, 2013 at 14:00
  • $\begingroup$ @Matt You can get out of the statement of the previous comment many examples for Question 1. (2) Matousek, on his web page, has lecture notes on metric embeddings which could be considered as an updated version of his mentioned book. (3) I think that an isometric embedding into $\ell_\infty$ should be called Frechet embedding (1910). $\endgroup$ Jul 29, 2013 at 14:09

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.