Intuition for Artin's lemma Let $E$ be a field. If $G$ is subgroup of $\text{Aut} (E)$, then the set:
$\text{Inv}(G) = \{a \in E: \forall \ \eta \in G, \eta(a) = a\}$ is a subfield of $E$. Artin's lemma is:

Let $E$ be a field, $G$ be a finite subgroup of $\text{Aut}(E)$, and $F = \text{Inv}(G)$. Then, $[E:F] \le |G|$.

The proof in the textbook is not very satisfying. It is not clear what is going on. I completely understand it, but it seems to come out of nowhere. 
Can someone provide some intuition?
Here's the proof: ($(17)$ is the equation $[E:F] \le |G|$)


(Just ignore the bit about linear equations..)
 A: I was recently trying to gain intuition for the same proof, so I will share my findings on this question which has remained unanswered for a few years now. My starting point was to read Noam Elkies' version. After reading it, my feeling is that there is really only one trick being used: arbitraging between symmetry of an object, and the size of the space it lives in. You can think of it like a fancy version of an averaging procedure. A physicist might even describe this as an inverse of symmetry breaking.
I'll employ a trick novelists use and start in medias res, halfway through Elkies' argument:

In fact, we show that in every nonzero $E$-vector subspace of $E^m$ that is invariant under $G$, a minimal-weight vector is proportional to one in $F^m$.

Without even knowing what "minimal-weight" means, we can already see what this claim is saying: we can go from a big space with a little bit of symmetry into a little space with lots of symmetry - swapping size for symmetry. Indeed, elements of $F$ are nothing but highly symmetric elements of $E$, and the little space I am referring to is the $1$-dimensional $E$-vector space spanned by any such minimal-weight vector.
The only property of $m$ used in the proof of the highlighted claim is that it is finite - for the proof uses a variation of Fermat's method of descent. We use the weight to track how "large" an element of $E^m$ is. Each symmetry (i.e. element of $G$) corresponds to an operation which reduces the weight of a vector $b\in E^m$ (after normalizing $b$ such that one of its entries equals $1$). The operation returns zero only when we have satisfied the corresponding symmetry. Since the weight can only decrease finitely many times before hitting zero, if we stop this procedure right before this happens we will have found an element with the desired amount of symmetry.
Great, so now we should have some intuition about why the highlighted claim is true (and the full details are spelled out precisely in the page I linked). But how is this related to the original question? Remember, we are trying to prove an upper bound on the dimension of a vector space. This means we are trying to find lots of linear dependencies between its elements. The only thing we know about the base field is that it is highly symmetric, so we had better find a way of exploiting symmetry.
Here we will use the same idea as before, to trade off size vs symmetry. We are trying to find a non-trivial $F$-linear dependence between $m$ arbitrary elements of $E$, where $m>|G|$. Equivalently, we are trying to find a non-zero element in the kernel of an arbitrary $F$-linear map from $F^m$ to $E$. But this map is not symmetric, so we have to find some way of introducing symmetry - at the cost of making the map higher dimensional.
The new map goes from $F^m$ to $E^{|G|}$, so it can be thought of as a collection of maps from $F^m$ to $E$ indexed by elements of $G$, where the map corresponding to $g\in G$ is obtained from our original map by applying $g$ to all of its coefficients. We've taken a single equation (which should be easy to satisfy, but hard to solve explicitly since it is asymmetric) and replaced it by a family of equations (which in principle is harder to solve since it is more constrained, but whose solution set is highly symmetric).
We can guarantee non-trivial solutions (for dimensional reasons) by extending the map from $F^m\to E^{|G|}$ to $E^m\to E^{|G|}$ - it has the same coefficients, but now ranging over $E$. We can apply the highlighted claim to the solution set of this extended map, obtaining a non-trivial highly symmetric element.
Due to its symmetries, it will actually belong to the kernel of the $F^m\to E^{|G|}$ map, which in particular yields the desired linear dependence (by considering the equation corresponding to the identity element of $G$), and hence the dimension bound.

In summary, my intuition for this result is that "size can be exchanged for symmetry". There are many ways to formulate such a vague principle, but in particular Elkies found a nice formulation (the highlighted quote above) and a slick proof (using Fermat descent). And once you know what you are looking for, you can more or less follow your nose to reduce the original problem to here.
A: Here is how I presented this in a course I just taught. The students seemed to find it made sense.
Lemma 1 Let $E$ be a field and let $V$ be an $E$-vector subspace of $E^m$. Then $V$ has a basis $v_1$, $v_2$, ..., $v_d$ such that the $d \times m$ matrix with rows $v_j$ is in reduced row echelon form.
Proof Take an arbitrary basis $w_1$, ..., $w_d$ for $V$, make a matrix whose rows are the $w_j$, and apply row operations to put the matrix into reduced row echelon form. Row operations don't change the span of the rows. $\square$
Lemma 2 Let $E$ be a field, let $G$ be a subgroup of $\mathrm{Aut}(E)$ and let $F$ be the fixed field of $G$. Let $V$ be a subspace of $E^m$ such that, for all $g \in G$, we have $g(V) = V$. Then $V$ has a basis in $F^m$.
Proof Let $v_1$, ..., $v_d$ be the basis in reduced row echelon form; we will show that the $v_i$ are in $F^m$. Let $j_i$ be the position of the pivot of $v_i$. Let $g\in G$. By hypothesis, $g(v_i)$ is in the $E$-linear span of $v_1$, ..., $v_d$, say $g(v_i) = \sum_{i'} c_{i'} v_{i'}$. Comparing the entry of both sides in position $j_{i'}$, we get that $c_i = 1$ and $c_{i'} = 0$ for $i' \neq i$. So $g(v_i) = v_i$, the vector $v_i$ is fixed by $g$ and, thus, $v_i \in F^m$. $\square$
Now, let's prove the result. Let $E$, $F$ and $G$ be as in Lemma 2 (and the OP's question). Let $n = |G|$. Suppose, for the sake of contradiction, that there are $F$-linearly independent elements, $u_1$, ..., $u_m$ of $E$ with $m>n$. Define a subspace $V$ of $E^m$ by
$$V = \left\{ (c_1, \ldots, c_m) \in E^m : \sum_{j=1}^m c_j g(u_j) = 0 \ \forall g \in G \right\}.$$
We note that this is an $E$-linear subspace of $E^m$. We also note that $g(V) = V$, since if $(c_1, \ldots, c_m) \in V$ and $h \in G$ then
$$\sum_{j=1}^m h(c_j) g(u_j) = h \left( \sum_{j=1}^m c_j \ h^{-1}(g(u_j)) \right) = h(0) = 0.$$
So Lemma 2 applies and $V$ has a basis in $F^m$. Also, since our hypothesis states that $m>n$, the subspace $V$ is cut out by $n$ equations in $m$ variables and thus $\dim V >0$. So there is some nonzero vector $(c_1, \ldots, c_m) \in V$.
But then, putting $g=e$ in the definition of $V$, we deduce that $\sum c_j u_j =0$, a contradiction since the $u_j$ were chosen to be a basis. $\square$.
Most textbooks seem to aim for getting one nonzero element of $E \cap F^m$. While that is all that is logically needed, they need to use ad hoc tricks, when they could just appeal to the reduced row echelon form that students have hopefully all seen in their linear algebra course.
