# fast way to calculate normal to set of vectors with $\pm$1 entries

Say I have a set of $(n-1)$ linearly independent vectors $\mathbf{v}_i$ of dimension $n$ with entries $\pm1$. I am interested in finding the $n-$dimensional vector $\mathbf{u}$which is normal to the hyperplane spanned by the $\mathbf{v}_i$. In other words, $\mathbf{u}$ is orthogonal to each of the $\mathbf{v}_i$, where $\mathbf{u}$ is unique up to multiplicative constant.

I have two questions:

1) Is it true that $\mathbf{u}$ is also a vector with entries $(0, \pm 1)$ with an arbitrary pre-factor (e.g. $\mathbf{u}=\alpha[-1,1,0]$)? Can this be proven?

2) I know that $\mathbf{u}$ can be calculated with standard linear algebraic techniques (e.g. Gaussian elimination), but if property 1) is true, is there a computationally faster trick to getting the answer?

Thank you for your help!

• The answer to Q1 must surely be no most of the time, otherwise Hadamard matrices would be a lot easier to construct or work with. Indeed, for $n=3$ and $v_ 1 = (1, 1, 1)$, $v_2 = (1,1,-1)$ the vector $u$ must have zero in the last entry – Yemon Choi Sep 7 '18 at 2:28
• Not necessarily, as one is not given n-1 rows of a Hadamard matrix. (If one were, completing would be computationally fast.) Usually Gram Schmidt orthonormalization is pretty fast. However, the orthogonal vector may not have all components the same size, especially if the dimension n is not a multiple of 4. Gerhard "It's A Theorem, You Know" Paseman, 2018.09.06. – Gerhard Paseman Sep 7 '18 at 4:32
• Yemon Choi is right. There must be zeros sometimes. I updated the question – user3433489 Sep 9 '18 at 17:32
• It would be better if you did not edit the question in a way that gives no indication of the original one, since now my comment makes no sense. I think the answer to the modified question is still no, by some trial and error: the point is that since you only require your columns to be lin ind, we can arrange that they have a bias towards a certain direction, which will lead to assymetry in the components of the normal vector to the hyperplane – Yemon Choi Sep 9 '18 at 18:07

To recap: we are given $n-1$ linearly independent vectors in ${\bf R}^n$ with $\pm 1$ entries. The original Q1 asked, in effect, if there is always a vector with $\pm 1$ entries that is orthogonal to all of the given ones. A counter examples is provided for $n=3$ by taking $$v_1 = e_1+e_2+e_3\quad,\quad v_2=e_1+e_2-e_3$$ since the normal vector to span($v_1$,$v_2$) must be a multiple of $e_1-e_2$. (Here I am using $e_1,e_2,\dots$ to denote the standard o.n. basis vectors of ${\bf R}^n$.)

A modified version of Q1 now relaxes the requirement on the normal vector, so that one merely requires it to have entries in $\{-1,0,1\}$. This also fails (Adam Goucher pointed our a counterexample while I was writing this answer) and in fact we can generate a family of examples for all $n\geq 4$ as follows. Let $u= e_1+\dots + e_n$ iinside ${\bf R}^n$ and consider the vectors $u-2e_1,\dots, u-2e_{n-1}$. A little bit of manipulation shows that a normal vector to this family must have the form $ae_1+\dots + ae_{n-1}+be_n$ where $(n-2)a+b=0$, and so it is not possible for such a vector to have entries in $\{-1,0,1\}$ when $n\geq 4$.

It's not clear whether the OP is interested in Q2 even when Q1 has a negative answer, and it's not something I have any immediate intuition for.

There is a six-dimensional counterexample:

• $(+1,+1,+1,+1,+1,+1)$
• $(-1,-1,+1,+1,+1,+1)$
• $(+1,+1,-1,-1,+1,+1)$
• $(+1,+1,+1,-1,-1,+1)$
• $(+1,-1,+1,-1,+1,-1)$

The normal to the linear span of these five vectors is $(2,-2,-1,1,-1,1)$.

• Was typing up a 5-dimensional counterexample but you beat me to it :) In fact, I think we can get a counterexample in dimension 4 – Yemon Choi Sep 9 '18 at 18:13