Nonextendable partial Hadamard matrices

Question

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?

---

Answer 1

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$.

Answer 2

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.