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.
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.
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
where the degree of r(x) is less than m.
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
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
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
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,
Let f(x) be a polynomial of positive degree, and let . Then if and only if divides f(x).
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).
Any polynomial of degree has at most n distinct zeros.
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.)
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.
If and are relatively prime polynomials, there exist polynomials and such that
where 1 denotes the constant polynomial with value 1.
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
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
Combining (5) and (6), we have
Thus, setting and , we obtain the desired result.
If are relatively prime polynomials, there exist polynomials such that
where 1 denotes the constant polynomial with value 1.
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.
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.
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
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.
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 is a finite ordered basis for V and then .
Exercise.
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,
.
.
Exercise.
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
.
.
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.
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.
Let and f(x) be polynomials. If is irreducible and does not divide f(x), then and f(x) are relatively prime.
Exercise.
Any two distinct irreducible monic polynomials are relatively prime.
Exercise.
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).
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
Since divides f(x)g(x), there is a polynomial h(x) such that Thus (7) becomes
So divides g(x).
Let be irreducible monic polynomials. If divides the product then for some .
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.
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
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
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
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
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.
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.
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 .