Choosing co-efficients from a restricted set to ensure a vector is orthogonal to another Let $\vec{u} = (p_1u_1,...,p_nu_n) \in \mathbb{R}^n$ where $p_i \in \{-1,1\}$.  Let $\vec{v} \in \mathbb{R}^n$.  Is there a systematic way to choose $p_i$ such that $\vec{u} \cdot \vec{v} = 0$, or to show that for the two given vectors that is not possible?
 A: $\vec{u} \cdot \vec{v}$ is a linear function of the $p_i$, say $\sum_{i} a_i p_i$.  You want to partition $\{1,\ldots, n\}$ into two subsets $A$ and $B$ such that $\sum_{i \in A} a_i = \sum_{i \in B} a_i$.  In the version where the $a_i$ are integers, this is the Set Partitioning Problem.  That is NP-complete, so you won't find an efficient algorithm.  However, there are 
algorithms that find good approximate solutions quickly.  If the $a_i$ are
all small multiples of some number, the pseudo-polynomial dynamic programming algorithm might be useful.
A: Abstractly, one an notice that the space of vectors perpendicular to $(p_1u_1,\ldots,p_nu_n)$ is a subspace of dimension $n-1$ (unless all the $u_i=0$). There are $2^n$ possible choices of $p_n$, so the set of vectors $v$ perpendicular to any of them is the union of $2^n$ such subspaces (although, since opposite choices of $p_n$ yield the same subspace, it can actually be written as a union of $2^{n-1}$ subspaces). One can show that $\mathbb R^n$ is not the union of any finite number of subspaces and, in fact, that in some senses most vectors $v$ are not perpendicular to such a vector.
More explicitly, let $\overrightarrow{v}=(1,0,0,0,0,\ldots,0)$ and $\overrightarrow{u}=(1,1,1,1,1,\ldots,1)$. Then, the dot product is $p_1,$ which can clearly never be zero.

As for finding such a set of $p_i$, this is exactly the partition problem. In particular, if we let $v'=(u_1v_1,u_2v_2,\ldots,u_nv_n)$, then we are looking to partition the multiset represented by $v'$ into two subsets which have equal sum. In particular, if $S$ and $T$ form a partition of the indices $\{1,\ldots,n\}$ into two subsets such that
$$\sum_{s\in S}u_sv_s=\sum_{t\in T}u_tv_T$$
then we have
$$\sum_{s\in S}u_sv_s-\sum_{t\in T}u_tv_T=0$$
thus, setting $p_i$ to $1$ where $i\in S$ and to $-1$ when $i\in T$ suffices to solve the problem. The Wikipedia page lists various algorithms for solving this problem.
