Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Polynomials in linear algebra

by , PhD

This lecture presents some facts about polynomials that are often used in linear algebra.

Table of Contents

Fields

In what follows we are going to use the concept of a field, which was previously defined in the lecture on vector spaces.

All that we need to know is that a field is a set equipped with two operations (addition and multiplication) that satisfy a number of properties. The latter are the usual properties satisfied by the addition and multiplication of real numbers, which we studied when we were in school. Importantly, these properties are also satisfied by the addition and multiplication of complex numbers. Thus, both the set of real numbers R and the set of complex numbers $U{2102} $, equipped with their usual operations, are fields.

Integer powers

When we deal with a field F, we can take non-negative integer powers of the elements of F by repeatedly multiplying them: if $m$ is a positive integer and $zin F$, then[eq1]

We adopt the convention that[eq2]where 1 is the multiplicative identity of the field.

Definition of polynomial

We can now define polynomials.

Definition Let F be a field. Let $m$ be a non-negative integer. A function $p:F
ightarrow F$ is called a polynomial of degree $m$ if and only if, for any $zin F$,[eq3]where [eq4] belong to F and $a_{m}
eq 0$.

The elements [eq4] are called coefficients of the polynomial.

In the above definition $m$ is assumed to be a non-negative integer. If [eq6] (i.e., the coefficients are all equal to zero), then the degree of p is conventionally set to $-infty $.

Example Let us consider the field of real numbers R. The function [eq7] that satisfies, for any $zin U{211d} $,[eq8]is a polynomial of degree $2$.

Example The function [eq9] that satisfies, for any $zin U{211d} $,[eq10]is a polynomial of degree 0.

Root of a polynomial

We now introduce the concept of a root.

Definition Let F be a field and $p:F
ightarrow F$ a polynomial of degree $mgeq 1$. We say that $lambda in F$ is a root of p if and only if[eq11]

Much of the theory of polynomials is concerned with studying roots and their properties.

Example Consider the polynomial [eq12] defined by[eq13]Then, $lambda =1$ is a root of the polynomial because[eq14]

Roots and factors

If we know a root of a polynomial p, then we can use it to factor p into simpler polynomials.

Proposition Let F be a field and $p:F
ightarrow F$ a polynomial of degree $mgeq 1$. Then, $lambda  $is a root of p if and only if, for any $zin F$,[eq15]where $q:F
ightarrow F$ is a polynomial of degree $m-1$.

Proof

Let us prove the "if" part, starting from the hypothesis that $lambda $ is a root of p. Note that, for any integer $kgeq 1$ and $z,lambda in F$, we have[eq16]Define[eq17]Note that $z^{k-1}$ has coefficient $lambda ^{0}=1$. Thus, [eq18] is a polynomial of degree $k-1$ and[eq19]Since p is of degree $m$, we have[eq20]Since $lambda $ is a root of p, we have[eq21]By subtracting the latter equation from the former, we obtain[eq22]The polynomial [eq23]is of degree $m-1$ because the highest power of $z$ it contains is $a_{m}z^{m-1}$ (with $a_{m}
eq 0$ by the assumption that p is of degree $m$). Let us now prove the "only if" part, starting from the hypothesis that [eq24]By setting $z=lambda $, we obtain[eq25]As a consequence, $lambda $ is a root of $pleft( z
ight) $.

Upper bound on the number of roots

Thanks to the previous factorization theorem, we can put an upper bound on the number of roots of a polynomial.

Proposition Let F be a field and $p:F
ightarrow F$ a polynomial of degree $mgeq 1$. Then, p has at most $m$ distinct roots.

Proof

The proof is by induction. For $m=1$, we have[eq26]with $a_{1}
eq 0$. Therefore, p has exactly one root [eq27]. Thus, the claim is true for $m=1$. Now, let us assume that it is true for a polynomial of degree $m-1$. We need to show that the claim is true for a polynomial p of degree $m$. If p has at least one root $lambda $, then[eq28]where $qleft( z
ight) $ is a polynomial of degree $m-1$. By the previous equation a root of p different from $lambda $ must necessarily be a root of $q$. But $q$ has at most $m-1$ distinct roots by the induction hypothesis. Therefore, p has at most $m$ distinct roots.

Polynomial of zero degree

The previous proposition does not cover the case $m=0$, in which[eq29]and $a_{0}
eq 0$. In this case, there are no roots.

Zero polynomial

