Distance matrices of subsets of the Hamming cube
Graham and Winkler derived a formula for the determinant of the distance matrix of a full-dimensional set of n+1 points {x0,x1,…,xn} in the Hamming cube Hn=({0,1}n,ℓ1). In this article we derive a formula for the determinant of the distance matrix D of an arbitrary set of m+1 points {x0,x1,…,xm} in Hn. It follows from this more general formula that det(D)=0 if and only if the vectors x0,x1,…,xm 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 ⟨D−11,1⟩=2/n where 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 Hn that have strict 1-negative type.