# Which linear maps on a finite field are field multiplications?

I am mainly interested in the fields $$\mathrm{GF}(2^n)$$, but the question can be asked for any prime.

We can write out each element $$x\in\mathrm{GF}(2^n)$$ in base $$2$$ and note that its additive group combined with multiplication by elements of $$\mathrm{GF}(2)$$ is isomorphic to the vector space $$\left(\mathbb{Z}/(2\mathbb{Z})\right)^n$$. Let $$v:\mathrm{GF}(2^n)\to\left(\mathbb{Z}/(2\mathbb{Z})\right)^n$$ stand for this "vectorisation" operation.

Linear maps on $$\left(\mathbb{Z}/(2\mathbb{Z})\right)^n$$ may be represented by $$n\times n$$, $$\{0,1\}$$-valued matrices.

Since field multiplication is linear for any $$x\in\mathrm{GF}(2^n)$$ there is a matrix $$M_x$$ such that for all $$y\in\mathrm{GF}(2^n)$$ \begin{align} M_x v(y) = v(x\cdot y), \end{align}

There are, however $$2^{n\times n}$$ matrices and only $$2^{n}$$ field elements, so the question is what can we say about the structure of the set of matrices $$\{M_x \mid x\in \mathrm{GF}(2^n)\}$$ as a subset of the full set of matrices?

Loosely speaking - if I give you a matrix then how can you tell if it represents a field element?

• The matrix associated to a multiplication in a field is invertible (unless you multiply by $0$). – Severin Schraven Jul 8 '20 at 12:09
• I wonder if it's easier if instead of asking which matrices are of some special class, you ask what the matrix looks like for a member of that special class? – Michael Hardy Jul 8 '20 at 14:38

We note that any finite field $$GF(p^n)$$ can be presented in the form $$GF(p^n) = \Bbb Z_p[x]/\langle q(x)\rangle$$, where $$\Bbb Z_p = \Bbb Z/p\Bbb Z$$ and $$q$$ is an irreducible polynomial of degree $$n$$. Relative to the basis $$\{1,x,\dots,x^{n-1}\}$$, we find that the matrix $$M_x$$ corresponding to multiplication by (the distinguished indeterminate) $$x$$ is given by the companion matrix $$C_q$$ of $$q$$. It follows that a matrix $$M$$ corresponds to a field element if and only if there exists there exists a polynomial $$f$$ for which $$M = f(C_q)$$.

Because the matrix $$C_q$$ is non-derogatory, it turns out that there is such a polynomial $$f$$ if and only if $$C_q M = MC_q$$ (cf. Horn and Johnson Matrix Analysis theorem 3.2.4.2).

We can get another perspective on this if we take the elements of the matrix to themselves be elements of $$GF(p^n)$$. Any irreducible polynomial over $$\Bbb Z_p$$ splits into distinct linear factors over its splitting field. It follows the polynomial $$q$$ splits into linear factors with $$q(x) = (x - a_1)\cdots (x - a_n), \quad a_i \in GF(p^n).$$ It follows that the matrix $$C_q$$ is diagonalizable $$GF(p^n)$$. A matrix $$M$$ will commute with $$\operatorname{diag}(a_1,\dots,a_n)$$ if and only if it is also diagonal. So, given a matrix, it suffices to change bases and check whether the transformed matrix has the required block structure.

More specifically, the eigenvectors of $$C_p$$ correspond to the polynomials of multiplication by $$x$$, which are $$q_i(x) = q(x)/(x - a_i), i = 1,\dots,n.$$ In particular, we can see that $$xq_i(x) = a_i q_i(x)$$, modulo $$q(x)$$. $$M$$ will correspond to multiplication by an element of $$GF(p^n)$$ if and only if $$p_i(x)$$ is an eigenvector of (the operator over $$\Bbb Z_p/q(x)$$ corresponding to) $$M$$ for all $$i$$.

• @J Thanks!${}{}{}$ – Ben Grossmann Jul 8 '20 at 12:34
• I'm not sure if it's possible for an irreducible polynomial over a finite field to have repeated roots (which is a possibility that I account for in my answer). If anybody has an example of such a polynomial or knows that no such polynomial exists, please let me know. – Ben Grossmann Jul 8 '20 at 12:46
• That's a really interesting point. I know it sounds crazy, but you could ask that as a question. :) – John Hughes Jul 8 '20 at 13:05
• @J Fair point.${}$ – Ben Grossmann Jul 8 '20 at 13:24
• @J Found this in the suggestions as I started typing the question; updating accordingly. – Ben Grossmann Jul 8 '20 at 13:28