A Geometrical Inter-retation of the Routh Test

by A. LEPSCHY,G. A.MIAN andu. VIARO

Department of Electronics and Informatics, University of Padova,
Via Gradenigo 6 A, 35131 Padova, Italy

ABSTRACT : A simple geometrical proof of the classical Routh test is presented. It is based
on the application of the root locus technique to suitable additive polynomial decompositions.
The procedure allows us to gain a new insight into the problem of polynomial zero clustering
and to give a common framework to many stability tests for both continuous- and discrete-
time systems.

I. Introduction

Recently, considerable attention has been devoted to the classical Routh stability
criterion (1-8) which is known to be related to the Euclid algorithm for constructing
a Sturm sequence. This enduring and continual interest is not surprising because
of its computational attractiveness and the wide variety of situations to which the
Routh algorithm can usefully be applied, e.g. zero location of real or complex
polynomials with respect to suitable lines, greatest common divisor calculation,
positivity determination of polynomials, system stability and passivity tests. Many
of these applications are described in the survey paper by Barnett and Siljak (9),
where it is rightly observed that “doubtless other uses remain to be discovered”.
Another growing field of application is concerned with the problem of model
reduction, which is related to the partial realization of transfer functions and the
evaluation of continued fraction expansions (10). In particular,’ it is possible to
construct the denominator of a reduced-order transfer function by truncating a
suitable continued fraction of the Hurwitz alternant for the original denominator
(Routh approximation). In this way, the reduced models are stable and preserve
some energy indices of the original systems (11, 12).
In view of the interest in the Routh algorithm and its application to stability
analysis, other proofs of this celebrated stability criterion have been proposed after
the original one based on the Strum theorem and the theory of Cauchy’s indices
(lS-15). In particular, Parks (16) was able to give a direct algebraic proof of the
Routh stability test based on Lyapunov theory, and Agashe (8) presented a more
general procedure which applies to complex polynomials too.
In the following section, we present a proof of the Routh criterion based on
simple geometrical considerations. Precisely, the basic additive decomposition of
a polynomial in its even and odd part is embedded into a suitable root locus (17) ;
this allows us to arrive easily at the usual rules for zero location and to gain a new
insight into the nature of the problem. A further advantage of this approach is the

0 The Franklin Institute 001&0932/88 $3.00+0.00 695

A. Lepschy et al.

possibility of giving a unified picture to a large class of stability tests both for
continuous- and discrete-time systems, as will be shown in the last part of the
paper.

ZZ.Proof” of the Routh Criterion

Consider the nth degree polynomial :

P,(S) = i U,,jSj,
qn > 0 (1)
j=O

and decompose it into the sum of its even and odd part as

Pn(s) = Qnb>+Qn-I<$, (2)

where

a,,,1s for n odd

/
en(s) = a,,,f+an,n_2sn-2+ ... + (3)
\
a, o for n even

and

a,,,o for n odd

/
Q-i(s) =a,,,~1Sn~1+a~,,_j~n-3+...+\ (4)
a, 1s for n even.

As is known, P,(s) is a Hurwitz polynomial if, and only if, the n zeros of Q,&s)
and the (n- 1) zeros of QnP i(s) are distinct, those of Qn_ 1(s) separate those of
Q&Y) along the imaginary axis, and an+ i > 0 like an,n (so that all polynomial
coefficients are positive). This corresponds to the condition that the phase variation
of P,(jo) equals 127~(counterclockwise) as o varies from - co to + co. Such a
condition is often referred to as the Mikhailov criterion (18), which is essentially
a geometrical interpretation of the argument principle.
From (3) and (4), let us form the polynomial of degree n - 2 :

Qn-2(s) = Q&)-CC,-isQn-l(s) (5)

with

a
c,-, z”‘” an,n- 1 f 0 (6)
an,n- 1’
so that the terms of degree n in Q&s) and in c,_ r,sQ+ r(s) cancel.
Notice that the coefficients of Qn_ 2(s) are nothing but the entries of the row of
order 12- 2 in the Routh array for P,(s).
It is easy to prove that P,(s) is Hurwitz if, and only if, c,_, > 0 and the
polynomial of degree IZ- 1

Journal of the Franklin Institute

696 Pergamon Press plc
 Interpretation of the Routh Test

Ims + Ims

Re s Re s
- l

I
II

