# Appendix E Polynomials

In this appendix, we discuss some useful properties of the polynomials with coefficients from a field. For the definition of a polynomial, refer to Section 1.2. Throughout this appendix, we assume that all polynomials have coefficients from a fixed field `F`.

# Definition.

*A polynomial* `f`(`x`) **divides** a polynomial`g`(`x`) *if there exists a polynomial* `q`(`x`) *such that* $g(x)=f(x)q(x)$.

Our first result shows that the familiar long division process for polynomials with real coefficients is valid for polynomials with coefficients from an arbitrary field.

# Theorem E.1 (The Division Algorithm for Polynomials).

*Let* `f`(`x`) *be a polynomial of degree n, and let* `g`(`x`) *be a polynomial of degree* $m\ge 0$. *Then there exist unique polynomials* `q`(`x`) *and* `r`(`x`) *such that*

*where the degree of* `r`(`x`) *is less than m.*

# Proof.

We begin by establishing the existence of `q`(`x`) and `r`(`x`) that satisfy (1). If $n<m$, take $q(x)=0$ and $r(x)=f(x)$ to satisfy (1). Otherwise, if $0\le m\le n$, we apply mathematical induction on `n`. First suppose that $n=0$. Then $m=0$, and it follows that `f`(`x`) and `g`(`x`) are nonzero constants. Hence we may take $q(x)=f(x)/g(x)$ and $r(x)=0$ to satisfy (1).

Now suppose that the result is valid for all polynomials with degree less than `n` for some fixed $n>0$, and assume that `f`(`x`) has degree `n`. Suppose that

and

and let `h`(`x`) be the polynomial defined by

Then `h`(`x`) is a polynomial of degree $k<n$, and therefore we may apply the induction hypothesis or the case where $k<m$ (whichever is relevant) to obtain polynomials ${q}_{1}(x)$ and `r`(`x`) such that `r`(`x`) has degree less than m and

Combining (2) and (3) and solving for `f`(`x`) gives us $f(x)=q(x)g(x)+r(x)$ with $q(x)={a}_{n}{b}_{m}^{-1}{x}^{n-m}+{q}_{1}(x)$, which establishes the existence of `q`(`x`) and `r`(`x`) by mathematical induction.

We now show the uniqueness of `q`(`x`) and `r`(`x`). Suppose that ${q}_{1}(x),{q}_{2}(x),{r}_{1}(x)$, and ${r}_{2}(x)$ exist such that ${r}_{1}(x)$ and ${r}_{2}(x)$ each has degree less than m and

Then

The right side of (4) is a polynomial of degree less than `m`. Since `g`(`x`) has degree `m`, it must follow that ${q}_{1}(x)-{q}_{2}(x)$ is the zero polynomial. Hence ${q}_{1}(x)={q}_{2}(x)$, and thus ${r}_{1}(x)={r}_{2}(x)$ by (4).

In the context of Theorem E.1, we call `q`(`x`) and `r`(`x`) the **quotient** and **remainder**, respectively, for the division of `f`(`x`) by `g`(`x`). For example, suppose that `F` is the field of complex numbers. Then the quotient and remainder for the division of

by

are, respectively,

# Corollary 1.

*Let* `f`(`x`) *be a polynomial of positive degree, and let* $a\in F$. *Then* $f(a)=0$ *if and only if* $x-a$ *divides* `f`(`x`).

# Proof.

Suppose that $x-a$ divides `f`(`x`). Then there exists a polynomial `q`(`x`) such that $f(x)=(x-a)q(x)$. Thus $f(a)=(a-a)q(a)=0\cdot q(a)=0$.

Conversely, suppose that $f(a)=0$. By the division algorithm, there exist polynomials `q`(`x`) and `r`(`x`) such that `r`(`x`) has degree less than 1 and

Substituting `a` for `x` in the equation above, we obtain $r(a)=0$. Since `r`(`x`) has degree less than 1, it must be the constant polynomial $r(x)=\mathit{0}$. Thus $f(x)=q(x)(x-a)$.

For any polynomial `f`(`x`) with coefficients from a field `F`, an element $a\in F$ is called a **zero** of `f`(`x`) if $f(a)=0$. With this terminology, the preceding corollary states that `a` is a zero of `f`(`x`) if and only if $x-a$ divides `f`(`x`).

# Corollary 2.

*Any polynomial of degree* $n\ge 1$ *has at most n distinct zeros.*

# Proof.

The proof is by mathematical induction on `n`. The result is obvious if $n=1$. Now suppose that the result is true for some positive integer `n`, and let `f`(`x`) be a polynomial of degree $n+1$. If `f`(`x`) has no zeros, then there is nothing to prove. Otherwise, if `a` is a zero of `f`(`x`), then by Corollary 1 we may write $f(x)=(x-a)q(x)$ for some polynomial `q`(`x`). Note that `q`(`x`) must be of degree `n`; therefore, by the induction hypothesis, `q`(`x`) can have at most `n` distinct zeros. Since any zero of `f`(`x`) distinct from `a` is also a zero of `q`(`x`), it follows that `f`(`x`) can have at most $n+1$ distinct zeros.

Polynomials having no common divisors arise naturally in the study of *canonical forms.* (See Chapter 7.)

# Definition.

*Polynomials* ${f}_{1}(x),\text{}{f}_{2}(x),\dots ,\text{}{f}_{n}(x)$ *are called relatively prime if no polynomial of positive degree divides all of them.*

For example, the polynomials with real coefficients $f(x)={x}^{2}(x-1)$ and $h(x)=(x-1)(x-2)$ are not relatively prime because $x-1$ divides each of them. On the other hand, consider `f`(`x`) and $g(x)=(x-2)(x-3)$, which do not appear to have common factors. Could other factorizations of `f`(`x`) and `g`(`x`) reveal a hidden common factor? We will soon see (Theorem E.9) that the preceding factors are the only ones. Thus `f`(`x`) and `g`(`x`) are relatively prime because they have no common factors of positive degree.

# Lemma.

*If* ${f}_{1}(x)$ *and* ${f}_{2}(x)$ *are relatively prime polynomials, there exist polynomials* ${q}_{1}(x)$ *and* ${q}_{2}(x)$ *such that*

*where* 1 *denotes the constant polynomial with value* 1.

# Proof.

Without loss of generality, assume that the degree of ${f}_{1}(x)$ is greater than or equal to the degree of ${f}_{2}(x)$. The proof is by mathematical induction on the degree of ${f}_{2}(x)$. If ${f}_{2}(x)$ has degree 0, then ${f}_{2}(x)$ is a nonzero constant `c`. In this case, we can take ${q}_{1}(x)=\mathit{0}$ and ${q}_{2}(x)=1/c$.

Now suppose that the theorem holds whenever the polynomial of lesser degree has degree less than `n` for some positive integer `n`, and suppose that ${f}_{2}(x)$ has degree `n`. By the division algorithm, there exist polynomials `q`(`x`) and `r`(`x`) such that `r`(`x`) has degree less than `n` and

Since ${f}_{1}(x)$ and ${f}_{2}(x)$ are relatively prime, `r`(`x`) is not the zero polynomial. We claim that ${f}_{2}(x)$ and `r`(`x`) are relatively prime. Suppose otherwise; then there exists a polynomial `g`(`x`) of positive degree that divides both ${f}_{2}(x)$ and `r`(`x`). Hence, by (5), `g`(`x`) also divides ${f}_{1}(x)$, contradicting the fact that ${f}_{1}(x)$ and ${f}_{2}(x)$ are relatively prime. Since `r`(`x`) has degree less than `n`, we may apply the induction hypothesis to ${f}_{2}(x)$ and `r`(`x`). Thus there exist polynomials ${g}_{1}(x)$ and ${g}_{2}(x)$ such that

Combining (5) and (6), we have

Thus, setting ${q}_{1}(x)={g}_{2}(x)$ and ${q}_{2}(x)={g}_{1}(x)-{g}_{2}(x)q(x)$, we obtain the desired result.

# Theorem E.2.

*If* ${f}_{1}(x),\text{}{f}_{2}(x),\dots ,\text{}{f}_{n}(x)$ *are relatively prime polynomials, there exist polynomials* ${q}_{1}(x),\text{}{q}_{2}(x),\dots ,\text{}{q}_{n}(x)$ *such that*

*where* 1 *denotes the constant polynomial with value* 1.

# Proof.

The proof is by mathematical induction on `n`, the number of polynomials. The preceding lemma establishes the case $n=2$.

Now assume the result is true for fewer than `n` polynomials, for some $n\ge 3$. We will first consider the trivial case where the first $n-1$ polynomials are relatively prime. By the induction hypothesis, there exist polynomials ${q}_{1}(x),\text{}{q}_{2}(x),\dots ,\text{}{q}_{n-1}(x)$ such that

Setting ${q}_{n}(x)=\mathit{0}$, the zero polynomial, we have

which proves the result if the first $n-1$ polynomials are relatively prime.

