Title

The Maximum Number of 2 X 2 Odd Submatrices in (0, 1)-Matrices

Document Type

Article

Publication Date

9-1-2003

Description

Let A be an m x 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 x 2 odd submatrices in a (0, 1)-matrix is related to the existence of Hadamard matrices and bounds on Turán 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 x q even submatrices of an m x 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 x 2 odd submatrices in an m x 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.

Link to Full Text
COinS