(4 (b)
FIG. 1. Positive root loci for Eq. (8) with (a) II = 6 and (b) n = 5.

is Hurwitz.
Concerning the “if” part, assume that P,_ ,(s) is Hurwitz so that its coefficients
have the same sign, i.e. are positive, and the zeros of Qn_ i(s) separate those of
Qnp&) on the imaginary axis. The n zeros of Q&) belong to the positive root
locus (k > 0) for the equation :

Q,-,<d+ksQn-~(d = 0. (8)
As is known, this locus is a real algebraic variety consisting of n branches on
which k is a coordinate. If the two addenda in (8) have a zero sj in common, a
corresponding branch degenerates to the single point ij (which certainly occurs for
IZ odd with 2j = 0). The base points for plotting the locus are: (i) the zeros
of Q,_&) (corresponding to k = 0), and (ii) the zeros of Qn_ ,(s) and s = 0
(corresponding to k = co). Starting from these points the locus is easily sketched
according to the rules given in the textbooks (17).
There are two different possibilities to be considered. Suppose first that y1is even ;
then the second addendum in (8) has a double zero in s = 0. The corresponding
positive root locus is of the type depicted in Fig. 1(a) for n = 6, where the zeros of
sQn_ i(s) are represented by small circles and those of Q,-&) by small crosses. It
is seen that this locus consists of n - 2 segments on the imaginary axis lying between
a circle and a cross, and of two vertical half-lines between a circle and the point at
infinity. Therefore, the zeros of Q&s) (represented by small squares in Fig. la)
alternate with those of Qn- ,(s) since they correspond to the locus points for
k = c,_, > 0.

Vol. 325, No. 6, pp. 69S703, 1988

Printed in Great Britain 697
A. Lepschy et al.

Res Re s
b .
Y

FIG. 2. Negative root loci for Eq. (9) with (a) n = 6 and (b) n = 5.

Similar considerations apply to the case of y1odd ; the corresponding root locus
is of the type depicted in Fig. 1(b) for y1= 5. The sole difference is that one branch
degenerates to the point s = 0 which is a root of (8) for any value of k.
In both cases, the n- 1 distinct zeros of Qn_ i(s) separate the n distinct zeros
of Q&) on the imaginary axis, and P,(s) = Qn(s) +Qn_ r(s) is Hurwitz since
an,nlan,n- 1 = c,- 1 > 0.
Concerning the “only if” part, assume that P,(s) is Hurwitz. In this case, c,_ I > 0
and the zeros of Qn_ I(s) separate those of Q,(s). From (5) it follows that the n-2
zeros of Q,_Z(s) belong to the negative root locus (k < 0) corresponding to the
equation :

QnM+ksQ,-,@I = 0 (9)
for k = - c,_ ,. For such a (negative) value of k, only n - 2 roots of (9) are finite
and, for reasons similar to those used above, they separate the zeros of Qn_ i(s) for
both n even and II odd, as exemplified in Fig. 2 for n = 6 and n = 5 ; in these figures
the zeros of sQn_ i(s) are again represented by small circles, those of en(s) by small
crosses and those of Q_ &) by small squares. Moreover, the coefficients of Qn_ 2(s)
are all positive like those of Qn_ i(s) [and QJs)].t
Therefore, P,_ 1(s) = Qn- ,(s) + Qn_ &) is Hurwitz.
The above theorem may be applied to every polynomial :

T This is immediately realized, for instance, if one considers that for Ik 1< c,_ , all roots
of (9) have zero real part, and thus all coefficients in (9) have the same sign. Since the
coefficient of s” is positive, the coefficients .of si, i < n, are positive and, for continuity, they
also remain so for Ikl = c,_ r.

Journal of the Franklin Institute

698 Pergamon Press p1c
 Interpretation of the Routh Test

P,(S) = i ai,jsj= + Qi-I (3)

Q~(s) (10)
j=O

iteratively formed starting from P,(s) according to expressions of the form (5) and
(6), i.e.

Qi- d4 = QiN - ci- I@- I 6) (11)

Ci- 1 = &,i/4,i- 1, (12)

