02. Rings and Polynomials

2.1 Rings

Ring

A non-empty set $R$ with two binary operations $+$ and $\times$ is a ring if

1. $(R,+,0)$ is an abelian group
2. Multiplication $\times$ is associative
3. Distribution laws hold so for all $a,b,c\in R$ then

$$(a+b)c=ac+bc\text{ and }a(b+c)=ab+ac$$

Note that it DOES NOT NEED a multiplicative identity

Link to original

Commutative Ring

Let $R$ be a ring then
For all $a,b\in R$ then

$$ab=ba$$

Note that any field is a commutative ring

Link to original

Ring Homomorphism

Let $R,S$ be two rings

Map $\varphi :R\to S$ is a ring homomorphism if
For all $r,r^{\prime }\in R$

$$\varphi (r+r^{\prime })=\varphi (r)+\varphi (r^{\prime })\text{ and }\varphi (r{r}^{\prime })=\varphi (r)\varphi (r^{\prime })$$

Link to original

Ring Isomorphism

Bijective Ring Homomorphism

Link to original

Ideal

Non-empty subset $I$ of ring $R$ is an ideal if
For all $s,t\in I$ and $r\in R$ then

$$s-t\in I\text{ and }sr,rs\in I$$

Link to original

Analogy between Ideals and Rings

Ideas are to rings as normal subgroups are to groups
In the sense that the set of additive cosets $R\setminus I$ inherit a ring structure from $R$ if $I$ is an ideal

For $r,r^{\prime }\in R$ then define

$$(r+I)+(r^{\prime }+I):=(r+r^{\prime })+I\text{and}(r+I)(r^{\prime }+I):=r{r}^{\prime }+I$$

Link to original

02 - First Isomorphism Theorem

First Isomorphism Theorem

Kernel $\mathrm{Ker}(\varphi ):={\varphi }^{-1}(0)$ of a ring homomorphism $\varphi :R\to S$ is an ideal

Image $\mathrm{Im}(\varphi )$ is a subring of $S$, and $\varphi$ induces an isomorphisms of rings

$$R\setminus \mathrm{Ker}(\varphi )\cong \mathrm{Im}(\varphi )$$

Proof (Missing)

Exercise (TODO?)

Link to original

---

2.2 Polynomial Rings

03 - Division Algorithm for Polynomials

Division Algorithm for Polynomials

Let $f(x),g(x)$ be two polynomials with $g(x)\ne 0$ then
There exists $q(x),r(x)\in \mathbf{F}[x]$ such that

$$f(x)=q(x)g(x)+r(x)\text{ and }\mathrm{deg}r(x)<\mathrm{deg}g(x)$$

Proof

If $\mathrm{deg}f(x)<\mathrm{deg}g(x)$ then $q(x)=0$ and $r(x)=f(x)$

Assume that $\mathrm{deg}f(x)\ge \mathrm{deg}g(x)$
Let

$$\begin{array}{rl}f(x)& =a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\\ g(x)& =b_k{x}^k+b_{k-1}{x}^{k-1}+\cdots +b_0(b_k\ne 0)\end{array}$$

Then

$$\mathrm{deg}\left(f(x)-\frac{a_n}{b_k}{x}^{n-k}g(x)\right)<n$$

By induction on $\mathrm{deg}f-\mathrm{deg}g$, then there exists $s(x)$ and $t(x)$ such that

$$f(x)-\frac{a_n}{b_k}{x}^{n-k}g(x)=s(x)g(x)+t(x)\text{ and }\mathrm{deg}g(x)>\mathrm{deg}t(x)$$

Hence put $q(x)=\frac{a_n}{b_k}{x}^{n-k}+s(x)$ and $r(x)=t(x)$

Link to original

Factor Theorem corollary

For all $f(x)\in \mathbf{F}[x]$ and $a\in \mathbf{F}$ then

$$f(a)=0⟹(x-a)\mid f(x)$$

Proof

By Division Algorithm for Polynomials then there exists $q(x),r(x)$ such that

$$f(x)=q(x)(x-a)+r(x)$$

As $\mathrm{deg}r(x)<1$ then $r(x)$ is a constant

Evaluating at $a$ then

$$f(a)=0=q(a)(a-a)+r=r$$

Hence $r=0$ so $(x-a)\mid f(x)$

Link to original

Maximum Roots of a Polynomial

Assume $f\ne 0$

If $\mathrm{deg}f\le n$ then $f$ has at most $n$ roots

Link to original

Monic Polynomial

Coefficient of highest power of $x$ of non-zero polynomial $f(x)$ is $1$

Link to original

Bezout's Identity for Polynomials

Let $a,b\in \mathbf{F}[x]$ be two non-zero polynomials

Let $c(x)$ be a monic polynomial of highest degree that divides both $a(x)$ and $b(x)$
So $c(x)=\gcd (a,b)$

Then there exists $s,t\in \mathbf{F}[x]$ such that

$$a(x)s(x)+b(x)t(x)=c(x)$$

Proof

If $c\ne 1$ then divide both $a,b$ by $c$
WLOG assume that $\mathrm{deg}a>\mathrm{deg}b$ and $gcd(a,b)=1$

