ELA, Volume 10, pp. 223-231, September 2003, abstract.
The Maximum Number of 2-by-2 Odd Submatrices in
(0,1)-Matrices
Michael Marks, Rick Norwood, and George Poole
Let A be an m-by-n, (0,1)-matrix. A submatrix of A is
odd if the sum of its entries is an odd integer and
even otherwise. The maximum number of 2-by-2 odd
submatrices in a (0,1)-matrix is related to the
existence of Hadamard matrices and bounds on Turan
numbers. Pinelis [On the minimal number of even
submatrices of 0-1 matrices, Designs, Codes and
Cryptography, 9:85-93, 1994] exhibits an asymptotic
formula for the minimum possible number of p-by-q
even submatrices of an m-by-n (0,1)-matrix.
Assuming the Hadamard conjecture, specific techniques
are provided on how to assign the 0's and 1's,
in order to yield the maximum number of 2-by-2 odd
submatrices in an m-by-n (0,1)-matrix. Moreover,
formulas are determined that yield the exact maximum
counts with one exception, in which case upper and
lower bounds are given. These results extend and
refine those of Pinelis.