# Linearly dependent vectors over finite fields

My problem is as follows:

Assume you have a vector space of dimension $(d + 1)$, with values over $GF(q)$. Every vector in this vector space can be regarded as an element of the extension field $GF(q^{d+1})$. It is well known that every element of a finite field can be expressed as a primitive element power and as a linear combination of primitive powers from $0$ up to $d$.

It turns out that the element of the field expressed as the $(i + kn)$th powers of a primitive element, taken modulo $n$ have linearly dependent vector representation (elements of vectors are the coefficients of the lin combination), where $n = (q^{d + 1} - 1)/(q - 1)$. They basically lie on the same line in the original vector space...

But i can't find a proof... I'm not really an expert of the field and i suspect the problem could be stated more formally. Any help? Thanks in advance!

Francesco

Edit: let's say $\beta = \alpha^i$, where $\beta$ is an element of the extension field and $\alpha$ is a primitive over that field. We also know that $\beta$ can be expressed as a linear combination of $1, \alpha, \alpha^2, \dots, \alpha^d$ with coefficients $(a_0, \dots, a_d)$ over $GF(q)$. Those coefficients actually determine a vector of the finite vector space of dimension $(d+1)$. Now take a second element $\beta' = \alpha^{i+kn}$, for some $k$ integer. The coefficient of the linear combination of $1, \alpha, \alpha^2, \dots, \alpha^d$ that represent $\beta'$ form a vector $(a_0', \dots, a_d')$ which is linearly dependent to $(a_0, \dots, a_d)$. So in the vector space of dimension $(d+1)$ with values over $GF(q)$, those vectors lie on the same line through the origin. I know that this is true, but I can't find a proof. So my question is actually a proof.

Hope to have make my point a bit more clear.

-
It's hard, for me at least, to make some sense of your question: what is that "$\,(i+kn)-\,$th powers of a primitive element" thing? Who are "they" that basically lie on a same line"? What's the question, anyway? – DonAntonio Jun 11 '12 at 9:44
I'll try to make those points a bit more clear. – Francesco Solera Jun 11 '12 at 9:52

Assume that $\alpha$ is a primitive element of $GF(q^{d+1})$. So $\alpha$ is of (multiplicative) order $q^{d+1}-1$, and $GF(q^{d+1})^*=\langle \alpha \rangle$. Consider the element $\gamma=\alpha^n,$ where $$n=(q^{d+1}-1)/(q-1)=q^d+q^{d-1}+q^{d-2}+\cdots+q+1.$$ We have $$qn=q(q^d+q^{d-1}+q^{d-2}+\cdots q^2+q+1)=q^{d+1}+q^{d}+q^{d-1}+\cdots q^2+q= n+ (q^{d+1}-1),$$ so $$\gamma^q=\alpha^{qn}=\alpha^{n+(q^{d+1}-1)}=\alpha^n\cdot \alpha^{q^{d+1}-1}=\alpha^n\cdot1=\gamma.$$ This means that $\gamma$ is an element of the smaller field $GF(q)$. Furthermore, the theory of cyclic groups tells that the order of $\gamma$ is $q-1$, so it is a primitive element of the field $GF(q)$. In other words the set $$GF(q)^*=\{1,\gamma, \gamma^2,\cdots, \gamma^{q-2}\}.$$
This gives an explanation to the phenomenon that you observed. If we fix an integer $i, 0\le i<n$, and let $k$ vary over the range $0\le k <q-1$, then $$\alpha^{i+kn}=\alpha^i\cdot(\alpha^n)^k=\alpha^i\gamma^k$$ ranges over the set $\{x \alpha^i\mid x\in GF(q)^*\}$. Together with $0$ these elements form the 1-dimensional subspace over $GF(q)$ generated by $\alpha^i$. In other words, they all lie on the same line throught the origin in the $(d+1)$-dimensional space $GF(q^{d+1})$ over $GF(q)$.
Note: The mapping $N: x\mapsto x^n$ is easily seen to be the relative norm map from the extension field $GF(q^{d+1})$ to $GF(q)$. This is because $$x^n=x^{1+q+q^2+\cdots q^d}=x\cdot x^q\cdot x^{q^2}\cdots x^{q^d}$$ is the product of the conjugates of $x$ gotten by iterating the Frobenius automorphism. – Jyrki Lahtonen Jun 11 '12 at 10:13