which essentially correspond to the Euclid algorithm (9). The computation of the
coefficients of polynomials Qi(s) may be organized in the usual Routh table.
In conclusion, P,(S) is Hmwitz if, and only if,
cj > 0, i=n-l,n-2 ,..., 0, (13)
i.e. if all the first-column elements in the array have the same sign, which proves
the Routh criterion.
If, at any stage of the iterative procedure, a,i_, = 0, one cannot compute ci_ 1
so that the sequence of polynomials Qi(S) [and, consequently, P,(S)] cannot be
terminated via (11) but P,(s) is certainly not Hurwitz.

ZZZ.Number of the Roots with Positive or Negative Real Part

Let ci be finite and different from zero for all i < n. From

Pi(s) = QiM + Qi- I (4 (10)

and

Pi- l(s) = Qi- I (s> + Qi- ~(3) (14)

and taking into account expression (1 l), we have

P,(S) = ci-ISQi-l(S)+Pi-I(S). (15)

Notice that the above assumption on coefficients ci ensures that Qi_ i(s) and
Pi_ 1(s) are coprime since the recursion is based on the Euclid algorithm for finding
the greatest common divisor.
The zeros of P,(s) belong to the complete root locus for the equation
Pi(Sgk) = kSQi-,(S)+Pi_1(S) = 0, kE(-m, +co). (16)
The base points for its plot are: (i) the i- 1 zeros of Pi_ 1(s) (for k = 0), and (ii)
the i- 1 zeros of Qi_ ,(s) and the origin (for k = m).
The locus has only one asymptote : the corresponding branch, which coincides
at least in part with the real axis, crosses the point at infinity of the s-plane for
k = 0.
The other i- 1 branches of the locus, which depart from the zeros of Pi_ 1(s) for
k = 0 and tend to the zeros of Qi_ 1(~) for k -+ co, remain finite and never cross
the imaginary axis.

Vol. 325, No. 6, pp. 69S703, 1988

Printed in Great Britain 699
A. Lepschy et al.

Im s
t

FIG. 3. Typical root locus for Eq. (16) with i = 6 and P&Y) Hurwitz. The small circles
correspond to the zeros of P5(s) and the small crosses to the zeros of its odd part Q,(S) and
the additional zero in the origin.

To prove this, it is enough to consider that if locus branches included points of

the imaginary axis for k = F finite and different from zero, a polynomial, R(s),
with only even or only odd powers of s could be factored out at the left-hand side
of (16) ; R(s) would be a factor of both the even and the odd part of P&V, k^), i.e.
of both bQi_ I(S) + QiP Z(S) and Qi_ I(S). A s a result, QiP i(s) and QiP 2(~) would
admit R(s) as a common factor, and Pi_ 1(s) and QjP 1(~) would not be coprime,
which contradicts the assumption.
A typical root locus plot for (16) with i = 6 is depicted in Fig. 3, which refers to
the Hurwitz polynomial :

P&Y) = (s+ 1) (s+2) (s+3) (s+ 1 -j2) (s+ 1 +j2)

and its odd part

Qs(s) = s(s’+2.642) (?+25.358).

It is clearly seen that all six roots of the corresponding equation (16) are in the
left half-plane [like the zeros of P&T)] for k > 0, whereas for k < 0, five roots are
in the left half-plane and one root is in the right half-plane.

Journal of the Franklin Institute

700 Pergamon Press plc
 Interpretation of the Routh Test

In conclusion, the i- 1 zeros of P,(s), belonging to the i- 1 branches departing

from the zeros of Pi_ 1(s), lie in the same half-plane as those of Pi_ 1(s) both for
ci_ 1 > 0 and for ci_ , < 0 ; the remaining ith zero, which belongs to the branch
originating from the point at infinity, lies in the left half-plane for ci_ I > 0 and in
the right half-plane for ci_ I < 0.
Therefore, the number of zeros of P&Y) with a positive real part is equal to the
number of the negative coefficients in the sequence of the coefficients cj, j = 0,
1, . . . , n - 1. This number clearly coincides with that of the sign variations in the
sequence of the first-column elements in the Routh array for P&Y).
When the highest-order coefficient of a polynomial Q(S) is zero, it is not possible
to generate the successive polynomial in the sequence using (11) and (12). As is
well known, if some coefficient of Qj(s) is different from zero, a perturbation
procedure can be adopted (3), e.g. by replacing the zero highest-order coefficient
by a suitably small quantity E. This corresponds to the consideration of a root locus
in which the zeros of Qj(s) are slightly modified. If, instead, all coefficients of Q,(s)
are zero, the vanishing polynomial may be replaced by dQj(S)/ds, which corresponds
to moving the imaginary axis a little to the right.

