next up previous contents index
Next: Generic and Nongeneric Kronecker Up: Singular Matrix Pencils   Previous: Regular Versus Singular Problems   Contents   Index


Kronecker Canonical Form

Just as the Jordan canonical form (JCF) describes the invariant subspaces and eigenvalues of a square matrix $A$ in full detail, there is a Kronecker canonical form (KCF) which describes the generalized eigenvalues and generalized eigenspaces of a pencil $A - \lambda B$ in full detail. In addition to Jordan blocks for finite and infinite eigenvalues, the Kronecker form contains singular blocks corresponding to minimal indices of a singular pencil (see below).

The KCF of $A - \lambda B$ exhibits the fine structure elements, including elementary divisors (Jordan blocks) and minimal indices (singular blocks), and is defined as follows [187]. Suppose $A, B \in {\cal C}^{m \times n}$. Then there exist nonsingular $P \in {\cal C}^{m \times m}$ and $Q \in {\cal C}^{n \times n}$ such that P^-1 (A - B)Q = Ã - B diag( A_1 - B_1 , ..., A_b - B_b ) , where $A_{i} - \lambda B_{i}$ is $m_i \times n_i$. We can partition the columns of $P$ and $Q$ into blocks corresponding to the $b$ diagonal blocks of $\tilde{A}- \lambda \tilde{B}$:

\begin{displaymath}
P=[ P_1 , \ldots , P_b ] \quad \mbox{and} \quad
Q=[ Q_1 , \ldots , Q_b ],
\end{displaymath}

where $P_i$ is $m \times m_i$, and $Q_i$ is $n \times n_i$, such that

\begin{displaymath}
(A - \lambda B) Q_i = P_i (A_{i} - \lambda B_{i}).
\end{displaymath}

Each block $M_i \equiv A_{i} - \lambda B_{i}$ must be of one of the following forms:

\begin{displaymath}
J_j ( \alpha ), \quad N_j, \quad L_j, \quad \mbox{or} \quad L_j^T.
\end{displaymath}

First we consider J_j ( ) cccc - & 1 & &
& & &
& & & 1
& & & - and N_j cccc 1 & -& &
& & &
& & & -
& & & 1 . $J_j ( \alpha )$ is simply a $j\times j$ Jordan block, and $\alpha$ is called a finite eigenvalue. A Jordan block $J_j ( \alpha )$ is a cyclic transformation. The range is generated by the $j$th unit vector $e_j$--the vectors of the Krylov sequence

\begin{displaymath}\{ e_j, J_j( \alpha ) e_j, J_j( \alpha )^2 e_j, \ldots, J_j( \alpha )^{j-1} e_j \}\end{displaymath}

span the range. From the cyclicity of the transformation we get the vector chain relations

\begin{displaymath}(J_j ( \alpha ) - (\alpha - \lambda)I) e_{k+1} = e_k \quad
{\rm for} \quad 1 \leq k \leq j-1.\end{displaymath}

The vector $ e_{k+1}$ is said to be a principal vector of grade $k+1$. The order $j$ is often referred to as the height of the chain. The eigenvectors are principal vectors of grade $1$.

$N_j$ is a $j\times j$ block corresponding to an infinite eigenvalue of multiplicity $j$:

\begin{displaymath}
N_j = \bmat{cccc}
1 & 0 & & \\
& \ddots & \ddots & \\
&...
...
& \ddots & \ddots & \\
& & \ddots & 1 \\
& & & 0 \emat.
\end{displaymath}

By exchanging the $A$-part and $B$-part of $N_j$ we get a $J_j(0)$ block. So if the KCF of $\{A,B\}$ has an $N_j$ block in its KCF, then $\{B,A\}$ has a $J_j(0)$ block in its KCF and vice versa. This fact is utilized in algorithms for computing canonical structure of matrix pencils.

The $J_j ( \alpha )$ and $N_j$ blocks together constitute the regular structure of the pencil. All the $A_{i} - \lambda B_{i}$ are regular blocks if and only if $A - \lambda B$ is a regular pencil. $\lambda(A, B)$ denotes the eigenvalues of the regular part of $A - \lambda B$ (counted with multiplicities) and is called the spectrum of $A - \lambda B$.

The other two types of diagonal blocks are L_j cccc - & 1 & &
& & &
& & - & 1 and L_j^T ccc -& &
1 & &
& & -
& & 1 . The $j \times (j+1)$ block $L_j$ is called a singular block of right (or column) minimal index $j$. It has a one-dimensional right null space, $[1, \lambda, \ldots, {\lambda}^j]^T$, for any $\lambda$, i.e.,

\begin{displaymath}
\bmat{ccccc}
- \lambda & 1 & & &\\
&- \lambda & 1 & & \\
...
...s \\ {\lambda}^j \emat =
\bmat{c} 0 \\ 0 \\ \vdots \\ 0 \emat.
\end{displaymath}

Similarly, the $(j+1) \times j$ block $L_j^T$ is a singular block of left (or row) minimal index $j$ and has a one-dimensional left null space for any $\lambda$. The left and right singular blocks together constitute the singular structure of the pencil and appear in the KCF if and only if the pencil is singular. The regular and singular structures define the Kronecker structure of a singular pencil.

We end this introductory description by briefly pointing to the relationship between structure information of the KCF and the GUPTRI form (8.28). The block $A_r - \lambda B_r$ contains all information about the right singular blocks and $A_l - \lambda B_l$ contains all information about the left singular blocks. The regular part corresponds to $ A_{reg} - \lambda B_{reg}$.


next up previous contents index
Next: Generic and Nongeneric Kronecker Up: Singular Matrix Pencils   Previous: Regular Versus Singular Problems   Contents   Index
Susan Blackford 2000-11-20