Low Rank Co-Diagonal Matrices and Ramsey Graphs

Abstract

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 (i.e., $n^{1/(p-1)}-O(1)$ ). 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.