Quartic Algorithm

Notational conventions:

iff is short for the phrase "if and only if"
det is short for determinant
tr means transpose of a matrix
Since we do not have a glyph showing a subscript, we will write ai to mean a with the subscript i. Likewise, xo is x with the subscript zero.

It is not the purpose to develop Linear Algebra here. However, we want to show the intimate relationship between polynomials and matrices. Given an n-by-n matrix A and a same-size identity matrix I, the equation

0 = det(A - x I)

is an n-degree polynomial equation. It is called the characteristic polynomial or characteristic equation. Its roots are called the eigenvalues. Thus, any method for finding the roots of a polynomial has an analogue for finding the eigenvalues of a matrix.

The Squaring algorithm

Lemma: If x is in the semi-open interval [0, 1); then we have

0 <= x^2 < x.

The proof is obvious.

Corollary: If x is in the semi-open interval [0, 1); then the limit, as m increases without bound, of (x^2)^m is zero.
The proof is obvious.

Lemma: Given the polynomial equation

0 = f(x) = x^n + a1 x^(n - 1) + a2 x^(n - 2) + ... + an.

Consider the polynomial equation

0 = g(x) = x^n + a1 p x^(n - 1) + a2 p^2 x^(n - 2) + ... + p^n an,

where p is any non-zero constant. Iff xo is a root of the first equation; so is (xo / p) a root of the second equation.
The proof is obvious.

Comment: If the first equation is the characteristic equation of the matrix A; then the second equation is the characteristic equation of (p A).

Corollary: If we take p = xo; then one is a root of g(x). That is, we have

0 = g(1).

The proof is obvious.

Corollary: If xo is the largest, in magnitude, root of f(x); then the set of roots of g(x) consists of one (perhaps, with some multiplicity) and other roots, each of whose magnitude is in the semi-open interval [0, 1).
The proof is obvious.

Lemma: Square. Given the polynomial equation

0 = f(x) = x^n + a1 x^(n - 1) + a2 x^(n - 2) + ... + an.

Consider the polynomial equation

0 = g(x) = x^n + a1^2 x^(n - 1) + a2^2 x^(n - 2) + ... + an^2.

Iff xo is a root of the first equation; so is xo^2 a root of the second equation.
The proof is obvious.

Comment: If the first equation is the characteristic equation of the matrix A; then the second equation is the characteristic equation of (A Atr).

Lemma: A polynomial equation

0 = x^n - x^m = (x^(n - m) - 1) x^m,

where 0 <= m < n, has the set of roots consisting of zero with a multiplicity of m and one with a multiplicity of (n - m).
The proof is obvious.

Theorem: Squaring algorithm. Successive squarings isolates the largest, in magnitude, root of a polynomial -- or matrix. This algorithm is much easier to understand in the context of a polynomial than as a matrix.

The 0, 1, 2, 3, and 4 degree polynomial equations

Theorem: Zero. Given the polynomial equation

ao = 0.

If ao is not zero; then, the set of roots consists of all complex values of x. Otherwise, the set of roots is null.
The proof is obvious.

Theorem: One ~ linear. Given the polynomial equation

0 = ao x + a1.

If ao is zero; then we know the set of roots from the previous theorem. Otherwise, the set of roots is

{- a1 / ao}.

The proof is obvious.

From the general transformations, discussed in the foregoing, we just could have the alternative
Theorem: One ~ linear. The set of roots of the polynomial equation

0 = x - a

{a}.

The proof is obvious.

Lemma: Given the polynomial equation

0 = f(x) = x^2 + a1 x + a2.

Consider the polynomial equation

0 = g(x) = x^2 - (a1^2 / 4 - a2).

Iff xo is a root of the first equation; so is

uo = xo + a1 / 2

a root of the second equation.
Proof: Substitute

x = u - a1 / 2

into the first equation, to obtain

0 = f(u - a1 / 2) = (u - a1 / 2)^2 + a1 (u - a1 / 2) + a2 = u^2 + (a2 - a1^2 / 4).

QED.

Theorem: Two ~ quadratic. Given the polynomial equation

0 = ao x^2 + a1 x + a2.

If ao is zero; then we know the set of roots from the previous theorem. Otherwise, the set of roots is

