7
$\begingroup$

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors is $0$.

Details. This of course relates to the famous Hadamard conjecture which looks at $m=n$, but I am interested in the weaker $m<n$ case. Specifically, I am wondering about how many distinct $m\times n$ PHM exist given some, say $2$, of the row vectors, up to row permutation - as well as their construction.

Questions. What are some good resources on results known about PHM? Are there iconic papers in the field?

Improve this question
$\endgroup$
3
  • $\begingroup$ I imagine doing a web search on "partial Hadamard" will go far towards answering your question. Further checking resources such as the handbook of combinatorial designs should provide decent references. $\endgroup$
    – The Masked Avenger
    Commented Jul 25, 2013 at 6:03
  • $\begingroup$ I searched before posting and Google yielded little outside sources making superficial observations. I'll check out that handbook, thanks. $\endgroup$
    – Favst
    Commented Jul 25, 2013 at 6:58
  • 1
    $\begingroup$ Did your web search turn up this paper? dx.doi.org/10.1007/s12095-010-0033-z I'm not sure it addresses exactly what you're looking for, but it's certainly not superficial. $\endgroup$
    – Mark Meckes
    Commented Jul 25, 2013 at 13:29

3 Answers 3

Reset to default
6
$\begingroup$

Many of the key results on partial Hadamard matrices are due to De Launey, going back to his 2000 paper On the asymptotic existence of partial complex Hadamard matrices and related combinatorial objects. [Discrete Applied Mathematics 102, 37–45, (2000)]. You can find references in one of his most recent papers, A Fourier-analytic Approach to Counting Partial Hadamard Matrices (which is the one mentioned by Mark Meckes). A slightly more recent reference is Searching for partial Hadamard matrices.

Improve this answer
$\endgroup$
3
$\begingroup$

One great paper that I recently became aware of on this topic is ``Integral Rational Completions of Combinatorial Matrices" by Eric Verheiden in the Journal of Combinatorial Theory Series A (1978). This paper studies extendebility of partial Hadamard matrices to Hadamard matrices. In particular, it is proven that any partial $n-r \times n$ Hadamard matrix can be extended to an $n \times n$ Hadamard matrix if $r \leq 7$.

It is not possible to improve this result as there are many examples of $n-8 \times n$ partial Hadamard matrices that cannot be extended to a Hadamard matrix, see ``A counter example to Beder's conjectures about Hadamard matrices" in Journal of Statistical Planning and Inference (2009) by Bulutoglu and Kaziska.

Improve this answer
$\endgroup$
1
$\begingroup$

Another paper on this topic is: Goldberger, A., Strassler, Y., A practical algorithm for completing half-Hadamard matrices using LLL, Journal of Algebraic Combinatorics, Volume 55, pages 217–244, (2022).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .