Skip to content

Fundamental Theorem of Algebra

Definition

Any univariate polynomial equation of degree \(n\) with complex coefficients (where \(n\) is at least \(1\)) has at least one root in the complex field.

From this, it follows that a complex coefficient polynomial equation of degree \(n\) has exactly \(n\) roots in the complex field, counting multiplicities.

Sometimes this theorem is stated as:

Any nonzero univariate polynomial of degree \(n\) with complex coefficients has exactly \(n\) complex roots.

The proof of the Fundamental Theorem of Algebra generally involves complex analysis or modern algebra, so it is often applied directly as a well-known result.

According to the Fundamental Theorem of Algebra, a complex coefficient polynomial \(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\) can 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\).

Complex Conjugate Root Theorem

The Fundamental Theorem of Algebra deals with polynomials with complex coefficients. When studying polynomials with real coefficients, although complex roots can still be factored out, it requires expanding the domain of study, which is somewhat inconvenient.

Imaginary root: A root that is not a real number.

Theorem: The complex conjugate of a root of a real coefficient polynomial is also a root of that polynomial.

Proof: Directly take the complex conjugate on both sides of the equation given by the Fundamental Theorem of Algebra.

If the root itself is real, taking its conjugate leaves it unchanged, so it is unaffected.

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

Theorem: For a polynomial equation with real coefficients, complex conjugate imaginary roots always appear in pairs, and their multiplicities are equal.

Proof: Suppose one root is \(a+b\mathrm{i}\), then the other root is \(a-b\mathrm{i}\). This means there are two factors in the factorization:

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

It can be seen that when these two factors are multiplied together, all coefficients become real numbers. The quadratic polynomial with real coefficients on the right-hand side of this equation divides the original polynomial.

Thus, dividing both sides of the equation from the Fundamental Theorem of Algebra by this quadratic trinomial yields an equation that is still a polynomial with real coefficients. Repeating this process on the new equation, as the degree decreases, eventually no imaginary roots remain after several steps.

Therefore, each pair of complex conjugate imaginary roots has the same multiplicity. Q.E.D.

The following are corollaries of the Complex Conjugate Root Theorem:

  • Any odd-degree polynomial with real coefficients has at least one real root, and the total number of real roots is odd.
  • An even-degree polynomial with real coefficients may have no real roots, and the total number of real roots is even.

The quadratic trinomial \(x^2-2ax+a^2+b^2=x^2+px+q\) mentioned above is called an irreducible quadratic factor with real coefficients. "Irreducible" means it cannot be factored further over the real numbers.

Theorem: Any polynomial with real coefficients can be expressed as a product of linear factors and 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, by pairing the imaginary roots using the Complex Conjugate Root Theorem in the original factorization from the Fundamental Theorem of Algebra, the proof is complete.

According to the Complex Conjugate Root Theorem, a real coefficient polynomial \(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\) can 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 we perform the factorization according to the Fundamental Theorem of Algebra for polynomials with real coefficients? Extending the number field to complex numbers would be complicated.

If we restrict ourselves to factorization over the real numbers, we can only guarantee that when the degree is greater than \(2\), there always exists a real coefficient quadratic trinomial factor.

This is because if the polynomial has imaginary roots, we can directly pair up a pair of complex conjugate imaginary roots. If the polynomial only has real roots, multiplying any two linear factors corresponding to two real roots also yields a real coefficient quadratic trinomial factor.

Once a quadratic trinomial factor is found, solving for real or complex roots from the quadratic factor becomes very easy. This leads to a computational method that successively finds a quadratic factor to obtain the complex roots of the equation, avoiding complex number arithmetic.

In August 1940, August 1943, and July 1947, Lin Shih-ê published three formal papers1 in the MIT journal Journal of Mathematics and Physics on methods for solving complex roots of higher-order equations, each with improvements.

This method is still used today for fast computation on modern computers. The polynomial root-finding routines in computer software packages (such as MATLAB) are also based on this algorithm.

Process

To find a quadratic trinomial factor, we want to decompose the polynomial as:

\[ f(x)=(x^2+p_1x+q_1)g(x) \]

Since we cannot find the quadratic trinomial factor directly, following an iterative solution approach, for initial values we have:

\[ f(x)=(x^2+px+q)g(x)+rx+s \]

This produces a linear remainder. As long as the remainder is sufficiently small, we can approximately find the desired factor.

We want the final solution to be 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 partial derivative relationships:

\[ 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, while the quotient \(g(x)\) and the remainder \(rx+s\) change as the divisor \(x^2+px+q\) changes. Therefore, we have the partial derivative relationships:

\[ 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} \]

Note that the partial derivatives are just numerical values, independent of the variable \(x\). Therefore, we have divisibility relationships:

\[ 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 precisely the remainders obtained by further dividing the quotient polynomial. Polynomial division by the given quadratic trinomial can be computed directly. This yields the four partial derivatives.

We want \(s\) and \(r\) plus the offsets \(ds\) and \(dr\) to become \(0\), meaning \(ds\) and \(dr\) are the negatives of \(s\) and \(r\). Therefore, we need to 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 for the offsets \(dp\) and \(dq\) for \(p\) and \(q\) from the above system of equations, which can be done directly using second-order determinants.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// a is the original polynomial, n is the polynomial degree, p is the target linear coefficient, q is the target constant term
void Shie(double a[], int n, double *p, double *q) {
  // Array b is the quotient of polynomial a divided by the current iterative quadratic trinomial
  memset(b, 0, sizeof(b));
  // Array c is the quotient of polynomial b multiplied by x squared and then divided by the current iterative quadratic trinomial
  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 user-defined
  {
    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

  1. Lin Shih-ê. On the Application of the Root-Squaring Method to Solve Higher-Order Characteristic Equations. Advances in Mathematics, 1963(03):207-217. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用