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