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 {\displaystyle p_{0}} and p 1 {\displaystyle p_{1}} two univariate polynomials. Suppose that they do not have a common root and the degree of p 0 {\displaystyle p_{0}} is greater than the degree of p 1 {\displaystyle p_{1}} . The Sturm series is constructed by:

p i := p i + 1 q i + 1 − p i + 2  for  i ≥ 0. {\displaystyle 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 {\displaystyle p_{i+2}} has negative sign.

Sturm series associated to a characteristic polynomial

Let us see now Sturm series p 0 , p 1 , … , p k {\displaystyle p_{0},p_{1},\dots ,p_{k}} associated to a characteristic polynomial P {\displaystyle P} in the variable λ {\displaystyle \lambda } :

P ( λ ) = a 0 λ k + a 1 λ k − 1 + ⋯ + a k − 1 λ + a k {\displaystyle P(\lambda )=a_{0}\lambda ^{k}+a_{1}\lambda ^{k-1}+\cdots +a_{k-1}\lambda +a_{k}}

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

p 0 ( μ ) := ℜ ( P ( ı μ ) ı k ) = a 0 μ k − a 2 μ k − 2 + a 4 μ k − 4 ± ⋯ p 1 ( μ ) := − ℑ ( P ( ı μ ) ı k ) = a 1 μ k − 1 − a 3 μ k − 3 + a 5 μ k − 5 ± ⋯ {\displaystyle {\begin{aligned}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{aligned}}}

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 ( μ ) = c i , 0 μ k − i + c i , 1 μ k − i − 2 + c i , 2 μ k − i − 4 + ⋯ {\displaystyle 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 {\displaystyle q_{i}} is equal to ( c i − 1 , 0 / c i , 0 ) μ {\displaystyle (c_{i-1,0}/c_{i,0})\mu } which provides the condition c i , 0 ≠ 0 {\displaystyle c_{i,0}\neq 0} . Moreover, the polynomial p i {\displaystyle p_{i}} replaced in the above relation gives the following recursive formulas for computation of the coefficients c i , j {\displaystyle c_{i,j}} .

c i + 1 , j = c i , j + 1 c i − 1 , 0 c i , 0 − c i − 1 , j + 1 = 1 c i , 0 det ( c i − 1 , 0 c i − 1 , j + 1 c i , 0 c i , j + 1 ) . {\displaystyle 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 {\displaystyle c_{i,0}=0} for some i {\displaystyle i} , the quotient q i {\displaystyle q_{i}} is a higher degree polynomial and the sequence p i {\displaystyle p_{i}} stops at p h {\displaystyle p_{h}} with h < k {\displaystyle h<k} .

References