Vector Spaces of Generalized Linearizations for Rectangular Matrix Polynomials

The seminal work by Mackey et al. in 2006 (reference [21] of the article) introduced vector spaces of matrix pencils, with the property that almost all the pencils in the spaces are strong linearizations of a given square regular matrix polynomial. This work was subsequently extended by De Ter\'an et al. in 2009 (reference [5] of the article) to include the case of square singular matrix polynomials. We extend this work to non-square matrix polynomials by proposing similar vector spaces of rectangular matrix pencils that are equal to the ones introduced by Mackey et al. when the polynomial is square. Moreover, the properties of these vector spaces are similar to those in the article by De Ter\'an et al. for the singular case. In particular, the complete eigenvalue problem associated with the matrix polynomial can be solved by using almost every matrix pencil from these spaces. Further, almost every pencil in these spaces can be trimmed to form many smaller pencils that are strong linearizations of the matrix polynomial which readily solve the complete eigenvalue problem for the polynomial. These linearizations are easier to construct and are often smaller than the Fiedler linearizations introduced by De Ter\'an et al. in 2012 (reference [7] of the article). Further, the global backward error analysis by Dopico et al. in 2016 (reference [10] of the article) applied to these linearizations, shows that they provide a wide choice of linearizations with respect to which the complete polynomial eigenvalue problem can be solved in a globally backward stable manner.