Can there be more than $\log_2(n)$ mutually orthogonal $(\pm1)$-vectors $x$ in $\mathbb{R}^n$ such that $x_{2k-1} \neq x_{2k}$ for all $k$?

Question

A Hadamard matrix of order $n$ is an $n \times n$ matrix with entries $\pm1$ such that any two rows are mutually orthogonal. Any Hadamard matrix must necessarily have order equal to $1$, $2$, or a multiple of $4$. A long-standing conjecture is that this condition is also sufficient for a Hadamard matrix of order $n$ to exist.

I'm trying to show that no Hadamard matrix $H$ can exist under the following restriction on its entries: for each $1 \leq k \leq n/2$, $H_{i,2k-1} \neq H_{i,2k}$, that is, in each row, the consecutive pairs of entries are all $\{\pm1\}$. My stronger guess is that there aren't more than $\log_2(n)$ mutually orthogonal $(\pm1)$-vectors $x$ in $\mathbb{R}^n$ with the property that $x_{2k-1} \neq x_{2k}$ for all $1 \leq k \leq n/2$.

It is easy to get at least $\log_2(n)$ such vectors as follows. Assume $n = 2^m$ for the sake of simplicity. Start with $x_1 = (1,-1,1,-1,\dotsc,1,-1) \in \mathbb{R}^n$. For $1 < i < m$, view $x_{i-1}$ as $(y_1,y_2,\dotsc,y_{2^i})$, each $y_j$ of length $2^{m-i}$, and then define $x_i$ inductively as $x_i = (y_1,-y_2,y_3,-y_4,\dotsc,y_{2^i - 1},-y_{2^i})$. Then, $x_1,\dotsc,x_m$ satisfy the required property. For instance, when $n = 8$, this gives the following three vectors: \begin{align} x_1 &= (1,-1,1,-1,1,-1,1,-1)\\ x_2 &= (1,-1,1,-1,-1,1,-1,1)\\ x_3 &= (1,-1,-1,1,-1,1,1,-1) \end{align}

Since my constraint is quite strong, I don't think there are any Hadamard matrices with entries restricted as above, and I also feel intuitively that the above construction is extremal. However, I'm unable to prove it. But, surely this is already well-known; can anyone help me prove it, or provide a reference for the same?

Answer 1

This answer is based on a helpful discussion in the comments under the question with Greg Martin.

---

I'm trying to show that no Hadamard matrix $H$ can exist under the following restriction on its entries: for each $1 \leq k \leq n/2$, $H_{i,2k-1} \neq H_{i,2k}$, that is, in each row, the consecutive pairs of entries are all $\{\pm1\}$.

Here is a simple way to show that no such Hadamard matrix $H$ can exist. Suppose, for the sake of contradiction, that there is such an $H$. Note that $H$ must be invertible. But, the all-ones vector $(1,\dots,1)$ is in the kernel of $H$, so this is not possible.

My stronger guess is that there aren't more than $\log_2(n)$ mutually orthogonal $(\pm1)$-vectors $x$ in $\mathbb{R}^n$ with the property that $x_{2k-1} \neq x_{2k}$ for all $1 \leq k \leq n/2$.

One can actually do much better than $\log_2(n)$. Here is a way to achieve a linear lower bound. For $1 \leq i \leq n/2$, define $v^{(i)} = \bigl(v^{(i)}_1,\dots,v^{(i)}_{n/2}\bigr) \in \mathbb{R}^{n/2}$ to be the vector $(1,\dots,1,-1,\dots,-1)$ having $i$ ones followed by $\frac{n}{2}-i$ negative ones. Define $x^{(i)} = \bigl(v^{(i)}_1,-v^{(i)}_1,\dots,v^{(i)}_{n/2},-v^{(i)}_{n/2}\bigr) \in \mathbb{R}^n$. Then, clearly $x^{(1)},\dots,x^{(n/2)}$ are $n/2$ vectors in $\mathbb{R}^n$ satisfying the required criterion.

Moreover, this upper bound is tight. To see why, first note that the vectors $v^{(1)},\dots,v^{(n/2)}$ form a basis of $\mathbb{R}^{n/2}$. Let $x = (x_1,\dots,x_n) \in \mathbb{R}^n$ be any $(\pm1)$-vector satisfying the given condition. Consider the vector $v = (x_1,x_3,\dots,x_{n-1}) \in \mathbb{R}^{n/2}$. Then, $v$ is a linear combination of $v^{(1)},\dots,v^{(n/2)}$. But, the same linear combination also shows that $x$ is a linear combination of $x^{(1)},\dots,x^{(n/2)}$, since $x_{2k} = -x_{2k-1}$ for all $1 \leq k \leq n/2$.