Ranks of matrices with few distinct entries

An L-matrix is a matrix whose off-diagonal entries belong to a set L, and whose diagonal is zero. Let N(r,L) be the maximum size of a square L-matrix of rank at most r. Many applications of linear algebra in extremal combinatorics involve a bound on N(r,L). We review some of these applications, and prove several new results on N(r,L). In particular, we classify the sets L for which N(r,L) is linear, and show that if N(r,L) is superlinear and L⊂Z, then N(r,L) is at least quadratic.

As a by-product of the work, we asymptotically determine the maximum multiplicity of an eigenvalue λ in an adjacency matrix of a digraph of a given size.