12.10 Polynomial

Recall: The arithmetic of \(\mathbb{F}[x]:p\left(x\right)+q\left(x\right);\lambda p\left(x\right);p\left(x\right)q\left(x\right)\)

Polynomial Concepts

Lemma

Given \(p(x)\) and \(d(x)\) with degree \(d(x)\leq \deg p(x)\), \(\exists f(x)\) such that \(p(x)-q(x)d(x)=0\) or \(\deg(p(x)-q(x)d(x))<\deg (p(x))\)

Proof

\(p(x)=a_{m}x^{m}+\sum_{i=0}^{m-1}a_{i}x_{i},d\left(x\right)=b_{n}x^{n}+\sum_{j=0}^{n-1}b_{j}x^{j}\) with \(m\geq n\)

Take \(q(x)=\frac{a_m}{b_n}x^{m-n}\) (kill \(b_nx^n\)). Then \(p(x)-q(x)d(x)=0\) or \(\deg (p(x)-q(x)d(x))<\deg p(x)\)

Remark

Lemma does not hold for \(\Z[x]\)

For example, \(p(x)=x^2+1,d(x)=2x,\nexists q\left(x\right)\) since we can not take \(q(x)=\frac12x\) since we are in \(\Z[x]\)

Theorem

Let \(p(x)\) and \(d(x)\neq 0\) in \(\mathbb{F}[x]\). Then there exists unique \(q(x)\) and \(r(x)\) such that

• \(p(x)=q(x)d(x)+r(x)\)​
• \(r(x)=0\) or \(\deg r(x)<\deg d(x)\)​

Proof

1. Existence

   If \(p(x)=0\), take \(q(x)=r(x)=0\)

   if \(p(x)\neq 0\) and \(\deg p(x)<\deg d(x)\), then we can take \(q(x)=0,r(x)=p(x)\)​

   If \(p(x)\neq 0\) and \(\deg p(x)\geq \deg d(x)\), then by lemma \(\exists q_1\left(x\right)\)

   such that \(p(x)-q_1(x)d(x)=0\) or \(\deg(p(x)-q_1(x)d(x))<\deg p(x)\) where \(p(x)-q_1(x)d(x)=r_1(x)\)

   Thus if \(\deg r_1(x)<\deg d(x)\), then take \(q(x)=q_1(x)\) and \(r(x)=r_1(x)\)​

   If not, that is \(\deg (p(x)-q_1(x)d(x))\geq \deg d(x)\), then by lemma again \(\exists t(x)\)

   such that \(p(x)-q_1(x)d(x)-t(x)d(x)=0\) or \(\deg(p(x)-q_1(x)d(x)-t(x)d(x))<\deg p\left(x\right)\) where \(p(x)-\left(q_1(x\right)+t\left(x)\right)d(x)=r_2(x)\)

   If \(\deg r_2(x)<\deg d(x)\), we are done.

   If not, we iterate this process after finite steps we end up with the required \(q(x)\) and \(r(x)\)​

2. Unicity

   Assume \(p(x)=q_1(x)d(x)+r_1(x)=q_2(x)d(x)+r_2(x)\Rightarrow (q_1(x)-q_2(x))d(x)=r_2(x)-r_1(x)\)​

   If \((q_1(x)-q_2(x))d(x)\neq0\Rightarrow\deg\left((q_1(x)-q_2(x))d(x)\right)\geq\deg d\left(x\right)\)​

   But \(\deg (r_2(x)-r_1(x))<\deg d(x)\) or \(r_2(x)-r_1(x)=0\)​

   Hence \(q_1(x)-q_2(x)=0\) and \(r_2(x)-r_1(x)=0\)​

Definition

Let \(d(x)\neq 0\) on \(\mathbb{F}[x]\). Given \(p(x)\) in \(\mathbb{F}[x]\), we say that \(d(x)\) divides \(p(x)\) if \(\exists q(x)\) such that \(p(x)=q(x)d(x)\)

In this case we say that \(p(x)\) is a multiple of \(d(x)\) and that \(p(x)\) is divisible by \(d(x)\)

\(q(x)\) is called the quotient of \(p(x)\) divided by \(d(x)\) and we write\(q(x)=p(x)/d(x)\)

Remark

\(d(x)\) divides \(p(x)\) if the \(r(x)\) from theorem is zero

Definition

Given \(p(x)\) in \(\mathbb{F}[x]\), a root of \(p(x)\) is \(\alpha \in \mathbb{F}\) such that \(p(\alpha)=0\)

Corollary

