Saturday, January 17, 2009

Sturm's Theorem: Sturm Chains

Before proceeding to Sturm's Theorem, let's talk about Sturm Chains.

Definition 1: Sturm Chain

A Sturm Chain is a series of polynomials P0, ...., Pm

such that:

(1) For any value of i where i ≥ 1, if Pi(x)=0, then Pi-1(x) = -Pi+1(x)

(2) If Pi(x) = 0 then Pi+1(x) ≠ 0 and if i ≥ 1, then Pi-1(x) ≠ 0.

(3) For a sufficiently small area surrounding a zero point of P0(x), P1(x) is everywhere greater than 0 or everywhere smaller than 0.

Lemma 1: Constructibility of a Sturm Chain from a Polynomial

If a polynomial P is differentiable and has only simple roots, then it is possible to construct a Sturm Chain based on it.

Proof:

(1) Let P0 be the polynomial and P1 be the first derivative of P0.

(2) We can now use an alternate form of Euclid's Algorithm for Greatest Common Divisor of Polynomials (see Theorem 1, here) to get the following:

P0 = Q1P1 - P2
...

Pm-2 = Qm-1Pm-1 - Pm

where all deg Pi is less than deg Pi-1 and deg Pm = 0.

(3) Since P0 is simple, we know that P0 and P1 are relatively prime [See Lemma 2, here].

(4) Therefore, Pm is degree 0. [See definition 3, here for the definition of relatively prime polynomials]

(5) Now, we can show that P0, P1, ..., Pm form a Sturm Chain. Here's the reasoning.

(6) Using step #2 above, we know for i, we have the following equation:

Pi-1 = QiPi - Pi+1

(7) Assume that Pi(x) = 0.

(8) Then it follows that:

Pi-1 = -Pi+1

(9) Assume that Pi(x) = 0 and Pi+1(x) = 0

(10) Then it follows that Pi+2(x) = 0 and so on.

(12) So that Pm(x) = 0. But this is impossible since Pm is a constant (a polynomial of degree 0)

(13) Therefore, we reject our assumption in step #7 and conclude that Pi+1(x) ≠ 0.

(14) In the same way, we can show that if Pi(x) = 0, then it follows that Pi-1 ≠ 0.

(15) Finally, since P0=P is a polynomial with only simple roots and P1 = P' is its derivative, we know that (see Lemma, here), for a sufficiently small area surrounding a zero point of P0(x), P1(x) is everywhere negative or everywhere positive.

QED

References