Ytukyg

Let $x_1,ldots ,x_n$ be $n$ distinct points in $mathbb{R}^3$. Consider the $ntimes n$ real symmetric matrix $A$ defined by $A_{ij}:=|x_i-x_j|$. I would like to show that

$$Ker,A;cap,{vinmathbb{R}^n,:, v_1+v_2 +ldots +v_n=0}={0}$$

Thank you for any suggestions.

$defRR{mathbb{R}}$Numerical experiments suggest that this matrix is negative semidefinite on the plane $sum v_i=0$. Specifically, I generated 20 sets of 10 points each, drawn uniformly from the unit cube, and this was true every time. I repeated the experiment with points in 2, 4 and 5 dimensions, and the same held.

I am reminded of this answer by Noam Elkies but can't make a precise connection.

Switching this answer to CW to write up darij's proof from the comments. We will show that:

• If $x_i$ are any $n$ points in $RR^d$ and $v_i$ are any scalars with $sum v_i=0$, then $sum v_i v_j |x_i-x_j| leq 0$ and




• If the $x_i$ are distinct and the $v_i$ are not all $0$, we have strict inequality.

The latter shows that the matrix $left[ |x_i-x_j| right]$ times the vector $left[ v_i right]$ is nonzero. We start, however, by proving the former. We turn to the issue of when zero occurs after the horizontal line.

We start with the averaging trick: By rotational and scaling invariance, we can see that there is some positive $c$ such that
$$int_{|w|=1} left| langle w cdot x rangle right| = c |x|.$$
So
$$sum v_i v_j |x_i-x_j| = c^{-1} int_{|w|=1} sum v_i v_j left| langle w cdot (x_i-x_j) rangle right|$$
and thus it is sufficient to show $sum v_i v_j left| langle w cdot (x_i-x_j) rangle right|leq 0$ for a particular vector $w$. Now, $w cdot (x_i-x_j)$ only depends on the orthogonal projections of $x_i$ and $x_j$ onto the line $RR w$, so we may (and do) assume all the $x_i$ lie on a line. Our goal is now to show, for any $n$ values $x_i in RR$, that $sum v_i v_j |x_i-x_j| leq 0$.

We have $|z| = max(z,0) + max(-z,0)$, so $sum v_i v_j |x_i-x_j|=2 sum v_i v_j max(x_i-x_j,0)$.
We use the notation $left[ mbox{statement} right]$ to mean $1$ if the statement is true and $0$ if it is false. So
$$max(x_i-x_j,0) = int_{t in RR} left[x_j < t < x_i right] dt$$
and
$$sum_{i,j} v_i v_j max(x_i-x_j,0) = int_{t in RR} sum_{i,j} v_i v_j left[x_j < t < x_i right] dt.$$ So it is enough to show that, for any $t$, we have
$$sum_{x_i < t < x_j} v_i v_j leq 0 . $$
Let $I = { i : x_i < t }$ and $J = { i : x_j > t }$. (For almost all $t$, none of the $x_i$ equal $t$, so we can disregard the boundary case.) Then
$$sum_{x_i < t < x_j} v_i v_j = sum_{i in I, j in J} v_i v_j = left( sum_{i in I} v_i right) left( sum_{j in J} v_j right) = - left(sum_{i in I} v_i right)^2 leq 0 .$$
In the final equality, we have finally used the hypothesis $sum v_k=0$.

Now, let's consider what happens for distinct $x_i$. As long as the $x_i$ as distinct, for almost as $w$, the orthogonal projections of the $x_i$ onto $RR w$ will stay distinct. In order to get $0$, we must get $0$ from all these choices of $w$. Let's say the orthogonal projections are ordered as $x_1 < x_2 < cdots < x_n$. Once again, we must get $0$ from every choice of $t$. So we must have $left( sum_{i=1}^k v_i right)^2 =0$ for all $k$, and this means that all $v_i$ are zero.

So, if I understand it correctly, you want to proof that $Ax=0 implies x=0$, correct?

So, we simply need to show that $det(A) neq 0$.

Let $A= begin{pmatrix}
a_{11} & a_{12} & a_{13} \
a_{21} & a_{22} & a_{23} \
a_{31} & a_{32} & a_{33}
end{pmatrix}$ where $a_{ij} := d(i,j) := |x_i-x_j|$

As $a_{ii}=d(i,i) = 0$ and $d(i,j)>0$ for $ineq j$