1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Instead of “length” you mean “dimension”. $\endgroup$ – Michael Hoppe Jan 19 '18 at 13:54
1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.