Dot product is $1$ with two vectors

Let $A=\{(e_1,e_2,\dots,e_n)\mid e_i\in\{0,1\}\}$, and $v$ be a nonzero vector in $A$. (So $|A|=2^n$.)

The number of vectors in $A$, whose dot product with $v$ in modulo $2$ is $1$, is exactly $2^{n-1}$. This is because for any nonzero position of $v$, choosing $0$ or $1$ in the vector to dot with it will yield different results.

If we choose any two different nonzero vectors $v,w\in A$, would the number of vectors in $A$, whose dot product with $v,w$ in modulo $2$ is $1$, be exactly $2^{n-2}$? If not, what are the upper and lower bounds?

Edit: If $v,w$ have two different positions where one has a $1$ and the other a $0$ and vice versa, then a similar argument should work. But what if the positions of $1$ in $v$ is a subset of those in $w$?

• You have made a good start. Try it by hand with $v=(1,0,0,0,0), w=(1,1,0,0,0)$ . That may give you inspiration about the general case. – Ross Millikan Oct 10 '16 at 20:18

If $v,w \in A$ are two different nonzero vectors, then they span a $2$-dimensional subspace $V$ of $A$. Then $V^\perp := \{ a \in A \mid a \cdot v = a \cdot w = 0 \}$ is a $n-2$-dimensional subspace, and thus has $2^{n-2}$ elements.
Choose any vector $u \in A$ such that $u \cdot v = u \cdot w = 1$. (It's easy to see that this is possible.) Then $u + V^\perp = \{ u + a \mid a \in V^\perp \}$ consists of exactly the vectors whose dot product with both $v$ and $w$ is $1$, and $a \mapsto u + a$ is a bijection between $V^\perp$ and $u + V^\perp$.
• I see. This argument will not generalize to $3$ vectors because they might be dependent, right? – pi66 Oct 10 '16 at 20:25
• @pi66: that is correct. As an example, let $n=3$ and the three vectors be $(1,1,0),(1,0,1),(0,1,1)$ Your formula would say you can find one vector that has dot product $1$ with all three, but there is not one. You can test it, or use the fact that $z\cdot (1,1,0)+z\cdot(1,0,1)+z\cdot (0,1,1)=z\cdot \left((1,1,0)+(1,0,1)+(0,1,1)\right)=z\cdot (0,0,0)=0$ – Ross Millikan Oct 10 '16 at 20:33