$\text{det}(\text{abs}({\bf d – d}^T))$ being zero implies two or more elements equal in $\bf d$

Question

When implementing a clustering algorithm earlier today I investigated (in Matlab syntax):

$$\text{det}(\text{abs}({\bf d – d}^T)), {\bf d }\in \mathbb R^{N}$$

edit: In non-Matlab syntax: $$\text{det}(\text{abs}({\bf d1}^T-{\bf 1d}^T))$$

In other words the determinant of a matrix consisting of absolute value of pairwise differences.

Now since determinants are usually terrible to calculate, this is mostly of a curiosity of mine, but it seems that if any two elements of $\bf d$ are the same, then the above determinant is 0, and if no two elements of $\bf d$ are the same, then determinant $\neq 0$.

Can we prove this?

For example the vector ${\bf d} = [1,2,3]^T$:

$$\text{det}(\text{abs}({\bf d – d}^T)) = \begin{bmatrix}|1-1|&|1-2|&|1-3|\\|2-1|&|2-2|&|2-3|\\|3-1|&|3-2|&|3-3|\end{bmatrix} = \left\|\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}\right\|\neq 0$$
And the vector : ${\bf d} = [3,2,3]^T$:
$$\text{det}(\text{abs}({\bf d – d}^T)) = \begin{bmatrix}|3-3|&|3-2|&|3-3|\\|2-3|&|2-2|&|3-3|\\|3-3|&|3-2|&|3-3|\end{bmatrix} = \left\|\begin{bmatrix}0&1&0\\1&0&1\\0&1&0\end{bmatrix}\right\|= 0$$

Answer 1

This is true. By permuting the rows and columns of the matrix, we may assume that the entries of $\mathbf d=(d_1,d_2,\ldots,d_n)^T$ are arranged in descending order. Moreover, since the rows and columns are simultaneously permuted, the determinant is unchanged. Now let $\Delta_i=d_i-d_{i+1}$, $$ L=\pmatrix{1\\ &\ddots\\ &&\ddots\\ &&&1\\ \frac12&\frac12&\cdots&\frac12&1} \ \text{ and } \ U=\pmatrix{1&-1\\ &\ddots&\ddots\\ &&\ddots&\ddots\\ &&&\ddots&-1\\ &&&&1}. $$ Then \begin{aligned} A:=|\mathbf d\mathbf 1^T-\mathbf 1\mathbf d^T| &=\pmatrix{0&d_1-d_2&d_1-d_3&\cdots&d_1-d_n\\ d_1-d_2&0&d_2-d_3&\cdots&d_2-d_n\\ d_1-d_3&d_2-d_3&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&0&d_{n-1}-d_n\\ d_1-d_n&d_2-d_n&\cdots&d_{n-1}-d_n&0},\\ B:=UAU^T &=\pmatrix{-2\Delta_1&0&\cdots&0&\Delta_1\\ 0&-2\Delta_2&\ddots&\vdots&\Delta_2\\ \vdots&\ddots&\ddots&0&\vdots\\ 0&\cdots&0&-2\Delta_{n-1}&\Delta_{n-1}\\ \Delta_1&\Delta_2&\cdots&\Delta_{n-1}&0},\\ C:=LBL^T &=\pmatrix{-2\Delta_1&0&\cdots&0&0\\ 0&-2\Delta_2&\ddots&\vdots&0\\ \vdots&\ddots&\ddots&0&\vdots\\ 0&\cdots&0&-2\Delta_{n-1}&0\\ 0&0&\cdots&0&\frac12(d_1-d_n)}. \end{aligned} Since $U$ and $L$ have determinants $1$, \begin{aligned} \det A=\det C &=\left[\prod_{i=1}^{n-1}(-2\Delta_i)\right]\left[\frac12(d_1-d_n)\right]\\ &=\left[\prod_{i=1}^{n-1}(-2\Delta_i)\right]\left[-\frac12(d_n-d_1)\right]\\ &=(-2)^{n-2}\prod_{cyc}(d_i-d_{i+1}). \end{aligned} (If the $d_i$s are arranged in ascending order, the formula becomes $\det A=2^{n-2}\prod_{cyc}(d_i-d_{i+1})$ instead.) Hence $A$ is nonsingular if and only if all entries of $\mathbf d$ are distinct.

---

Remark. As pointed out by darij grinberg, there is actually a more general result, namely, if $\mathbf x_1,\ldots,\mathbf x_n\in\mathbb R^m$ and $A$ is the distance matrix defined by $a_{ij}=\|\mathbf x_i-\mathbf x_j\|_2$, then:

1. (cf. A matrix involving distances of $n$ points in $\mathbb{R}^3$ ) $A$ is negative semidefinite on $\mathbf1^\perp$ and if all $\mathbf x_i$s are distinct, it is negative definite on $\mathbf1^\perp$;
2. (cf. Nonsingularity of Euclidean distance matrix ) when all $\mathbf x_i$s are distinct, since we also have $\mathbf1^TA\mathbf1>0$, $A$ must be nonsingular.

My argument above only proves the non-singularity of $A$ when $m=1$. It cannot deal with the higher-dimensional case and it doesn't concern about the negative semidefiniteness of $A$ on $\mathbf1^\perp$.