Number of Orthogonal vectors

Question

I need to prove or disprove this:

For each $n>1$ vector with dimension of $4n$ that contains only $1$ and $-1$ (for example $(1,-1,1,1,1,-1,1,-1)$) has at least 3 orthogonal such vectors (they should also contains only $1$ and $-1$).

I tried to solve it in this way:
If the vector contains only $1$ and $-1$, its orthogonal vector must to be with number of changes = number of similarity. So the distances between 2 orthogonal vectors must be exactly $2n$.
So I tried to find the number of vectors that their distance from some vector is $2n$. Let $V$ to be such vector, so the number of its orthogonal vectors (with distance $2n$) should be $\binom{4n}{2n}$. Lets pick one (say $V_2$).
So I need to find more 2 vectors in such way. But now I need to find another vector that its distance is $2n$ from both $v$ and $v_2$ but how can I do that? How much vectors with distance $2n$ have from both $v$ and $v_2$?

Answer 1

Michael Burr already succintly answered this question, but I wanted to point out some interesting details to those who are interested in such vectors.

Since each component of the vector is either $+1$ or $-1$, we can represent each vector as an unsigned integer in binary, with each binary digit $i$ (value $2^i$) representing the $(i+1)$'th vector component, $0 \le i \in \mathbb{N}$.

If we have a function $N_0(x)$ that returns the number of zeros in the binary representation of $x$, and $N_1(x)$ that returns the number of ones in the binary representation of $x$, the dot product between two vectors represented by unsigned integer values $a$ and $b$ is $\left(N_1(a \otimes b) - N_0(a \otimes b)\right)$, where $\otimes$ is the exclusive-or binary operator.

(Many processor architectures have a low-level operation called popcount, which returns the number of bits set. If $a$ and $b$ are $d$-bit unsigned integers representing two vectors, the dot product of the two vectors is $d - 2\operatorname{popcount}(a \otimes b)$. Using GCC with C or C++, this can be written as d - 2*__builtin_popcountll(a ^ b), where a and b are of unsigned long long type.)

Interestingly, the number of dimensions must be even for there to be such perpendicular vectors.

Using an exhaustive brute force search, I found out that

$$\begin{array}{c|c} \text{Dimensions} & \text{Maximum number of orthogonal vectors} \\ \hline 2 & 2 \\ 4 & 4 \\ 6 & 2 \\ 8 & 8 \\ 10 & 2 \\ 12 & 4 \\ 14 & 2 \\ 16 & 16 \\ 18 & 2 \\ 20 & 4 \end{array}$$

Including the odd numbers of dimensions (where no two such vectors can be perpendicular, so using $1$ for those), we get the integer sequence $1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, \dots$, whis is OEIS A006519: the highest power of 2 dividing the number of dimensions. Which gels nicely with the binary representation of such vectors.

Answer 2

It's enough to do this for the case $n=1$. If you break the vector of length $4n$ into $n$ vectors of length $4$ and make a new vector that is a combination of orthogonal vectors to each length $4$ piece, the entire vector is orthogonal.

Hint for the case $n=1$. In this case, a vector looks like $\vec{v}=(1,-1,-1,1)$ or something similar. The dot product of the vector with itself is $4$, but if you create a vector $\vec{u}$ by changing two of the signs of $\vec{v}$, then you hve something orthogonal to $\vec{v}$.

The new vectors you construct do not need to be orthogonal to each other, just to $\vec{v}$, if I'm reading your question correctly. If you need them all orthogonal to each other, try following the following pattern:

$$ (1,1,1,1);(-1,-1,1,1);(-1,1,-1,1);(1,-1,-1,1) $$