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

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 . Then there exist unique polynomials q(x) and r(x) such that

 (1)

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 , take  and  to satisfy (1). Otherwise, if , we apply mathematical induction on n. First suppose that . Then , and it follows that f(x) and g(x) are nonzero constants. Hence we may take  and  to satisfy (1).

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



and



and let h(x) be the polynomial defined by

 (2)

Then h(x) is a polynomial of degree , and therefore we may apply the induction hypothesis or the case where  (whichever is relevant) to obtain polynomials  and r(x) such that r(x) has degree less than m and

 (3)

Combining (2) and (3) and solving for f(x) gives us  with , 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 , and  exist such that  and  each has degree less than m and



Then

 (4)

The right side of (4) is a polynomial of degree less than m. Since g(x) has degree m, it must follow that  is the zero polynomial. Hence , and thus  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 . Then  if and only if  divides f(x).

# Proof.

Suppose that  divides f(x). Then there exists a polynomial q(x) such that . Thus .

Conversely, suppose that . 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 . Since r(x) has degree less than 1, it must be the constant polynomial . Thus .

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

# Corollary 2.

Any polynomial of degree  has at most n distinct zeros.

# Proof.

The proof is by mathematical induction on n. The result is obvious if . Now suppose that the result is true for some positive integer n, and let f(x) be a polynomial of degree . 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  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  distinct zeros.

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

# Definition.

Polynomials  are called relatively prime if no polynomial of positive degree divides all of them.

For example, the polynomials with real coefficients  and  are not relatively prime because  divides each of them. On the other hand, consider f(x) and , 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  and  are relatively prime polynomials, there exist polynomials  and  such that



where 1 denotes the constant polynomial with value 1.

# Proof.

Without loss of generality, assume that the degree of  is greater than or equal to the degree of . The proof is by mathematical induction on the degree of . If  has degree 0, then  is a nonzero constant c. In this case, we can take  and .

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

 (5)

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

 (6)

Combining (5) and (6), we have



Thus, setting  and , we obtain the desired result.

# Theorem E.2.

If  are relatively prime polynomials, there exist polynomials  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 .

Now assume the result is true for fewer than n polynomials, for some . We will first consider the trivial case where the first  polynomials are relatively prime. By the induction hypothesis, there exist polynomials  such that



Setting , the zero polynomial, we have



which proves the result if the first  polynomials are relatively prime.

Now suppose that the first  polynomials are not relatively prime, and let g(x) be the monic polynomial of maximum positive degree that divides each of these polynomials. For , let  be the polynomial defined by . Then the polynomials  are relatively prime. So by the induction hypothesis, there exist polynomials  such that



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



Note that g(x) and  are relatively prime, and hence there exist polynomials p(x) and  such that



Let  for . Then combining the two preceding equations yields



which completes the induction argument.

# Example 1

Let , and . As polynomials with real coefficients,  and  are relatively prime. It is easily verified that the polynomials , and  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  matrix with entries from F, we define



# Example 2

Let T be the linear operator on  defined by  and let  It is easily checked that  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.

1. f(T) is a linear operator on V.

2. If  is a finite ordered basis for V and  then .

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  and  with coefficients from F,

1. .

2. .

Exercise.

# Theorem E.5.

Let T be a linear operator on a vector space V over a field F, and let A be an  matrix with entries from F. If  and  are relatively prime polynomials with entries from F, then there exist polynomials  and  with entries from F such that

1. .

2. .

# 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,  is irreducible over the field of real numbers, but it is not irreducible over the field of complex numbers since .

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  and f(x) be polynomials. If  is irreducible and  does not divide f(x), then  and f(x) are relatively prime.

Exercise.

# Theorem E.7.

Any two distinct irreducible monic polynomials are relatively prime.

Exercise.

# Theorem E.8.

Let f(x), g(x), and  be polynomials. If  is irreducible and divides the product f(x)g(x), then  divides f(x) or  divides g(x).

# Proof.

Suppose that  does not divide f(x). Then  and f(x) are relatively prime by Theorem E.6, and so there exist polynomials  and  such that



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

 (7)

Since  divides f(x)g(x), there is a polynomial h(x) such that  Thus (7) becomes



So  divides g(x).

# Corollary.

Let  be irreducible monic polynomials. If  divides the product  then  for some .

# Proof.

We prove the corollary by mathematical induction on n. For  the result is an immediate consequence of Theorem E.7. Suppose then that for some  the corollary is true for any  irreducible monic polynomials, and let  be n irreducible polynomials. If  divides



then  divides the product  or  divides  by Theorem E.8. In the first case,  for some  by the induction hypothesis; in the second case,  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  and unique positive integers  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  for some constants a and b with  Setting  we have  Since  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  and let f(x) be a polynomial of degree n. Then



for some constants  with  If f(x) is irreducible, then



is a representation of f(x) as a product of  and an irreducible monic polynomial. If f(x) is not irreducible, then  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  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

 (8)

where c and d are constants,  and  are irreducible monic polynomials, and  and  are positive integers for  and  Clearly both c and d must be the leading coefficient of f(x); hence  Dividing by c, we find that (8) becomes

 (9)

So  divides the right side of (9) for  Consequently, by the corollary to Theorem E.8, each  equals some  and similarly, each  equals some  We conclude that  and that, by renumbering if necessary,  for  Suppose that  for some i. Without loss of generality, we may suppose that  and  Then by canceling  from both sides of (9), we obtain

 (10)

Since  divides the left side of (10) and hence divides the right side also. So  for some  by the corollary to Theorem E.8. But this contradicts that  are distinct. Hence the factorizations of f(x) in (8) are the same.

It is often useful to regard a polynomial  with coefficients from a field F as a function  In this case, the value of f at  is  Unfortunately, for arbitrary fields there is not a one-to-one correspondence between polynomials and polynomial functions. For example, if  and  are two polynomials over the field  (defined in Example 4 of Appendix C), then f(x) and g(x) have different degrees and hence are not equal as polynomials. But  for all  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  for all  then f(x) and g(x) are equal.

# Proof.

Suppose that  for all  Define  and suppose that h(x) is of degree  It follows from Corollary 2 to Theorem E.1 that h(x) can have at most n zeroes. But



for every  contradicting the assumption that h(x) has positive degree. Thus h(x) is a constant polynomial, and since  for each  it follows that h(x) is the zero polynomial. Hence .