Ryser's embedding problem for Hadamard matrices

✍ Scribed by T. S. Michael

• Publisher: John Wiley and Sons
• Year: 2005
• Tongue: English
• Weight: 110 KB
• Volume: 14
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20063

✦ Synopsis

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 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}$:

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