Low-rank matrices, tournaments, and symmetric designs.

Let a = (a i) i ≥ 1 be a sequence in a field F , and f : F × F → F be a function such that f (a i , a i) ≠ 0 for all i ≥ 1. For any tournament T over [ n ] , consider the n × n symmetric matrix M T with zero diagonal whose (i , j) th entry (for i < j) is f (a i , a j) if i → j in T , and f (a j , a i) if j → i in T. It is known [3] that if T is a uniformly random tournament over [ n ] , then rank (M T) ≥ (1 2 − o (1)) n with high probability when char (F) ≠ 2 and f is a linear function. In this paper, we investigate the other extremal question: how low can the ranks of such matrices be? We work with sequences a that take only two distinct values, so the rank of any such n × n matrix is at least n / 2. First, we show that the rank of any such matrix depends on whether an associated bipartite graph has certain eigenvalues of high multiplicity. Using this, we show that if f is linear, then there are real matrices M T (f ; a) of rank at most n 2 + O (1). For rational matrices, we show that for each ε > 0 we can find a sequence a (ε) for which there are matrices M T (f ; a) of rank at most (1 2 + ε) n + O (1). These matrices are constructed from symmetric designs, and we also use them to produce bisection-closed families of size greater than ⌊ 3 n / 2 ⌋ − 2 for n ≤ 15 , which improves the previously best known bound given in [5]. [ABSTRACT FROM AUTHOR]