Fundamental Theorem of Algebra

Definition

Every equation of a univariate polynomial of degree $n$ with complex coefficients ($n$ at least $1$) has at least one root in the complex number field.

It follows that an equation of a degree-$n$ polynomial with complex coefficients has exactly $n$ roots in the complex number field, with multiple roots counted according to their multiplicities.

Sometimes this theorem is also stated as follows:

Every nonzero univariate polynomial of degree $n$ with complex coefficients has exactly $n$ complex roots.

Proofs of the Fundamental Theorem of Algebra generally use complex analysis or abstract algebra, so it is often applied directly as a familiar conclusion.

According to the Fundamental Theorem of Algebra, a polynomial with complex coefficients $f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0$ can always be uniquely factored as:

$$f(x)=a_n{(x-x_1)}^{k_1}{(x-x_2)}^{k_2}\ldots{(x-x_t)}^{k_t}$$

where all roots are complex numbers and $k_1+k_2+\ldots+k_t=n$.

Conjugate Complex Roots Occur in Pairs

The Fundamental Theorem of Algebra studies polynomials with complex coefficients. When studying polynomials with real coefficients, although complex roots can also be factored out, expanding the field of study is inconvenient.

An imaginary root is a non-real root.

Theorem: The conjugate of a root of a polynomial with real coefficients is also a root of that polynomial.

Proof: Take conjugates of both sides of the equation in the Fundamental Theorem of Algebra directly.

If the root itself is real, taking its conjugate leaves it unchanged and has no effect.

If the root is imaginary, its conjugate is also a root of the original polynomial. Thus, the two imaginary roots can be paired.

Theorem: Conjugate imaginary roots of an equation with real coefficients always occur in pairs, and the multiplicities of conjugate imaginary roots are equal.

Proof: Suppose one root is $a+b\mathrm{i}$; then the other root is $a-b\mathrm{i}$. This means that the factorization contains the two terms:

$$(x-a-b\mathrm{i})(x-a+b\mathrm{i})=x^2-2ax+a^2+b^2$$

When the two terms are multiplied together, all coefficients become real. The quadratic polynomial with real coefficients on the right-hand side divides the original polynomial.

Therefore, in the equation from the Fundamental Theorem of Algebra, dividing both sides by this quadratic trinomial still gives an equation of a polynomial with real coefficients. Repeating the operation on the new equation, as the degree decreases, eventually no imaginary roots remain.

Therefore, the multiplicities of each pair of conjugate imaginary roots are equal. QED.

The following are consequences of the theorem on conjugate imaginary roots occurring in pairs:

• A real-coefficient polynomial of odd degree has at least one real root and has an odd total number of real roots.
• A real-coefficient polynomial of even degree may have no real roots and has an even total number of real roots.

The quadratic trinomial $x^2-2ax+a^2+b^2=x^2+px+q$ above is called an irreducible quadratic factor with real coefficients. Irreducible means irreducible over the real numbers.

Theorem: A real-coefficient polynomial is a product of linear factors or irreducible quadratic factors with real coefficients.

Proof:

Whenever a real-coefficient polynomial has a real root $c$, there is a corresponding real-coefficient factor $x-c$; whenever it has a pair of imaginary roots $a\pm b\mathrm{i}$, there is a corresponding real-coefficient factor $x^2-2ax+a^2+b^2$.

Therefore, pairing the imaginary roots in the factorization from the Fundamental Theorem of Algebra proves the result.

According to the theorem on conjugate imaginary roots occurring in pairs, a real-coefficient polynomial $f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0$ can always be uniquely factored as:

$$f(x)=a_n{(x-x_1)}^{k_1}{(x-x_2)}^{k_2}\ldots{(x-x_t)}^{k_t}{(x^2+p_1x+q_1)}^{l_1}{(x^2+p_2x+q_2)}^{l_2}\ldots{(x^2+p_sx+q_s)}^{l_s}$$

where all coefficients are real numbers and $k_1+k_2+\ldots+k_t+2(l_1+l_2+\ldots+l_s)=n$.

Lin's Algorithm

Introduction

How can a real-coefficient polynomial be factored according to the Fundamental Theorem of Algebra? Extending the number field to the complex numbers makes the problem complicated.

If we factor only over the real numbers, we can guarantee only that when the degree is greater than $2$, there is a quadratic trinomial factor with real coefficients.

This is because if the polynomial has imaginary roots, a pair of conjugate imaginary roots can be directly combined. If the polynomial has only real roots, multiplying the linear factors corresponding to any two real roots also gives a quadratic trinomial factor with real coefficients.

After finding a quadratic trinomial factor, solving the real or complex roots of the quadratic is very easy. Thus, there is a computational method that finds one quadratic factor successively to obtain the complex roots of the equation; this method avoids complex-number operations.

