Premium
Ryser's embedding problem for Hadamard matrices
Author(s) -
Michael T. S.
Publication year - 2006
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20063
Subject(s) - mathematics , hadamard matrix , combinatorics , hadamard transform , hadamard's maximal determinant problem , conjecture , order (exchange) , upper and lower bounds , complex hadamard matrix , matrix (chemical analysis) , multiplicative function , embedding , discrete mathematics , mathematical analysis , materials science , finance , economics , composite material , artificial intelligence , computer science
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