A Pencil Approach for Embedding a Polynomial Matrix into a Unimodular matrix

Abstract

In this paper a new method for constructing the unimodular embedding of a polynomial matrix $P( \lambda )$ is derived. As proposed by Eising, the problem can be transformed to one of embedding a pencil, derived from the polynomial matrix $P( \lambda )$. The actual embedding of the pencil is performed here via the staircase form of this pencil, which shortcuts Eising’s construction. This then leads to a new, fast, and numerically reliable algorithm for embedding a polynomial matrix. The new method uses a fast variant of the staircase algorithm and only requires $O( p^3 )$ operations in contrast to the $O( p^4 )$ methods proposed up to now (where p is the largest dimension of the pencil). At the same time we also treat the connected problem of finding the (right) null space and (right) inverse of a polynomial matrix $P( \lambda )$.