Generalized Bezoutians and families of efficient zero-location procedures

It is shown that the procedures of Routh-Hurwitz and Schur-Cohn for determining the zero-distribution of polynomials with respect to the imaginary axis and the unit circle, respectively, serve, at the same time, to efficiently evaluate the inertia of certain so-called Bezoutian matrices. These procedures require O(n²) operations to determine the inertia of an n×n Bezoutian, in contrast to the O(n³) operations that would be required to determine the inertia of an arbitrary (Hermitian) matrix of the same size. Generalized Bezoutians whose inertia specifies the zero-distribution with respect to arbitrary circles and straight lines in the complex plane are introduced. These Bezoutian matrices are shown to be members in the family of matrices with (generalized) displacement structure, for which efficient O(n²) procedures for triangular factorization exist and, hence, inertial determination. The formulation displays a large variety of O(n²) procedures that can be associated with a single (generalized) Bezoutian matrix. For Bezoutians on the imaginary axis and the unit circle, the formulation leads to (among other possibilities) the Routh-Hurwitz and Schur-Cohn tests