Low rank co-diagonal matrices and Ramsey graphs (Q1972674)

Summary: We examine \(n\times n\) matrices over \(Z_m\), with 0's in the diagonal and nonzeros elsewhere. If \(m\) is a prime, then such matrices have large rank. If \(m\) is a non-prime-power integer, then we show that their rank can be much smaller. For \(m=6\) we construct a matrix of rank \(\exp(c\sqrt{\log n\log \log n})\). We also show that explicit constructions of such low rank matrices imply explicit constructions of Ramsey graphs.