Zero-sum squares in bounded discrepancy \(\{-1,1\}\)-matrices

Alma R. Arévalo¹ ; Amanda Montejano² ; Edgardo Roldán-Pensado³

¹Instituto de Matemáticas, UNAM
²Facultad de Ciencias, UNAM, campus Juriquilla
³Centro de Ciencias Matemáticas, UNAM, campus Morelia

The electronic journal of combinatorics, Tome 28 (2021) no. 4

Résumé

For $n\geqslant 5$, we prove that every $n\times n$ matrix $\mathcal{M}=(a_{i,j})$ with entries in $\{-1,1\}$ and absolute discrepancy $\lvert\mathrm{disc}(\mathcal{M})\rvert=\lvert\sum a_{i,j}\rvert\leqslant n$ contains a zero-sum square except for the split matrices (up to symmetries). Here, a square is a $2\times 2$ sub-matrix of $\mathcal{M}$ with entries $a_{i,j}, a_{i+s,s}, a_{i,j+s}, a_{i+s,j+s}$ for some $s\geqslant 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\geqslant 5$ every zero-sum $n\times n$ matrix with entries in $\{-1,1\}$ contains a zero-sum square.

Détail

DOI : 10.37236/9617

Classification : 05D10, 05B20, 11B75, 15B36
Mots-clés : Erickson matrix, discrepancy theory, zero-sum matrix