Polynomial Zigzag Matrices, Dual Minimal Bases, and the Realization of Completely Singular Polynomials

Minimal bases of rational vector spaces are a well known and important tool in systems theory. If minimal bases for two subspaces of rational n-space are displayed as the rows of polynomial matrices Z1(λ)k×n and Z2(λ)m×n, respectively, then Z1 and Z2 are said to be dual minimal bases if the subspaces have complementary dimension, i.e., k+m = n, and Z1(λ)Z T 2 (λ) = 0. In other words, each Zj(λ) provides a minimal basis for the nullspace of the other. It has long been known that for any dual minimal bases Z1(λ) and Z2(λ), the row degree sums of Z1 and Z2 are the same. In this paper we show that this is the only constraint on the row degrees, thus characterizing the possible row degrees of dual minimal bases. The proof is constructive, making extensive use of a new class of sparse, structured polynomial matrices that we have baptized zigzag matrices. Another application of these polynomial zigzag matrices is the constructive solution of the following inverse problem for minimal indices – given a list of left and right minimal indices and a desired degree d, does there exist a completely singular matrix polynomial (i.e., a matrix polynomial with no elementary divisors whatsoever) of degree d having exactly the prescribe