Linear independance of (binary) vectors

Question

here is what i want to do.

I have 4 vectors (in $\mathbb{Z}^{12}_{2}$), lets say

$v_1 = (1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0)$

$v_2 = (1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0)$

$v_3 = (1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0)$

$v_4 = (1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1)$

These vectors are supposed to build a 4-dimensional vector subspace of $\mathbb{Z}^{12}_{2}$. For that to be the case they have to be linearly independent.

Now i want to check if they are. I could do that with a system of linear equations but accordung to my script i should: "[...] compute all 16 linear combinations in $\mathbb{Z}_{2}$ and check if any of them occur twice. If so, $v_1,v_2,v_3,v_4$" are not linearly independent."

I thought about that for over an hour now and i dont really get what i am supposed to do and whyit is correct. Would really appreciate some help.

Answer 1

Compute all the $16$ possibilities, if two of them happen to be equal, then you can set them equal, subtract one from the other one and find a new linear combination that has a non-zero coefficient.

In other words, write all linear combinations of the form

$$f(\alpha_1,\alpha_2,\alpha_3,\alpha_4)= \alpha_1 v_1 + \alpha_2 v_2 + \alpha_3 v_3 + \alpha_4 v_4$$

You have $2^4$ inputs.

If $v_1,v_2,v_3,v_4$are linearly independent, then each of the vectors $f(\alpha_1,\alpha_2,\alpha_3,\alpha_4)$ must be different, because if not, we find two different representations for the same vector in the space which violates linear independence. (Remember: Linear independence gives you the ability to write vectors in its span "uniquely").

Answer 2

The subspace they span is $$\{av_1+bv_2+cv_3+dv_4:a,b,c,d\in \mathbb{Z}_2\}$$ However, since $|\mathbb{Z}_2|=2$, there are only 16 elements (at most), corresponding to choosing $0$ or $1$ for each of $a,b,c,d$. Compute these 16, and see if there are any duplicates. Done.

Answer 3

You can show that a collection of vectors is linearly independent iff there is a unique way to write each element of its span as a linear combination of those vectors. (The trick is that the difference of two duplicates is zero...) This is why searching for duplicates will tell you if the vectors are independent.

Answer 4

You can immediately see that $v_4$ is independent from the others since its 12th element is $1$, whereas the others have $0$ in that position; there is no way that a combination of $0$s can create a $1$.

Similarly, $v_2$ and $v_3$ are independent of the others based on the 3rd and 2nd elements respectively.

You can then see that $v_1$ is not a combination of the others. Therefore they are all independent, and no need to compute any of the 16 combinations.

Answer 5

@Thèophile 's answer is the best, I think. There's no way zeros can produce a $1$. So, $v_4$ is independent of the other vectors because of the last component. Then $v_3$ is independent of $v_1$ and $v_2$ because of the sixth component. And finally, $v_2$ is independent of $v_1$ because of the third component.