Polynomials and roots

Andrew Thangaraj

Aug-Nov 2020

Recap

  • Vector space \(V\) over a scalar field \(F\)
    • \(F\): real field \(\mathbb{R}\) or complex field \(\mathbb{C}\) in this course
  • \(m\times n\) matrix A represents a linear map \(T:F^n\to F^m\)
    • dim null \(T\) + dim range \(T\) = dim \(V\)
  • Linear equation: \(Ax=b\)
    • Solution (if it exists): \(u+\) null\((A)\)
  • Four fundamental subspaces of a matrix
    • Column space, row space, null space, left null space
  • Determinant of a square matrix
    • Function with many interesting properties
  • Change of basis for linear map
    • Can result in simpler matrix representation

Polynomials: degree 0,1,2

constant: \(a\), \(a\in F\)

  • Roots: all scalars if \(a=0\); no roots for nonzero

  • \(a=0\): zero polynomial

linear: \(ax+b\), \(a,b\in F\), \(a\ne 0\)

  • Roots: one root \(=-b/a\)

quadratic: \(ax^2+bx+c\), \(a,b,c\in F\), \(a\ne 0\)

  • Roots: \((-b\pm\sqrt{b^2-4ac})/2a\)

    • Two roots (repeated or multiplicity 2 if \(b^2=4ac\))

    • \(F=\mathbb{R}\): two complex roots or two real roots

Polynomials: degree 3,4,5 and higher

cubic: \(ax^3+bx^2+cx+d\), \(a\ne0\)

  • Roots: there is a formula involving cube roots etc

    • Three roots (multiplicities: 1,1,1 or 1,2 or 3)

    • \(F=\mathbb{R}\): at least one real root

quartic: \(ax^4+bx^3+cx^2+dx+e\), \(a\ne0\)

  • Roots: there is a formula involving fourth roots etc

    • Four roots (multiplicities: 1,1,1,1 or 1,1,2 or 2,2 or 1,3 or 4)

quintic and higher: \(p_nx^n+\cdots+p_1x+p_0\)

  • Roots: there is no formula involving radicals (Abel-Ruffini theorem)

modern numerical methods: compute roots for polynomials

  • Try MATLAB, Mathematica, Python numpy/scipy

Polynomials

Polynomials in one variable with coefficients from a field

\(p(x)=p_0+p_1x+p_2x^2+\cdots+p_nx^n,\quad p_i\in F\)

Degree of \(p(x)\): deg \(p(x)\) \(=\) largest \(n\) such that \(p_i\ne 0\)

degree(zero polynomial) \(=-\infty\)

Leading term of \(p(x)\): LT \(p(x)=p_nx^n\), where \(n=\) deg \(p(x)\)

  • Addition, Multiplication (well-known)

    • deg \(a(x)b(x)\ge\) deg \(a(x)\), if \(b(x)\ne 0\)

Division algorithm: \(p(x)\) by \(a(x)\)

  • \(i=0\), \(q(x)=0\), \(p_0(x)=p(x)\)
  • while deg \(p_i(x)\ge\) deg \(a(x)\)
    • \(t_i(x)=\text{LT}(p_i(x))/\text{LT}(a(x))\)
    • \(q(x)=q(x)+t_i(x)\)
    • \(p_{i+1}(x)=p_i(x)-t_i(x)a(x)\)
    • \(i=i+1\)
  • return \(q(x)\), \(r(x)=p_i(x)\)

Division, roots, factors

Given two polynomials \(p(x)\) and \(a(x)\), there exist unique polynomials \(q(x)\) and \(r(x)\) such that \[p(x)=q(x)a(x)+r(x),\] with \(r(x)=0\) or deg \(r(x)<\) deg \(a(x)\).

\(q(x)\): quotient, \(r(x)\): remainder

Proof: Use division algorithm with induction

Roots and factors

  • \(\lambda\in F\) is a root of \(p(x)\) if \(p(\lambda)=0\)

  • If \(p(x)\) divided by \(a(x)\) results in remainder zero,

    • \(p(x)=q(x)a(x)\)

    • \(a(x)\) divides \(p(x)\), denoted \(a(x)\,|\,p(x)\)

    • \(a(x)\) is a factor of \(p(x)\)

Existence of roots and factorization

Fundamental theorem of algebra

Every non-constant polynomial with complex coefficients has a complex root.

Proof: Involves complex analysis.

\(\lambda\) is a root of \(p(x)\) iff \(x-\lambda\) is a factor of \(p(x)\).

degree-1 factor: called linear factor

Proof: Divide \(p(x)\) by \(x-\lambda\).

\(p(x)=p_nx^n+\cdots+p_1x+p_0\), \(p_i\in\mathbb{C}\), \(p_n\ne 0\)

There exists \(n\) complex roots \(\lambda_1,\ldots,\lambda_n\) and \[p(x)=p_n(x-\lambda_1)\cdots(x-\lambda_n)\]

Proof: Use fundamental theorem and degree-1 factor result repeatedly

Polynomials with real coefficients

\(p(x)=p_nx^n+\cdots+p_1x+p_0\), \(p_i\in\mathbb{R}\), \(p_n\ne 0\)

  • Need not have real roots (eg: \(x^2+1\))

  • If \(\lambda\) is a root, \(\bar{\lambda}\) is a root

Factors with real coefficients

  • If \(\lambda\) is a real root, \(x-\lambda\) is a factor

  • If \(\lambda\) is a complex root, \(x^2-(\lambda+\bar{\lambda})x+\lambda\bar{\lambda}\) is a factor

Factorization

\(p(x)=\) (quadratic factors) (linear factors)