Linear independence of Galois conjugates Suppose we have an irreducible degree $n$ polynomial in $\mathbb{F}_{q}[x]$ whose roots
$$ \alpha, \alpha^q, \alpha^{q^2}, \dots, \alpha^{q^{n-1}} $$
over the extension field $\mathbb{F}_{q^n}$ do not form a normal basis. If we consider the roots as elements of the vector space over $\mathbb{F}_q$ with basis $\{1,\alpha,\alpha^2,\dots,\alpha^{n-1}\}$, is there a minimum number of these roots which must be linearly independent? 
For example, take $f(x)=x^3+2x+1$. Over $\mathbb{F}_{3^3}$ viewed as a vector space with basis $\{1,\alpha,\alpha^2\}$, the set of roots $\{\alpha,\alpha^3\}$ is linearly independent but once we add the third root, we find that $\alpha^{3^2} = 2\alpha+2\alpha^3$.
 A: I don't think much at all can be said in general. It is even possible that any two of the conjugates are linearly dependent over the smaller field. Consider the case $q=5$, and let $\alpha$ be a root of 
$$f(x)=x^4-2.$$
Because $2$ is of multiplicative order four, we see that $\alpha$ is necessarily of order $16$. But $5^n-1$ is a multiple of $16$ only when $4\mid n$. This mean that $\Bbb{F}_5(\alpha)=\Bbb{F}_{5^4}$, and hence $f(x)$ is irreducible over $\Bbb{F}_5$.
Here
$$
\begin{aligned}
\alpha^5&=\alpha\cdot\alpha^4=2\alpha,\\
\alpha^{25}&=(\alpha^5)^5=(2\alpha)^5=2^5\alpha^5=4\alpha,\\
\alpha^{125}&=8\alpha=3\alpha.
\end{aligned}
$$
You get linear dependence relations between other pair of conjugates by applying the Frobenius automorphism to the above relations.
A: Observation 1: For $n>1$, if $\gcd(n,q-1)=1$, then any two roots are linearly independent. 
Indeed, let $\alpha$ and $\beta$ be two roots of the degree-$n$ polynomial over $\mathbb{F}_q$ and assume $\beta = c\alpha$ with $c$ in $\mathbb{F}_q$. We have to show that $c=1$.
Let $\phi$ be the element of the Galois group (i.e. the power of Frobenius) that maps $\alpha$ to $\beta$; that is, $c\alpha = \beta=\phi(\alpha)$. Thus $\phi^r(\alpha)=c^r\alpha$, and we get that the order of $\phi$ (as an element in the Galois group) and the order of $c$ (in the multiplicative group $\mathbb{F}_q^*$) are equal. But the former divides $n$ and the latter divides $q-1$, so by assumption the order must be one and so $c=1$, as needed. 
Observation 2: If $n\mid q-1$, there exists an irreducible polynomial $f(X) = X^n - u$, such that any two distinct roots are linearly dependant.
Indeed, since there exists an $n$-th root of unity $c\in \mathbb{F}_q$, by Kummer theory, the extension $\mathbb{F}_{q^n}$ has a generator $\alpha$, with $\alpha^n \in \mathbb{F}_q$. From here you see that the conjugates of $\alpha$ are $c^i\alpha$, qed. 
