---
tag: 4B0R70F4VE
kind: statement
role: theorem
name: Schoenberg's embedding criterion
msc: [51K05, 15B48]
uses: [1BCJ7A73KS, 01MMVW8CKC, 00SPJSDT3Z, 0ZC9YTXZRY]
about: [1BCJ7A73KS]
sources:
  - url: https://en.wikipedia.org/wiki/Euclidean_distance_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.

1. $D$ is a [[Euclidean distance matrix|1BCJ7A73KS]] if and only if $G$ is [[positive semidefinite|01MMVW8CKC]].
2. In that case, points of $\R^k$ realize $D$ if and only if $k$ is at least the [[rank|0ZC9YTXZRY]] 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|00SPJSDT3Z]] 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.

## Explanations

### L1 human

A table of squared distances comes from real points exactly when a related matrix has no negative eigenvalues.
This turns a geometric question into a check that a computer does quickly.
The number of nonzero eigenvalues tells you how many dimensions the points need.

### L2 human

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|HPW5F0GQ4B]], and it is closely related to the [[Cayley–Menger determinant|KGC5CYDF53]].
The criterion is named after Isaac Schoenberg.