Estimating the Sensitivity of the Algebraic Structure of Pencils with Simple Eigenvalue Estimates

The sensitivity of the algebraic (Kronecker) structure of rectangular matrix pencils to perturbations in the coefficients is examined. Eigenvalueperturbation bounds in the spirit of Bauer-Fike are used to develop computational upper and lower bounds on the distance from a given pencil to one with a qualitatively different Kronecker structure. is a matrix with one more row than column, and J is a square matrix in Jordan Canonical Form. We call L a "tall-thin" K-block, LT a "short-fat" K-block, and J the "regular" part. In this paper, we deal exclusively with tall-thin pencils. Such pencils always have at least n −p tall-thin K-blocks. In (3), we showed that the set of all tall-thin pencils with only tall-thin K-blocks is open and dense in the set of all pencils of the same shape. Hence, given a tall-thin pencil, the question we attempt to address is if it has any other types of K-blocks, and if not, what is the distance to the nearest pencil which does. In (15) and (10), algorithms were proposed that compute the complete KCF for a given pencil guaranteed to be exact for a pencil close to the original given pencil (backward stable). If the KCF computed in this way has only tall-thin K-blocks (the "generic case"), then one is still left with determining how far it is from a pencil with other types of K-blocks. In this paper, we attempt to estimate this distance from both above and below. A detailed algebraic analysis for square pencils was given by Waterhouse (17), but beyond that surprisingly little has been found in the literature on this topic.