# Pairwise distance matrix

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$?

• Nothing elegant, I'm afraid. The best I know is the first code block of this answer. – user357151 Apr 18 '17 at 19:08

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.$$

• This is a bit late, but I did happen to come up with this one. Thanks though! – user369210 Apr 23 '17 at 3:51
• 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$$ – greg Apr 20 at 16:42

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)$$