6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The matrix associated to a multiplication in a field is invertible (unless you multiply by $0$). $\endgroup$ – Severin Schraven Jul 8 '20 at 12:09
  • $\begingroup$ 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? $\endgroup$ – Michael Hardy Jul 8 '20 at 14:38
4
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ @J Thanks!${}{}{}$ $\endgroup$ – Ben Grossmann Jul 8 '20 at 12:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Grossmann Jul 8 '20 at 12:46
  • $\begingroup$ That's a really interesting point. I know it sounds crazy, but you could ask that as a question. :) $\endgroup$ – John Hughes Jul 8 '20 at 13:05
  • $\begingroup$ @J Fair point.${}$ $\endgroup$ – Ben Grossmann Jul 8 '20 at 13:24
  • $\begingroup$ @J Found this in the suggestions as I started typing the question; updating accordingly. $\endgroup$ – Ben Grossmann Jul 8 '20 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.