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.