Distance matrices of subsets of the Hamming cube (Q2020430)

Consider the Hamming cube \(H_n\left\{0,1\right\}^n\) with the \(l_1\) metric. Let \(G\) denote the Gram matrix of a set of vectors \(\left\{x_1,\ldots,x_m\right\}\), i.e. \[ G(x_1,\ldots,x_m)=(x_i\cdot x_j)_{i,j=1}^m=BB^T, \] where \(B\) is the matrix whose \(i\)th row is given by the vector \(x_i\). In this article, the authors generalize the result of \textit{R. L. Graham} and \textit{P. M. Winkler} [Trans. Am. Math. Soc. 288, 527--536 (1985; Zbl 0576.05017); Trans. Am. Math. Soc. 294, 379 (1986; Zbl 0584.05032)] and derive the formula for the determinant of the distance matrix \(D=(d(x_i,x_j))_{i,j=0}^m\) of an arbitrary set of vectors \(\left\{x_1,\ldots,x_m\right\}\subseteq H_n\). More precisely, they prove that \[ \det(D)=(-1)^{m-1}2^{m-1}\det\begin{pmatrix} 0 & u^T \\ u & G \\ \end{pmatrix} \quad\text{with } u=(x_1\cdot x_1,x_2\cdot x_2,\ldots,x_m\cdot x_m)^T, \] and \begin{itemize} \item[1.] if the set of vectors \(\left\{x_1,\ldots,x_m\right\}\) is linearly dependent, then \[ \det(D)=\det\begin{pmatrix} 0 & u^T \\ u & G \\ \end{pmatrix}=0, \] \item[2.] if the set of vectors \(\left\{x_1,\ldots,x_m\right\}\) is linearly independent, then \[ \det(D) = (-1)^m2^{m-1}\det(G)\langle G^{-1}u,u\rangle = (-1)^m2^{m-1}V^2\langle G^{-1}u,u\rangle, \] where \(V\) is the volume of the \(m\)-dimensional parallelepiped with sides \(x_1\), \(\ldots\), \(x_m\). \par Moreover, in that case \(\langle G^{-1}u,u\rangle=n\). \end{itemize} The authors apply the above results for analysis of properties of subsets of \(H_n\) like \(p\)-negative type, strict \(p\)-negative type and supremal negative type. They also derive a corollary concerning the distance matrix of a tree on \(n+1\) vertices.