\(\alpha\) is a root of \(p(x)\) iff \((x-\alpha)\) divides \(p(x)\)

Proof

Let \(p(x)=q(x)(x-\alpha)+r(x)\) where \(x-\alpha =d(x)\), then \(r(x)=0\) or \(\deg r(x)<1\). Hence \(r(x)=r\in\mathbb{F}\)​

\(\Rightarrow\)) Since \(\alpha\) is a root, then \(p(\alpha)=0=q(\alpha)(\alpha-\alpha)+r(\alpha)=r\)

Thus \(x-\alpha\) divides \(p(x)\)

\(\Leftarrow\)) If \((x-\alpha)\) divides \(p(x)\), then \(p(x)=q(x)(x-\alpha)\), then \(p(\alpha)=q(\alpha)(\alpha-\alpha)=0\)

Thus \(\alpha\) is a root of \(p(x)\)

Corollary

A polynomial of degree \(n\) in \(\mathbb{F}[x]\) has at most \(n\) roots

Proof

Use induction on \(n\)

If \(n=1\), then \(x-c=0\) has a root \(x=c\) yes!

Assume a polynomial of degree \(n\) has at most \(n\) roots, then let \(p(x)\) be of degree \(n+1\).

If \(\alpha\) is a root of \(p(x)\), then \(p(x)=q(x)(x-\alpha)\) with \(\deg q(x)=n\)

Since \(q(x)\) at most \(n\) roots, rhus \(p(x)\) at most \(n+1\) roots

Definition

Let \(p(x)\in \mathbb{F}[x]\) . A root \(\alpha\) of \(p(x)\) is of multiplicity \(m\) if \((x-\alpha)^m\) divides \(p(x)\) and \((x-\alpha)^{m+1}\) does not divide \(p(x)\)

Remark

\(p(x)=q_1(x)(x-\alpha)=q_2(x)(x-\alpha)^2=\ldots=q_{m}\left(x\right)\left(x-\alpha\right)^{m}\) with \(q_m(x)\neq 0\)

Polynomial ideals

Definition

A ideal of \(\mathbb{F}[x]\) is a subspace \(U\) of \(\mathbb{F}[x]\) such that \(p(x)q(x)\in U\) \(\forall q(x)\in \mathbb{F}[x]\) if \(p(x)\in U\)

Example

1. \(U=\{p(x):x^2+1\text{ divides }p(x)\}\hookrightarrow\mathbb{F}[x]\)​

   \(p_1(x)+p_2(x)=q_1(x)(x^2+1)+q_2(x)(x^2+1)=(q_1(x)+q_2(x))(x^2+1)\)​

   \(\lambda p(x)=\lambda(q(x)(x^2+1))=(\lambda q(x))(x^2+1)\)

   Thus \(U\) is a subspace

   \(p(x)q(x)=(q_1(x)(x^2+1))q(x)=(q_1(x)q(x))(x^2+1)\in U\)​

   Thus it is a ideal

2. \(U=\{p(x):p_1(x)(x^3+1)+p_2(x)(x^2+1)\}\hookrightarrow\mathbb{F}[x]\)

   \(p(x)q(x)=(p_1(x)(x^3+1)+p_2(x)(x^2+1))q(x)=\left(p_1(x\right)q\left(x)\right)(x^3+1)+\left(p_2(x\right)q\left(x)\right)(x^2+1)\in U\)

   How big is \(U\)? Is there a \(p(x)\in \mathbb{F}[x]-U\)?

   No!!!

   Let \(x^3+1=(x^2+1)q(x)+r(x)=(x^2+1)x+1-x\), then \((x^3+1)-x(x^2+1)=1-x\in U\)

   Let \(x^2+1=(1-x)\bar{q}(x)+\bar{r}(x)=(1-x)\left(-x\right)+x+1\), then \((x^2+1)+x(1-x)=x+1\in U\) since definition of ideal

   Then \(1-x+1+x\in U\Rightarrow2\in U\Rightarrow1\in U\Rightarrow\mathbb{F}[x]\subseteq U\Rightarrow\mathbb{F}[x]=U\)​

Notation

Given \(a(x)\in \mathbb{F}[x]\), the ideal \(U_{a(x)}=\left\lbrace p\left(x\right):a\left(x\right)\text{ divides }p(x)\right\rbrace\) is called the principal ideal generated by \(a(x)\)

Theorem

Let \(U\) be a non zero ideal of \(\mathbb{F}[x]\). Then there exists unique monic (leading coefficients is 1) \(a(x)\) such that \(U\) is the principal ideal generated by \(a(x)\)

