Ryser's embedding problem for Hadamard matrices

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$${(ab)}^{\sharp } \leq {\cal R}(a,b)\leq {a}^{\sharp }{b}^{\sharp },$$ 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$${\rm max} \{ {\left (2\lceil a /2 \rceil b \right )}^{\sharp },\, {\left (2\lceil b /2 \rceil a \right )}^{\sharp } \} \le {\cal R}(a,b) \le {\rm min} \{ {a}^{\sharp }{b}^{\sharp },\, {\left ( a /2\right )}^{\sharp }{(2 b )}^{\sharp },\, {\left ( b /2\right )}^{\sharp }{(2 a )}^{\sharp }\}$$ for min { a , b } ≥ 2. The Hadamard conjecture therefore implies that if 4 divides both 2 ab 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}$ :$${\cal R}(a _1 a _2, b _1 b _2)\le {\cal R}(a _1,b _1)\cdot {\cal R}(a _2, b _2).$$ 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