Derivation of the Routh array

The Routh array is a tabular method permitting one to establish the stability of a system using only the coefficients of the characteristic polynomial. Central to the field of control systems design, the Routh–Hurwitz theorem and Routh array emerge by using the Euclidean algorithm and Sturm's theorem in evaluating Cauchy indices.
The Cauchy index.
Given the system:
Assuming no roots of formula_2 lie on the imaginary axis, and letting
then we have
Expressing formula_8 in polar form, we have
where
and 
from (2) note that
where
Now if the ith root of formula_2 has a positive real part, then ()
and
and
Similarly, if the ith root of formula_18 has a negative real part,
and
and
From (9) to (11) we find that formula_22 when the ith root of formula_8 has a positive real part, and from (12) to (14) we find that formula_24 when the ith root of formula_8 has a negative real part. Thus,
So, if we define
then we have the relationship
and combining (3) and (17) gives us
Therefore, given an equation of formula_8 of degree formula_32 we need only evaluate this function formula_33 to determine formula_3, the number of roots with negative real parts and formula_5, the number of roots with positive real parts.
In accordance with (6) and Figure 1, the graph of formula_36 vs formula_37, varying formula_38 over an interval (a,b) where formula_39 and formula_40 are integer multiples of formula_41, this variation causing the function formula_42 to have increased by formula_41, indicates that in the course of travelling from point a to point b, formula_37 has "jumped" from formula_45 to formula_46 one more time than it has jumped from formula_46 to formula_45. Similarly, if we vary formula_38 over an interval (a,b) this variation causing formula_42 to have decreased by formula_41, where again formula_37 is a multiple of formula_41 at both formula_54 and formula_55, implies that formula_56 has jumped from formula_46 to formula_45 one more time than it has jumped from formula_45 to formula_46 as formula_38 was varied over the said interval.
Thus, formula_62 is formula_41 times the difference between the number of points at which formula_64 jumps from formula_46 to formula_45 and the number of points at which formula_64 jumps from formula_45 to formula_46 as formula_38 ranges over the interval formula_71 provided that at formula_72, formula_73 is defined.
In the case where the starting point is on an incongruity (i.e. formula_74, "i" = 0, 1, 2, ...) the ending point will be on an incongruity as well, by equation (17) (since formula_3 is an integer and formula_5 is an integer, formula_33 will be an integer). In this case, we can achieve this same index (difference in positive and negative jumps) by shifting the axes of the tangent function by formula_78, through adding formula_78 to formula_37. Thus, our index is now fully defined for any combination of coefficients in formula_8 by evaluating formula_82 over the interval (a,b) = formula_83 when our starting (and thus ending) point is not an incongruity, and by evaluating
over said interval when our starting point is at an incongruity.
This difference, formula_33, of negative and positive jumping incongruities encountered while traversing formula_38 from formula_87 to formula_88 is called the Cauchy Index of the tangent of the phase angle, the phase angle being formula_42 or formula_90, depending as formula_91 is an integer multiple of formula_41 or not.
The Routh criterion.
To derive Routh's criterion, first we'll use a different notation to differentiate between the even and odd terms of formula_8:
Now we have: 
Therefore, if formula_32 is even, 
and if formula_32 is odd:
Now observe that if formula_32 is an odd integer, then by (3) formula_101 is odd. If formula_101 is an odd integer, then formula_103 is odd as well. Similarly, this same argument shows that when formula_32 is even, formula_103 will be even. Equation (15) shows that if formula_103 is even, formula_37 is an integer multiple of formula_41. Therefore, formula_36 is defined for formula_32 even, and is thus the proper index to use when n is even, and similarly formula_111 is defined for formula_32 odd, making it the proper index in this latter case.
Thus, from (6) and (23), for formula_32 even:
and from (19) and (24), for formula_32 odd:
Lo and behold we are evaluating the same Cauchy index for both:
formula_117
Sturm's theorem.
Sturm gives us a method for evaluating formula_118. His theorem states as follows:
Given a sequence of polynomials formula_119 where:
1) If formula_120 then formula_121, formula_122, and formula_123
2) formula_124 for formula_125
and we define formula_126 as the number of changes of sign in the sequence formula_119 for a fixed value of formula_38, then:
A sequence satisfying these requirements is obtained using the Euclidean algorithm, which is as follows:
Starting with formula_130 and formula_131, and denoting the remainder of formula_132 by formula_133 and similarly denoting the remainder of formula_134 by formula_135, and so on, we obtain the relationships:
or in general 
where the last non-zero remainder, formula_138 will therefore be the highest common factor of formula_139. It can be observed that the sequence so constructed will satisfy the conditions of Sturm's theorem, and thus an algorithm for determining the stated index has been developed.
It is in applying Sturm's theorem (28) to (29), through the use of the Euclidean algorithm above that the Routh matrix is formed.
We get
and identifying the coefficients of this remainder by formula_141, formula_142, formula_143, formula_144, and so forth, makes our formed remainder 
where
Continuing with the Euclidean algorithm on these new coefficients gives us
where we again denote the coefficients of the remainder formula_148 by formula_149, formula_150, formula_151, formula_152,
making our formed remainder 
and giving us
The rows of the Routh array are determined exactly by this algorithm when applied to the coefficients of (20). An observation worthy of note is that in the regular case the polynomials formula_155 and formula_156 have as the highest common factor formula_157 and thus there will be formula_32 polynomials in the chain formula_119.
Note now, that in determining the signs of the members of the sequence of polynomials formula_160 that at formula_161 the dominating power of formula_162 will be the first term of each of these polynomials, and thus only these coefficients corresponding to the highest powers of formula_162 in formula_164, and formula_138, which are formula_166, formula_167, formula_141, formula_149, ... determine the signs of formula_130, formula_131, ..., formula_138 at formula_173.
So we get formula_174 that is, formula_175 is the number of changes of sign in the sequence formula_176, formula_177, formula_178, ... which is the number of sign changes in the sequence formula_166, formula_167, formula_141, formula_149, ... and formula_183; that is formula_184 is the number of changes of sign in the sequence formula_185, formula_186, formula_187, ... which is the number of sign changes in the sequence formula_166, formula_189, formula_141, formula_191, ... 
Since our chain formula_166, formula_167, formula_141, formula_149, ... will have formula_32 members it is clear that formula_197 since within formula_198 if going from formula_166 to formula_167 a sign change has not occurred, within 
formula_201 going from formula_166 to formula_189 one has, and likewise for all formula_32 transitions (there will be no terms equal to zero) giving us formula_32 total sign changes.
As formula_206 and formula_207, and from (18) formula_208, we have that formula_209 and have derived Routh's theorem -
The number of roots of a real polynomial formula_210 which lie in the right half plane formula_211 is equal to the number of changes of sign in the first column of the Routh scheme.
And for the stable case where formula_212 then formula_213 by which we have Routh's famous criterion:
In order for all the roots of the polynomial formula_210 to have negative real parts, it is necessary and sufficient that all of the elements in the first column of the Routh scheme be different from zero and of the same sign.