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.
Citation Information
Marks, Michael; Norwood, Rick; and Poole, George. 2003. The Maximum Number of 2 X 2 Odd Submatrices in (0, 1)-Matrices. Electronic Journal of Linear Algebra. Vol.10 223-231. https://www.emis.de/journals/ELA/ela-articles/articles/vol10_pp223-231.pdf ISSN: 1081-3810