Ryser's embedding problem for Hadamard matrices

Abstract What is the minimum order ${\cal R}\,(a, b)$ 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 ${\cal R}(a,b)=ab$ . 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 ${\cal R}$ (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 ${\cal R}$ : 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 ${\cal R}(a,b)$ . © 2005 Wiley Periodicals, Inc. J Combin Designs