Next: Generalized Schur-Staircase Form Up: Singular Matrix Pencils   Previous: Generic and Nongeneric Kronecker   Contents   Index

## Ill-Conditioning

Singular pencils may or may not have eigenvalues. Indeed, the generic case corresponds to a singular pencil that has no eigenvalues. Below we illustrate this with two 3 by 3 examples:

Obviously, and for all . Although both pencils have the same diagonal elements they have very different canonical forms. Indeed, both pencils are in KCF: and . From top to bottom, the diagonal blocks of correspond to , diag(), and . So has a regular part of size with eigenvalues at zero () and infinity () and a singular part of size corresponding to one block (of size ) and one block, while is a generic singular pencil with no regular part.

If is upper triangular and a zero element appears on the diagonal, then the pencil is singular. We see that both examples have this property (the entries of and are zero as well as for and ). This situation will appear if we apply the QZ algorithm to a square singular pencil in infinite precision. Such a pair (, ) = (0, 0) is called an indeterminate eigenvalue 0/0. In the presence of roundoff, the QZ algorithm may fail to detect and isolate the singularity due to the ill-conditioning of the problem as illustrated below.

The eigenvalue problem for a singular pair is much more complicated than for a regular pair. Consider, for example, the singular pair

which has one finite eigenvalue 1 and one indeterminate eigenvalue 0/0 (corresponding to a singular part diag()). To see that neither the eigenvalue 1 nor the singular part is well determined by the data, consider the slightly perturbed problem

where the are tiny nonzero numbers. It follows that is regular with eigenvalues and . Given any two complex numbers and , we can find arbitrary tiny such that and are the eigenvalues of . Since, in principle, roundoff could change to , we cannot hope to compute accurate or even meaningful eigenvalues of singular problems, without further information. Typically, this information includes restrictions of allowable perturbations so that unperturbed and perturbed problems have similar structural characteristics. For this example the regularization requires that the perturbed pencil also have a regular part and a singular part.

A well-known class of singular pencils is the class of matrix pairs with intersecting null spaces. Let belong to the intersection of the null spaces of and , i.e., . Then for any , we have , implying that the pair is singular. By inspection we see that and above have a common one-dimensional column (and row) null space spanned by . The dimensions of the intersecting column and row null spaces, respectively, are the number of and blocks, respectively, in the pencils' KCF. Notice that the intersection of null spaces of and is a sufficient but not a necessary condition for a pencil to be singular, as illustrated with in the first set of examples.

It is possible for a pair in Schur form to be very close to singular, and so to have very sensitive eigenvalues, even if no diagonal entries of or are small. It suffices for and to nearly have a common null space. For example, consider the matrices

Then has all eigenvalues at 1. Changing and to makes both and singular to machine precision, with a common null vector; i.e., there exists a unit vector such that . Then, using a technique analogous to the one applied to the example above, we can show that there is a perturbation of and of norm , for any , that makes the 16 perturbed eigenvalues have any prescribed complex values.

With these examples in mind we are ready to introduce the GUPTRI form and the regularization method used to compute meaningful and reliable information.

Next: Generalized Schur-Staircase Form Up: Singular Matrix Pencils   Previous: Generic and Nongeneric Kronecker   Contents   Index
Susan Blackford 2000-11-20