Zero-sum squares in bounded discrepancy {−1,1}-matrices

Abstract

For n⩾5, we prove that every n×n matrix M=(ai,j) with entries in {−1,1} and absolute discrepancy |disc(M)|=|∑ai,j|⩽n contains a zero-sum square except for the split matrices (up to symmetries). Here, a square is a 2×2 submatrix of M with entries ai,j, ai+s,s, ai,j+s, ai+s,j+s for some s⩾1, and a split matrix is a matrix with all entries above the diagonal equal to -1 and all remaining entries equal to 1. In particular, we show that for n>5 every zero-sum n×n matrix with entries in {−1,1} contains a zero-sum square.