IV. Extensions of the Procedure

As mentioned in the Introduction, the procedure used in the previous sections
may be applied to different stability criteria. In fact, many of these are based on a
suitable additive decomposition of the polynomial to be tested ; subsequently,
a sequence of polynomials of decreasing degree is generated, each of which is
decomposed in a similar way.
In the case of the Routh algorithm, polynomial P,(s) is decomposed according
to (2) into its even and odd part, Q&) and Q+i(s). Then, using recursion
(1 l), the sequence of polynomials Q&s), i = n - 2, y1- 3,. . . , 0, is generated and
polynomials P,(S) = Qi(S) + Q1_I(s ) are formed. These; however, may directly be
obtained starting from P,(s) and P,- ,(s) (19) via the recursion

P,(S) =$Pi+2(S)- CiS++- l pi+l(S) (17)

r+1 ( r+ 1 1

involving only polynomials of the same family.

Concerning discrete-time systems, it is known that the Jury-Marden type criteria
(20) correspond to the decomposition of the characteristic polynomial P,(z) =
Eai,ri into a polynomial P,_ ,(z) and its reciprocated polynomial zPcn- “P,- 1(z- ‘)
(whose zeros are symmetric to those of P,_,(z) with respect to the unit circle),
multiplied by z- ’ :

P”(Z) = P,-l(z)+knz-“P,-,(z-‘). (18)

It is thus possible to generate a sequence of polynomials P,(z), i = n - 1, n - 2, . . . ,
0, according to the backward Levinson algorithm. The results of the corresponding
computations may be organized in the usual Jury table.

Vol. 325, No. 6, pp. 695-703, 1988

Printed in Oreat Britain 701
A. Lepschy et al.

In this case, the proof of the stability criterion essentially consists of showing
that P,(z) is ‘stable’ (i.e. its zeros are all inside IzJ = 1) if and only if P,_l(z) is
stable and lkil < 1. This fact may easily be demonstrated with the aid of the root
locus technique as in (21), where it is proved that the locus branches may intersect
the unit circle only for jkil = 1.
It is worth noting that the bilinear transformation s = (z- l)/(z+ l),
z = (1 +s)/(l -S) allows one to obtain a Routh-type criterion for discrete systems
(S), as well as a Levinson-type criterion for continuous systems (22). In the
first case, PJz) is separated into a mirror-image polynomial M,(z) = J[PJz)+
z-“P,(z- ‘)] and an antimirror-image polynomial A,(z) = f [P,(z) - z-“P,(z- ‘)I.
Polynomials M,(z) and A,(z) play roles similar to those played by Q(S) and
Qn_ ,(s) in (2). A sequence of polynomials of descending degree is then obtained
by factoring out the term 1 -z- ’ necessarily present in the antimirror-image poly-
nomials. In the second case, one decomposes P,(s) according to

P,(S) = (s+l)P,_1(s)+k,(s-l)P,~1(-s), (19)

where the zeros of P,_ 1(-s) are symmetric to those of P,_ 1(s) with respect to the
imaginary axis, and generates a sequence of polynomials Pi(S) of descending degree
different from those obtained from (17). Also, in these cases, it is straightforward
to use the root locus technique to prove the corresponding stability criteria as done
in (22) for the continuous-time case.
Among other things, such an approach points out a geometrical link between
the two types of criteria. In fact, referring for instance to the continuous-time case,
the compZete root locus drawn starting from the zeros of QJs) and Qn_ r(s) of (9)
coincides with the complete root locus relative to the zeros of (s+ l)P,_ r(s) and
(s- l)P,_ i( - s), except for the graduation. It is immediately verified that in this
second locus the zeros of Q&s) and Q,_l(s) correspond to the points where
parameter k, in (19) is equal to + 1 or to - 1, respectively [notice that one of the
intersections of the locus with the imaginary axis occurs at the point at infinity
(23), which corresponds to the fact that Q,+ i(s) has a degree less than that of
Q&)1.

V. Conclusions
Resorting to the classical root locus technique allows one to prove the Routh
stability test in an elementary way and to gain a geometrical insight into the
corresponding algorithm.
The same technique may be applied to a wide variety of stability criteria for both
continuous- and discrete-time systems, thus providing a common framework for
many problems of polynomial zero location with respect to circles or lines.

