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

  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ I see. This argument will not generalize to $3$ vectors because they might be dependent, right? $\endgroup$ – pi66 Oct 10 '16 at 20:25
  • $\begingroup$ @pi66 Right, but it should work as long as they are linearly independent. $\endgroup$ – arkeet Oct 10 '16 at 20:30
  • $\begingroup$ @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$ $\endgroup$ – Ross Millikan Oct 10 '16 at 20:33

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.