Wednesday, October 29, 2008

Sturm's Theorem: An Initial Lemma

Here's a major problem that Jacques Charles Francois Sturm solved:

Find the number of real roots of an algebraic equation with real coefficients over a given interval.

There are two possible cases:

(I) The real roots of the equation in question are all simple over the given interval.

(II) The equation also possesses multiple real roots over the interval.

Before proceeding to his solution, let's start with a lemma.

Lemma:

Any equation of multiple real roots can be broken down into a set of equations with only simple real roots.

Proof:

(1) Let the F(x) = 0 have the distinct roots α, β, γ, ...

(2) Let the root α be a-fold, the root β be b-fold, γ c-fold, etc where a,b,c,... are not necessarily 1.

(3) Using the Fundamental Theorem of Algebra (see Thereom, here), we have:

F(x) = (x - α)a(x - β)b(x - γ)c*...

(4) Using some basic properties of the derivative (see Corollary 2.2, here), we have:

F'(x)/F(x) = a/(x - α) + b/(x - β) + c/(x - γ) + ... =

= [a(x - β)(x - γ)(x - λ)*... + b(x - α)(x - γ)(x - λ)*... + ...]/[(x - α)(x - β)(x - γ)*...]

(5) Let:

p(x) = [a(x - β)(x - γ)(x - λ)*... + b(x - α)(x - γ)(x - λ)*... + ...]

q(x) = [(x - α)(x - β)(x - γ)*...]

so that we have:

F'(x)/F(x) = p(x)/q(x)

(6) We note that p(x) and q(x) do not have any common divisors since for each factor of q(x), we are left with a remainder of the form c/(x - d) where c,d are constants.

(7) Let G(x) = F(x)/q(x)

(8) Then:

F(x) = G(x)*q(x)

F'(x) = G(x)*p(x) [since F'(x)/F(x)=p(x)/q(x) → F'(x) = F(x)*p(x)/q(x) = G(x)*p(x)]

(9) Since p(x) and q(x) do not have any common divisors, it follows that G(x) is the greatest common divisor of F(x) and F'(x)

(10) Since we can always figure out the greatest common divisor of two equations (see Theorem 1, here for the greatest common divisor of polynomials), it follows that G(x) is obtainable based solely on F(x) and F'(x).

(11) Now since F(x)=G(x)*q(x), it follows that F(x)=0 divides into two equations:

G(x)=0

q(x)=0

(12) Since q(x) = (x - α)*(x - β)*(x - γ)*..., it is clear that it consists only of simple roots [from step#1]

(13) Since we can apply the same logic to G(x), it follows that we can always break down an equation of multiple real roots into a set of equations with only simple real roots.

QED

References

1 comment:

  1. Hi.

    Are the greek letters real or complex?
    Are the coefficients of q(x) real or complex?

    ReplyDelete