References
(1) V. Singh, “A note on the Routh-Hurwitz criterion”, IEEE Trans. Aut. Control, Vol.
AC-23, pp. 83-84, 1978.
(2) K. P. White, Jr, “Technique fixation and the Routh-Hurwitz criterion”, IEEE Trans.
Aut. Control, Vol. AC-24, pp. 987-988, 1979.

Journal of the FranWin Institute

702 Pergamon Press plc
 Interpretation of the Routh Test

(3) M. M. Fahmy and J. O’Reilly, “A note on the Routh-Hurwitz test”, IEEE Trans.
Aut. Control, Vol. AC-27, pp. 483485, 1982.
(4) K. S. Yeung, “Routh-Hurwitz test under vanishing leading array elements”, IEEE
Trans. Aut. Control, Vol. AC-28, pp. 104-106, 1983.
(5) Y. Bistritz, “Direct bilinear Routh stability criteria for discrete systems”, Systems
Control Lett., Vol. 4, pp. 265-271, 1984.
(6) B. R. Barmish, “Invariance of the strict Hurwitz property for polynomials with
perturbed coefficients”, IEEE Trans. Aut. Control, Vol. AC-29, pp. 935-936, 1984.
(7) J. Feinstein, “The negative Routh test and its application to the cases of vanishing
leading elements and imaginary roots”, IEEE Trans. Aut. Control, Vol. AC-30,
pp. 164-165, 1985.
(8) S. D. Agashe, “A new general Routh-like algorithm to determine the number of RHP
roots of a real or complex polynomial”, IEEE Trans. Aut. Control, Vol. AC-30,
pp. 406-409, 1985.
(9) S. Barnett and D. D. Siljak, “Routh algorithm: A centennial survey”, SIAM Rev.,
Vol. 19, pp. 472489, 1977.
(10) A. Bultheel and M. Van Barel, “Padi: techniques for model reduction in linear system
theory: a survey”, J. Comput. appl. Math., Vol. 14, pp. 401438, 1986.
(11) A. Lepschy, G. A. Mian and U. Viaro, “System approximation by matching the
impulse response energies”, J. Franklin Inst., Vol. 325, No. 1, pp. 17-26, 1988.
(12) A. Lepschy, G. A. Mian and U. Viaro, “Stability preservation and computational
aspects of a newly proposed reduction method”, IEEE Trans. Aut. Control, Vol.
AC-33, pp. 307-310, 1988.
(13) E. J. Routh, “A Treatise on the Stability of a Given State of Motion”, Macmillan,
London, 1877.
(14) E. J. Routh, “The Advanced Part of a Treatise on the Dynamics of a Rigid Body”,
Macmillan, London, 1905 (6th edn) .
(15) F. R. Gantmacher, “The Theory of Matrices”, Vol. 2, Chelsea, New York, 1959.
(16) P. C. Parks, “A new proof of the Routh-Hurwitz stability criterion using the second
method of Liapunov”, Proc. Cambridge Philos. Sot., Vol. 58, pp. 694-702, 1962.
(17) W. R. Evans, “Control-System Dynamics”, McGraw-Hill, New York, 1954.
(18) A. V. 0. Mikhailov, “A new method of study of feedback control systems” (in
Russian), Automat. Telemekh., Vol. 1, 1938.
(19) A. Lepschy and U. Viaro, “Proprieta di una famiglia di polinomi associati ad una
tabella di Routh”, Atti Accad. Patavina, Cl. SC. Mat. Natur., Vol. 94, pp. 5-21,
1982.
(20) E. I. Jury, “Theory and Application of the z-Transform Method”, John Wiley, New
York, 1964.
(21) A. Lepschy, G. A. Mian and U. Viaro, “An alternative proof of the Jury-Marden
stability criterion”, Int. Co& Lin. Algebra and Appl., 28-30 Sept., Valencia, Spain,
1987.
(22) A. Lepschy, G. A. Mian and U. Viaro, “A stability test for cont’lnuous systems”,
Systems Control Lett., Vol. 10, pp. 175-179, 1988.
(23) A. Lepschy and U. Viaro, “Some properties of complete root loci”, Alta Frequenza,
Vol. 52, pp. 297-299, 1983.

Vol. 325, No. 6, pp. 69S703, 1988

Printed in Great Britain 703