Eigendecompositions

We discuss four eigendecompositions, or four pencils that are equivalent to $A - \lambda B$ and for which it is simpler to solve eigenproblems. This section is analogous to §2.5.4.

The first eigendecomposition, diagonal form, exists only when there are $n$ independent eigenvectors. The second one, Weierstrass form, generalizes diagonal form to all pencils where the characteristic polynomial $p(\lambda)$ is not identically 0. We can also describe the Weierstrass form as the generalization of the Jordan form matrices to pencils. The Weierstrass form, like the Jordan form, can be very ill-conditioned (indeed, it can change discontinuously), so for numerical purposes we typically use the third one, generalized Schur form, which is cheaper and more stable to compute. We briefly mention a fourth one, which we call the Weierstrass-Schur form, that is as stable as the Schur form but computes some of the detailed information about deflating subspaces provided by the Weierstrass form.

Define $\Lambda = {\rm diag}(\lambda_1 ,\ldots, \lambda_n )$. If there are $n$ independent right eigenvectors $x_1,\ldots,x_n$, we define $X = [x_1,\ldots,x_n]$. $X$ is called a (right) eigenvector matrix of $A$. Similarly let $Y = [y_1,\ldots,y_n]$ be a left eigenvector matrix. The $2n$ equalities $A x_i = \lambda_i B x_i$ and $y_i^* A = \lambda_i y_i^* B$ for $i=1,\ldots,n$ may also be written $AX = BX \Lambda$ and $Y^*A = \Lambda Y^* B$. $X$ and $Y$ may furthermore be chosen so that $Y^*AX = \Lambda_A$ and $Y^*BX = \Lambda_B$ are both diagonal, and $\Lambda = \Lambda_A \Lambda_B^{-1}$.The factorization

$$A - \lambda B = Y^{-*} ( \Lambda_A - \lambda \Lambda_B) X^{-1}$$

is called the diagonal form of $A - \lambda B$. In this case we call $A - \lambda B$ diagonalizable.

If we take a subset of $k$ columns of $X$ and of $Y$ (say $\hat{X}= X(:,[2,3,5])$ = columns 2, 3, and 5 and $\hat{Y}= Y(:,[2,3,5])$) then these columns span a pair of deflating subspaces of $A - \lambda B$. If we take the corresponding submatrices $\hat{\Lambda}_A = {\rm diag}(\lambda_{A,2} , \lambda_{A,3} , \lambda_{A,5} )$ and $\hat{\Lambda}_B = {\rm diag}(\lambda_{B,2} , \lambda_{B,3} , \lambda_{B,5} )$, then we can write the corresponding partial diagonal form as $\hat{Y}^* A \hat{X}= \hat{\Lambda}_A$ and $\hat{Y}^* B \hat{X}= \hat{\Lambda}_B$. If the columns in $\hat{X}$ and $\hat{Y}$ are replaced by $k$ different vectors spanning the same deflating subspaces, then we get a different partial eigendecomposition $\check{Y}^* A \check{X}= \check{A}$ and $\check{Y}^* B \check{X}= \check{B}$, where $\check{A}- \lambda \check{B}$ is a $k$ by $k$ pencil whose eigenvalues are those of $\hat{\Lambda}= \Lambda_A \Lambda_B^{-1}$, though $\check{A}- \lambda \check{B}$ may not be diagonal. Similar procedures for producing partial eigendecompositions work for the other eigendecompositions discussed below.

If all the $\lambda_i$ are distinct, then there are $n$ independent eigenvectors, and the diagonal form exists. This is the simplest and most common case. For example, if one picks $A$ and $B$ ``at random,''the probability is 1 that the eigenvalues are distinct.

A diagonal form of the pencil $A(0) - \lambda I$ in (2.3) in §2.5.4 does not exist, since it has just one independent eigenvector. Instead, we can compute its Weierstrass form, which is a decomposition

$$A - \lambda B = Y^{-*}(J_A - \lambda J_B)X^{-1},$$

where $J_A - \lambda J_B$ is a block-diagonal pencil, with one or more upper triangular diagonal blocks for each eigenvalue. When there are no infinite eigenvalues, this is identical to the Jordan form discussed in §2.5.4. When there are infinite eigenvalues, there are blocks quite similar to Jordan blocks with a single infinite eigenvalue and one right and left eigenvector.It can be shown that the Weierstrass form explicitly describes all possible deflating subspaces of $A - \lambda B$ as being spanned by certain subsets of the columns of $X$ and $Y$ [187].

Unfortunately, the Weierstrass form is generally not suitable for numerical computation, for the same reason that the Jordan form is not suitable. See §2.5.4 for discussion.

So instead we use eigendecompositions of the form

$$A - \lambda B = Z(T_A - \lambda T_B)Q^*,$$

where $Q$ and $Z$ are unitary (or orthogonal) matrices and $T_A - \lambda T_B$ is triangular (or quasi-triangular). This is called the generalized Schur form of $A - \lambda B$. When $A - \lambda B$ is complex, or real with all real or infinite eigenvalues, then $T_A - \lambda T_B$ is triangular with the eigenvalues of $A - \lambda B$ on its diagonal. When $A - \lambda B$ is real with complex eigenvalues and $Q$ is real and orthogonal, then $T_A - \lambda T_B$ cannot be real and triangular. Instead, we allow 2 by 2 blocks with complex eigenvalues to appear on the diagonal of $T_A - \lambda T_B$, which we call quasi-triangular form. For simplicity of presentation, we will consider the complex case, so that $T_A - \lambda T_B$ is triangular. Let $\lambda_1 = T_{A,11}/T_{B,11} ,\ldots, \lambda_n = T_{A,nn}/T_{B,nn}$ be the eigenvalues in the order they appear on the diagonal of $T$; there is a (different) generalized Schur form for every order. The columns of $Q$ and $Z$ are called generalized Schur vectors. The generalized Schur form does not give explicit eigenvectors and bases for all deflating subspaces the way diagonal form and Weierstrass form do, but it can be computed quite stably. The leading $k$ columns of $Q$ and of $Z$ do span the right and left deflating subspaces for eigenvalues $\lambda_1$ through $\lambda_k$, but all other eigenspaces require a computation. For example, right eigenvectors can be computed simply by solving a triangular system of equations taken from $T_A - \lambda T_B$ and multiplying by $Q$.

Finally, we consider the Weierstrass-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 Weierstrass form, it explicitly shows what the sizes of the (Jordan) blocks are and gives explicit bases for many more invariant subspaces than the Schur form.

Many textbooks give explicit solutions for problems such as solving ordinary differential equations $B \dot{x} (t) = A x(t)$ in terms of the Weierstrass form of $A - \lambda B$ [114]. These methods are to be avoided numerically, because of the difficulty of computing the Weierstrass form. Nearly all these problems have alternative solutions in terms of the generalized Schur form, or in some cases the Weierstrass-Schur form.