Can someone explain me why and how a left multiplication of an element of a finite field GF(2^k) can be seen as a linear transformation on GF(2^k) over GF(2)? I read this https://www.maa.org/sites/default/files/Wardlaw47052.pdf but it is not clear to me.
Thank you!
The field $\operatorname{GF}(2^k)$ is a finite dimensional vector space over $\operatorname{GF}(2)$ for $k$ any integer greater zero, so we can talk about linear transformations on this vector space. Let $\alpha \in \operatorname{GF}(2^k)$ and define the following map
$$ \begin{align} T_\alpha: \operatorname{GF}(2^k) &\to \operatorname{GF}(2^k) \\ x & \mapsto \alpha x \end{align} $$
That is, $T_\alpha$ is a map which takes an element of $x \in \operatorname{GF}(2^k)$ and maps it to $\alpha x \in \operatorname{GF}(2^k)$. This is the multiplication map you are talking about. This is indeed a linear transformation since for $x, y \in \operatorname{GF}(2^k)$ and $c \in \operatorname{GF}(2)$ we have that
$$ T_\alpha(x + y) = \alpha(x + y) = \alpha x + \alpha y = T_\alpha(x) + T_\alpha(y) $$
and
$$ T_\alpha(cx) = \alpha(cx) = c(\alpha x) = cT_\alpha(x) $$
Edit: As mentioned in the comment by lhf, all of the above argument still holds if the field extension $\operatorname{GF}(2^k)/\operatorname{GF}(2)$ is replaced by an arbitrary field extension $L/K$. It is not necessary that the field $K$ be finite, nor is it necessary that the degree of the extension be finite. This is readily seen because the fact that $L$ is a vector space over $K$, as well as linearity of $T_\alpha$ follows simply from the field axioms and the fact that $K$ is a subfield of $L$.
Let's look at something you are hopefully more familiar with and that is the complex and real numbers. Every complex number can be written uniquely as $a + bi$ with $a, b \in \mathbf R$. This means that $\{1, i\}$ is linearly independent over $\mathbf R$ (it is a basis of $\mathbf C$ over $\mathbf R$). A linear transformation of $\mathbf C$ over $\mathbf R$ is a function $T : \mathbf C \to \mathbf C$ such that
Every such transformation takes the form
$$ T(a + bi) = (ar + bs) + (at + bu)i, $$
for some real numbers $r,s,t,u$. We can write this equation in matrix form as
$$ \begin{pmatrix} r & s \\ t & u \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} ar + bs \\ at + bu \end{pmatrix}. $$
For instance, the complex conjugation map $T(a + bi) = a - bi$ corresponds to the matrix equation
$$ \begin{pmatrix} 1 & 0 \\ 0 & - 1 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} a \\ -b \end{pmatrix}. $$
We can also consider the map $T(a + bi) = (c + di)(a + bi)$ (that is, $T$ multiplies on the left by $c + di$). Expanding this out we have
$$T(a + bi) = (c + di)(a + bi) = (ac - bd) + (ad + bc)i, $$
which corresponds to the matrix equation
$$ \begin{pmatrix} c & -d \\ d & c \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} ac - bd \\ ad + bc \end{pmatrix}. $$
For ${\rm GF}(2^k)$ over ${\rm GF}(2)$ it is the same idea but instead of $\{1, i\}$ as a basis you have some other basis.
Thank you for your answers. So, let us suppose to have $\mathbb{F}_{2^3}$ over $\mathbb{F}_{2}$, with $\mathbb{F}_{2^3}=\dfrac{\mathbb{F}_{2}[x]}{<x^3+x+1>}$. A basis is $\{1,\alpha,\alpha^{2}\}$, with $\alpha^{3}=\alpha+1$. Let us consider the left multiplication by a generic element $a_{0}+a_{1}\alpha+a_{2}\alpha^{2}$. So, $$(a_{0}+a_{1}\alpha+a_{2}\alpha^{2})(b_{0}+b_{1}\alpha+b_{2}\alpha^{2})$$ and one have $(a_{0}b_{0}+a_{2}b_{1}+a_{1}b_{2})+(a_{0}b_{1}+a_{1}b_{0}+a_{1}b_{2}+a_{2}b_{2})\alpha+(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}+a_{2}b_{1}+a_{2}b_{2})\alpha^2$.
The matrix representation is $$\begin{bmatrix} a_{0} & a_{2} & a_{1} \\ a_{1} & a_{0} & a_{1}+a_{2} \\ a_{2} & a_{1}+a_{2} & a_{0}+a_{2} \end{bmatrix} \begin{bmatrix} b_{0} \\ b_{1} \\ b_{2}. \end{bmatrix}$$ So, if we multiply for $\alpha$ we have that $a_{0}=0, a_{1}=1$ and $a_{2}=0$ so that we obtain \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} which is the companion matrix of $x^3+x+1$. Is that correct?