# Why does polynomial factorization generalize to matrices

I'm reading about linear algebra and I came across with the following theorem where I have a problem convincing myself:

Theorem 2.1 $\,$ Every linear operator on a finite-dimensional complex vector space has an eigenvalue.

Proof:

To show that $T$ (our linear operator on $V$) has an eigenvalue, fix any nonzero vector $v \in V$. The vectors $v, Tv, T^2v,..., T^nv$ cannot be linearly independent, because $V$ has dimension $n$ and we have $n + 1$ vectors. Thus there exist complex numbers $a_0,...,a_n$, not all $0$, such that

$$a_0v + a_1Tv + ··· + a_nT^nv = 0.$$ Make the $a$’s the coefficients of a polynomial, which can be written in factored form as $$a_0 + a_1z + ··· + a_nz^n = c(z − r_1)\cdots(z − r_m),$$ where $c$ is a non-zero complex number, each $r_j$ is complex, and the equation holds for all complex $z$. We then have

$${\color{red}{ 0=(a_0I + a_1T + ··· + a_nT^n)v= c(T − r_1I)\cdots(T − r_mI)v}},$$ which means that $T − r_j$ I is not injective for at least one $j$. In other words, $T$ has an eigenvalue.$\;\blacksquare$

I'm having trouble with the factorized form of the matrix polynomial (in red). I understood that the factorization holds for a polynomial by the fundamental theorem of algebra but why does this also hold for matrices?

In other words, why is the the part I highlighted true? Does such an factorization always exist?

Could I have some help to see this? Thank you =)

P.S. here is my reference (page 3).

UPDATE:

Someone else also has asked the same question before it seems.

• Take the vectors $[1,0,\cdots]$, $[1,0,\cdots]$, $\cdots$ , $[1,0,\cdots]$. They will be $n+1$ vectors, none zero, generated for example by the matrix with a lone 1 up in the left corner, but not linearly independent. – mathreadler Aug 4 '16 at 9:47
• Would you like to do some work and type the quote instead of using an image? It will make the question better, and ensure it's always accessible to users – Yuriy S Aug 4 '16 at 13:32
• Roger that. I will edit my post :) – jjepsuomi Aug 4 '16 at 13:44
• See also math.stackexchange.com/a/654471/589. – lhf Aug 4 '16 at 14:08
• @You'reInMyEye edited the text =) – jjepsuomi Aug 4 '16 at 19:12

What matters is that the matrices involved, namely powers of $T$, commute with each other. With that in mind, the legitimacy of the factorisation should be clear: just think about expanding the brackets using the associative and distributive properties of matrix multiplication. A more sophisticated argument can be obtained by viewing the equation in terms of an action of the polynomial ring $\mathbb{C}[x]$, in which factorisation is more familiar.

• One more question is buzzing my mind. So the factorization always exists? If we have a matrix polynomial then we can always find such values $r_1, ..., r_m$ and $c$ that the factorization of the matrix polynomial is possible? – jjepsuomi Aug 4 '16 at 12:12
• Yep. This works because $\mathbb{C}$ is algebraically closed (i.e. fundamental theorem of algebra). – Mr. Chip Aug 4 '16 at 12:24
• Thank you. One last question :) Does the roots of the matrix polynomial always have to be of the form $r_i I$? Can there be arbitrary (meaning not of the form $r_i I$) root-matrices for the matrix polynomial? If not, why? – jjepsuomi Aug 4 '16 at 12:46
• Maybe the easiest case to consider would be $T^2 = I$. Make it easy and let $T$ be 2x2. You'll find that $T$ doesn't have to be a multiple of $I$. – Mr. Chip Aug 4 '16 at 12:59
• @jjepsuomi Actually what matters is that constants $\,cI\,$ commute with $\,T.\,$ See my answer where I explain this from a general perspective, which shows why polynomial factorizations, the Binomial Theorem, etc persist to be true when "evaluated" at $\,x = T.\$ – Bill Dubuque Aug 4 '16 at 15:56

This follows simply from the universal property of polynomial rings, which implies that any polynomial equation in $\, R[x]\,$ will persist when "evaluated" into any ring where the images of the constants commute with the image of $x$ (which is precisely the condition necessary for such a map to be a ring homomorphism).

Indeed, a polynomial ring is designed precisely to have this property, i.e. it is the most general ("free") ring that contains $\,R\,$ and a new element $\,x\,$ that commutes with all elements of $R$. Because we use only the ring axioms and constant commutativity when proving polynomial equations, such proofs persist in said ring images where constant commutativity persists.

This is true in your example because constants $\,r\,$ map to a constant matrices $\,rI\,$ which commute with $\,T =$ image of $x$.

