Left-multiplication of a finite field element - Matrix representation

Question

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!

Answer 1

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

• $T(w + z) = T(w) + T(z)$ for every $w, z \in \mathbf C$
• $T(az) = aT(z)$ for every $z \in \mathbf C$ and $a \in \mathbf R$

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.

Answer 2

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

Answer 3

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?