# Finding the basis vectors of a null space of a matrix in GF2

In this document, page 11, the author writes that the basis vectors of the null space of the following matrix

\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}

are (1, 0, 0, 0) and (0, 0, 1, 1). How did the author find these vectors ? The matrix is singular, I don't see how he achieved this result. Subsidiary question: what would be the basis vectors ? (0, 1, 1, 0) and (1, 1, 0, 0) ?

Thank you.

• What are the basis vectors of a matrix? – Bernard Nov 16 '15 at 23:47
• The basis vectors of the kernel of the vector space forming the given matrix. – Copro Nov 17 '15 at 8:16

You find the null space just like you would with any other matrix, just doing your operations in $\mathbb{F}_{2}$. However, the author is using the slightly unusual convention of multiplying (row) vectors from the left side of the matrix. This makes it a little awkward to work things by hand, because you would have to do column operations, etc. The easiest way is to work with the transpose of the matrix, so you can do row operations like usual. So you would look at $$A^{T} = \begin{bmatrix} 0 & 0 & 1 & 1\\0 & 1 & 1 & 1\\0 & 1 & 0 & 0\\0 & 0 & 0 & 0 \end{bmatrix}$$ which row reduces to $$\begin{bmatrix} 0 & 1 & 0 & 0\\0&0&1&1\\0&0&0&0\\0&0&0&0\end{bmatrix}$$ so you see the null space has basis given by $(1,0,0,0)$, $(0,0,1,1)$.
(you can check that these two vectors, if you use them as column vectors, are in the null space of $A^{T}$; if you use them as row vectors, they are in the null space of your original matrix when multiplied from the left, that is, they satisfy $vA = 0$).