# Existence of n-dimensional polyhedron given edges

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.

-
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

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$.

-

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.

-