On the nonnegative rank of distance matrices

For real numbers a(1), ... , a(n), let Q (a(1), ... , a(n)) be the n x n matrix whose i. j-th entry is (a(i) - a(j))(2). We show that Q(1, ... , n) has nonnegative rank at most 2 log(2) n + 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 a(1), ... , a(n) for which Q (a(1), ... , a(n)) 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. (C) 2012 Elsevier B.V. All rights reserved.