In August 1940, August 1943, and July 1947, Lin Shih-E successively published three papers on methods for calculating complex roots of high-degree equations in the MIT-published journal Mathematical Physics¹, improving the method each time.

This method is still used for fast computation in modern computers, and the principle behind polynomial root-finding programs in computer packages (such as MATLAB) is also this algorithm.

Process

To find a quadratic trinomial factor, factor the polynomial as:

$$f(x)=(x^2+p_1x+q_1)g(x)$$

Because it is impossible to find the quadratic trinomial factor at once, following an iterative solution approach, for the initial values we have:

$$f(x)=(x^2+px+q)g(x)+rx+s$$

This produces a linear expression as the remainder. As long as the remainder is sufficiently small, the desired factor can be found approximately.

We hope the final solution is the initial value plus an offset correction:

$$p_1=p+dp$$ $$q_1=q+dq$$

The two numbers $(r, s)$ in the remainder are determined by the given coefficients $(p, q)$ of the divisor. There are the partial-derivative relations:

$$dr=\frac{\partial r}{\partial p}dp+\frac{\partial r}{\partial q}dq$$ $$ds=\frac{\partial s}{\partial p}dp+\frac{\partial s}{\partial q}dq$$

In the initial equation, the dividend $f(x)$ is given, and the quotient $g(x)$ and remainder $rx+s$ change as the divisor $x^2+px+q$ changes. Therefore, we have the partial-derivative relations

$$0=xg(x)+\frac{\partial g(x)}{\partial p}(x^2+px+q)+\frac{\partial r}{\partial p}x+\frac{\partial s}{\partial p}$$ $$0=g(x)+\frac{\partial g(x)}{\partial q}(x^2+px+q)+\frac{\partial r}{\partial q}x+\frac{\partial s}{\partial q}$$

Notice that the partial derivatives are numerical values independent of the variable $x$. Therefore, the divisibility relations are

$$xg(x)=-\frac{\partial g(x)}{\partial p}(x^2+px+q)-\frac{\partial r}{\partial p}x-\frac{\partial s}{\partial p}$$ $$g(x)=-\frac{\partial g(x)}{\partial q}(x^2+px+q)-\frac{\partial r}{\partial q}x-\frac{\partial s}{\partial q}$$

The conclusion here is that the desired partial derivatives are exactly the remainders obtained by continuing to divide the quotient. Division of a polynomial by the given quadratic trinomial can be calculated directly. This gives the four partial derivatives.

We want $s$ and $r$ plus the offsets $ds$ and $dr$ to become $0$, that is, $ds$ and $dr$ are the negatives of $s$ and $r$. Therefore, solve the equations:

$$-\frac{\partial r}{\partial p}dp-\frac{\partial r}{\partial q}dq=r$$ $$-\frac{\partial s}{\partial p}dp-\frac{\partial s}{\partial q}dq=s$$

Solve the corresponding offsets $dp$ and $dq$ of $p$ and $q$ from the above system of equations; they can be obtained directly using a second-order determinant.

Implementation

// a is the original polynomial, n is its degree, p is the linear coefficient being found, and q is the constant term being found
void Shie(double a[], int n, double *p, double *q) {
  // Array b is the quotient when polynomial a is divided by the quadratic trinomial in the current iteration
  memset(b, 0, sizeof(b));
  // Array c is the quotient when polynomial b is multiplied by x squared and then divided by the quadratic trinomial in the current iteration
  memset(c, 0, sizeof(c));
  *p = 0;
  *q = 0;
  double dp = 1;
  double dq = 1;
  while (dp > eps || dp < -eps || dq > eps || dq < -eps)  // eps is set separately
  {
    double p0 = p;
    double q0 = q;
    b[n - 2] = a[n];
    c[n - 2] = b[n - 2];
    b[n - 3] = a[n - 1] - p0 * b[n - 2];
    c[n - 3] = b[n - 3] - p0 * b[n - 2];
    int j;
    for (j = n - 4; j >= 0; j--) {
      b[j] = a[j + 2] - p0 * b[j + 1] - q0 * b[j + 2];
      c[j] = b[j] - p0 * c[j + 1] - q0 * c[j + 2];
    }
    double r = a[1] - p0 * b[0] - q0 * b[1];
    double s = a[0] - q0 * b[0];
    double rp = c[1];
    double sp = b[0] - q0 * c[2];
    double rq = c[0];
    double sq = -q0 * c[1];
    dp = (rp * s - r * sp) / (rp * sq - rq * sp);
    dq = (r * sq - rq * s) / (rp * sq - rq * sp);
    *p += dp;
    *q += dq;
  }
}

References and notes

Footnotes

1. Lin Shih-E. On the Application of the Factor-Splitting Method to the Roots of High-Order Characteristic Equations. Advances in Mathematics, 1963(03):207-217. ↩