3

Hopefully someone can help me with a reference for this problem, or the construction. I have a metric defined on $n$ points in $\mathbb{R}^2$. Is it possible to find a higher dimensional Euclidean space so that you can place $n$ points in such a way that these distances are attained with the standard metric? If it is possible, is there a formula of some sort to determine the locations (up to rigid motions)?

To make it more explicit: If $\{x_i\}$ are the original points with distances $d(x_i, x_j)$ and $\{y_i\}$ are the images in $\mathbb{R}^N$, find $y_i$ such that $$|y_i - y_j| = d(x_i, x_j)$$

muaddib
  • 8,267
  • 1
    Wouldn't the metric in the higher dimension be equal to the metric in $\mathbb R^2$ when restricted to $\mathbb R^2$? So I'm guessing the answer is no. – Gregory Grant May 24 '15 at 13:24
  • Perhaps my statement was unclear. The $n$ points will be given new locations in $\mathbb{R}^n$ so you can't really restrict to $\mathbb{R}^2$. I'l modify it. – muaddib May 24 '15 at 13:27
  • In that case my intuition tells me the answer is yes. That's not a proof though, I'll think about it. – Gregory Grant May 24 '15 at 13:29
  • Using the notation I added to the problem, maybe I just need to set up a system of quadratic equations and solve them? $$|y_i - y_j|^2 = d(x_i, x_j)^2$$ – muaddib May 24 '15 at 15:39

1 Answers1

5

This is not always possible. Let $e_1=(1,0)$ and $e_2=(0,1)$ be the standard basis vectors in $\mathbb R^2$. Take $X=\{e_1,e_2,-e_1,-e_2\}\subseteq\mathbb R^2$, equipped with the $\infty$-metric, i.e. $$d(e_1,e_2)=d(e_1,-e_2)=d(e_2,-e_1)=d(-e_1,-e_2)=1$$ and $$d(e_1,-e_1)=d(e_2,-e_2)=2.$$

This space $X$ cannot be isometrically embedded into any $\mathbb R^n$. The reason is as follows: suppose $f:X\to\mathbb R^n$ is an isometric embedding. Since $$2=d(e_1,-e_1)=d(e_1,e_2)+d(e_2,-e_1)=1+1,$$ we must have $$\|f(e_1)-f(-e_1)\|=\|f(e_1)-f(e_2)\|+\|f(e_2)-f(-e_1)\|.$$ But in the euclidean case, equality in the triangle inequality is possible only if the points are collinear. In fact, comparing the distances, $f(e_2)$ has to be the midpoint between the other two: $$f(e_2)=\frac{f(e_1)+f(-e_1)}2.$$ Similarly, $$2=d(e_1,-e_1)=d(e_1,-e_2)+d(-e_2,-e_1)=1+1,$$ so we must have $$f(-e_2)=\frac{f(e_1)+f(-e_1)}2.$$ But this means that $f(e_2)=f(-e_2)$, contradicting the fact that $f$ is an embedding.

Dejan Govc
  • 17,007
  • Very pretty. If you'd like to keep an eye out, I'll be then asking for sufficient conditions or adding extra structure (e.g. a metric) in a followup question to see when it can be done. – muaddib May 24 '15 at 16:18
  • 2
    Very nice. Arguing less rigorously, since the four points will lie in a three-dimensional affine subspace, we can just as well assume $n=3$. Then the first equality forces them to be vertices of simplex with all edges of length $1$ (I know, this is only a reformulation...) and this already determines all distances. – Carsten S May 24 '15 at 16:22
  • Regarding my previous comment, I mean I will ask those in a separate post. – muaddib May 24 '15 at 16:25
  • @muaddib: thanks. Sounds interesting, I'll probably take a look. – Dejan Govc May 24 '15 at 16:26