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
x
1
,
x
2
,
…
,
x
n
are defined on m-dimensional space, then the elements of A are given by
A
=
(
a
i
j
)
;
a
i
j
=
|
|
x
i
−
x
j
|
|
2
2
where ||.||2 denotes the 2-norm on Rm.
Simply put, the element
a
i
j
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. it is a hollow matrix).
The trace of A is zero (by the above property).
A is symmetric (i.e.
a
i
j
=
a
j
i
).
a
i
j
≤
a
i
k
+
a
k
j
(by the triangle inequality)
a
i
j
≥
0
The number of unique (distinct) non-zero values within an n-by-n Euclidean distance matrix is bounded above by
n
(
n
−
1
)
/
2
due to the matrix being symmetric and hollow.
In dimension m, a Euclidean distance matrix has rank less than or equal to m+2. If the points
x
1
,
x
2
,
…
,
x
n
are in general position, the rank is exactly min(n, m + 2).
