Vrftsjtryk

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$

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 $ntimes n$ matrix $A$ is a Euclidean distance matrix if and only if $x^top Axle0$ 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 Aegt0$), 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 $alphalt2$; you can see from the example of three points in a line that they can be bent to accommodate $alphalt2$ but not $alphagt2$.

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.