Distance matrices of subsets of the Hamming cube

Abstract 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 , … , x n } in the Hamming cube H n = ( { 0 , 1 } n , l 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 , … , x m } in H n . It follows from this more general formula that det ( D ) ≠ 0 if and only if the vectors x 0 , x 1 , … , 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 〈 D − 1 1 , 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 H n that have strict 1-negative type.