Given pairwise distances between points in space how can the dimension of the space the points lie in be determined if the data is incomplete?

Question

My problem concerns a finite set of points in a space, for example (A,B,C,D,E). The information I have on the points is the distances of separations between the points and it comes in two sets. The distance of A from all of (B,C,D,E) and the distance of B from all of (A,C,D,E). The values of these distances are impossible if the points were to lie in a two dimensional space. To determine the minimum dimension that these points could lie in it has been suggested to me to try running an algorithm by the name of Multidimensional Scaling, MDS for short, that maps points in high dimensional space to lower dimensions. This algorithm that takes as input the pairwise distances between all of the points has a "stress" function can be evaluated to see how well these distances are maintained when mapped to the lower dimension. Therefore one possible way of solving my problem could be to to run the algorithm and start from the second dimension and increment upwards until the stress function approaches zero closely enough at which point I will have the answer for what dimension the points lie in. However the pairwise distance data I have is not complete and plugging in zeros for the missing data does not make sense because we believe the all of the points in question to be distinct.

Answer 1

It seems that if the following interpretation of you question is right then the answer is trivial. So, suppose that you have five distinct points $A, B, C, D$, and $E$ belonging to $\mathbb R^n$ for some $n\ge 3$ and you know the distances $d(A,B)$, $d(A,C)$, $d(A,D)$, $d(A,E)$, $d(B,C)$, $d(B,D)$, and $d(B,E)$. I claim that there exist points $A', B', C', D'$, and $E'$ belonging to $\mathbb R^3$ such that $d(X,Y)=d(X',Y')$ for each pair $X, Y$ of letters of $\{A, B, C, D, E\}$. Indeed, choose arbitrary points $A', B'\in\mathbb R^3$ such that $d(A',B')=d(A,B)$. Let $X$ be any of the letters from $\{C, D, E\}$. Let $S^{A'}_{X}$ be a sphere with the center $A'$ and radius $d(A,X)$ and $S^{B'}_{X}$ be a sphere with the center $B'$ and radius $d(B,X)$. Triangle inequality implies that $d(A,X)+d(X,B)\ge d(A,B)$. Therefore the intersection $S(X)=S^{A'}_{X}\cap S^{B'}_{X'}$ is nonempty. It rests to show that there exists an injective map $i:\{C, D, E\}\to\mathbb R^3$ such that $i(X)\in S(X)$ for each $x$. We may encounter a problem with the construction of such a map only if there are different $X, Y$ such that both $S(X)$ and $S(Y)$ are singletons (that is one-point sets) and $S(X)=S(Y)$. But this is impossible, because then points $X$ and $Y$ coincide in $\mathbb R^n$, a contradiction.