{(- a1 + sqrt(a1^2 - 4 ao a2)) / (2 ao), (- a1 - sqrt(a1^2 - 4 ao a2)) / (2 ao)},

which we write as the quadratic formula

{(- a1 +- sqrt(a1^2 - 4 ao a2)) / (2 ao)} = {(2 a2) / (- a1 -+ sqrt(a1^2 - 4 ao a2))}.

The proof is obvious.

From the general transformations, discussed in the foregoing, we just could have the alternative
Theorem: Two ~ quadratic. The set of roots of the polynomial equation

0 = x^2 - a

{+- sqrt(a)}.

The proof is obvious.

From here on, things become more complicated; so, we only consider these alternative versions.
We provide three references:

Our high-school textbook College Algebra by Rider
A history and derivation of the cubic and quartic formulae. http://www-groups.dcs.st-andrews.ac.uk/~history/HistTopics/Quadratic_etc_equations.html
Also, employ a symbolic-mathematics program to solve a general cubic or quartic equation, to see the result.

Lemma: For any given u; there are three cube-roots of u. Let one of them be v. Then, the set of cube-roots of u is

{v, ((- 1 +- i sqrt(3)) / 2) v}.

Proof: Observe that

((- 1 +- i sqrt(3)) / 2)^3 = (- 1 +- 3 i sqrt(3) - 3 * 3 -+ i sqrt(3)) / 8 = 1.

QED.

Corollary: We have

1 / ((- 1 +- i sqrt(3)) / 2) = (- 1 -+ i sqrt(3)) / 2.

The proof is obvious.

Algorithm: Three ~ cubic. The set of roots of the polynomial equation

0 = x^3 + m x - n

may be obtained as follows. We employ the conventional notation for the coefficients of this equation. First, we observe that

0 = (a - b)^3 + 3 a b (a - b) - (a^3 - b^3)

is an identity in a and b. By comparison, we see that

x = a - b

would be a solution of the given polynomial equation iff the system of the two equations

3 a b = m
a^3 - b^3 = n

were to be solved for the two unknowns a and b. From the first equation, we see that b is

b = m / (3 a).

Substitute this into the second equation, to obtain

a^3 - (m / (3 a))^3 = n.

Multiply through by a^3 -- thus, introducing three extraneous roots -- and rearrange the terms, to obtain

0 = a^6 - n a^3 - (m / 3)^3.

This is a quadratic equation in a^3. We already know how to solve it. To obtain a, take the qube-root, of which there is a set of three. Now, substitute back. First, we obtain b as

b = m / (3 a).

Substitute into the equation for x, to obtain

x = a - b = a - m / (3 a).

We desired a set of three roots. We got more than that for which we bargained. We have a set of six potential roots, of which three are extraneous. But, which three are the valid roots? It depends upon the discriminant of the quadratic formula, in the foregoing. The procedure is to compute all six of the roots and substitute each back into the cubic polynomial-equation, to see which three check.

Lemma: The two roots of a quadratic are equal -- hence the quadratic is a perfect square -- iff the discriminant is zero.
The proof is obvious.

Algorithm: Four ~ quartic. The set of roots of the polynomial equation

0 = x^4 + p x^2 + q x + r.

may be obtained as follows. We employ the conventional notation for the coefficients of this equation. By completing the square, re-write this equation as

(x^2 + p + y)^2 = x^4 + 2 (p + y) x^2 + y^2 + 2 p y + p^2 =
= (p + 2 y) x^2 - q x + (p^2 - r + 2 p y + y^2).

where y will be chosen, presently. The right-hand side is a quadratic in x. To make it a perfect square, we set its discriminant equal to zero

0 = q^2 - 4 (p + 2 y) (p^2 - r + 2 p y + y^2) =
= - 8 y^3 - 20 p y^2 + (- 16 p^2 + 8 r) y + (q^2 - 4 p^3 + 4 p r).

This is a cubic in y. Solve it by the foregoing algorithm. Substitute the roots into the previous equation. Since each side is a perfect square, we take the square-roots. Subtract (p + y) from each side. Take the square-root, to obtain x. We are finished. Well, I did not say that it would be easy, did I?