No polynomial of positive degree can be identically equal to zero, provided that its underlying field has a sufficient number of members.

Proposition Let F be a field and $p:F
ightarrow F$ the polynomial defined by[eq30]If F has at least $m+1$ members and [eq31] for any $zin F$, then [eq32]

Proof

The proof is by contradiction. Suppose that at least one of the coefficients is different from zero. Then, the degree of p is between 0 and $m$. As a consequence, p can have at most $m$ distinct roots. But this contradicts the fact that the polynomial p has at least $m+1$ distinct roots because $F $ has at least $m+1$ members and [eq33] for any $zin F$. Therefore, all the coefficients of the polynomial must be equal to zero.

The requirement that the field F has at least $m+1$ members is always satisfied for the field R of real numbers and the field $U{2102} $ of complex numbers, which have infinitely many members.

Linear independence of powers

The previous proposition can be seen as a result stating that the polynomials [eq34] are linearly independent: the only way to linearly combine them so as to get the zero polynomial as a result is to set all their coefficients equal to zero.

Spaces of polynomials

If you are wondering why we are speaking about polynomials using "vector space language" and, in particular, the concept of linear independence, you might want to revise the lectures on vector spaces and coordinate vectors, where we have discussed the fact that the set of all polynomials of degree $m$ is a vector space.

Since any polynomial of degree $m$ has the form[eq35]the space of all polynomials of degree $m$ is spanned by the polynomials [eq36]. We have just demonstrated that the latter are linearly independent. Therefore, they are a basis for the space being discussed.

Uniqueness of degree

Since the representation in terms of a basis is unique, there is no other way to linearly combine the basis so as to obtain $pleft( z
ight) $. In other words, there is only one way to obtain a given polynomial by taking linear combinations of the functions $z^{k}$. As a consequence, the degree of a polynomial is unique.

Fundamental theorem of algebra

The next proposition is known as the Fundamental Theorem of Algebra.

Proposition Let [eq37] be a polynomial of degree $mgeq 1$. Then, p has at least one root.

Proof

This is a deep result in complex analysis, which we leave without a proof.

In other words, when we are working with the field of complex numbers, then we are guaranteed to find a root of a given polynomial.

Factorization of complex polynomials

By combining the Fundamental theorem of algebra and the factorization theorem, we obtain the following important proposition.

Proposition Let [eq38] be a polynomial of degree $mgeq 1$. Then, there exist complex numbers [eq39] such that[eq40]for any $zin U{2102} $. The numbers [eq41] are unique up to a permutation of [eq42].

Proof

We first demonstrate the existence of [eq43]. By the Fundamental Theorem of Algebra (FTA), p has at least one root. Denote it by $lambda _{1}$. Then, we can factorize p as[eq44]where $q$ is a polynomial of degree $m-1$. If $m-1=0$, then [eq45] and we are done. If $m-1geq 1$, the FTA guarantees the existence of a root $lambda _{2}$ of $q$. So we have[eq46]where $r$ is a polynomial of degree $m-2$. If $m-2=0$, then [eq47] and we are done. Otherwise, we proceed by factoring out other terms, until we get the desired result. We now prove uniqueness. By carrying out the multiplication of the factors of p, we get[eq48]By the uniqueness of the representation of polynomials of degree $m$ in terms of the basis [eq49], we have that $c$ is unique. Suppose there is another factorization[eq50]We can write[eq51]where we have divided both sides by $c$ (which is different from zero because p is of degree $m$). Note that the latter equation holds for any $z $. When we set $z=lambda _{1}$ on the right-hand side, one of the factors on the left-hand side must be equal to zero. We can suppose without loss of generality that it is $z-mu _{1}$ (if it is not, we can re-order the roots $mu _{j}$). Thus, [eq52]. We then divide everything by [eq53] and obtain[eq54]By the same line of reasoning as earlier, we obtain [eq55], possibly after re-ordering the roots $mu _{j}$. We proceed in this manner until we have proved that [eq56] for $j=1,ldots ,m$.

Factorization into linear factors

A polynomial of degree 1 such as[eq57]is often called a linear factor.

Thus, the previous proposition shows that any complex polynomial can be written as a product of linear factors.

Moreover, the linear factors expose all the roots $lambda _{j}$ of the polynomial.

How to cite

Please cite as:

Taboga, Marco (2017). "Polynomials in linear algebra", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/polynomials-in-linear-algebra.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.