### Invariant subspaces of linear maps: Invariant subspaces

### The extended Euclidean algorithm

*Previously* we indicated that the *greatest common divisor* (gcd) of a pair of two polynomials can be calculated with the *Euclidean algorithm*. Sometimes we are not only interested in the gcd, but also in the possibility of writing a greatest common divisor as a sum of multiples of #f# and #g#.

Let #f# and #g# be polynomials with #f\ne0# and #\deg(f)\ge \deg(g)#. Write #d# for a greatest common divisor of #f# and #g#. Then there are polynomials #a# of degree \(\deg(a)\le\deg(f)-\deg(d)\) and \(b\) of degree \(\deg(b)\le\deg(g)-\deg(d)\), such that

\[d = a\cdot f + b\cdot g\]

The algorithm below describes how to calculate a gcd of #f# and #g# together with the polynomials #a# and #b# as above. The sign #:=# indicates that the components of the vector on the left-hand side get new values that are prescribed by the right-hand side.

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

*output:* a pair #\rv{a,b}# of polynomials with #a\cdot f+b\cdot g = \gcd\left(f,g\right)#

- Choose #Q = \matrix{1&0\\ 0 &1}# and #\matrix{r\\ s}= \matrix{f\\ g}#.
- Keep calculating the quotient #q# of division of #r# by #s# and renew the values \[\begin{array}{rcl} \small Q &:=&\small \matrix{0&1\\1&-q}\, Q\\ \matrix{r\\ s} &:=&\matrix{0&1\\1&-q}\matrix{r\\ s} \end{array}\] until #s=0#.
- Return #\rv{a,b} = \rv{Q_{11},Q_{12}}#.

&\text{and}&\\

g(x)&=&x^4+9 x^3+31 x^2+47 x+26\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+8 x^2+22 x+20,x^4+9 x^3+31 x^2+47 x+26)}\\

&=&{\small \gcd(x^4+9 x^3+31 x^2+47 x+26,x^3+8 x^2+22 x+20)}\\

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

&=& \gcd(x^3+8 x^2+22 x+20,x^2+5 x+6)\\

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

&&\phantom{xx}\color{blue}{\text{of division of }x^4+9 x^3+31 x^2+47 x+26}\\

&&\phantom{xx}\color{blue}{\text{by }x^3+8 x^2+22 x+20}\\

&=& \gcd(x^2+5 x+6,x+2)\\

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

&&\phantom{xx}\color{blue}{\text{of division of }x^3+8 x^2+22 x+20}\\

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

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

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

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

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

&=&x+2\\&&\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.