linear algebrametric-spaces
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$
How it rotation defined for other metrics/norms/vector spaces?
Some definitions:
$(1)$ Let $C_d$ be the unit circle for a metric $d((x_1,y_1);(x_2,y_2))$.
$(2)$ Let the arc length of $C_d$, with respect to $d$, equal $2 \cdot \pi_d$.
$(3)$ Given two rays that extend from the origin to $C_d$ the angle $\theta_d$ between them is the arc length of the circle contained in the two rays.
$(4)$ We can define $\cos_d(\theta_d)$ as the $x$ value if an angle $\theta_d$ is swept starting from the right and going counter clockwise. Similarly, $sin_d(\theta_d)$ as the $y$ value if an angle $\theta_d$ is swept. In other words the two functions allow us to rotate points about $C_d$.
Results:
Clearly we have $$d((\cos_d(\theta_d),0);(0,\sin_d(\theta_d))=1$$
If we wish to rotate a point $r_1=(x_1,y_1)$ we need to use a matrix $R_d$. Then we can obtain the location of the rotated point as $r_2=(x_2, y_2)$ using,
$$\vec r_1=R_d \cdot \vec r_2$$
$$R_d=\begin{bmatrix} \cos_d(\theta_d) & -\sin_d(\theta_d) \\ \sin_d(\theta_d) & \cos_d(\theta_d) \end{bmatrix}$$
Note that rotation doesn't change the length with respect to the metric $d$. Now we're ready to talk about invariance.
How is rotational invarience defined/calculated in other metrics/norms/vector spaces?
The first thing is that rotation of the unit circle results in another unit circle. In fact, we have,
$$C_d=R_d \cdot C_d$$
Below we have the unit circle for the $p=1$ p-norm metric. We see that at various stages of rotation we still have the same unit circle since it's invariant under rotation. However, if we rotate one part of the circle, it doesn't remain invariant.
I found a sufficient answer in other posts:
Gaussian kernels for arbitrary metric spaces
Is the exponential of −d a positive definite kernel for a general metric space (X,d)?
For further details on which metric spaces result in PSD kernels of this type, I highly recommend to take a look in the following papers:
Open Problem: Kernel methods on manifolds and metric spaces
Geodesic exponential kernels: When Curvature and Linearity Conflict
Best Answer
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$.