Find the basis of GF(2)

Question

I do past papers and I stumbled upon this question in one of the papers. I know what is GF(2), but I have no idea how to find the basis from the given data.

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

The question asks me to find the basis of GF(2)^4 with the given 3 elements above. I tried to find information online, but could not find any examples upon GF(2). Basically, I need to find one more element, but I have no idea how to do it.

Answer 1

Hint:

Transpose these column vectors to row vectors, and perform row reduction in $\mathbf F_2$. It is not hard then to find a row vector which is not in the row space of the first three: you just have to check the determinant is not $0$.

Answer 2

Unsophisticated method:

There are $16$ elements of GF$(2)^4:$

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

Linear combinations of your $3$ elements yield the following $8$:

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

Take an element on the first list that's not on the second list, and you're done.

Answer 3

You just want to do the standard method to complete a set of vectors to a basis. The standard basis for $\mathrm{GF(2)}^{4}$ is $$\left\lbrace \begin{bmatrix}1\\0\\0\\0\end{bmatrix},\begin{bmatrix}0\\1\\0\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\\0\end{bmatrix},\begin{bmatrix}0\\0\\0\\1\end{bmatrix} \right\rbrace.$$ So you set up a matrix with your three vectors, and then the standard basis, as columns: $$\begin{bmatrix}1&1&1&1&0&0&0\\1&0&0&0&1&0&0\\0&1&0&0&0&1&0\\0&0&1&0&0&0&1\end{bmatrix}$$ and then you find a basis for the column space by reducing the matrix to echelon form (over $\mathrm{GF}(2)$ and determining the pivot columns. Those columns of your original matrix will give you a basis for $\mathrm{GF}(2)^{4}$.