5
$\begingroup$

Consider all $30$-dimensional vectors $v$ such that $v_i \in \{-1,1\}$. It seems that none of them has the property that $(v_1, \dots, v_{30})$ is orthogonal to $(v_{30}, v_1, \dots, v_{29})$.

Without just exhaustively enumerating all $2^{30}$ such vectors, how can one prove this?

$\endgroup$
6
$\begingroup$

This is true not just for $30$ but for all $n$ of the form $4k+2$. (Also all odd $n$, but only trivially)

Assume there exists such a vector such that $(v_1, \cdots, v_{4k+2}) \cdot (v_{4k+2}, v_1, \cdots, v_{4k+1}) = 0$ (s.t. they are othogonal). This can be written as the sum of $4k+2$ terms $$v_1v_{4k+2} + v_2 v_1 + \cdots + v_{4k+2} v_{4k+1}= 0 $$ since each $v_i \in \{1, -1\}$, each term is $\pm 1$. So $2k+1$ terms must be $1$ and $2k+1$ terms must be $-1$.

Now we count the $-1$ terms in the sum $v_1v_{4k+2} + v_2 v_1 + \cdots + v_{4k+2} v_{4k+1}$. If all $v_i$ are $1$, then there are zero terms that have value $-1$. Now consider an sum $v_1v_{4k+2} + v_2 v_1 + \cdots + v_{4k+2} v_{4k+1}$ with arbitrary $v_i$. Flipping the value of a $v_j$ for some $j \in \{1, \cdots, 4k+2\}$ will change the value of exactly two terms. Depending on the previous signs of these terms, the number of negative terms will be changed by $+2, 0$ or $-2$. So the number of negative terms in the sum is always even! This means that there can never be exactly $2k+1$ negative terms in the sum, so the dot product can never be $0$.

Set $k=7$ and done.

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