Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a following quantitative statement:

Is there a finite number of triples in $\mathbb{Z}^{3}$ such that if the vectors $v_1,v_2,v_3$ are linearly dependent, then for some triple $(k_1,k_2,k_3)\neq 0$ we have $$k_{1}v_{1}+k_{2}v_{2}+k_{3}v_{3}=0?$$

The important thing is that the collection should work for all triples of linearly dependent vectors under consideration. If the answer to this question is NO, can one then give a infinite collection of such "test" integer triples that would have a very small density in $\mathbb{Z}^{3}$? That is, we clearly do not need to consider all triples of integers - having considered (1,2,3), we do not need (2,4,6) in the collection etc.


There are only $2^3=8$ possibilities for the rows of $(v_1 v_2 v_3)$. Duplicated rows don't matter. Hence there are only $2^8$ essentially different triples of vectors, so a collection of size at most $2^8$ suffices.

(I realise this is a bit trivial for an answer, but I don't have enough rep to comment)

  • $\begingroup$ Indeed. I will post a refined version of the question as well as $2^n$ is too much for me. $\endgroup$ – TOM May 7 '15 at 3:25
  • $\begingroup$ Also, did you not mean that $\binom{2^n}{3}$ is an upper bounds as there are these many triples of vectors whose linear independence we have to check? $\endgroup$ – TOM May 7 '15 at 4:16
  • $\begingroup$ No. The point is that however many rows there are (i.e. however large $n$ is), we only only care about which of the $8$ possible rows are present for the triple $(v_1 v_2 v_3)$, since we don't care about multiplicity of rows. This gives a bound of $2^8$, not $2^n$. $\endgroup$ – David May 7 '15 at 12:19

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.