The conditioning of linearizations of matrix polynomials

Abstract. The standard way of solving the polynomial eigenvalue problem of degree m in n×n matrices is to “linearize ” to a pencil in mn×mn matrices and solve the generalized eigenvalue prob-lem. For a given polynomial, P, infinitely many linearizations exist and they can have widely varying eigenvalue condition numbers. We investigate the conditioning of linearizations from a vector space DL(P) of pencils recently identified and studied by Mackey, Mackey, Mehl, and Mehrmann. We look for the best conditioned linearization and compare the conditioning with that of the original polynomial. Two particular pencils are shown always to be almost optimal over linearizations in DL(P) for eigenvalues of modulus greater than or less than 1, respectively, provided that the prob-lem is not too badly scaled and that the pencils are linearizations. Moreover, under this scaling assumption, these pencils are shown to be about as well conditioned as the original polynomial. For quadratic eigenvalue problems that are not too heavily damped, a simple scaling is shown to convert the problem to one that is well scaled. We also analyze the eigenvalue conditioning of the widely used first and second companion linearizations. The conditioning of the first companion linearization relative to that of P is shown to depend on the coefficient matrix norms, the eigenvalue, and the left eigenvectors of the linearization and of P. The companion form is found to be potentially much mor