Sturm series

In mathematics, the Sturm series^[1] associated with a pair of polynomials is named after Jacques Charles François Sturm.

Definition

Let $p_0$ and $p_1$ two univariate polynomials. Suppose that they do not have a common root and the degree of $p_0$ is greater than the degree of $p_1$. The Sturm series is constructed by:

$p_i := p_{i+1} q_{i+1} - p_{i+2} \text{ for } i \geq 0.$

This is almost the same algorithm as Euclid's but the remainder $p_{i+2}$ has negative sign.

Sturm series associated to a characteristic polynomial

Let us see now Sturm series $p_0,p_1,\dots,p_k$ associated to a characteristic polynomial $P$ in the variable $\lambda$:

$P(\lambda)= a_0 \lambda^k + a_1 \lambda^{k-1} + \cdots + a_{k-1} \lambda + a_k$

where $a_i$ for $i$ in $\{1,\dots,k\}$ are rational functions in $\mathbb{R}(Z)$ with the coordinate set $Z$. The series begins with two polynomials obtained by dividing $P(\imath \mu)$ by $\imath ^k$ where $\imath$ represents the imaginary unit equal to $\sqrt{-1}$ and separate real and imaginary parts:

$\begin{align} p_0(\mu) & := \Re \left(\frac{P(\imath \mu)}{\imath^k}\right ) = a_0 \mu^k - a_2 \mu^{k-2} + a_4 \mu^{k-4} \pm \cdots \\ p_1(\mu) & := -\Im \left( \frac{P(\imath \mu)}{\imath^k}\right)= a_1 \mu^{k-1} - a_3 \mu^{k-3} + a_5 \mu^{k-5} \pm \cdots \end{align}$

The remaining terms are defined with the above relation. Due to the special structure of these polynomials, they can be written in the form:

$p_i(\mu)= c_{i,0} \mu^{k-i} + c_{i,1} \mu^{k-i-2} + c_{i,2} \mu^{k-i-4}+\cdots$

In these notations, the quotient $q_i$ is equal to $(c_{i-1,0}/c_{i,0})\mu$ which provides the condition $c_{i,0}\neq 0$. Moreover, the polynomial $p_i$ replaced in the above relation gives the following recursive formulas for computation of the coefficients $c_{i,j}$.

$c_{i+1,j}= c_{i,j+1} \frac{c_{i-1,0}}{c_{i,0}}-c_{i-1,j+1} = \frac{1}{c_{i,0}} \det \begin{pmatrix} c_{i-1,0} & c_{i-1,j+1} \\ c_{i,0} & c_{i,j+1} \end{pmatrix}.$

If $c_{i,0}=0$ for some $i$, the quotient $q_i$ is a higher degree polynomial and the sequence $p_i$ stops at $p_h$ with $h<k$.

References

1. (French) C. F. Sturm. Résolution des équations algébriques. Bulletin de Férussac. 11:419–425. 1829.