11
$\begingroup$

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$

  • 0
    This clearly holds for $n=2$. Perhaps some induction argument can be made using minors?2012-08-25
  • 0
    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.2012-08-25
  • 2
    Note that the term "Euclidean distance matrix" (sometimes abbreviated "EDM") is usually used for the matrix of *squared* Euclidean distances; see [Wikipedia](http://en.wikipedia.org/wiki/Euclidean_distance_matrix). 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$.2012-08-25
  • 1
    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$](http://www.wolframalpha.com/input/?i=table+[|i-j|%2C{i%2C1%2C10}%2C{j%2C1%2C10}])) 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.2012-08-25
  • 0
    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$.2012-08-26

2 Answers 2