Companion matrices and extension fields

In this section, we finally explain how to contruct the fields mentioned in §2.1.3 above. This section assumes some familiarity with linear algebra.

Definition 2.7.1   If $p(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+x^n$ is a monic polynomial of degree $n$ having coefficients in a ring $F$ then the companion matrix of $p(x)$ is the $n\times n$ matrix

$$C=\left( \begin {array}{cccccc} 0&0&0&0&0&-a_0\\ \noal... ...align{\medskip }0&\dots&0&0&1&-a_{n-1} \end{array} \right).$$

This matrix has the property that its characteristic polynomial is $p(x)$:

$$\det (C-x I_n)=p(x),$$

where $I_n$ is the $n\times n$ identity matrix,

$$I_n=\left( \begin {array}{cccc} 1&0&\dots &0\\ \noalig... ...1&0\\ \noalign{\medskip }0&\dots &0&1 \end{array} \right)$$

Example 2.7.2   Let $P(x)=x^2+x+1$. This is an irreducible polynomial over $\mathbb{F}_2$. The companion matrix of $p(x)$ is

$$C= \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right).$$

The set $\mathbb{F}_4=\{0,C,C^2,I_2=C^3\}$ is a field.

Example 2.7.3   If $p(x)={x}^{4}+9\,{x}^{3}+2\,{x}^{2}+17\,x+5$ then its companion matrix is

$$\left(\begin {array}{cccc} 0&0&0&-5\\ \noalign{\medskip }1&0&... ...ign{\medskip }0&1&0&-2\\ \noalign{\medskip }0&0&1&-9 \end {array} \right)$$

One of the main reasons for introducing the companion matrix at this stage is because of the following theorem.

Theorem 2.7.4   Let $F$ be a field and let $m(x)\in F[x]$ denote an irreducible monic polynomial in $F[x]$ of degree $d$. Let $C$ denote the companion matrix of $m(x)$. Then under ordinary matrix addition and matrix multiplication, $F[C]$ is a field extension of $F$ of degree $d$. Moreover, $F[x]/(m(x))$ is a field and the mapping $x^i\longmapsto C^i$ ( $i=0,1,2,...$) induces a field isomorphism $F[x]/(m(x))\cong F[C]$.

The proof of this fact uses the Cayley-Hamilton theorem from linear algebra (see for example [NJ]) and therefore would take us a little too far afield to present here.

Example 2.7.5   Let $F=\mathbb{F}_2$ and let $m(x)=x^3+x+1$. The multiplication table is

$*$	0	$1$	$x$	$x+1$	${x}^{2}$	${x}^{2}+1$	${x}^{2}+x$	${x}^{2}+x+1$
0	0	0	0	0	0	0	0	0
1	0	1	$x$	$x+1$	${x}^{2}$	${x}^{2}+1$	${x}^{2}+x$	${x}^{2}+x+1$
$x$	0	$x$	${x}^{2}$	${x}^{2}+x$	$x+1$	$1$	${x}^{2}+x+1$	${x}^{2}+1$
$x+1$	0	$x+1$	${x}^{2}+x$	${x}^{2}+1$	${x}^{2}+x+1$	${x}^{2}$	$1$	$x$
${x}^{2}$	0	${x}^{2}$	x+1	${x}^{2}+x+1$	${x}^{2}+x$	x	${x}^{2}+1$	1
${x}^{2}+1$	0	${x}^{2}+1$	1	${x}^{2}$	x	${x}^{2}+x+1$	x+1	${x}^{2}+x$
${x}^{2}+x$	0	${x}^{2}+x$	${x}^{2}+x+1$	1	${x}^{2}+1$	x+1	x	${x}^{2}$
${x}^{2}+x+1$	0	${x}^{2}+x+1$	${x}^{2}+1$	x	1	${x}^{2}+x$	${x}^{2}$	x+1

The addition table is

$+$	0	1	x	x+1	${x}^{2}$	${x}^{2}+1$	${x}^{2}+x$	${x}^{2}+x+1$
0	0	1	x	$x+1$	${x}^{2}$	${x}^{2}+1$	${x}^{2}+x$	${x}^{2}+x+1$
1	1	0	x+1	x	${x}^{2}+1$	${x}^{2}$	${x}^{2}+x+1$	${x}^{2}+x$
x	x	x+1	0	1	${x}^{2}+x$	${x}^{2}+x+1$	${x}^{2}$	${x}^{2}+1$
x+1	x+1	x	1	0	${x}^{2}+x+1$	${x}^{2}+x$	${x}^{2}+1$	${x}^{2}$
${x}^{2}$	${x}^{2}$	${x}^{2}+1$	${x}^{2}+x$	${x}^{2}+x+1$	0	1	x	$x+1$
${x}^{2}+1$	${x}^{2}+1$	${x}^{2}$	${x}^{2}+x+1$	${x}^{2}+x$	1	0	x+1	x
${x}^{2}+x$	${x}^{2}+x$	${x}^{2}+x+1$	${x}^{2}$	${x}^{2}+1$	x	x+1	0	1
${x}^{2}+x+1$	${x}^{2}+x+1$	${x}^{2}+x$	${x}^{2}+1$	${x}^{2}$	x+1	x	1	0

Exercise 2.7.6   In Example 2.7.5, show that $\mathbb{F}_2[x]/(x^3+x+1)$ is a field.

Exercise 2.7.7   If $A$ is any $n\times n$ matrix with entries in a ring $F$, let $F[A]$ denote the set of all ``polynomials in $A$'', i.e., all matrices of the form $a_0I_n+a_1A+a_2A^2+...+a_kA^k$, where $k\geq 0$ is any integer and $a_i\in F$ are arbitrary. Under ordinary matrix addition and matrix multiplication, $F[A]$ is a ring. Check this.