How to find a linear combination of vectors that is congruent to $0\pmod 2$

Question

My goal is to find a linear combination of the following vectors such that the result is $(0,0,0,0,0,0,0,0,0,0,0) \pmod 2$. I've been trying to find a calculator to do it, but even Wolfram Alpha says it's too big of a matrix to reduce. In order to find the coefficients $a_i$ such that $a_1v_1+a_2v_2+...a_{12}v_{12}\equiv (0,0,0,0,0,0,0,0,0,0,0)\pmod 2$, my textbook says something about setting up a $12$ by $12$ identity matrix $I$ to the right of the $12$ vectors and then the diagonal of that former identity matrix will be my coefficients?

Here are the $12$ vectors:

$$v_1 = (0,1,0,0,0,0,0,1,0,1,0)$$ $$v_2 = (0,1,1,0,1,1,0,0,0,0,0)$$ $$v_3 = (1,0,0,1,0,0,0,1,0,0,0)$$ $$v_4 = (0,0,1,0,0,0,0,0,0,0,0)$$ $$v_5 = (1,0,0,1,0,0,0,0,1,0,0)$$ $$v_6 = (1,0,1,0,1,0,0,0,0,0,1)$$ $$v_7 = (0,1,0,1,0,0,0,0,0,0,0)$$ $$v_8 = (0,0,1,0,0,1,0,0,0,0,0)$$ $$v_9 = (1,1,1,1,0,0,0,0,0,1,0)$$ $$v_{10} = (1,0,0,1,0,0,0,1,0,0,0)$$ $$v_{11} = (0,1,1,0,1,0,0,0,0,0,0)$$ $$v_{12} = (1,1,1,0,0,1,0,0,1,0,0)$$

Answer 1

Indeed, @Gerry Myerson is right to say that it is a kernel issue. Here is why :

$$a_1v_1+a_2v_2+\cdots a_nv_n=0 \ \iff $$

$$\pmatrix{| & | & \cdots & | \\ v_1&v_2& \cdots & v_n\\| & | & \cdots & | }\pmatrix{a_1\\a_2\\ \cdots\\a_n}=\pmatrix{0\\0\\ \cdots\\0}$$

The computation of a basis of the kernel can be easily done by the following SAGE program :

B = MatrixSpace(GF(2),12,11);
# B = space of 12 x 11 boolean matrices
# Notation GF() = Galois Field
M = B.matrix([
[0,1,0,0,0,0,0,1,0,1,0],#v1
[0,1,1,0,1,1,0,0,0,0,0],#v2
[1,0,0,1,0,0,0,1,0,0,0],#v3
[0,0,1,0,0,0,0,0,0,0,0],#v4
[1,0,0,1,0,0,0,0,1,0,0],#v5
[1,0,1,0,1,0,0,0,0,0,1],#v6
[0,1,0,1,0,0,0,0,0,0,0],#v7
[0,0,1,0,0,1,0,0,0,0,0],#v8
[1,1,1,1,0,0,0,0,0,1,0],#v9
[1,0,0,1,0,0,0,1,0,0,0],#v10
[0,1,1,0,1,0,0,0,0,0,0],#v11
[1,1,1,0,0,1,0,0,1,0,0] #v12
]);
K = M.kernel();K 

It provides (instantly !) the following answer about a basis of the kernel :

"Vector space of degree 12 and dimension 4 over Finite Field of size 2"

"Basis matrix:"

[1 0 0 1 0 0 0 0 1 1 0 0]
[0 1 0 1 0 0 0 1 0 0 1 0]
[0 0 1 0 0 0 0 0 0 1 0 0]
[0 0 0 0 1 0 1 1 0 0 0 1]

What is the meaning of this answer ? That any of the four lines $[a_1,a_2,\cdots,a_{12}]$ gives a list of coefficients of a null combination $\sum a_kv_k=0$.

For example, the first line gives :

$$v_1+v_4+v_9+v_{10}=0$$

The third line : $v_3+v_{10}=0$ attracts our attention on the fact that $v_3$ and $v_{10}$ are identical...

Of course, these are "basic" null linear relationships. Any of the $2^4-1$ combinations of those yield also null linear relationships (these have been given in a comment by @JMoravitz, obtained by a different method).

It is to be noted that the kernel in SAGE is a left kernel (i.e., the kernel of the transposed matrix), but this is exactly what we need here.

Remark : it is very easy to use SAGE : just call https://sagecell.sagemath.org/ : a window is opened, type your program in it and press the button "Evaluate".