# Linear Independence of Elements over Binary Finite Fields

Consider the binary finite field $\mathbb{F}_{2^q}$ for some $q$. consider a set of elements $r_i$, $1\leq i \leq m$, in $\mathbb{F}_{2^q}$ where $m<2^q$.

My question: How to check that elements $r_i$'s are linear linear independence over $\mathbb{F}_{2^q}$.

Is there a matrix method such as the method that we use for vectors. In fact, is it true that we consider $r_i$'s as a vector in $\mathbb{F}_{2}$ and construct a matrix by these vectors. In the rest, if determinant of this matrix over $\mathbb{F}_{2}$ be non-zero then we conclude that $r_i$'s are linear linear independence over $\mathbb{F}_{2^q}$.

There is a similar question here but I can not understand how to apply for my question.

• It's a bit unclear what you are asking. Any two elements of $\Bbb{F}_{2^q}$ are linearly dependent over $\Bbb{F}_{2^q}$. They may or may not be linearly independent over a subfield though. Or if you meant vectors, like elements of $(\Bbb{F}_{2^q})^m$ for some $m>1$ you can use determinants like José's answer. – Jyrki Lahtonen Aug 13 '18 at 21:19
• @JyrkiLahtonen I appreciate for your comments. My clear question is: I work over $\operatorname{GF}(2^q)$ for $q>7$. In these fields I need to select some elements (at lease $2^{q-1}$) such that these elements be linear independence over$\operatorname{GF}(2^q)$. The first method is this, I calculate all linear combinations of these elements to check is zero or not. I thought that instead of the first method, I can use binary vectors for these elements and construct a binary matrix with these vectors and check singularity of the matrix. Just because of this I asked this question. Thanks again. – user0410 Aug 14 '18 at 6:59
• Still very unclear. If $\alpha$ and $\beta$ are two elements of $GF(2^q)$, then the relation $$\alpha\beta+\beta\alpha=0$$ shows that $\alpha$ and $\beta$ are linearly dependent over $GF(2^q)$. Either you actually want to study their linear independence over a subfield of $GF(2^q)$, or you are to study the linear indepence of vectors from $(GF(2^q))^m$ when the vectors have $m$ components, each from $GF(2^q)$. – Jyrki Lahtonen Aug 14 '18 at 7:05
• @JyrkiLahtonen Professor Lahtonen, is it possible to ask you to see Step 1 in Algorithm 1 of this paper. In fact, I want to apply the Algorithm 1, but its Step 2, confused me. – user0410 Aug 14 '18 at 7:22
• It seems clear to me that you are to generate a set of $m$ elements of $GF(2^n)$ such that they are linearly independent over $GF(2)$. If you have any basis of $GF(2^n)$ over $GF(2)$ (such as the monomial basis given by a generator of the field extension) then this is equivalent to selecting $m$ linearly independent vectors from $GF(2)^n$. Use the $n$-tuples of elements of $GF(2)$ as coordinate vectors w.r.t. the basis you had. Observe that you only need $m$ linearly independent vectors. They are just denoted as $x_1,x_2,x_4,x_8,\ldots,x_{2^{m-1}}$ because this helps with the rest. – Jyrki Lahtonen Aug 14 '18 at 8:44

There is nothing peculiar about these fields as far as linear independence is concerned. Consider, for instance, the vectors $(1,1,0)$, $(0,1,1)$, and $(1,0,1)$. Are they linearly independent over $\mathbb{F}_{2^q}$? In order to know, compute the determinant$$\begin{vmatrix}1&0&1\\1&1&0\\0&1&1\end{vmatrix}.$$In turns out that it is equal to $0$. Therefore, the vectors are linearly dependent (for any $q$).
• Thanks for your answer. In your example, vectors $(1,1,0)$, $(0,1,1)$ and $(1,0,1)$ means elements $\alpha +1$, $\alpha^2 +\alpha$ and $\alpha^2 +1$ where $\alpha$ is a root of $f$ that is used to construct $\mathbb{F}_{2^q}$. Am I right? – user0410 Aug 13 '18 at 14:32
• @user0410 No. $(1,1,0),(0,1,1),(1,0,1)\in{\mathbb{F}_{2^q}}^3=\mathbb{F}_{2^q}\times\mathbb{F}_{2^q}\times\mathbb{F}_{2^q}$. This has nothing to do with polynomials. – José Carlos Santos Aug 13 '18 at 14:39
• Excuse me, I'm a little confused. Consider for example $\mathbb{F}_{2^4}$ that is constructed with $f=x^4+x+1$. Consider $\alpha$ is a root of $f$. Now how to check elements $\alpha^2 +\alpha$, $\alpha^2 +1$ and $\alpha +1$ are linearly dependent by matrix method over $\mathbb{F}_{2^4}$? – user0410 Aug 13 '18 at 14:57
• @user0410 You can just check that $(\alpha^2+\alpha)+(\alpha^2+1)+(\alpha+1)=0$. This is equivalent to what José's answer is saying. Actually, studying determinants can also be turned into a method for finding a linear dependency relation. – Jyrki Lahtonen Aug 13 '18 at 21:29