| Abstract: | What is the minimum order  of a Hadamard matrix that contains an a by b submatrix of all 1's? Newman showed that  where c? denotes the smallest order greater than or equal to c for which a Hadamard matrix exists. It follows that if 4 divides both a and b, and if the Hadamard conjecture is true, then  . We establish the improved bounds  for min {a,b} ≥ 2. The Hadamard conjecture therefore implies that if 4 divides both 2ab and ?a/2? ?b/2?, then  (a, b) = 2 · max {?a/2?b, ?b/2?a}. Our lower bound comes from a counting argument, while our upper bound follows from a sub‐multiplicative property of  :  Improvements in our upper bound occur when suitable conference matrices or Bush‐type Hadamard matrices exist. We conjecture that any (1,?1)‐matrix of size a by b occurs as a submatrix of some Hadamard matrix of order at most  . © 2005 Wiley Periodicals, Inc. J Combin Designs |
