On the nonnegative rank of distance matrices

For real numbers a1,…,ana1,…,an, let Q(a1,…,an)Q(a1,…,an) be the n×nn×n matrix whose i,ji,j-th entry is (ai−aj)2(ai−aj)2. We show that Q(1,…,n)Q(1,…,n) has nonnegative rank at most 2log2n+2. This refutes a conjecture from Beasley and Laffey (2009) [1] (and contradicts a “theorem” from Lin and Chu (2010) [5]). We give other examples of sequences a1,…,ana1,…,an for which Q(a1,…,an)Q(a1,…,an) has logarithmic nonnegative rank, and pose the problem whether this is always the case. We also discuss examples of matrices based on hamming distances between inputs of a Boolean function, and note that a lower bound on their nonnegative rank implies lower bounds on Boolean formula size.

► We study the nonnegative rank of Euclidean distance matrices.
► We show that the rank can be logarithmic.
► Hamming distance based matrices are also discussed.