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 is true. Over in the comments of a related question, darij grinberg has just shown that $A$ is negative definite when restricted to the codimension one subspace where the coordinates sum to $0$. Let $\lambda_1 \geq \lambda_2 \geq \cdots \lambda_n$ be the eigenvalues of $A$, and let $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_{n-1}$ be the eigenvalues of $A$ restricted to this subspace, so darij shows that $0 > \mu_1 \geq \cdots \geq \mu_{n-1}$. By the Eigenvalue Interlacing Theorem, we have $\mu_1 \geq \lambda_2 \geq \mu_2 \geq \lambda_3 \geq \cdots \geq \mu_{n-1} \geq \lambda_n$, so we know that $0 > \lambda_2$, ..., $\lambda_n$. So it remains to show that $\lambda_1$ is not zero.
If $\lambda_1$ were $0$, then $A$ would be negative semidefinite. But, letting $\vec{j}$ denote the all ones vector, we have $\vec{j}^T A \vec{j} > 0$, a contradiction.
