Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following assertion is true in $2$ and $3$ dimensions:

Given $\sigma_{ij},\ 1\leq i\neq j\leq n$ with $\sigma_{ij}=\sigma_{ji}$ and $\sigma_{ij} \leq \sigma_{ik}+\sigma_{kj}$, then there exist $A_1,...,A_n \in \Bbb{R}^{n-1}$ such that $dist(A_i,A_j)=\sigma_{ij}$.

Is it possible to prove this for higher dimensions? I tried an induction argument, but I can't seem to imagine what is happening in higher dimensions. Is there an easier proof, without induction? Thank you.

share|improve this question
    
I think what you mean is $|A_i - A_j| = \sigma_{ij}$. –  Robert Israel Feb 26 '12 at 20:42
    
Yes. I used the same notation as in classical geometry –  Beni Bogosel Feb 26 '12 at 21:00

2 Answers 2

up vote 1 down vote accepted

Try $n=4$ with all distances $1$ except $|A_1 - A_4|$. Note that $A_1, A_2, A_3$ and $A_2, A_3, A_4$ must form equilateral triangles of side 1 with side $A_2A_3$ in common, and conclude that we must have $|A_1 - A_4| \le \sqrt{3}$. But the triangle inequalities allow $\sigma_{14}$ to be up to $2$.

share|improve this answer

It is not possible even for four points. Consider the following distance table:

$$ \sigma = \begin{pmatrix} 0 & 18 & 18 & 10 \\ 18 & 0 & 18 & 10 \\ 18 & 18 & 0 & 10 \\ 10 & 10 & 10 & 0 \end{pmatrix} $$

This table satisfies the conditions: it is symmetric and the triangle inequalities hold. However, this table cannot be realized by vectors in $\mathbb{R}^3$. Let's try to construct such vectors $A_1, \dotsc, A_4$. Without loss of generality we can take $A_1 = 0$. Then $||A_k||^2 = \sigma_{1,k}^2$ for $k \in \{2,3,4\}$. For $i, j \geq 2$ and $i \neq j$ the following equality must hold:

$$ \sigma_{i,j}^2 = ||A_i - A_j||^2 = ||A_i||^2 + ||A_j||^2 - 2\langle A_i, A_j\rangle = \sigma_{1,i}^2 + \sigma_{1,j}^2 - 2 \langle A_i, A_j \rangle $$

and so $\langle A_i, A_j \rangle = (\sigma_{1,i}^2 + \sigma_{1,j}^2 - \sigma_{i,j}^2)/2$. The Gram matrix $A_{i,j} = \langle A_{i+1}, A_{j+1} \rangle$ for the vectors $A_2, A_3, A_4$ must therefore be

$$ A = \begin{pmatrix} 324 & 162 & 162 \\ 162 & 324 & 162 \\ 162 & 162 & 100 \end{pmatrix}. $$

However, $\det(A) = -629856 < 0$ and this is impossible for a Gram matrix in Euclidean three-space since such a matrix must be positive (semi-)definite.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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