Proof
Polynomials are continuous functions, and any sign change must occur at a root, so consider the behavior of a Sturm chain around the roots of its constituent polynomials.
First, note that two adjacent polynomials can share a common root only when it is a multiple root of p (in which case it is a root of every pi). Indeed, if pi and pi−1 are both zero at, then pi+1 also have to be zero at, since . The zero then propagates recursively up and down the chain, so that is a root of all the polynomials p0, ..., pm.
Next, consider roots of polynomials in the interior (i.e., ) of the Sturm chain that are not multiple roots of p. If, then from the previous paragraph it is true that and . Furthermore, so in the vicinity of there is a single sign change across pi−1, pi, pi+1. In other words, sign changes in the interior of the Sturm chain do not affect the total number of sign changes across the chain.
So only roots of the original polynomial, at the top of the chain, can affect the total number of sign changes. Consider a root, so, and assume first that it is a simple root. Then p's derivative, which is p1, must be non-zero at, so p must be either increasing or decreasing at . If it's increasing, then its sign is changing from negative to positive when moving from left to right while its derivative (again, p1) is positive, so the total number of sign changes decreases by one. Conversely, if it's decreasing, then its sign changes from positive to negative while its derivative is negative, so again the total number of sign changes decreases by one.
Finally, let be a multiple root of p, and let p0, ..., pm be the canonical Sturm chain. Let d = gcd(p,p'), q = p/d, and let q0, ..., qm' be the canonical Sturm chain of q. Then m = m' and pi = qid for every i. In particular, σ(x) is the same for both chains whenever x is not a root of d. Then the number of sign changes (in either chain) around decreases by one, since is a simple root of q.
In summary, only sign changes at roots of the original polynomial affect the total number of sign changes across the chain, and the total number of sign changes always decreases by one as roots are passed. The theorem follows directly.
Read more about this topic: Sturm's Theorem
Famous quotes containing the word proof:
“a meek humble Man of modest sense,
Who preaching peace does practice continence;
Whose pious lifes a proof he does believe,
Mysterious truths, which no Man can conceive.”
—John Wilmot, 2d Earl Of Rochester (16471680)
“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is what should be. Now, if youre taught to live up to a what should be that never existedonly an occult superstition, no proof of this should beMthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (19251966)