Ranks of matrices with few distinct entries (Q1686308): Difference between revisions

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\). At first, the author reviews some applications of linear algebra in extremal combinatorics that involve a bound on \(N(r,L)\). He then proves several new results on \(N(r,L)\). He also gives a classification of the sets \(L\) for which \(N(r,L)\) is linear and shows that if \(N(r,L)\) is superlinear and \(L\subset\mathbb{Z}\), then \(N(r,L)\) is at least quadratic.