Schoenberg's embedding criterion

Builds on Euclidean distance matrix Positive semidefinite matrix Gram matrix Rank of a matrix

Statement

Let $n \ge 2$ and let $D = (d_{ij})$ be a real symmetric $n \times n$ matrix with $d_{ii} = 0$ for all $i$ . Let $G$ be the $(n - 1) \times (n - 1)$ matrix with entries $G_{ij} = \frac{1}{2} \left( d_{1i} + d_{1j} - d_{ij} \right), \qquad 2 \le i, j \le n.$ Then the following hold.

$D$ is a Euclidean distance matrix if and only if $G$ is positive semidefinite.
In that case, points of $\R^k$ realize $D$ if and only if $k$ is at least the rank of $G$ .

Remarks

If $x_1, \ldots, x_n$ realize $D$ , translate so that $x_1 = 0$ . The polarization identity $\ip{x_i}{x_j} = \frac{1}{2}(\norm{x_i}^2 + \norm{x_j}^2 - \norm{x_i - x_j}^2)$ shows that $G$ is the Gram matrix of $x_2, \ldots, x_n$ , hence positive semidefinite. Conversely, a positive semidefinite $G$ of rank $k$ factors as $G = X^T X$ with $X$ a $k \times (n - 1)$ matrix. Its columns, together with $x_1 = 0$ , realize $D$ in $\R^k$ .

Example: the matrix with rows $(0, 1, 9)$ , $(1, 0, 1)$ and $(9, 1, 0)$ gives $G = \begin{pmatrix} 1 & 4.5 \\ 4.5 & 9 \end{pmatrix}$ . Its determinant is $9 - 20.25 < 0$ , so $G$ is not positive semidefinite and $D$ is not a Euclidean distance matrix.

An equivalent form uses the centring matrix $J = I - \frac{1}{n} \mathbf{1}\mathbf{1}^T$ : $D$ is a Euclidean distance matrix if and only if $-\frac{1}{2} J D J$ is positive semidefinite.

Going deeper

For a student

The criterion is the basis of classical multidimensional scaling. One forms $-\frac{1}{2} J D J$ , takes its eigendecomposition, and reads off coordinates from the top eigenvectors. It is the matrix side of distance geometry, and it is closely related to the Cayley–Menger determinant. The criterion is named after Isaac Schoenberg.

Reading path

To understand this page from the ground up, read these 5 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

Euclidean distance matrix concept
Gram matrix concept
Positive semidefinite matrix concept
Rank of a matrix concept
Schoenberg's embedding criterion statement

Tag	`4B0R70F4VE`
URI	`m2://4B0R70F4VE`
Kind	statement, theorem
Writing	W0 stub
MSC	51K05, 15B48
Status	This copy of the site has no build data. Run `m2 status 4B0R70F4VE`.
About	Euclidean distance matrix
Uses	Euclidean distance matrix, Positive semidefinite matrix, Gram matrix, Rank of a matrix