Euclid algorithm, orthogonal polynomials, and generalized Routh-Hurwitz algorithm (Q1816934)

This paper, which is based on control-systems engineering, begins with a review of the classical Euclidean algorithm to find the gcd of two univariate polynomials over a field. The algorithm is said to be regular if all the quotient polynomials have degree one, otherwise it is singular. In the case of real coefficients, the relationship of the algorithm to orthogonal polynomials and Sturm's theorem is outlined. The main thrust of the paper is to lift the restriction to real coefficients. Let a bar denote complex conjugation. Let \(P(p)\) be any complex polynomial of degree \(n\) and define \[ \begin{aligned} P_0(p) & =\textstyle {{1\over 2}} \bigl[P(p) +(-1)^n \overline P(-\overline p) \bigr], \\ P_1(p) & = \textstyle {{1\over 2}} \bigl[P(p) -(-1)^n \overline P(-\overline p) \bigr], \end{aligned} \] which are often called the paraeven and paraodd parts of \(P(p)\). The leading coefficient of \(P_0(p)\) may be assumed to be pure real so that \(\deg P_0= n>\deg P_1\). Then the generalized Routh-Hurwitz algorithm is defined to be the Euclidean algorithm applied to \(P_0(p)\), \(P_1(p)\), i.e. \(P_{i-1} (p)= q_i(p) P_i(p) + P_{i+1} (p)\) for \(i=1,2, \dots, n'\), with \(n'\leq n\) and \(P_{n'+1} (p)=0\), extended as follows to handle singular cases. If there exists some value of \(i\), say \(i_0\), for which \(\deg P_{i_0} >0\) and \(P_{i_0+1} (p)=0\) then replace the ``missing'' polynomial by \(P_{i_0+1} (p): =dP_{i_0} (p)/ dp\) and continue the algorithm. Denote by \(i_0,i_1, \dots, i_{s-1}\) the sequence of indices for which this occurs. The quotient polynomials can be expanded as \(q_i(p)= -j \sum^{\mu_i}_{s=0} q_{i,s} (jp)^{\mu_i-s}\), where \(j= \sqrt {-1}\), \(\mu_i= \deg q_i\) and all the coefficients \(q_{i,s}\) are real numbers. Only the leading coefficients \(q_{i,0}\) are used in the following. Let \(N(P) \), \(N_0(P)\), \(\overline N(P)\) denote respectively the number of zeros of \(P(p)\) with \(\text{Re} p>0\), \(=0\), \(<0\). Then the following theorem is deduced. 1. The zeros of polynomial \(P (p)\) are distributed in the complex plane as follows: \[ \begin{aligned} N(P) & = {1\over 2} \left(n- \sum^{n '}_{{i=1 \atop \mu_i \text{odd}}} \text{sgn} q_{i,0} \right), \\ N_0(P) & = \sum^{n'}_{{i=i_0+1 \atop \mu_i \text{odd}}} \text{sgn} q_{i,0}, \\ \overline N(P) & = {1\over 2} \left(n+ \sum^{i_0}_{ {i=1 \atop \mu_i \text{odd}}} \text{sgn} q_{i,0}- \sum^{n'}_{{i=i_0+1 \atop\mu_i \text{odd}}} \text{sgn} q_{i,0} \right). \end{aligned} \] 2. \(P(p)\) admits the factorization \(P(p)= {\mathbf P}(p) {\mathcal P} (p)\) with \({\mathcal P} (p)= P_{i_0} (p)\) and \({\mathbf P} (p)= P(p)/{\mathcal P} (p)\); moreover, \({\mathcal P} (p)\) is paraeven or paraodd, and its only zeros are precisely the paraconjugate zeros of \(P(p)\). The zero distributions of \({\mathbf P} (p)\) and \({\mathcal P} (p)\) are given by formulae similar to those above. 3. The paraeven or paraodd part \({\mathcal P} (p)\) of \(P(p)\) is itself (squarefree) factorizable as \[ {\mathcal P} (p)= C\pi_1(p) \pi^2_2 (p) \cdots \pi_s^s (p) \] with \(\pi_k(p) =P_{i_k-1} (p)P_{i_k+1} (p)/P^2_{i_k} (p)\) for \(k=1,2, \dots, s-1\) and \(\pi_s(p) =P_{i_s-1} (p)/P_{i_s} (p)\); moreover, the polynomial factors \(\pi_k(p)\) are pairwise coprime and their zeros are distributed as follows: \[ \begin{aligned} N(\pi_k) & = \overline N(\pi_k) ={\deg \pi_k-N_0 (\pi_k) \over 2}, \\ N_0 (\pi_k) & = \sum^{i_k}_{{i=i_{k-1} +1 \atop \mu_i \text{odd}}} \text{sgn} q_{i,0} -\sum^{i_{k+1}}_{{i=i_k+ 1 \atop \mu_i \text{odd}}} \text{sgn} q_{i,0}. \end{aligned} \] The generalized algorithm is no more complex than the standard algorithm and it does not have any singular cases. Some essentially well known polynomial zero criteria are derived as corollaries of the above theorem. The generalized Routh-Hurwitz algorithm also leads to two further results that are believed to be original. A polynomial \(G(p)\) satisfies \(G(p)\geq 0\) on \(\text{Re} p=0\) if and only if 1) \(G(p)\) is paraeven of even degree \(n\), 2) its leading coefficient \(g_0\) satisfies \((-1)^{n/2} g_0>0\), 3) the generalized Routh-Hurwitz algorithm applied to \(P_0(p) =G(p)\), \(P_1(p) =dG(p)/dp\) generates quotient polynomials \(q_i(p)\) of degree \(\mu_i\) satisfying \[ \sum^{i_k}_{i=i_{k-1} +1 \atop \mu_i \text{odd}} \text{sgn} q_{i,0} =\begin{cases} \sum^{i_{k+1}}_{i=i_k+1 \atop \mu_i \text{odd}} \text{sgn} q_{i,0} \quad & \text{for all } k\text{ odd, } k\leq s-1, \\ 0 \quad & \text{for } k=s \text{ odd}. \end{cases} \] A rational function \(Z(p)= B(p)/A(p)\), with \(A(p)\) and \(B(p)\) coprime polynomials, is positive (real) if and only if 1) \(G(p)= A(p) \overline B(-\overline p) +B(p) \overline A(- \overline p)\) is nonnegative almost everywhere on \(\text{Re} p =0\), 2) \(P(p) =A (p) +B(p)\) is a strict-sense Hurwitz polynomial, i.e. it has no zeros in the closed right half plane \(\text{Re} p \geq 0\). An example is given. These characterizations are claimed to be more efficient than the ``classical'' versions.