This implies that all familiar polynomial equations (e.g. Binomial Theorem and difference of squares factorization) persist to be true when evaluated into any ring where the constants commute with the indeterminates. Ditto for many other ubiquitous polynomial equations, e.g. cyclotomic polynomial factorizations, polynomial Bezout identities for the gcd, resultants, etc. Therefore such equations represent universal laws (identities), modulo said constant commutativity.

These ideas are brought to the fore when one studies $(R-)$algebras, which are rings containing a central image of $R$, i.e. where the images of elements of $R$ commute with everything. Any polynomial equation that holds true in $\,R[x_1,\ldots,x_n]\,$ will persist to be true when evaluated into any $R$-algebra, i.e. it is an identity (law) of $R$ algebras. In fact it is easy to show that an equation holds true in $\,R[x_1,\ldots,x_n]\,$ iff it is true in all all $R$ algebras. Hence the equations that hold true $\,R[x_1,\ldots,x_n]\,$ are precisely the identities (universal laws) of $R$-algebras.

• Thank you very much, appreciate it! – jjepsuomi Aug 4 '16 at 18:55

An explanation is that the polynomials in a given matrix $A$ constitute a commutative subring $\mathbb{K}[A]$ of the ring of matrices, and can be considered as an image of the ring of polynomials $\mathbb{K}[X]$ , thus you can consider that in this subring, you work exactly as in $\mathbb{K}[X]$.

In fact, $\mathbb{K}[A]$ is isomorphic to the quotient ring $\mathbb{K}[X]/(m(X))$ where $m(X)$ is a minimal polynomial for matrix $A$.

Edit : let us take an example (the matrix has been borrowed from (https://www.youtube.com/watch?v=FecegfvA-Pg)).

Consider matrix $A=\begin{pmatrix}0&-2&-2\\1&3&1\\0&0&2\end{pmatrix}$ whose characteristic polynomial is $$c(X)=X^3+X^2+1$$

Using Cayley-Hamilton theorem, one has $$c(A)=A^3+A^2+I=0$$ (think to replace 1 by $I$!), otherwise said, each time you meet $A^3$ in a computation, you can replace it by $-A^2-I$. These leads to a systematic degree lowering: any polynomial of any degree in $A$ can be brought to a (unique) form as an (at most) 2nd degree polynomial, for example $A^5+A=A^3A^2+A=(-A^2-I)A+A=-A^3=-A^2-I$. But in fact, in this case there is lower degree combination of powers of $A$ that is annihilated, more precisely $$m(A)=A^2-3A+2I=0 \ \ \ (1)$$ ($m(X)=X^2-3X+2$ is called the/a minimal polynomial). Thus in fact, the degree lowering makes that any polynomial $P(A)$ in $A$ can be written a first degree polynomial $\pi(A)$. This transformation can be considered as a linear mapping, i.e., an homomorphism between linear spaces (note that I have changed $A$ into $X$).

$$\varphi: \ \ \begin{cases}P(X) \longrightarrow \pi(X)\\ \mathbb{K}[X] \longrightarrow \mathbb{K}_1[X]\end{cases}$$

(denoting by $\mathbb{K}_1[X]$ the vector space of polynomials of degree at most 1)

Note that the kernel of this mapping is the set $M$ of polynomials multiples of $m(x)$. You may know that taking classes modulo the kernel leads to an isomorphism (but may be not yet). The definition of $M$ sounds like a principal ideal. This is not astonishing because linear mapping $\varphi$ can also - fruitfully - be considered as a ring mapping (homomorphism between rings) with the following multiplication rule (because of relationship (1)): $$(aX+b)(a'X+b')=aa'(3X-2I)+...=(3aa'+ab'+a'b)X+(bb'-2aa')$$

The quotient space, like for vector spaces, would yield an isomorphism.

Remark: the unifying structure for vector spaces that are also rings with a certain compatibility relationship betwen the rules is that of an algebra structure.

• Thank you for your help. Appreciate it =) – jjepsuomi Aug 4 '16 at 10:00
• Could you elaborate little bit more your answer? :) Thank you, just to make the subject a bit more tangible for me ;) – jjepsuomi Aug 4 '16 at 12:18
• I will add an Edit to my answer. – Jean Marie Aug 4 '16 at 12:50
• Thank you =). Other question: could the the factorization be proven/shown without using algebraic structures or notions (rings, isomorphism etc.)? Could you prove your point by simply using linear algebra? Can such a proof be found from some reference? – jjepsuomi Aug 4 '16 at 12:59
• Edit done. Is your "other question" connected to the central issue that $(fog)v=0$ implies that either $f$ or $g$ is such that either $f(v)=0$ or $g(v)=0$ ? – Jean Marie Aug 4 '16 at 14:01