Next: Conditioning Up: Non-Hermitian Eigenproblems  J. Demmel Previous: Equivalences (Similarities)   Contents   Index

## Eigendecompositions

We discuss four eigendecompositions, or four matrices that are similar to and for which it is simpler to solve eigenproblems. The first one, diagonal form, exists only when there are independent eigenvectors. The second one, Jordan form, generalizes diagonal form to all matrices. It can be very ill-conditioned (indeed, it can change discontinuously), so for numerical purposes we typically use the third one, Schur form, which is cheaper and more stable to compute. We briefly mention a fourth one, which we call Jordan-Schur form, that is as stable as the Schur form but computes some of the detailed information about invariant subspaces provided by the Jordan form.

Define . If there are independent right eigenvectors , we define . is called an eigenvector matrix of . The equalities for may also be written or . The factorization

is called the diagonal form of . Note that . Letting denote the th row of , we see that . In other words, the rows of are the left eigenvectors of . Thus, if has independent eigenvectors, then it is similar to the diagonal matrix . In this case we call diagonalizable.

If we take a subset of columns of (say = columns 2, 3, and 5), these columns span an invariant subspace of . If we take the corresponding submatrix of , and the corresponding three rows of (say ), we can write the corresponding partial diagonal form as or . If the columns in are replaced by different vectors spanning the same invariant subspace, we get a different partial eigendecomposition , where is a by matrix whose eigenvalues are those of , though may not be diagonal. Similar procedures for producing partial eigendecompositions for the other eigendecompositions discussed below.

If all the are distinct, there are independent eigenvectors, and the diagonal form exists. This is the simplest and most common case. For example, if one picks a matrix at random,''the probability is 1 that the eigenvalues are distinct.

A diagonal form of the matrix in (2.3) does not exist, since it has just one independent eigenvector. Instead, we can compute its Jordan form, which is a decomposition

where is a block-diagonal matrix, i.e., a matrix of the form , where each is a square matrix called a Jordan block. Each is upper triangular with its single eigenvalue on the diagonal, and ones on the first superdiagonal. has a single independent right and left eigenvector. is a 2 by 2 Jordan block with its single eigenvalue at 0, and is a 2 by 2 Jordan block with its single eigenvalue at . It can be shown that the Jordan form explicitly describes all possible invariant subspaces of as being spanned by certain subsets of the columns of [187].

Unfortunately, the Jordan form is generally not suitable for numerical computation. Here are two reasons. First, it can change discontinuously as changes. For example, the matrix for with is , but for , itself. Second, the eigenvector matrix can be very ill-conditioned, i.e., hard to invert accurately. In the case of , the condition number of grows like .

So instead we use eigendecompositions of the form

where is a unitary (or orthogonal) similarity transformation, and is triangular (or quasi-triangular). This is called the Schur form of . When is complex, or real with all real eigenvalues, then is triangular with the eigenvalues of on its diagonal. When is real with complex eigenvalues and is real and orthogonal, then cannot be real and triangular. Instead, we allow 2 by 2 blocks with complex eigenvalues to appear on the diagonal of , which we call quasi-triangular form. For simplicity of presentation, we will consider the complex case, so that is triangular. Let be the eigenvalues in the order they appear on the diagonal of ; there is a (different) Schur form for every order. The columns of are called Schur vectors. The Schur form does not give explicit eigenvectors and bases for all invariant subspaces the way diagonal form and Jordan form do, but it can be computed quite stably. The leading columns of span the invariant subspace for eigenvalues through , but all other eigenspaces require a computation. For example, eigenvectors can be computed simply by solving a triangular system of equations taken from , and multiplying by [114].

Finally, we consider the Jordan-Schur form. It is quite complicated, so we only summarize its properties here. Like the Schur form, it only uses unitary (orthogonal) transformation, and so can be computed stably. Like the Jordan form, it explicitly shows what the sizes of the Jordan blocks are and gives explicit bases for many more invariant subspaces than Schur form.

Many textbooks give explicit solutions for problems such as computing the matrix of the exponential in terms of the Jordan form of [114]. These methods are to be avoided numerically, because of the difficulty of computing the Jordan form. Nearly all these problems have alternative solutions in terms of the Schur form, or in some cases the Jordan-Schur form.

Next: Conditioning Up: Non-Hermitian Eigenproblems  J. Demmel Previous: Equivalences (Similarities)   Contents   Index
Susan Blackford 2000-11-20