Proof

Let \(a(x)\) be a monic polynomial in \(U\) of the smallest possible degree.

Now given \(p(x)\in U\), \(p(x)=q(x)a(x)+r(x)\) with \(r(x)=0\) or \(\deg r(x)< \deg a(x)\)

Since \(r(x)=p(x)-q(x)a(x)\) (\(a(x)\in U,p(x)\in U\)), thus \(r(x)\in U\)

Since \(\deg a(x)\) is the smallest, \(r(x)=0\). Hence \(U=\left\lbrace p\left(x\right):p\left(x\right)=q\left(x\right)a\left(x\right)\right\rbrace\)

Finally, if \(a_1(x)\) and \(a_2(x)\) are monic generators of \(U\), then \(a_1(x)=q_1(x)a_2(x)\) and \(a_2(x)=q_2(x)a_1(x)\)

Then \(a_1(x)=q_1(x)q_2(x)a_1(x)\Rightarrow deg(q_1(x)q_2(x))=0\Rightarrow q_1(x)=1=q_2(x)\)

Example

\(U=\{q_1(x)(x^2+1)+q_2(x)(x^3-ix^2)\}\hookrightarrow\mathbb{C}[x]\)

Notice that \(x^3-ix^2=(x-i)x^2\) and \(x^2+1=(x+i)(x-i)\)

Then \(x-i=(x-i)(x^2+1)+(-1)(x^3-ix^2)\Rightarrow x-i\in U\)

Hence \(U=\langle x-i\rangle_{\mathbb{F}[x]}\)

Polynomials, matrices and operators

Let \(p(X)=a_0+a_1(x)+...+a_nx^n\). Given \(\begin{cases}A\in M_{n\times n}\left(\mathbb{F}\right)\rightsquigarrow p\left(A\right)=a_0I+a_1A+\cdots+a_{n}A^{n}\in M_{n\times n}\left(\mathbb{F}\right)\\T\in\text{End}(V)\rightsquigarrow p\left(T\right)=a_0I+a_1T+\cdots+a_{n}T^{n}\in\text{End}(V)\end{cases}\)​

Example

1. \(A=\begin{pmatrix}0&1\\1&0\end{pmatrix}\) and \(p(X)=2-x+x^2-3x^3\)

   \(A^2=\begin{pmatrix}1 & 0\\ 0 & 1\end{pmatrix},A^3=A\Rightarrow p\left(A\right)=2I-A+I-3A=3I-4A=\begin{pmatrix}3 & -4\\ -4 & 3\end{pmatrix}\)​

2. \(A=\begin{pmatrix}0 & 1 & 1\\ 0 & 0 & 1\\ 0 & 0 & 0\end{pmatrix},A^2=\begin{pmatrix}0 & 0 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\end{pmatrix},A^3=\begin{pmatrix}0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{pmatrix},\ldots,A^{k}=0,\forall k\geq3\)​

   If \(p(x)=a_0+a_1x+...+a_nx^n\), then \(p(A)=a_0I+a_1A+a_2A^2\)​

   Then \(p(A)=\begin{pmatrix}a_0 & a_1 & a_1+a_2\\ 0 & a_0 & a_1\\ 0 & 0 & a_0\end{pmatrix}\)​

Example

1. \(T:\R^2\rightarrow \R^2,(x,y)\mapsto (x,0)\) \(T^2=T\) since \(T\circ T =T\)​

   Thus we can inducts \(T^k=T\)​

   Hence If \(p(x)=a_0+a_1x+...+a_nx^n\), then \(p\left(T\right)=a_0I+\left(a_1+\cdots+a_{n}\right)T\)

2. \(T:\mathbb{R}^2\rightarrow\mathbb{R}^2,(x,y)\mapsto(-y,x)\) \(T^2=-I,T^3=-T,T^4=I\)​

   Thus we can inducts \(T^k=T\)

   Hence If \(p(x)=a_0+a_1x+...+a_nx^n\), then \(p\left(T\right)=aI+bT\)

Remark

If \(A=\begin{pmatrix}\lambda_1 & \cdots & 0\\ \vdots & \ddots & \vdots\\ 0 & \cdots & \lambda_{n}\end{pmatrix}\), then \(p(A)=\begin{pmatrix}p\left(\lambda_1\right) & \cdots & 0\\ \vdots & \ddots & \vdots\\ 0 & \cdots & p\left(\lambda_{n}\right)\end{pmatrix}\)​

‍