Generalized Schur-Staircase Form

In general, we cannot guarantee stable computation of the KCF of a pencil, since the transformation matrices that reduce $A - \lambda B$ to KCF can be arbitrarily ill-conditioned. However, it is possible to compute the Kronecker structure (or parts of it) using only unitary transformations. The price we have to pay is a denser canonical form, called a generalized Schur-staircase form. This form is block upper triangular with diagonal blocks in staircase form (also block upper triangular) that reveal the fine structure elements of the KCF.

In most applications it is enough to reduce $A - \lambda B$ to a generalized Schur-staircase form, e.g., to GUPTRI form [121,122]: P^ (A- B) Q = ccc A_r - B_r & * & *
0 & A_reg - B_reg & *
0 & 0 & A_l - B_l , where $P$ ($m \times m$) and $Q$ ($n \times n$) are unitary. Here the square upper triangular block $A_{reg} - \lambda B_{reg}$ is regular and has the same regular structure as $A - \lambda B$ (i.e., contains all finite and infinite eigenvalues of $A - \lambda B$). The rectangular block $A_r - \lambda B_r$ has only right minimal indices in its KCF--indeed the same $L_j$ blocks as $A - \lambda B$. Similarly, $A_l - \lambda B_l$ has only left minimal indices in its KCF, the same $L_j^T$ blocks as $A - \lambda B$. If $A - \lambda B$ is singular, at least one of $A_r - \lambda B_r$ and $A_l - \lambda B_l$ will be present in (8.34). If $A - \lambda B$ is regular, $A_r - \lambda B_r$ and $A_l - \lambda B_l$ are not present in (8.34) and the GUPTRI form reduces to $A_{reg} - \lambda B_{reg}$. Staircase forms that reveal the Jordan structure of the zero and infinite eigenvalues are contained in $A_{reg} - \lambda B_{reg}$: A_reg = ccc A_z & * & *
0 & A_f & *
0 & 0 & A_i ,          B_reg = ccc B_z & * & *
0 & B_f & *
0 & 0 & B_i .

In summary, the diagonal blocks of the GUPTRI form of $A - \lambda B$ describe the Kronecker structure as follows:

iAAAAAAA 		 $A_r - \lambda B_r$ has all right singular structure (the right minimal indices).  

$A_z - \lambda B_z$ has all Jordan structure for the zero eigenvalue. 

$A_f - \lambda B_f$ has all finite, nonzero eigenvalues. 

$A_i - \lambda B_i$ has all Jordan structure for the infinite eigenvalue.

$A_l - \lambda B_l$ has all left singular structure (the left minimal indices). 

The explicit structure of the diagonal blocks in staircase form is presented in the next section. The nonzero, finite eigenvalues of $A - \lambda B$ (if any) are in the block $A_f - \lambda B_f$ but their multiplicities or Jordan structures are not computed explicitly. However, it is possible to extract the Jordan structure of a finite, nonzero eigenvalue of $A - \lambda B$ by computing the $RZ$ (right-zero)-staircase form (see §8.7.6) of the shifted pencil $(A_f - {\lambda}_iB_f) - \lambda B_f$, which has zero as an eigenvalue of multiplicity $\geq 1$.

Given $A - \lambda B$ in GUPTRI form we also know different pairs of reducing subspaces [451,121]. Suppose the eigenvalues on the diagonal of $A_{reg} - \lambda B_{reg}$ are ordered so that the first $k$, say, are in $\Lambda_1$ (a subset of the spectrum) and the remainder are outside $\Lambda_1$. Then the GUPTRI form can also be expressed as P^ (A - B) Q = cc A_11 - B_11 & A_12 - B_12
0 & A_22 - B_22, where $A_{11} - \lambda B_{11}$ contains $A_r - \lambda B_r$ and the regular part corresponding to $\Lambda_1$, and $A_{22} - \lambda B_{22}$ contains the remaining regular part and $A_l - \lambda B_l$. If $A_r - \lambda B_r$ is $m_r \times n_r$, then the left and right reducing subspaces corresponding to $\Lambda_1$ are spanned by the leading $m_r + k$ columns of $P$ (denoted $P_1$) and the leading $n_r + k$ columns of $Q$ (denoted $Q_1$), respectively, such that

$$(A - \lambda B) Q_1 = P_1(A_{11} - \lambda B_{11}).$$

When $\Lambda_1$ is empty, the corresponding reducing subspaces are called minimal, and when $\Lambda_1$ contains the whole spectrum the reducing subspaces are called maximal. The computation of minimal and maximal reducing subspaces appears in several applications, e.g., computing controllable and observable subspaces of generalized linear systems, which represent ill-posed problems in control theory [447,120].