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.