Euclidean distance matrix

Definition

Let $n \ge 1$ . Let $D = (d_{ij})$ be a real $n \times n$ matrix. It is a Euclidean distance matrix if some integer $k \ge 1$ and points $x_1, \ldots, x_n \in \R^k$ satisfy $d_{ij} = \norm{x_i - x_j}^2 \quad \text{for all } i, j,$ where $\norm{x_i - x_j}$ is the Euclidean distance of $x_i$ and $x_j$ . The points $x_1, \ldots, x_n$ are then said to realize $D$ .

Remarks

Every Euclidean distance matrix is symmetric, has zero diagonal and has nonnegative entries.

Example: the points $0, 1, 3 \in \R$ give $D = \begin{pmatrix} 0 & 1 & 9 \\ 1 & 0 & 4 \\ 9 & 4 & 0 \end{pmatrix},$ since $1^2 = 1$ , $3^2 = 9$ and $2^2 = 4$ .

Non-example: the matrix with rows $(0, 1, 9)$ , $(1, 0, 1)$ and $(9, 1, 0)$ is symmetric with zero diagonal, but it is not a Euclidean distance matrix. Points realizing it would have distances $1$ , $1$ and $3$ , and $3 > 1 + 1$ violates the triangle inequality.

Some authors use the distances themselves instead of their squares.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`668HBS6C06`
URI	`m2://668HBS6C06`
Kind	definition
Writing	W0 stub
MSC	51K05, 15B48
Defines	Euclidean distance matrix
Uses	Euclidean distance

Euclidean distance matrix

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here