Saturday, May 20, 2006

Fundamental Theorem of Algebra: The Proof

In today's blog, I complete the proof for the Fundamental Theorem of Algebra. In my next blog, I will use this result to factor Fermat's Last Theorem into cyclotomic integers.

Today's proof is taken from David Antin's translation of Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.

Lemma 1: if an algebraic equation f(x) has a root α, then f(x) can be divided by x-α without a remainder and the degree of the result f'(x) is less than the degree of f(x).

Proof:

(1) Let f(x) = xn + a1xn-1 + ... + an-1x + an

(2) Let α be a root such that f(α) = 0

(3) Now, if we divide the polynomial by (x-α), we get the following (see here if proof needed):

f(x)/(x - α) = f1(x) + R/(x-α)

where R is a constant and f1(x) is a polynomial with order n-1.

(4) Multiplying both sides with x-α gives us:

f(x) = (x - α)f1(x) + R

(5) Now, if we substitute α for x we get:

f(α) = 0 which means that the constant in the equation is 0 so R = 0.

QED

Theorem: Fundamental Theorem of Algebra

For any polynomial equation of order n, there exist n roots ri such that:

xn + a1xn-1 + ... + an-1x + an = (x - r1)(x - r2)*...*(x - rn)

Proof:

(1) Let f(x) = xn + a1xn-1 + ... + an-1x + an

(2) We know that f(x) has at least one solution α1. [See here for proof]

(3) Using Lemma 1 above, we know that:

f(x)/(x - α1) = f'(x) where deg f'(x) = n-1.

So that we have:

f(x) = (x - α1)f'(x)

(4) But we know f'(x) has at least one solution (from here) so we can repeat steps #2 and #3 to get:

f'(x)/(x - α2) = f''(x) where deg f''(x) = n-2.

which combined with step #3 gives us:

f(x) = (x - α1)(x - α2)f''(x)

(5) Eventually we get to the point where the degree of fn(x) = 1.

In this case, fn(x) = x - αn.

(6) This establishes that there are n roots for a given equation f(x) where the degree is n.

(7) Putting this all together gives us:

f(x) = (x - α1)(x - α2)*...*(x - αn)

(8) Now, since f(x)=0 only when one of the values αi=x, we see that the n roots αi are the only solutions.

(9) So, we have proven that each equation is equal to n roots.

One important point to remember is that the n roots are not necessarily distinct. That is, it is possible that αi = αj where i ≠ j.

QED

References

Friday, May 19, 2006

Fundamental Theorem of Algebra: At least one solution

In today's blog, I continue the proof for the Fundamental Theorem of Algebra. Today, I will show the proof that all polynomials in the complex domain have at least one root that leads to 0.

Today's proof is taken from David Antin's translation of Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.

Lemma 1: If f(x) = xn + a1xn-1 + ... + an-1x + an where ai and x are complex numbers, then there exists at least one solution r such that f(r)=0.

Proof:

(1) Let f(x) = xn + a1xn-1 + ... + an-1x + an

(2) Assume that for all x, f(x) ≠ 0

(3) We know that there exists a value x0 such that w0=f(x0) and w0 is the smallest absolute number. [See Lemma 2 here for proof]

(4) From step #2, we can assume that absolute(w0) is greater than 0.

(5) We can plot the minimal point, w0, on the plane of complex numbers (see here for more details if needed)

(6) From this point, we can define a small circle K with radius R.

(7) Now, for any point x in K, x = x0 + ζ

In other words, complex numbers form a one-to-one mapping between the possible values for f(x) and the Cartesian coordinate system. If we use the form r(cos θ + i sin θ), then we see that r is the radius of K [See here if more information needed]

(8) Using the plane of complex numbers, we know that there exists ρ, θ such that ζ = ρ(cos θ + isin θ) (see here for review of how cos θ + isin θ can be used in this situation)

(9) In the above case, ρ = the absolute magnitude of ζ

(10) So, for any value x, there exists a value w and a value ζ such that:

