Given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ with positive entries and zero diagonal, is it always possible to construct a high-dimensional configuration in Euclidean space, such that these coordinates give rise to distances from $A$? (high-dimensional configuration implies dimensionality at most $n-1$)

If this is generally not possible, what would be the conditions that have to be met in order to achieve a high-dimensional configuration giving rise to distances in $A$?


1 Answer 1


From suitable linear combinations of the entries of the distance matrix (the matrix of squared distances) one can construct the Gram matrix of the direction vectors from one point (taken as zero) to the others. To be embeddable into a Euclidean space of dimension $r$, this matrix must be positive semidefinite of rank $r$; then the Cholesky factor provides an explicit embedding. (This is old stuff by Schoenberg, http://www.jstor.org/stable/10.2307/1989894; see also my paper http://www.mat.univie.ac.at/~neum/scan/16.pdf and http://www.mat.univie.ac.at/~neum/scan/combcon.pdf)

If one allows a monotone transformation of the distances, an embedding is always possible: Simply add a large constant to all distances between distinct elements.

Related is the technique of multidimensional scaling; http://en.wikipedia.org/wiki/Multidimensional_scaling

  • $\begingroup$ Bottomline: the embedding is not possible with an arbitrary symmetric matrix $A$ with zero diagonal and all remaining entries being positive. On the other hand, if we allow for addition of constant $c$ to entries of $A$, the embedding in at most $n-1$ dimensional space is possible with large $c$. $\endgroup$
    – usero
    Aug 15, 2012 at 13:53
  • 1
    $\begingroup$ ... to the nondiagonal entries $\endgroup$ Aug 15, 2012 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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