Euclidean distance matrix

In mathematics, a Euclidean distance matrix is an n×n matrix representing the spacing of a set of n points in Euclidean space. If A is a Euclidean distance matrix and the points are defined on m-dimensional space, then the elements of A are given by

${\begin{array}{rll}A&=&(a_{ij});\\a_{ij}&=&||x_{i}-x_{j}||_{2}^{2}\end{array}}$

where ||.||₂ denotes the 2-norm on R^m.

Properties

Simply put, the element a_ij describes the square of the distance between the i ^th and j ^th points in the set. By the properties of the 2-norm (or indeed, Euclidean distance in general), the matrix A has the following properties.

• All elements on the diagonal of A are zero (i.e. is it a hollow matrix).
• The trace of A is zero (by the above property).
• A is symmetric (i.e. a_ij = a_ji).
• a_ij^1/2 is less than or equal to a_ik^1/2 + a_kj^1/2 (by the triangle inequality)
• $a_{ij}\geq 0$

References

• Jon Dattorro (2005). Convex Optimization and Euclidean Distance Geometry. Meboo. ISBN 0976401304.; chapter 4.
• James E. Gentle (2007). Matrix Algebra: Theory, Computations, and Applications in Statistics. Springer-Verlag. p. 299. ISBN 0387708723.