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

In this paper a new method for constructing the unimodular embedding of a polynomial matrix P( λ ) is derived. As proposed by Eising, the problem can be transformed to one of embedding a pencil, derived from the polynomial matrix P( λ ). 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³ ) operations in contrast to the O( p⁴ ) 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( λ ).