Doing induction on $\mathrm{deg}(a)+\mathrm{deg}(b)$

By the Division Algorithm for Polynomials then there exist $q,r\in \mathbf{F}[x]$ such that

$$a=qb+r\text{ with }\mathrm{deg}b>\mathrm{deg}r$$

Then $\mathrm{deg}(a)+\mathrm{deg}(b)>\mathrm{deg}(b)+\mathrm{deg}(r)$ and $\gcd (b,r)=1$
If $r=0$ then $b(x)=\lambda$ since $\gcd (a,b)=1$ hence

$$a(x)+b(x)\left(\frac{1}{\lambda }\right)(1-a(x))=1$$

Assume that $r\ne 0$ so by induction hypothesis, there exists $s^{\prime },t^{\prime }\in \mathbf{F}[x]$ such that

$$b{s}^{\prime }+r{t}^{\prime }=1$$

Hence

$$b{s}^{\prime }+(a-qb)t^{\prime }=1\text{ and }a{t}^{\prime }+b(s^{\prime }-q{t}^{\prime })=1$$

So then let $t = t'$ and $s = s' - qt'$

Link to original

---

2.3 Evaluating Polynomials on Matrices

Properties of Polynomials on Matrices

Let $A\in M_n(\mathbf{F})$ and $f(x)=a_k{x}^k+\cdots +a_0\in \mathbf{F}[x]$ then

$$f(A):=a_k{A}_k+\cdots +a_{0}I\in M_n(\mathbf{F})$$

As $A^p{A}^q=A^q{A}^p$ and $\lambda A=A\lambda$ for all $p,q\ge 0$ and $\lambda \in \mathbf{F}$ then
For all $f(x),g(x)\in \mathbf{F}[x]$ then

$$\begin{array}{rl}& f(A)g(A)=g(A)f(A)\\ & Av=\lambda v⟹f(A)v=f(\lambda )v\end{array}$$

Note that these can be deduced by looking at ring homomorphism $E_A:\mathbb{F}[x]\to M_n(\mathbb{F})$

Link to original

Annihilating Polynomial of a Matrix lemma

For all $A\in M_n(\mathbf{F})$ there exists a non-zero polynomial $f(x)\in \mathbf{F}[x]$ such that

$$f(A)=0$$

Proof

Note the dimension $\dim M_n(\mathbf{F})=n\times n$ is finite
Hence

$$\{I,A,A^2,\cdots ,A^k\}\subseteq M_n(\mathbf{F})\text{ is linearly dependent for }k\ge n^2$$

So by definition there exist scalars $a_i\in \mathbf{F}$ (not all $0$) such that

$$a_k{A}^k+\cdots +a_{0}I=0$$

Hence

$$f(x)=a_k{x}^k+\cdots +a_0$$

is an annihilating polynomial

Link to original

---

2.4 Minimal and Characteristic Polynomials

Minimal Polynomial of $A$

Defined as the the monic polynomial $p(x)$ of least degree such that $p(A)=0$
Commonly written as

$$m_A(x)$$

Link to original

04 - Minimal Polynomial divides Annihilating Polynomials

Minimal Polynomial divides Annihilating Polynomials

If $f(A)=0$ then

$$m_A\mid f$$

where $m_A$ is the minimal polynomial

Furthermore, $m_A$ is unique

Proof - Main

By Division Algorithm for Polynomials then
There exist polynomials, $q,r$ with $\mathrm{deg}r<\mathrm{deg}{m}_A$ such that

$$f=q{m}_A+r$$

Evaluating at $A$ gives $f(A)=0=r(A)$ so as $m_A$ is minimal then

$$r=0$$

Hence $m_A$ divides $f$

Proof - Uniqueness

Suppose $m$ is another monic polynomial of minimal degree and $m(A)=0$
So by the theorem above then $m_A\mid m$

As $m$ and $m_A$ have the same degree then

$$m=a{m}_A\text{ for some }a\in \mathbf{F}$$

As both polynomials are monic then $a=1$ so $m=m_A$

Link to original

Characteristic Polynomial of $A$

Defined as

$${\chi }_A(x)=\det (A-xI)$$

Link to original

Alternate form of Characteristic Polynomial of $A$ lemma

$${\chi }_A(x)=(-1{)}^n{x}^n+(-1{)}^{n-1}\mathrm{Tr}(A)x^{n-1}+\cdots +\det A$$

Link to original

Eigenvalue and Eigenvector

Let $A\in M_n(\mathbf{F})$
$\lambda$ is an eigenvalue of $A$ if there exists non-zero $v\in {\mathbf{F}}^n$ such that

$$Av=\lambda v$$

where $v$ is the eigenvector

Link to original

05 - Eigenvalue-Polynomial Characterisation

Eigenvalue-Polynomial Characterisation

Let $A\in M_n(\mathbf{F})$

$$\lambda \text{ is an eigenvalue of }A⟺\lambda \text{ is a root of }{\chi }_A(x)⟺\lambda \text{ is a root of }{m}_A(x)$$

