### Invariant subspaces of linear maps: Diagonalizability

### The Euclidean algorithm

Just as with integers there exists an Euclidean algorithm with which you can find the gcd of two polynomials. Rules 1 and 2 for the gcd of polynomials are sufficient to calculate the gcd, as shown by the following algorithm.

An **algorithm** is a series of steps that need to be executed after one another to obtain a particular prescribed result out of a certain type of data. When presenting an algorithm, we start by specifying with which data the algorithm starts, the **input**, and what the algorithm delivers, the **output**. Next we indicate the steps which the algorithm consists of.

The Euclidean algorithm for polynomials

The following algorithm, called the **Euclidean algorithm for polynomials**, calculates the gcd of two polynomials if at least one of them is not equal to #0#.

*input:* a set #\rv{f,g}# of polynomials with #f\ne0# or #g\ne0#

*output:* #\gcd\left(f,g\right)#

- choose #\rv{r,s}= \rv{f,g}#
- keep replacing #\rv{r,s}# by #\rv{s,t}# until #s=0#, in which #t# is the remainder when dividing #r# by #s#,
- return #r#

A special application of the Euclidean algorithm is the following simple determination of the existence of multiple roots of polynomials:

Double-root criterium Let #f# be a polynomial. Then #\gcd(f,f') = 1# if and only if #f# has no multiple complex roots.

The last criterium provides us with a quick method to check if a square matrix is diagonalizable:

Diagonalizability criterium A square matrix #A# is then and only then diagonalizable if the minimal polynomial #m_A# satisfies#\gcd(m_A,m_A') = 1#, in which #m_A'# is the derivative of #m_A#.

&\text{and}&\\

g(x)&=&x^4+5 x^3+11 x^2+11 x+4\end{array}\] by using the

*Euclidean algorithm*.

By use of the

*Euclidean algorithm*we find

\[\begin{array}{rcl}\gcd(f(x),g(x))&=&{\small \gcd(x^3+4 x^2+6 x+3,x^4+5 x^3+11 x^2+11 x+4)}\\

&=&{\small \gcd(x^4+5 x^3+11 x^2+11 x+4,x^3+4 x^2+6 x+3)}\\

&&\phantom{xx}\color{blue}{\text{highest degree polynomial in first argument}}\\

&=& \gcd(x^3+4 x^2+6 x+3,x^2+2 x+1)\\

&&\phantom{xx}\color{blue}{\text{iteration 1: }x^2+2 x+1\text{ is the remainder}}\\

&&\phantom{xx}\color{blue}{\text{of division of }x^4+5 x^3+11 x^2+11 x+4}\\

&&\phantom{xx}\color{blue}{\text{by }x^3+4 x^2+6 x+3}\\

&=& \gcd(x^2+2 x+1,x+1)\\

&&\phantom{xx}\color{blue}{\text{iteration 2: } x+1\text{ is the remainder}}\\

&&\phantom{xx}\color{blue}{\text{of division of }x^3+4 x^2+6 x+3}\\

&&\phantom{xx}\color{blue}{\text{by }x^2+2 x+1}\\

&=&\gcd(x+1,0)\\

&&\phantom{xx}\color{blue}{\text{iteration 3: } 0 \text{ is the remainder}}\\

&&\phantom{xx}\color{blue}{\text{of division of }x^2+2 x+1}\\

&&\phantom{xx}\color{blue}{\text{by }x+1}\\

&=&x+1\\&&\phantom{xx}\color{blue}{\gcd(p(x),0)=p(x)}\end{array} \]

**Pass Your Math**independent of your university. See pricing and more.

Or visit omptest.org if jou are taking an OMPT exam.