Distance Matrix

For an ordered list in a metric space with metric , the distance matrix of is the square matrix

(1)

It is symmetric, has zero diagonal and nonnegative entries, and its entries obey the triangle inequality . Conversely, any matrix with these properties and with iff defines a metric on its index set. A dissimilarity matrix need not satisfy all of these conditions.

Suppose , ..., are points in a Euclidean space. The matrix of their squared distances,

(2)

is commonly called a squared Euclidean distance matrix, or sometimes simply a Euclidean distance matrix. Let be the all-ones vector and define

			(3)
			(4)

Then is the gram matrix of the points after translating their geometric centroid to the origin. A symmetric matrix with zero diagonal is a squared Euclidean distance matrix iff is positive semidefinite; equivalently, whenever (Schoenberg 1935). The smallest Euclidean dimension in which the distances can be realized is (Young and Householder 1938). If contains unsquared Euclidean distances, these criteria are applied to .

If is nonzero and the points have affine dimension , then . More precisely, the rank is when the points lie on a hypersphere in their affine hull, and is otherwise (Gower 1985). Thus an affinely two-dimensional configuration gives a squared Euclidean distance matrix of rank at most 4, with rank 3 when the points lie on a circle.

Moreover, every nonzero squared Euclidean distance matrix has exactly one positive eigenvalue; all its other nonzero eigenvalues are negative.

A graph distance matrix is the distance matrix obtained from the graph distances among the vertices of a graph. Distance matrices also serve as input to multidimensional scaling and other methods that reconstruct or approximate point configurations from pairwise distances.

The distance matrix of a list of objects can be computed in the Wolfram Language using DistanceMatrix[x1, ..., xn], with the metric specified by the DistanceFunction option when needed. Choosing SquaredEuclideanDistance as the distance function produces .