In mathematics, the Sturm series associated with a pair of polynomials is named after Jacques Charles François Sturm.
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
for
i
≥
0.
This is almost the same algorithm as Euclid's but the remainder
p
i
+
2
has negative sign.
Let us see now Sturm series
p
0
,
p
1
,
…
,
p
k
associated to a characteristic polynomial
P
in the variable
λ
:
P
(
λ
)
=
a
0
λ
k
+
a
1
λ
k
−
1
+
⋯
+
a
k
−
1
λ
+
a
k
where
a
i
for
i
in
{
1
,
…
,
k
}
are rational functions in
R
(
Z
)
with the coordinate set
Z
. The series begins with two polynomials obtained by dividing
P
(
ı
μ
)
by
ı
k
where
ı
represents the imaginary unit equal to
−
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
±
⋯
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
+
⋯
In these notations, the quotient
q
i
is equal to
(
c
i
−
1
,
0
/
c
i
,
0
)
μ
which provides the condition
c
i
,
0
≠
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
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
)
.
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
.
