On computing root polynomials and minimal bases of matrix pencils

We revisit the notion of root polynomials, thoroughly studied in (Dopico and Noferini, 2020 [9]) for general polynomial matrices, and show how they can efficiently be computed in the case of a matrix pencil λE+A. The method we propose makes extensive use of the staircase algorithm, which is known to compute the left and right minimal indices of the Kronecker structure of the pencil. In addition, we show here that the staircase algorithm, applied to the expansion (λ−λ₀)E+(A−λ₀E), constructs a block triangular pencil from which a minimal basis and a maximal set of root polynomials at the eigenvalue λ₀, can be computed in an efficient manner.