10
$\begingroup$

Suppose $x_1,\dots,x_n \in \mathbb{R}^d$. Is there a vectorized way of representing the square distance matrix $D_{ij} = \lVert x_i - x_j \rVert^2$?

$\endgroup$
1
  • $\begingroup$ Nothing elegant, I'm afraid. The best I know is the first code block of this answer. $\endgroup$
    – user357151
    Commented Apr 18, 2017 at 19:08

2 Answers 2

8
$\begingroup$

We could make use of $\|x_i-x_j\|^2=\|x_i\|^2+\|x_j\|^2-2(x_i \cdot x_j)$, the Gramian matrix $G=[\langle x_i, x_j\rangle]$, its diagonal elements vector $g=\operatorname{diag}(G)$, and the vector of all ones $\mathbf{1}$ to write $$ D = g\mathbf{1}^T + \mathbf{1}g^T - 2G. $$

$\endgroup$
2
  • $\begingroup$ This is a bit late, but I did happen to come up with this one. Thanks though! $\endgroup$
    – user369210
    Commented Apr 23, 2017 at 3:51
  • $\begingroup$ Collect the $x_k$ vectors as the columns of a matrix, i.e. $X={\tt[}x_1\;x_2\;\ldots\,x_n {\tt]},\;$ then the result can be reformulated in terms of the all-ones matrix $(J)$ and Hadamard products $(\odot)$ $$D = (X\odot X)^TJ + J^T(X\odot X) - 2X^TX$$ $\endgroup$
    – greg
    Commented Apr 20, 2021 at 16:42
1
$\begingroup$

The first answer gives a nice formula for the distance matrix using the Gramian matrix.

Here I will develop the answer a little more.

We can write the distance between two vectors $x_i$ and $x_j$ in terms of their inner product as follow: $$ d(x_i,x_j)^2 = \langle x_i-x_j, x_i-x_j\rangle = \langle x_i,x_i\rangle + \langle x_j, x_j\rangle - 2\langle x_i, x_j\rangle \\ = \|x_i\|^2 + \|x_j\|^2 -2\langle x_i, x_j\rangle \quad\qquad\qquad$$

In matrix form, we have $$D = [d(x_i, x_j)^2] $$

$$= \begin{pmatrix} 0 & \langle x_1,x_1\rangle + \langle x_2, x_2\rangle - 2\langle x_1, x_2\rangle & \cdots & \langle x_1,x_1\rangle + \langle x_n, x_n\rangle - 2\langle x_1, x_n\rangle \\ \langle x_2,x_2\rangle + \langle x_1, x_1\rangle - 2\langle x_2, x_1\rangle & 0 & \cdots & \langle x_2,x_2\rangle + \langle x_n, x_n\rangle - 2\langle x_2, x_n\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_n,x_n\rangle + \langle x_1, x_1\rangle - 2\langle x_n, x_1\rangle & \langle x_n,x_n\rangle + \langle x_2, x_2\rangle - 2\langle x_n, x_2\rangle & \cdots & 0 \end{pmatrix} $$

Which can be written as

$$D = \begin{pmatrix} \langle x_1,x_1\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_n, x_n\rangle \\ \langle x_1,x_1\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_n, x_n\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_1,x_1\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_n, x_n\rangle \end{pmatrix} + \begin{pmatrix} \langle x_1,x_1\rangle & \langle x_1, x_1\rangle & \cdots & \langle x_1, x_1\rangle \\ \langle x_2,x_2\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_2, x_2\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_n,x_n\rangle & \langle x_n, x_n\rangle & \cdots & \langle x_n, x_n\rangle \end{pmatrix} - 2 \begin{pmatrix} \langle x_1,x_1\rangle & \langle x_1, x_2\rangle & \cdots & \langle x_1, x_n\rangle \\ \langle x_2,x_1\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_2, x_n\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_n,x_1\rangle & \langle x_n, x_2\rangle & \cdots & \langle x_n, x_n\rangle \end{pmatrix} $$

Which has the form $$D = diag(G)1_n^T + 1_ndiag(G)^T - 2G,$$

where $$ G= \begin{pmatrix} \langle x_1,x_1\rangle & \langle x_1, x_2\rangle & \cdots & \langle x_1, x_n\rangle \\ \langle x_2,x_1\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_2, x_n\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_n,x_1\rangle & \langle x_n, x_2\rangle & \cdots & \langle x_n, x_n\rangle \end{pmatrix} , diag(G) = \begin{pmatrix} \langle x_1,x_1\rangle \\ \langle x_2,x_2\rangle \\ \vdots \\ \langle x_n,x_n\rangle \end{pmatrix} , 1_n=\begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}$$

D can be given also as $$D = 1_n^Tdiag(G) + diag(G)^T1_n - 2G,$$

where $$ G= \begin{pmatrix} \langle x_1,x_1\rangle & \langle x_1, x_2\rangle & \cdots & \langle x_1, x_n\rangle \\ \langle x_2,x_1\rangle & \langle x_2, x_2\rangle & \cdots & \langle x_2, x_n\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_n,x_1\rangle & \langle x_n, x_2\rangle & \cdots & \langle x_n, x_n\rangle \end{pmatrix} , \\ diag(G) = \begin{pmatrix} \langle x_1,x_1\rangle & \langle x_2,x_2\rangle &\cdots & \langle x_n,x_n\rangle \end{pmatrix} , \\ 1_n=\begin{pmatrix} 1 & 1 \cdots 1 \end{pmatrix}$$

The last point, if the vectors $x_i, x_j$ are normalized, that is $$\langle x_i,x_i\rangle=\langle x_j,x_j\rangle=1 $$

We get

$$D = 2(1_{nxn}- G)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .