# Nonsingularity of Euclidean distance matrix

Let $x_1, \dots, x_k \in \mathbb{R}^n$ be distinct points and let $A$ be the matrix defined by $A_{ij} = d(x_i, x_j)$, where $d$ is the Euclidean distance. Is $A$ always nonsingular?

I have a feeling this should be well known (or, at least a reference should exists), on the other hand, this fact fails for general metrics (take e.g. path metric on the cycle $C_4$)

edit: changed number of points from $n$ to general $k$

-
This clearly holds for $n=2$. Perhaps some induction argument can be made using minors? – Alex Becker Aug 25 '12 at 18:22
wlog let one of the pts be zero and the others located at $v_i$. Suppose $\Vert v_i \Vert = 1$. The distance matrix is $2 1 - (v_i \cdot v_j)$ where $1$ is the matrix of all ones and $(v_i \cdot v_j) = V^tV$ where $V$ has the $v_i$ down the rows. Both of these matrices can be very singular so I don't think the matirx is necessarily invertible. – mike Aug 25 '12 at 19:28
Note that the term "Euclidean distance matrix" (sometimes abbreviated "EDM") is usually used for the matrix of squared Euclidean distances; see Wikipedia. An EDM can be singular, e.g. in the case of a square, whose EDM is the distance matrix of the path metric on the cycle $C_4$. – joriki Aug 25 '12 at 21:52
The matrix (your non-squared one) for a unit $k$-simplex (with $n=k+1$) has one positive eigenvalue $k$ and $k$ negative eigenvalues $-1$. Empirically, the matrix for a line of $n$ equidistant points (e.g. for $n=10$) seems to also have one positive eigenvalue and $n-1$ negative eigenvalues. Since one might expect these two cases to be extreme in some sense, this suggests that the matrix might always have the same signature, in which case none of the eigenvalues would ever cross $0$ to make it singular. – joriki Aug 25 '12 at 22:23
We can write the distance matrix in terms of a matrix with pairwise displacement vectors as columns. Can we use some linear independence argument on this displacement matrix? E.g. there can be a maximum of 3 linearly independent vectors in $\mathbb{R}^3$. And it seems linked to the fact that a squared Euclidean distance matrix in $\mathbb{R}^3$ will have rank at most $3$. – Kartik Audhkhasi Aug 26 '12 at 0:19

I think it should be possible to show that your distance matrix is always nonsingular by showing that it is always a Euclidean distance matrix (in the usual sense of the term) for a non-degenerate set of points. I don't give a full proof but sketch some ideas that I think can be fleshed out into a proof.

Two relevant papers on Euclidean distance matrices are Discussion of a Set of Points in Terms of Their Mutual Distances by Young and Householder and Metric Spaces and Positive Definite Functions by Schoenberg. They show that an $n\times n$ matrix $A$ is a Euclidean distance matrix if and only if $x^\top Ax\le0$ for all $x$ with $e^\top x=0$ (where $e$ is the vector with $1$ in each component) and that the affine dimension of the points is $n$ if and only if the inequality is strict.

It follows that a Euclidean distance matrix can only be singular if the affine dimension of the points is less than $n$: If the affine dimension is $n$, there cannot be an eigenvalue $0$, since there is a positive eigenvalue (since $e^\top Ae\gt0$), and the span of these two eigenspaces would non-trivially intersect the space $e^\top x=0$, contradicting the negative definiteness of $A$ on that space.

To use all this for your case, one could try to show that a distance matrix in your sense is always a Euclidean distance matrix in the usual sense for points with affine dimension $n$. I think this could be done by continuously varying the exponent $\alpha$ in $A_{ij}=d(x_i,x_j)^\alpha$ from $1$ to $2$ and showing a) that there is always a direction in which the points can move such that $A$ remains their distance matrix with the changing exponent and b) that this movement necessarily causes them to have affine dimension $n$.

To get a feel for how this might work, consider a square: The movement would bend the square into a tetrahedron. The proof would need to account for the fact that this seems to hold only for $\alpha\lt2$; you can see from the example of three points in a line that they can be bent to accommodate $\alpha\lt2$ but not $\alpha\gt2$.

-
Thanks for answer, although - what happens if the number of points is greater than $n$? Dimension arguments won't work anymore. – Marcin Kotowski Aug 26 '12 at 11:37
@Marcin: I didn't mention that because you'd originally asked about $n$ points in $\mathbb R^n$. It doesn't make a difference, though; just embed the points in $\mathbb R^k$ (e.g. by adding $0$s) so they're free to move. – joriki Aug 26 '12 at 11:51