w = f(x) = f(x0 + ζ) = (x0 + ζ)n + a1(x0 + ζ)n-1 + ... + an

(11) From the equation in #10, we can rearrange the values to get the following:

w = f(x0) + c1ζ + c2ζ2 + ... + cnζn = w0 + c1ζ + c2ζ2 + ... + cnζn

(12) Now, it is quite possible that some of the ci values are 0 so we can rearrange the values so the first nonzero coefficient is c and the power is v, the next is c' and the power is v', and so on where each c,v are nonzero and v is less than v' is less than v'', etc.:

w = w0 + cζv + c'ζv' + c''ζv'' + ...

(13) Since we assume that w0 is nonzero, we can divide both sides by w0 to get:

w/w0 = 1 + (cζv)/w0 + (c'ζv')/w0 + (cζv'')/w0 + ...

(14) Now let us define some values to make this equation more manageable:

Let q = c/w0

Let ξ = (c'ζv' + c''ζv'' + ...)/(cζv)

So that:

w/w0 = 1 + qζv(1 + ζξ)

(15) Now, since q, ζ are complex numbers, we can represent them both using r(cos + isin) form (see here if more information needed)

So that there exists h, λ such that:

q = h(cos λ + i sin λ)

From step #8, there exists ρ, θ such that:

ζ = p(cos θ + i sin θ)

(16) To shorten the equation we can use:

1λ = cos λ + i sin λ

And use:

1θ = cos θ + i sin θ

So that we have:

q = h * 1λ

ζ = ρ * 1θ

(17) Using step #16, we get:

v = h*1λ*(ρ*1θ)v = h*pv*1λ*(1θ)v

(18) Now, using Euler's Formula (see Lemma #1, Lemma #2 here if needed), we know that:

(1θ)v = 1

1*1λ = 1λ + vθ

(19) Within the circle K, we can now consider only the values of x that are associated with θ = (π - λ)/v. [Since a circle includes all values of θ between 0 and, see here if needed]

(20) In this case:

1λ + vθ = 1λ + v(π - λ)/v = 1λ - λ + π = 1π

(21) Now 1π = cos (π) + isin(π) = -1 + i*0 = -1. [See here if needed]

(22) So, in this case, combining step #21 with step #17:

v = h*ρv*(-1) = -h*ρv

(23) Combining step #22 with step #14:

w/w0 = 1 - hρv(1 + ζξ)

(24) Now, we can set the radius of K to any value so we can constrain ζξ to be as close to 0 as we wish so that for all purposes, we have:

w/w0 = 1 - hρv

