Finding positions of vectors in n-dimensional space based on distances between them?

Note that this problem is not well-defined for all n, since distances in n+1-dimensional space can't always be represented by points in n-dimensional space. Also note that any construction has to be translation and rotation invariant since translating and rotating points won't change their distances. One nice thing about distances is that we can map each point i to a vector which is nonzero in dimension i and zero everywhere else and ask which matrix A is such that (xi - xj)^T A (xi - xj) is the distance between all pairs of points xi and xj. This gives you a linear system with n^2 parameters (all entries of A) and n(n-1)/2 equations (all pairs of points). It's easy to see that this system is underdetermined, so you need to specify a norm for each point (the diagional entries of A, essentially). Once you've done that, you can represent each point xi as the product A^(1/2) xi, where A^(1/2) is the matrix square root of A.

So, to recap, the algorithm that will give you an n-dimensional representation for n points given a distance matrix and their norms is to form an n-dimensional matrix with the distances in the off-diagonal entries and norms in the diagonal entries and take its square root. Each row of the square root will be a representation of one point. If you want less dimensionality you can then do a PCA of this square root matrix and see if it's low rank, or truncate the lowest eigenvalues to zero and accept some error in your estimate of the distances.

Multidimensional scaling