Now suppose that the first $n-1$ polynomials are not relatively prime, and let `g`(`x`) be the monic polynomial of maximum positive degree that divides each of these polynomials. For $k=1,\text{}2,\dots ,\text{}n-1$, let ${h}_{k}(x)$ be the polynomial defined by ${f}_{k}(x)=g(x){h}_{k}(x)$. Then the polynomials ${h}_{1}(x),\text{}{h}_{2}(x),\dots ,\text{}{h}_{n-1}(x)$ are relatively prime. So by the induction hypothesis, there exist polynomials ${\varphi}_{1}(x),\text{}{\varphi}_{2}(x),\dots ,\text{}{\varphi}_{n-1}(x)$ such that

Multiplying both sides of this equation by `g`(`x`), we obtain

Note that `g`(`x`) and ${f}_{n}(x)$ are relatively prime, and hence there exist polynomials `p`(`x`) and ${q}_{n}(x)$ such that

Let ${q}_{i}(x)=p(x){\varphi}_{i}(x)$ for $i=1,\text{}2,\dots ,\text{}n-1$. Then combining the two preceding equations yields

which completes the induction argument.

# Example 1

Let ${f}_{1}(x)=x-1,\text{}{f}_{2}(x)={x}^{2}+x-2\text{}{f}_{3}(x)={x}^{2}-x-1$, and ${f}_{4}(x)=x+1$. As polynomials with real coefficients, ${f}_{1}(x),\text{}{f}_{2}(x),\text{}{f}_{3}(x)$ and ${f}_{4}(x)$ are relatively prime. It is easily verified that the polynomials ${q}_{1}(x)=-{x}^{2},\text{}{q}_{2}(x)=x,\text{}{q}_{3}(x)=-3$, and ${q}_{4}(x)=x-2$ satisfy

and hence these polynomials satisfy the conclusion of Theorem E.2.

Throughout Chapters 5, 6, and 7, we consider linear operators that are polynomials in a particular operator T and matrices that are polynomials in a particular matrix `A`. For these operators and matrices, the following notation is convenient.

# Definitions.

*Let*

*be a polynomial with coefficients from a field F. If* T *is a linear operator on a vector space* V *over F, we define*

*Similarly, if A is an* $n\times n$ *matrix with entries from F, we define*

# Example 2

Let T be the linear operator on ${\text{R}}^{2}$ defined by $\text{T}(a,\text{}b)=(2a+b,\text{}a-b),$ and let $f(x)={x}^{2}+2x-3.$ It is easily checked that ${\text{T}}^{2}(a,\text{}b)=(5a+b,\text{}a+2b);$ so

Similarly, if

then

The next three results use this notation.

# Theorem E.3.

*Let* `f`(`x`) *be a polynomial with coefficients from a field F, and let* T *be a linear operator on a vector space* V *over F. Then the following statements are true.*

`f`(T)*is a linear operator on*V.*If*$\beta $*is a finite ordered basis for*V*and*$A={[\text{T}]}_{\beta},$*then*${[f(\text{T})]}_{\beta}=f(A)$.

# Proof.

Exercise.

# Theorem E.4.

*Let* T *be a linear operator on a vector space* V *over a field F, and let A be a square matrix with entries from F. Then, for any polynomials* ${f}_{1}(x)$ *and* ${f}_{2}(x)$ *with coefficients from F*,

${f}_{1}(\text{T}){f}_{2}(\text{T})={f}_{2}(\text{T}){f}_{1}(\text{T})$.

${f}_{1}(A){f}_{2}(A)={f}_{2}(A){f}_{1}(A)$.

# Proof.

Exercise.

# Theorem E.5.

*Let* T *be a linear operator on a vector space* V *over a field F, and let A be an* $n\times n$ *matrix with entries from F. If* ${f}_{1}(x)$ *and* ${f}_{2}(x)$ *are relatively prime polynomials with entries from F, then there exist polynomials* ${q}_{1}(x)$ *and* ${q}_{2}(x)$ *with entries from F such that*

${q}_{1}(\text{T}){f}_{1}(\text{T})+{q}_{2}(\text{T}){f}_{2}(\text{T})=\text{I}$.

${q}_{1}(A){f}_{1}(A)+{q}_{2}(A){f}_{2}(A)=I$.

# Proof.

Exercise.

In Chapters 5 and 7, we are concerned with determining when a linear operator T on a finite-dimensional vector space can be *diagonalized* and with finding a simple (canonical) representation of T. Both of these problems are affected by the factorization of a certain polynomial determined by T (the *characteristic polynomial* of T). In this setting, particular types of polynomials play an important role.

# Definitions.