[The idea here is that the radius of K was selected arbitarily in step #6, any nonzero radius r will do]


(25) Now, we can choose any value for ρ so we choose a value such that ρ is greater than 0 and less than (1/h)(1/v).

We can do this since ρ is the magnitude of ζ (see step #9). In step #19, we constrained θ and in step #24, we constrained the maximum magnitude of the circle K.

Even with all of the above constraints, we are still left with a set of values and we can select a value of x such that the magnitude is less than the radius of K and less than (1/h)(1/v) but still greater than 0.

(26) But then v is greater than 0 and less than h*(1/h) = 1 since:

h*[(1/h)(1/v)]v = 1

(27) But this means there is a value of x such that w/w0 is greater than 0 and less than 1.

(28) But this is a contradiction because it means that w is less than w0 which is impossible from step #3.

The reasoning here is that if w/w0 = fraction, this implies that w = w0 * fraction which implies that w is less than w0

(25) So we are forced to reject our assumption in step #2.

QED

References

Sunday, May 14, 2006

Fundamental Theorem of Algebra: Preliminaries

Cyclotomic integers allow Fermat's Last Theorem to be factored in the following way:

xn + yn = (x + y)(x + αy)(x + α2y)*...*(x + αn-1y)

In the above factorization, n is an odd prime and α is a root of unity where αn = 1 and αi ≠ 1 for all 1 ≤ i ≤ n-1.

To establish this refactorization, I will be using the Fundamental Theorem of Algebra.

The main idea behind the Fundamental Theorem of Algebra is that for any given polynomial of a single variable of order n, there are at least n zeros to this equation in the complex domain.

This is an easy proof to state but difficult to prove. Rene Descartes and Jean le Rond d'Alembert knew about this result but it was not until Carl Friedrich Gauss that the fundamental theorem was rigorously proved. d'Alembert thought that the existence of a minimum point for a complex equation was obvious and needed no proof. I do not find this point so obvious so I begin with its proof.

The details in today's proof are taken from B. N. Delone's article on Algebra from Mathematics: Its Content, Methods, and Meaning by A. D. Aleksandrov, A. N. Kolmogorov, and M. A. Lavrent'ev and translated by S. H. Gould.

Theorem 1: Bolzano-Weierstrass Theorem

If a rectangle contains an infinite sequence of points (z1, z2, ..., zn, ... in its interior, then there exists a point z0 such that in any arbitrarily small neighborhood of z0, there are infinitely many points of the sequence z1, z2, ..., zn, ...

Proof:

(1) Let R1 be a rectanlge that contains an infinite sequence of points.

(2) We divide it up into 4 equal parts using two lines parallel to each of its sides.

(3) At least one of these four parts contains infinitely many points, let us label it R2

(4) We now divide up R2 into 4 equal parts using two lines parallel to each of its sides.

(5) One of these four parts contains infinitely many points and we label it R3

(6) In this way, we are able to generate a sequence of nested rectangles which we can label R1, R2, ..., Rn

(7) We can think of each side of this rectangle representing two nested intervals that exist on the x and y axises.

(8) Using Lemma 1 here, we there exists a point on the x-axis and a point on the y-axis that each of these nested intervals have in common.

(9) But this means that there is a point within the nested rectangles such that any arbitrary small neighborhood contains an infinity of points.

QED

Theorem 2: There exists a minimum point for c0xn + c1xn-1 + ... + cn.

Let f(x) = c0xn + c1xn-1 + ... + cn.

There exists a value x0 such that w0 = c0(x0)n + c1(x0)n-1 + ... + cn where absolute(w0) is the minimum value.

Proof:

(1) Let g = absolute(f(0))

(2) Let G be a number greater than g.

(3) Let R be a number such that if absolute(x) > R, then absolute(f(x)) is greater than G

(4) Now, if f(0)=0, then x0=0 and w0=0 so we can assume going forward that f(0) ≠ 0

(5) If f(0) is greater than 0 and all f(x) ≥ g, then x0=0 and w0=g so we can assume that there exists at least 1 point x' such that absolute(f(x')) is less than g.

(6) Based on a nonzero g, we can set up the follow sequence:

0, g/n, 2g/n, ..., ng/n = g

(7) We can find a value i, cn such that cn = (i/n)g and all values absolute(f(x)) ≥ cn.

(8) From i, we can also find a value cn' such that cn' = [(i+1)/n]g and there exists at least one value x' such that absolute(f(x')) is less than cn'

(9) We can find cn,i,cn' regardless of the value of n so we can let n increase to infinity.

(10) Now for all values of n, we can assume that absolute(x) ≤ R since if absolute(x) is greater than R, then absolute(f(x)) is greater than G and therefore greater than g. For purposes here, let's call these values xn

(11) So, we only need to consider the points xn that lie inside a rectangle of sides 2R and with its center at the origin.

(12) By Theorem 1 above, there exists a point z0 such that every neighborhood of z0 contains infinitely many points of the sequence z1, z2, ..., zn. Let us call this point x0

(13) For any point x, we have:

absolute(f(x)) is greater than cn = cn' - g/n which is greater than absolute(f(xn)) - g/n = absolute(f(x0)) + absolute(f(xn)) - absolute(f(x0)) - g/n.

(14) This inequality is true for all values of n so as n increases toward infinity, we see that difference absolute(f(xn)) - absolute(f(x0)) becomes arbitrarily small in absolute value with g/n.

(15) Consequently, all absolute(f(xn)) ≥ absolute(f(x0)) so x0 is the minimum point.

QED

References