Efficient transformation of certain singular polynomial matrix eigenvalue problems

Several transformations of the singular (|A_r| =0) n x n polynomial matrix eigenvalue problem (A_rλ^r+A_r-1λ^r-1 + ...+A₁λ+A₀)x = 0 of degree r, where A_r has k<n nonzero rows, are described. The transformed problems are either of degree one, order r(n - 1) + k, and usually (in a sense made precise) nonsingular, or of degree r-1, order n + k, and singular. For a wide range of k, n, and r, the transformed problems can be solved more efficiently than the original problem of degree r and order n.