*A polynomial* `f`(`x`) *with coefficients from a field F is called monic if its leading coefficient is* 1. *If* `f`(`x`) *has positive degree and cannot be expressed as a product of polynomials with coefficients from F each having positive degree, then* `f`(`x`) *is called irreducible.*

Observe that whether a polynomial is irreducible depends on the field `F` from which its coefficients come. For example, $f(x)={x}^{2}+1$ is irreducible over the field of real numbers, but it is not irreducible over the field of complex numbers since ${x}^{2}+1=(x+i)(x-i)$.

Clearly any polynomial of degree 1 is irreducible. Moreover, for polynomials with coefficients from an algebraically closed field, the polynomials of degree 1 are the only irreducible polynomials.

The following facts are easily established.

# Theorem E.6.

*Let* $\varphi (x)$ *and* `f`(`x`) *be polynomials. If* $\varphi (x)$ *is irreducible and* $\varphi (x)$ *does not divide* `f`(`x`), *then* $\varphi (x)$ *and* `f`(`x`) *are relatively prime.*

# Proof.

Exercise.

# Theorem E.7.

*Any two distinct irreducible monic polynomials are relatively prime*.

# Proof.

Exercise.

# Theorem E.8.

*Let* `f`(`x`), `g`(`x`), *and* $\varphi (x)$ *be polynomials. If* $\varphi (x)$ *is irreducible and divides the product* `f`(`x`)`g`(`x`), *then* $\varphi (x)$ *divides* `f`(`x`) *or* $\varphi (x)$ *divides* `g`(`x`).

# Proof.

Suppose that $\varphi (x)$ does not divide `f`(`x`). Then $\varphi (x)$ and `f`(`x`) are relatively prime by Theorem E.6, and so there exist polynomials ${q}_{1}(x)$ and ${q}_{2}(x)$ such that

Multiplying both sides of this equation by `g`(`x`) yields

Since $\varphi (x)$ divides `f`(`x`)`g`(`x`), there is a polynomial `h`(`x`) such that $f(x)g(x)=\varphi (x)h(x).$ Thus (7) becomes

So $\varphi (x)$ divides `g`(`x`).

# Corollary.

*Let* $\varphi (x),{\varphi}_{1}(x),{\varphi}_{2}(x),\dots ,{\varphi}_{n}(x)$ *be irreducible monic polynomials. If* $\varphi (x)$ *divides the product* ${\varphi}_{1}(x){\varphi}_{2}(x)\cdots {\varphi}_{n}(x),$ *then* $\varphi (x)={\varphi}_{i}(x)$ *for some* $i\text{}(i=1,\text{}2,\dots ,\text{}n)$.

# Proof.

We prove the corollary by mathematical induction on `n`. For $n=1,$ the result is an immediate consequence of Theorem E.7. Suppose then that for some $n>1,$ the corollary is true for any $n-1$ irreducible monic polynomials, and let ${\varphi}_{1}(x),{\varphi}_{2}(x),\dots ,{\varphi}_{n}(x)$ be `n` irreducible polynomials. If $\varphi (x)$ divides

then $\varphi (x)$ divides the product ${\varphi}_{1}(x){\varphi}_{2}(x)\cdots {\varphi}_{n-1}(x)$ or $\varphi (x)$ divides ${\varphi}_{n}(x)$ by Theorem E.8. In the first case, $\varphi (x)={\varphi}_{i}(x)$ for some $i\text{}(i=1,\text{}2,\dots ,\text{}n-1)$ by the induction hypothesis; in the second case, $\varphi (x)={\varphi}_{n}(x)$ by Theorem E.7.

We are now able to establish the unique factorization theorem, which is used throughout Chapters 5 and 7. This result states that every polynomial of positive degree is uniquely expressible as a constant times a product of irreducible monic polynomials.

# Theorem E.9 (Unique Factorization Theorem for Polynomials).

*For any polynomial* `f`(`x`) *of positive degree, there exist a unique constant c; unique distinct irreducible monic polynomials* ${\varphi}_{1}(x),\text{}{\varphi}_{2}(x),\dots ,\text{}{\varphi}_{k}(x);$ *and unique positive integers* ${n}_{1},\text{}{n}_{2},\dots ,\text{}{n}_{k}$ *such that*

# Proof.

We begin by showing the existence of such a factorization using mathematical induction on the degree of `f`(`x`). If `f`(`x`) is of degree 1, then $f(x)=ax+b$ for some constants `a` and `b` with $a\ne 0.$ Setting $\varphi (x)=x+b/a,$ we have $f(x)=a\varphi (x).$ Since $\varphi (x)$ is an irreducible monic polynomial, the result is proved in this case. Now suppose that the conclusion is true for any polynomial with positive degree less than some integer $n>1,$ and let `f`(`x`) be a polynomial of degree `n`. Then

