3
$\begingroup$

I have distance matrix $D$ that was calculated by some distance (non-Euclidean but satisfying distance requirements). Is there a set of points in some Euclidean space such that it generates matrix of Euclidean distances that is equal $D$?

I know that if $G=-HDH/2$ is p.d. where H is the centering matrix then such embedding exists. However, I don't have any information about $G$.

$\endgroup$
  • 5
    $\begingroup$ Choose one of the points are the origin. Use the "polarization identity" to write find $(x,y)$ for any other points $x,y$ using the known distances $|x|^2$, $|y|^2$, $|x+y|^2$. The embedding problem can be solved iff the resulting Gram matrix is positive-definite. $\endgroup$ – Noam D. Elkies Sep 30 '16 at 4:24
  • 2
    $\begingroup$ See also: en.wikipedia.org/wiki/Distance_geometry_problem $\endgroup$ – Noam D. Elkies Sep 30 '16 at 4:25
4
$\begingroup$

No. The magic words are Cayley-Menger, but an explicit answer is given here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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