On the Smith Normal Form of Structured Polynomial Matrices

The Smith normal form of a polynomial matrix $D( s ) = Q( s ) + T( s )$ is investigated, where $D( s )$ is “structured” in the sense that (i) the coefficients of the entries of $Q( s )$ belong to a field ${\bf K}$, (ii) the nonzero coefficients of the entries of $T( s )$ are algebraically independent over ${\bf K}$, and (iii) every minor of $Q( s )$ is a monomial in s. Such matrices have been useful in the structural approach in control theory. It is shown that all the invariant polynomials except for the last are monomials in s and the last invariant polynomial is expressed in terms of the combinatorial canonical form (CCF) of a layered mixed matrix associated with $D( s )$. On the basis of this, the Smith form of $D( s )$ can be computed by means of an efficient (polynomial-time) matroid-theoretic algorithm that involves arithmetic operations in the base field ${\bf K}$ only.