for some constants ${a}_{i}$ with ${a}_{n}\ne 0.$ If `f`(`x`) is irreducible, then

is a representation of `f`(`x`) as a product of ${a}_{n}$ and an irreducible monic polynomial. If `f`(`x`) is not irreducible, then $f(x)=g(x)h(x)$ for some polynomials `g`(`x`) and `h`(`x`), each of positive degree less than `n`. The induction hypothesis guarantees that both `g`(`x`) and `h`(`x`) factor as products of a constant and powers of distinct irreducible monic polynomials. Consequently $f(x)=g(x)h(x)$ also factors in this way. Thus, in either case, `f`(`x`) can be factored as a product of a constant and powers of distinct irreducible monic polynomials.

It remains to establish the uniqueness of such a factorization. Suppose that

where `c` and `d` are constants, ${\varphi}_{i}(x)$ and ${\psi}_{j}(x)$ are irreducible monic polynomials, and ${n}_{i}$ and ${m}_{j}$ are positive integers for $i=1,\text{}2,\dots ,\text{}k$ and $j=1,\text{}2,\dots ,\text{}r.$ Clearly both `c` and `d` must be the leading coefficient of `f`(`x`); hence $c=d.$ Dividing by `c`, we find that (8) becomes

So ${\varphi}_{i}(x)$ divides the right side of (9) for $i=1,\text{}2,\dots ,\text{}k.$ Consequently, by the corollary to Theorem E.8, each ${\varphi}_{i}(x)$ equals some ${\psi}_{j}(x),$ and similarly, each ${\psi}_{j}(x)$ equals some ${\varphi}_{i}(x).$ We conclude that $r=k$ and that, by renumbering if necessary, ${\varphi}_{i}(x)={\psi}_{i}(x)$ for $i=1,\text{}2,\dots ,\text{}k.$ Suppose that ${n}_{i}\ne {m}_{i}$ for some `i`. Without loss of generality, we may suppose that $i=1$ and ${n}_{1}>{m}_{1}.$ Then by canceling ${[{\varphi}_{1}(x)]}^{{m}_{1}}$ from both sides of (9), we obtain

Since ${n}_{1}-{m}_{1}>0,\text{}{\varphi}_{1}(x)$ divides the left side of (10) and hence divides the right side also. So ${\varphi}_{1}(x)={\varphi}_{i}(x)$ for some $i=2,\dots ,\text{}k$ by the corollary to Theorem E.8. But this contradicts that ${\varphi}_{1}(x),\text{}{\varphi}_{2}(x),\dots ,\text{}{\varphi}_{k}(x)$ are distinct. Hence the factorizations of `f`(`x`) in (8) are the same.

It is often useful to regard a polynomial $f(x)={a}_{n}{x}^{n}+\cdots +{a}_{1}x+{a}_{0}$ with coefficients from a field `F` as a function $f:F\to F.$ In this case, the value of `f` at $c\in F$ is $f(c)={a}_{n}{c}^{n}+\cdots +{a}_{1}c+{a}_{0}.$ Unfortunately, for arbitrary fields there is not a one-to-one correspondence between polynomials and polynomial functions. For example, if $f(x)={x}^{2}$ and $g(x)=x$ are two polynomials over the field ${Z}_{2}$ (defined in Example 4 of Appendix C), then `f`(`x`) and `g`(`x`) have different degrees and hence are not equal as polynomials. But $f(a)=g(a)$ for all $a\in {Z}_{2},$ so that `f` and `g` are equal polynomial functions. Our final result shows that this anomaly cannot occur over an infinite field.

# Theorem E.10.

*Let* `f`(`x`) *and* `g`(`x`) *be polynomials with coefficients from an infinite field F. If* $f(a)=g(a)$ *for all* $a\in F,$ *then* `f`(`x`) *and* `g`(`x`) *are equal.*

# Proof.

Suppose that $f(a)=g(a)$ for all $a\in F.$ Define $h(x)=f(x)-g(x),$ and suppose that `h`(`x`) is of degree $n\ge 1.$ It follows from Corollary 2 to Theorem E.1 that `h`(`x`) can have at most `n` zeroes. But

for every $a\in F,$ contradicting the assumption that `h`(`x`) has positive degree. Thus `h`(`x`) is a constant polynomial, and since $h(a)=0$ for each $a\in F,$ it follows that `h`(`x`) is the zero polynomial. Hence $f(x)=g(x)$.