Next: A Singular Pencil in Up: Singular Matrix Pencils   Previous: Generalized Schur-Staircase Form   Contents   Index

## GUPTRI Algorithm

The algorithm for computing the GUPTRI form is based on two reductions (staircase forms) [121]. The first is the -staircase form that reveals the right singular structure and the Jordan structure of the zero eigenvalue of .

The -algorithm uses a finite number of unitary equivalence transformations, where in step , dimension of the column null space of and dimension of the intersecting column null space of and are determined. Here, and , and for correspond to the deflated matrix pair obtained after the equivalence transformation in step . The structure indices (-indices) display the Kronecker structure as follows:

Before we state the general case we consider a matrix pencil in -staircase form:

Nonzero entries after each deflation are marked with a unique letter (x from first step, y from second step, etc.), and they appear in bold or italic. The superdiagonal blocks of have full column rank and the diagonal blocks of have full row rank. The nonzero entries of the full rank blocks are marked in bold font. We use this notation in later examples as well.

The diagonal blocks (defining the stairs'') in are of size and show the following information:

Now, we can conclude that the KCF of is .

In general, let and be complex matrices. Then it can be shown that there exist unitary matrices and such that the matrix pencil is transformed to the following so-called RZ-staircase form [121,122]: U^*(A - B)V = [

] - [

], where the staircase block structure of and reveals the right singular structure and the Jordan structure of the zero eigenvalue of :

The subblocks in (8.37) and (8.38) have the following properties:

• is and are , where .
• , where is and upper triangular.
• has full row rank for .
• has full column rank for .
• and are by , where has full column rank if it appears.

Three cases can appear in the -staircase form depending on and :

1. and , in which case has full column rank.
2. and .
3. .
In cases 1 and 2, the blocks appear as in (8.37) and the remaining Kronecker structure of is in . In case 3, does not exist in (8.37). In all three cases, it is possible that the th block column of (8.38) does not appear; if it does, also has full column rank. For convenience, let .

We see that the example above corresponds to case 3 and that does not have a th block column.

The second reduction is the (left-infinity)-staircase form that reveals the left singular structure and the Jordan structure of the infinite eigenvalue of . This dual staircase form is obtained by working from the southeast corner of and replacing column compressions by row compressions in the -algorithm. The block indices and are dimensions of corresponding row null spaces and define the -indices. Moreover, and are the number of and blocks, respectively.

Both the -staircase and -staircase reductions give us two types of structure elements which must be separated to obtain the GUPTRI form. For example, the right singular structure and the Jordan structure of the zero eigenvalue are separated by first applying the -staircase reduction to and insisting on the same right minimal indices. Then we obtain and are left with a pencil, say, corresponding to the zero eigenvalue. Finally, is obtained by transforming to -staircase form.

We return to the example and show the separated -staircase and -staircase forms:

and

As for , the superdiagonal blocks of and have full column rank and the diagonal blocks of and have full row rank. In the following table, the structure indices for the -, -, and -staircase forms of the example are summarized. We see that the -staircase indices are the sum of the - and -staircase indices, respectively.

 1 2 3 4 4 2 2 0 3 2 1 0
 1 2 3 4 2 1 1 0 1 1 0 0
 1 2 3 4 2 1 1 0 2 1 1 0

In summary, the GUPTRI algorithm for computing (8.34) and (8.35) comprises seven reduction steps. The first three steps apply the -staircase reduction to different blocks of , giving the right singular structure ( ) and the zero Jordan structure ( ) in the top left corner of and . Similarly, the next three steps apply the -staircase reduction to different blocks of the remaining pencil, giving the infinite Jordan structure ( ) and the left singular structure ( ) in the bottom right corner of and . Then a square regular pencil is left in the middle of the transformed pencil, which corresponds to the finite and nonzero eigenvalues of . By applying the QZ algorithm to this pencil, the upper triangular block is obtained.

Subsections

Next: A Singular Pencil in Up: Singular Matrix Pencils   Previous: Generalized Schur-Staircase Form   Contents   Index
Susan Blackford 2000-11-20