1
$\begingroup$

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.

Thanks for your suggestions.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 13 '18 at 21:19
  • $\begingroup$ @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. $\endgroup$ – user0410 Aug 14 '18 at 6:59
  • $\begingroup$ 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) $. $\endgroup$ – Jyrki Lahtonen Aug 14 '18 at 7:05
  • $\begingroup$ @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. $\endgroup$ – user0410 Aug 14 '18 at 7:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 14 '18 at 8:44
1
$\begingroup$

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$).

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ – user0410 Aug 13 '18 at 14:32
  • $\begingroup$ @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. $\endgroup$ – José Carlos Santos Aug 13 '18 at 14:39
  • $\begingroup$ 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}$? $\endgroup$ – user0410 Aug 13 '18 at 14:57
  • 1
    $\begingroup$ OP wants to know if they are linearly independent, regarding the field with 16 elements as a vector space over the field with 2 elements. The ground field is the field with two elements. $\endgroup$ – Alfred Yerger Aug 13 '18 at 15:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Aug 13 '18 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.