An $m\times n$ matrix with entries $\pm 1$ is said to be partial Hadamard if any two rows are orthogonal. See Reference for partial Hadamard matrices. Given $n\equiv 0\,(\mathrm{mod}\,4)$, what is the minimum value of $m$ for which there exists an $m\times n$ partial Hadamard matrix that cannot be extended to an $(m+1)\times n$ partial Hadamard matrix?

  • $\begingroup$ I think m=4, n=12. Take 3 times H_4. Minimality of m and n should be easy for you to prove. $\endgroup$ – The Masked Avenger Mar 16 '14 at 16:01
  • $\begingroup$ Sorry. I just now realized n=(2k+1)2^t was a parameter. t+2 then. $\endgroup$ – The Masked Avenger Mar 16 '14 at 16:08

I am not exactly an expert but I think the problem is open. I have seen some results in that direction in the paper: A counterexample to Beder's conjectures about Hadamard matrices

In particular they explicitly found $m=13$ when $n=32$, which is odd like $m$.


There is probably a cleaner justification, but I'll give this sketch and wait for something more slick from someone else. Recall that any binary matrix of order k2^t where k is odd can be put into a normal form through column operations so that the first row is all ones, the next has (the equivalent of) a sign pattern of ++..+--..-, with only one change of sign, on down to the t+1st row of 2^t blocks of length k, with entries of each block having the same sign and adjacent blocks having different signs. This shows m > t+1.

Suppose t=2, and we have a 3 row normalized Hadamard matrix. Duplicate the third row, flip the signs on the latter half, and you have a candidate 4th row (4=t+2). Any fifth row has to have k ones in the first 2k slots and the same number in the last 2k slots. Break up the row into two halves and consider the portion of the dot product on each half of the putative fifth row with each of the last two rows. One gets a linear system A+B=0=A-B, so A=B=0. Except, since k is odd, A and B are 2 mod 4, so there is no fifth row possible.

For t > 2, produce t+1 rows as before and flip half the signs to produce row t+2. This time, if you do find another row orthogonal to the others, you use that to produce an example for a Hadamard matrix of half the order, and again produce a contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.