Graham and Winkler derived a formula for the determinant of the distance matrix of a full-dimensional set of $n + 1$ points $\{ x_{ 0}, x_{ 1}, \ldots , x_{ n} \}$ in the Hamming cube $H_{ n} = ( \{ 0,1 \}^{ n}, \ell_{ 1} )$. In this article we derive a formula for the determinant of the distance matrix $D$ of an arbitrary set of $m + 1$ points $\{ x_{ 0}, x_{ 1}, \ldots , x_{ m} \}$ in $H_{ n}$. It follows from this more general formula that $\det (D) \not= 0$ if and only if the vectors $x_{ 0}, x_{ 1}, \ldots , x_{ m}$ are affinely independent. Specializing to the case $m = n$ provides new insights into the original formula of Graham and Winkler. A significant difference that arises between the cases $m < n$ and $m = n$ is noted. We also show that if $D$ is the distance matrix of an unweighted tree on $n + 1$ vertices, then $\langle D^{ -1} \mathbf{ 1}, \mathbf{ 1} \rangle = 2/n$ where $\mathbf{ 1}$ is the column vector all of whose coordinates are $1$. Finally, we derive a new proof of Murugan's classification of the subsets of $H_{ n}$ that have strict $1$-negative type.
Categories: math.FA