Proof

$$\begin{array}{rl}{\chi }_A(\lambda )=0& ⟺\det (A-\lambda I)=0\\ & ⟺A-\lambda I\text{ is singular}\\ & ⟺\exists v\ne 0:(A-\lambda I)v=0\\ & ⟺\exists v\ne 0:Av=\lambda v\\ & ⟹m_A(\lambda v)=m_A(A)v=0v=0\\ & ⟹m_A(\lambda )=0(\text{as }v\ne 0)\end{array}$$

For the converse, assume $\lambda$ is a root of $m_A$ so

$$m_A(x)=g(x)(x-\lambda )\text{ for some }g$$

By minimality of $m_A$ then $g(A)\ne 0$
Hence there exists $w\in {\mathbf{F}}^n$ such that $g(A)w\ne 0$ so

$$(A-\lambda I)(g(A)w)=m_A(A)w=0$$

So $v$ is a $\lambda -$eigenvector for $A$

Link to original

Polynomials are similar under similar matrices

For $A,C\in M_n(\mathbf{F})$ similar so there exists $P\in M_n(\mathbf{F})$ such that $C=P^{-1}AP$
Then for any polynomial $f(X):=a_k{X}_k+\cdots +a_{0}I\in M_n(\mathbf{F})$

$$f(C)=f(P^{-1}AP)=P^{-1}f(A)P$$

Proof $k\ge 0$ then

For

$$C^k=(P^{-1}AP{)}^k=\underset{k\text{ times}}{\underbrace{(P^{-1}AP)(P^{-1}AP)\cdots (P^{-1}AP)}}=P^{-1}{A}^{k}P$$

as $P{P}^{-1}=I$ when looking at the middle terms

So

$$\begin{array}{rl}f(C)& =a_k{C}^k+\cdots +a_{0}I\\ & =a_k{P}^{-1}{A}^{k}P+\cdots +a_0{P}^{-1}IP\\ & =P^{-1}(a_k{A}^k+\cdots +a_{0}I)P\\ & =P^{-1}f(A)P\end{array}$$

Link to original

Minimal Polynomial is invariant for similar matrices

Let $C,P,A$ be $(n\times n)-$matrices such that $C=P^{-1}AP$ so ($C$ is similar to $A$) then

$$m_C(x)=m_A(x)$$

Proof

As we know polynomials are similar applied to similar matrices then

$$f(C)=f(P^{-1}AP)=P^{-1}f(A)P$$

for all polynomials $f$

Hence

$$0=m_C(C)=P^{-1}{m}_C(A)P\text{ and so }{m}_C(A)=0$$

As $m_A\mid m_C$ and similarly $m_C\mid m_A$ then $m_C=m_A$ as both are monic

Link to original

Characteristic Polynomial is invariant under similar matrices

Let $C,P,A$ be $(n\times n)-$matrices such that $C=P^{-1}AP$ so ($C$ is similar to $A$) then

$${\chi }_C(x)={\chi }_A(x)$$

Proof

$$\begin{array}{rl}{\chi }_C(x)& =\det (C-xI)\\ & =\det (P^{-1}AP-xI)\\ & =\det (P^{-1}AP-P^{-1}\cdot xI\cdot P)\\ & =\det (P^{-1}(A-xI)P)\\ & =\det (P^{-1})\cdot \det (A-xI)\cdot \det P\\ & =\det (A-xI)\text{ as }\det P\cdot \det P^{-1}=1\\ & ={\chi }_A(x)\end{array}$$

Link to original

Minimal Polynomial of $T$ Let $V$ be a finite dimensional vector space Let $T:V\to V$ be a linear transformation

Minimal polynomial of $T$ is defined as

$$m_T(x)=m_A(x)$$

where $A={}_{\mathcal{B}}[T{]}_{\mathcal{B}}$ for some basis $\mathcal{B}$ of $V$

As we have showed previously that $m_A(x)=m_{P^{-1}AP}(x)$ then $m_T(x)$ is independent of choice basis

Link to original

Transclude of 08---Polynomials-on-Linear-Maps#^c29dbb

Appendix: Algebraically Closed Fields

Algebraically Closed field

Let $\mathbf{F}$ be a field then

$\mathbf{F}$ is algebraically closed if every non-constant polynomial in $\mathbf{F}[x]$ has a root in $\mathbf{F}$

Link to original

06 - Fundamental Theorem of Algebra

Fundamental Theorem of Calculus

The field of complex numbers $\mathbb{C}$ is algebraically closed

Link to original

Algebraic Closure of $\mathbf{F}$

Let $\overline{\mathbf{F}}$ be a algebraically closed field containing $\mathbf{F}$ such that
There does not exist a smaller algebraically closed field $L$ with

$$\overline{\mathbf{F}}\subseteq L\subseteq \mathbf{F}$$

Then $\overline{F}$ is called the algebraic closure of $\mathbf{F}$

Link to original

07 - Existence of an Algebraic Closure

Existence of an Algebraic Closure

Every field $\mathbf{F}$ has an algebraic closure $\overline{\mathbf{F}}$

Link to original