Given numbers $\ell_{ij}\in\Bbb R^+$ with $i,j=1,...,n$ but $i\not= j$. Are there any nice criteria for testing whether there exists an $(n-1)$-dimensional simplex with these $\ell_{ij}$ as side length? More precisely: when do exist points $p_1,...,p_n\in\Bbb R^{n-1}$ so that
$$\|p_i-p_j\|=\ell_{ij},\quad \text{for all $i,j=1,...,n$ but $i\not=j$}.$$
Moreover, when is this simplex non-degenerate, i.e. full-dimensional.
Some thoughts
- It is trivial for $n=1,2$.
- For $n=3$ we only have to test the triangle inequalities $\ell_{12}\le \ell_{23}+\ell_{31}$ (and all permutations).
- For $n\ge 4$ it does not suffice to test realizability of all triangle faces, e.g. take $\ell_{12}=\ell_{23}=\ell_{31}=1$ and sufficiently large $\ell_{14}=\ell_{24}=\ell_{34}<1/\sqrt{3}$. All triangles are realizable, but the $3$-simplex is not.
- I might remember that there was some criterion in terms of positive-semidefinite matrices. But I am not sure and I do not remember any search terms.
Construct a matrix A with elements $a_{ij} = \tfrac12 (l_{1,i+1}^2 + l_{1, j+1}^2 - l_{i+1, j+1}^2)$ for $i, j \in \{1, \ldots, n-1\}$. Then the points $p_1, \ldots, p_n \in \mathbb R^{n-1}$ exist such that
$\|p_i - p_j\| = l_{ij}$ for all $i, j = 1, \ldots, n$ but $i \ne j$
if and only if $A$ is positive semidefinite.
Indeed, if such points exist, then $a_{ij} = (p_{i+1} - p_1)^T(p_{j+1} - p_1)$, so $A$ is a matrix of the form $X^T X$ which is positive semidefinite.
In the other direction, for any positive semidefinite matrix $A$ there exist vectors $x_i$ such that $a_{ij} = x_i^Tx_j$. Since there are $n-1$ vectors in total, we can make then at most $(n-1)$-dimensional, by choosing some orthonormal basis in the vector space spanned by these vectors. Now choose a random point $p_1 \in \mathbb R^{n-1}$ and set $p_{i+1} = p_1 + x_i$ for $i = 1, \ldots, n-1$. Easy to check that the distances between $p_i$ will be as required.
So, we just need to check if $A$ is positive semidefinite, which can be done by the Sylvester criterion: check if the determinant of any $k\times k$ minor is nonnegative. For example, for $n = 3$, after some simplification we get the inequality $$ (l_{13} + l_{23} - l_{12}) (l_{23} + l_{12} - l_{13})(l_{12} + l_{13} - l_{23}) (l_{13} + l_{23} + l_{12}) \ge 0 $$ which for nonnegative $l$ is equivalent to the triangle inequalities.