# The dimension of matrices (matrix pencils) with given Jordan (Kronecker) canonical forms

The Dimension of Matrices (Matrix Pencils) with Given Jordan (Kronecker) Canonical Forms

James W. Demmel Alan Edelmany November 1993

The set of n by n matrices with a given Jordan canonical form de nes a subset of matrices in complex n2 dimensional space. We analyze one classical approach and one new approach to count the dimension of this set. The new approach is based upon and meant to give insight into the staircase algorithm for the computation of the Jordan Canonical Form as well as the occasional failures of this algorithm. We extend both techniques to count the dimension of the more complicated set de ned by the Kronecker canonical form of an arbitrary rectangular matrix pencil A ? B .

Abstract

1 Introduction

Given any square matrix A, the set of matrices similar to A forms a manifold in complex n2 dimensional space. This manifold is, of course, the orbit of A under the action of conjugation: orbit(A) = fPAP ?1 : det(P ) 6= 0g; The matrix pencil analog is to consider any pair of m by n matrices A and B , and de ne the orbit of the matrix pencil A ? B by the action of multiplication on the left and right by square nonsingular matrices of the appropriate size: orbit(A ? B ) = fP (A ? B )Q?1 : det(P )det(Q) 6= 0g; This orbit de nes a manifold of pencils in 2mn dimensional space. All pencils on this manifold are said to be equivalent to A ? B . (In matrix theory, a \pencil" refers to a linear matrix polynomial, often in the indeterminate . See 5].) Our concern in this work is to count the (co)dimension of these manifolds as objects in complex Euclidean space. For simplicity of exposition, we sometimes refer to these two problems as counting the (co)dimension of a (single) matrix or of a matrix pencil, when more properly, we would refer to counting the (co)dimension of the orbits. We take two approaches, one based on classical techniques

Computer Science Division and Department of Mathematics, University of California, Berkeley, CA 94720, demmel@cs.berkeley.edu. Supported by NSF grants DMS-9120852, ASC-9005933 and under a subcontract with the University of Tennessee under DARPA contract DAAL03-91-C-0047. y Department of Mathematics Room 2-380, Massachusetts Institute of Technology, Cambridge, MA 02139, edelman@math.mit.edu. Supported by NSF grant DMS-9120852 and the Applied Mathematical Sciences subprogram of the O ce of Energy Research, U.S. Department of Energy under Contract DE-AC03-76SF00098.

1

that identify the tangent spaces of these manifolds and the other based upon existing numerical algorithms for computing the Jordan and Kronecker forms 8, 9, 10, 11, 13, 16, 15, 19, 20]. The classical approach to solving this problem requires the computation of the tangent space to the orbits. In the single matrix case, the tangent vectors have the form

XA ? AX;

while in the matrix pencil case, the tangents have the form

(1) (2)

X (A ? B) ? (A ? B)Y:

Thus the codimension of the single matrix orbit is the number of linearly independent matrices X for which (1) vanishes, while the codimension of the matrix pencil orbit is related to the number of linearly independent matrix pairs X; Y for which (2) vanishes. Arnold 1] has rederived the formula for the Jordan case for the purpose of de ning a particular normal form for deformations of a matrix with a given Jordan form. This form is convenient because of its minimum number of parameters 4]. We are unaware of any general dimension count for matrix pencils in the literature. One partial result of Waterhouse 18] counts the codimension of a singular pair of n by n matrices (i.e. the square case) to be n + 1. Our new approach is based on the so called staircase algorithms for the Jordan and Kronecker canonical forms. The staircase algorithm for the Jordan canonical form proceeds by computing the Weyr characteristics of the matrix, while the staircase canonical form proceeds by computing a more complicated set of structural indices. In this paper we lay the groundwork for a theory that we hope might explain the occasional failures of existing staircase algorithms to nd the \right" Jordan or Kronecker form. These algorithms are used in systems and control theory to nd the input matrix (or pencil) of highest codimension within a user-supplied distance of the input data. The structures of these matrices or pencils re ect important physical properties of the systems they model, such as controllability 3, 17]. The user chooses to measure the uncertainty in the data. The existence of a matrix or pencil with a di erent structure within distance of the input means that the actual system may have a di erent structure than the approximation supplied as input. So the goal of these algorithms is to perturb the input by at most so as to nd the matrix or pencil of as high a codimension as possible. The algorithm is said to fail if there is another perturbation of size at most which would raise the codimension even further. Therefore, we need to understand how the algorithm produces outputs of each codimension, which is explained in this paper, although this is just a rst step to explaining the failures. In particular, this is why we need to prove a known result (Theorem 2.1) using a new technique: staircase form. We believe the dimension count for the matrix pencil case (Theorem 2.2) is new.

2 Main Results

Theorem 2.1 The codimension of the orbit of a given matrix A is X

cJor =

(q1( ) + 3q2( ) + 5q3 ( ) + : : :);

where q1 ( ) q2 ( ) q3 ( ) : : :, denotes the sizes of the Jordan blocks of A corresponding to .

Theorem 2.2 The codimension of the orbit of A ? B depends only on its Kronecker structure.

2

This codimension can be computed as the sum of separate codimensions as given in the table below.

This equation is expressed more compactly in Equation 6 in the next section. Section 7 provides examples of how to use these formulas. Readers already familiar with the Kronecker form may wish to proceed directly to Section 7 before reading the proofs.

Breakdown of the codimension count:

The codimension of the orbit of A ? B depends only on its Kronecker structure. It can be computed as the sum cTotal = cJor + cRight + cLeft + cJor;Sing + cSing, whose components are de ned as: 1. The codimension of the Jordan structure:

cJor =

X

(q1 ( ) + 3q2 ( ) + 5q3 ( ) + : : :);

where the sum is over all eigenvalues as in Theorem 2.1, including the in nite eigenvalue if it is present. 2. The codimension of the L singular blocks:

cRight =

X

j>k

(j ? k ? 1);

where the sum is taken over all pairs of blocks Lj and Lk for which j > k. 3. The codimension of the LT singular blocks:

cLeft =

X

j>k

(j ? k ? 1);

where the sum is taken over all pairs of blocks LT and LT for which j > k. j k 4. The codimensions due to interactions of the Jordan structure with the singular blocks:

cJor;Sing = (size of Jordan structure)(number of singular blocks):

Here the number of singular blocks counts both the left and the right blocks. 5. The codimensions due to interactions between L and LT singular blocks:

cSing =

X

j;k

(j + k + 2);

where the sum is taken over all pairs of blocks Lj and LT . k These are complex codimensions, but the answers are correct for real codimensions when the matrices or matrix pencils have real Jordan or Kronecker forms. For the rest of this paper all dimensions will be complex dimensions (half the number of real dimensions).

3

3 Mathematical Preliminaries and Notation

The basic notation in this area has been reinvented by many authors. So as to make this work self-contained and also to x notation, we review the basic de nitions. Further information may be found in standard matrix theory texts such as 5] or 12]. Given a matrix A that has only one eigenvalue it is always possible to nd a similarity that transforms A into the form J (A) = diag(Jq1 ; Jq2 ; : : :) (3) where Jq is a q by q matrix with on the diagonal and 1 on the superdiagonal known as a Jordan block. For an arbitrary matrix, it is always possible to nd a similarity that transforms A into a union of blocks of the form (3): (4) J (A) = diag(J 1 (A); J 2 (A); : : :); where 1 ; 2 denotes the distinct eigenvalues of A. To x the order of the Jordan blocks within (3), we assume

3.1 Matrix Canonical Forms

q1 ( ) q2( ) : : :;

but we do not x the order of the eigenvalues:

De nition 3.1 The matrix J (A) de ned up to eigenvalue orderings is known as the Jordan Canonical Form of A. De nition 3.2 The sequence of numbers (qi( )) de ned above gives the sizes of the Jordan blocks for the eigenvalue . They are known as the Segre characteristics of A relative to .

It is sometimes convenient to think of this as an in nite sequence with qj ( ) = 0 for j >(the number of Jordan blocks corresponding to ).

the indeterminate x, where is an eigenvalue of A and qi ( ) is a Segre characteristic corresponding to .

De nition 3.3 The elementary divisors of the matrix A ? xI are the polynomials ( ? x)qi in

( )

De nition 3.4 The invariant factors of the matrix A ? xI are the polynomials Pi(x) = Q ( ?

x)qi ( ). It follows that if we let pi denote the degree of the ith invariant factor then pi =

X

qi( ):

Of course n = pi because this counts the sizes of all the Jordan blocks of all the eigenvalues of A. Some authors (see 12] pages 43 and 93) consider the quantity mi de ned as the degree of the greatest common divisor of all the i by i minors of the linear matrix polynomial A ? I . It can be shown that mi = pn+1?i + : : : + pn .

P

De nition 3.5 The nullity of an n by n matrix A is n ? rank(A). For m by n matrices the row nullity and the column nullity are m ? rank(A) and n ? rank(A) respectively.

4

De nition 3.6 Let wj ( ) denote the di erence nullity(A ? I )j ? nullity(A ? I )j ? rank(A ? I )j ? ? rank(A ? I )j : The numbers wj ( ) are the Weyr characteristics of A relative to .

1 1

It turns out that the number of blocks Jq with q j is exactly wj ( ). The dimension of the nullspace of (A ? I ) is w1( ) ( 5, 12]). The following lemma is critical for the construction of the staircase algorithm.

Then

Lemma 3.1 Let Q be any unitary matrix whose rst w columns span the nullspace of A ? I . w n?w !

1

0 ^ where A is an n ? w1 by n ? w1 matrix. With the deletion of w1( ), the Weyr characteristics of ^ A are the same as that of A. In particular, the Weyr characteristics of the other eigenvalues are unchanged. Without loss of generality we may assume that QT AQ is already a (row and column permutation ^ of a) Jordan form. The Jordan structure of A is the same as the Jordan structure of A except that ^ corresponding to the eigenvalue is exactly one dimension smaller. every Jordan block of A Let A ? B be an m by n matrix pencil. (When discussing the Kronecker case, is always an indeterminate.) It is possible to nd an equivalent pencil Kron(A ? B ) in the Kronecker Form: (5) Kron(A ? B ) = diag(L 1 ; : : :; L g ; LT1 ; : : :; LTh ; J; J 1 ): The L blocks are by + 1 rectangular blocks with on the diagonal and 1 on the superdiagonal. The LT blocks are + 1 by , with on the diagonal, and 1 on the subdiagonal. The and (sometimes referred to as the size) can be 0, leading to 0 columns and rows respectively. The J block is of the form (4) with the addition of I . This constitutes the Jordan structure of the nite eigenvalues. The J 1 block is the union of blocks of size qi (1) each of which has 1 on the main diagonal and on the superdiagonal. This constitutes the Jordan structure corresponding to the in nite eigenvalue. Frequently there will be no need to distinguish between the nite and in nite eigenvalues. Indeed, with an appropriate Mobius transformation sending A ? B to ( A + B ) ? ( A + B ), all eigenvalues may be assumed nite. The L and LT blocks constitute the singular part of the pencil. The Jordan structure for nite and in nite eigenvalues constitutes the regular part of the pencil. The Segre characteristics remain well de ned for a matrix pencil, but we must include the characteristics for the in nite eigenvalue as well. 0 1 2 ::: g denote the sizes of the g L blocks of a pencil, and let 0 1 2 ::: h denote the sizes of the h LT blocks. Then the numbers i are known as the column minimal indices, while the i are the row minimal indices. 5

QT AQ =

I

1

S ^ A

1

Proof Idea

De nition 3.7 Let

We can now recast Theorem 2.2 using the notation from the previous de nitions. The codimension of the orbit of A ? B can be written compactly as cod(orbit(A ? B )) = (p1 + 3p2 + 5p3 + : : :) + (g + h) pi X X X + ( i ? j ? 1) + ( i ? j ? 1) + ( i + j + 2);

i> j i> j

X

i;j

(6)

where the pi include any in nite eigenvalue blocks.

3.2 Conjugate Partitions

De nition 3.8 Let k

k2

The Weyr characterists and the Segre characterists of a matrix for a given eigenvalue are closely related. 0 be a partition of the positive integer k (i.e. k = k1 + k2 + : : :). Let lj denote the number of ki that are greater than or equal to j . Then the lj form a partition of k known as the conjugate partition of the ki .

1

k3

:::

It is easy to verify that the property of being a conjugate partition is symmetric. For example, 17=6+6+3+1+1=5+3+3+2+2+2 are conjugate partitions of 17. This is easy to verify by reading the diagram below (known as a Ferrers diagram) vertically and horizontally: 5 3 3 2 2 2 6 . . . . . . 6 . . . . . . 3 1 1 . . . . .

The idea of the conjugate partition is very simple, yet very powerful. It allows the interchange of summations: lj ki XX XX f (i; j ); f (i; j ) = where f (i; j ) is any function of i and j , and the ki and lj are conjugate partitions.

i j j i

Lemma 3.2 The Weyr characteristics and the Segre characteristics of a matrix corresponding to a particular eigenvalue are conjugate partitions.

The proof of this lemma is evident from the Jordan form of the matrix 12, p.74].

3.3 A Fundamental Codimension Count

Our codimension counts for the Jordan and Kronecker form are built up from the fundamental Lemma 3.3. To state it, we need to introduce a little notation from manifold theory.

6

De nition 3.9 The set of k dimensional subspaces of n dimensional space along with its natural manifold structure forms the Grassmann manifold denoted Gk (n). The Grassman manifold and its dual Gn?k (n) are isomorphic of dimension k(n ? k). In Lemma 3.3 we will need a full-rank parameterization for Gn?k (n), which we construct as follows. (Recall that a chart for a complex d-dimensional manifold M is an open neighborhood U

in C d plus a homeomorphism from M into U . A full rank parameterization is the inverse of this homeomorphism.) Because of the action of the unitary group, it su ces to specify a local full rank parameterization near any one element, say Ek , the one generated by the rst k coordinate vectors. We create a parameterization from unitary matrices of the form

Q0 =

I ?R R I

!

I +R R

0

I + RR

0

!? =

1 2

;

(7)

where R is n ? k by k. The homeomorphism maps complex n ? k by k matrices R to the span of the rst k columns of Q0 . If Q is any xed unitary matrix, the homeomorphism from R 2 C n?k k to the space spanned by the rst k columns of QQ0 provides the parameterization mapping from a neighborhood of the origin in C n?k k to a neighborhood in Gk (n) of the space spanned by the rst k columns of Q.

Lemma 3.3 The set of m by n matrices with rank r is a manifold with codimension (m ? r)(n ? r). Proof We construct a parameterization whose image is a neighborhood of a particular m by n rank

r matrix A as follows. A neighborhood of the origin in the product space C r n?r C m r will serve as a domain for the parameterization. Let Q be any unitary matrix whose rst n ? r columns span the nullspace of A, so that AQ = 0M ] is zero in its rst n ? r columns and its last r columns M have full rank. Let Q0 be as in (7), with k = n ? r. Then the map from (R; T ) 2 C r n?r C m r to 0; M + T ]Q0Q is the desired homeomorphism. If m = n, then we may equally well use the homeomorphism mapping (R; T ) to QQ0 0; M + T ]Q0 Q . Thus the dimension is r(n ? r) + mr, and the codimension is mn ? r(n ? r) ? mr = (m ? r)(n ? r).

We graphically depict the independent parameters as follows:

n?r m?r r

R

r

S ^ A (8)

^ Here R refers to the coordinates that de ne the null space, while T = S T ; AT ]T is the matrix m r . The black square in the upper left clearly indicates the codimension of (m ? r)(n ? r). in C Later, we will take advantage of this construction to recursively construct further submanifolds ^ ^ by placing analogous rank constraints on A, so that A still lies in a small neighborhood of the origin. Therefore, it will be easy to see that we need merely add the codimensions of our constraints at each level in order to compute the overall codimension of the nal submanifold. Indeed, the parameterization of Lemma 3.3 is constructed explicitly at each step of the staircase algorithm. 7

4 Proofs of Theorem 2.1 (Codimension Count for Jordan Form)

Consider conjugating the matrix A by I + X , where is a small scalar. This yields (I + X )?1A(I + X ) = A + (XA ? AX ) + O( 2); from which it is evident that the tangent space to orbit(A) at A consists of the matrices of the form XA ? AX . The dimension of the orbit is equal to the dimension of the tangent space so that the codimension of the orbit is equal to the dimension of the nullspace of the mapping that sends X to XA ? AX . The codimension of the orbit is then the number of linearly independent solutions to AX = XA. This number of solutions is well known to be p1 + 3p2 + 5p3 + : : :: (See page 222 of volume 1 of 5].) An alternative expression for the number of solutions to AX = XA is n + 2(m1 + : : : + mn?1 ) as given in 12]. According to the remark following De nition 3.4, these expressions are identical.

4.1 Classical Proof

4.2 Outline of the Staircase Algorithm

The staircase algorithm for the computation of the Jordan Canonical Form appears in 6, 7, 10, 11, 13]. Some references refer to \stairacase form" to mean a slightly di erent concept 2, 14]. The staircase algorithm of interest to us computes the Weyr characteristics. It is built recursively upon the idea in Lemma 3.1.

Staircase algorithm for computing the Jordan form for eigenvalue i=0 Atmp = A ? I while Atmp not full rank i= i+1P Let n0 = ij?1 wj and ntmp = n ? n0 = dim(Atmp) =1 Compute an ntmp by ntmp unitary matrix Q whose leading wi columns span the null space of Atmp A = diag(In0 ; Q ) A diag(In0 ; Q) Let Atmp be the lower right ntmp ? wi by ntmp ? wi corner of A Atmp = Atmp ? I endwhile The nal A is easily seen to be unitarily similar to the initial A. The nal A is in staircase form, as illustrated with the following example:

w1 w2 w3 w4 n0 w1 I A12 w2 I A23 w3 I A34 w4 I 0 n A0

8

Here, the superdiagonal blocks Ai;i+1 (the \stairs") and also A0 ? I are of full column rank, while the staircase region in the lower triangle is entirely 0. If A has only one eigenvalue then n0 is 0 and the last block row and block column do not appear. If A has other eigenvalues 0, then the staircase form corresponding to the remaining eigenvalues may be extracted by applying the same algorithm to A0. An easy observation is that Lemma 4.1 The wi computed by the staircase algorithm for the eigenvalue are the Weyr characteristics corresponding to the eigenvalue .

4.3 Second Proof of Theorem 2.1

Let A be any matrix. We will show that the staircase algorithm, in e ect, creates a parameterization for an open neighborhood N (A) of A on the manifold orbit(A). Let be an eigenvalue of A. Then A ? I has rank n ? w1. The independent parameters portrayed in (8) may be used as a parameterization for a neighborhood of A ? I on the manifold of rank n ? w1 matrices. Lemma 3.1 tells us that we have a parameterization for orbit(A) if we make further assumptions on the ^ Jordan structure of A. Notice that in a small enough neighborhood of A, the last n ? r columns of the staircase form are full rank. It is important to observe the independence of the w1(n ? w1) parameters in R1 from the w1(n ? w1) parameters of S1 and the as of yet uncounted parameters in ^ ^ A. The rst eigenvalue is \fully parameterized" when A ? I has full rank. The parameters are ^ pictorially depicted below in an example that recurs two more times before A ? I has full rank.

R1

S1 S2 S3 R2 R

3

w1 w2 w3

^ A

w1 w2 w3

^ This parameterization process is repeated on A with a new eigenvalue shift in an identical ^ does not exist. The areas of the black squares in the manner. This repetition continues until A gure above indicate the codimension that we might attribute to the eigenvalue . This codimension is then

X

i

wi =

2

wi XX

= =

i k=1 qk XX k X i=1 k

(2k ? 1)

(2k ? 1)

(2k ? 1)qk ;

using the fact that the Weyr and Segre characteristics are conjugate partitions. The total codimension for the entire Jordan structure of A is obtained by summing over all the eigenvalues because of the independence of the parameters. 9

5 Tangent Space Proof of Theorem 2.2

We include two proofs both of which we believe to be new. The rst proof requires counting the number of independent solutions to two simultaneous matrix equations derived by analyzing the tangent space, while the second proof (in Section 6) requires an analysis of the staircase algorithms for the Kronecker canonical form. Consider an orbit preserving transformation of the m by n pencil A? B obtained by multiplying on the left by I + X and the right by I ? Y , where is a small scalar. This yields A ? B + (X (A ? B ) ? (A ? B )Y ) + O( 2 ); from which it is evident that the tangent space to the orbit of the pencil consists of the pencils that can be represented in the form

f (X; Y ) = X (A ? B) ? (A ? B)Y;

(9)

where X is an m by m matrix and Y is an n by n matrix. Since (9) maps a space of dimension m2 + n2 linearly into a space of dimension 2mn, the dimension of the image space is m2 + n2 ? d, where d is the dimension of the kernel of f (X; Y ), and so the codimension is 2mn ? (m2 + n2 ? d) = d ? (m ? n)2 : (10) The term (m ? n)2 represents extra baggage due to our consideration of rectangular pencils. As in the Jordan case, we need to calculate d, the number of linearly independent solutions to f (X; Y ) = 0. This can be written as the two simultaneous equations

XA = AY and XB = BY:

(11)

Unfortunately, we can not simply quote a classical count of the number of independent solutions to (11) as we were able to do in Section 4.1. However since

Pf (X; Y )Q?1 = (PXP ?1 )P (A ? B)Q?1 ? P (A ? B)Q?1 (QY Q?1 );

it follows that the number of linearly independent solutions to f (X; Y ) = 0 depends only on the Kronecker structure of A ? B . Thus, we assume that A ? B is already in Kronecker canonical form M = diag(M1; M2; : : :). The Kronecker case is more complicated than the Jordan case due to the greater number of possibilities for the Kronecker structure M . We partition the equation XM = MY conformally with M = diag(M1 ; M2; : : :) so that Xij Mj = Mi Yij , where Mk is mk by nk , Xij is mi by mj , and Yij is ni by nj :

m1 m2

m1 m2 ! n1 n2 ! n1 n2 ! n1 n2 ! X11 X12 m1 M1 m1 M1 n1 Y11 Y12 X21 X22 m2 M2 = m2 M2 n2 Y21 Y22

The next lemma allows us to compute the quantity d mentioned before Equation (11) as the sum of the number dij of independent solutions of Xij Mj = Mi Yij in the variables Xij and Yij .

Lemma 5.1 In terms of the above notation

d=

X

i;j

dij :

10

Proof As is evident from the example !

X11 X12 X21 X22

M1

!

M2

=

M1

!

M2

Y11 Y12 ; Y21 Y22

!

the equations Xij Mj = Mi Yij , i = 1; 2; : : :, j = 1; 2; : : : are all mutually independent. Given any two blocks, Mi and Mj (we allow i = j here) we de ne their interaction and the cointeraction: De nition 5.1 Let Mi be mi ni and let Mj be mj nj . Let X be an arbitrary mj mi matrix and Y be an arbitrary nj ni matrix. We de ne the interaction dij of Mi with Mj as the dimension of the linear space fX; Y g such that XMj = Mi Y . We de ne the cointeraction of Mi with Mj as cij = dij ? (mi ? ni)(mj ? nj ). We also consider the combined cointeraction which we de ne as cij + cji when i = j , and simply cii when i = j . 6 Notice that the combined cointeraction has a di erent de nition depending on whether Mi and Mj are distinct blocks (even if they happen to be equal) on one hand, or if i = j on the other hand. Strictly speaking the combined cointeraction is a function of Mi , Mj , and the Kronecker delta ij .

Lemma 5.2 The codimension of a matrix pencil M with Kronecker structure diag(M ; M ; : : :) is

the sum of cointeractions of Mi with Mj for all combinations of i and j .

1 2

Proof The sum of the cointeractions is X fdij ? (mi ? ni )(mj ? nj )g = d ? (m ? n)

i;j

2

as in Equation (10). We must now count the number of linearly independent solutions (and the associated combined cointeractions) to the following equations: XLj = Lk Y and XLT = LT Y j k

XLj = LT Y and XLT = Lk Y j k XJ = Lj Y and XLj = JY and related structures XJ = JY where J denotes the non-singular structure of the pencil.

= Lk Y and XLT = LT Y j k Consider the equation XLj = Lk Y , where X is an unknown k by j matrix and Y is an unknown k + 1 by j + 1 matrix. This equation is equivalent to the two equations X 0 Ij ] = 0 Ik ]Y X Ij 0] = Ik 0]Y;

XLj

5.1

11

where 0 denotes a column of zeros. These two equations are in turn equivalent to the conditions = 1; : : :; k; = 1; : : :; j Y ; = Y +1; +1; = 1; : : :; k; = 1; : : :; j Y +1;1 = Y ;j+1 = 0; = 1; : : :; k

;

X

=Y ; ;

If j < k there is only the trivial solution X = 0 and Y = 0. The interaction is 0, so that the cointeraction is 0 ? (j ? (j + 1))(k ? (k + 1)) = ?1. If j k then there are non-trivial solutions: Y can be any upper triangular Toeplitz matrix with 1 + j ? k diagonals starting from the main diagonal. X is then obtained from Y by omitting the rst row and column. The interaction of Lj with Lk is 1 + j ? k so that the cointeraction is (1 + j ? k) ? 1 = j ? k. We conclude that the combined cointeraction of Lj and Lj is 0, while if j > k then the combined cointeraction of Lj with Lk is j ? k ? 1. Taking the transpose and interchanging the roles of j and k, we see that the same result holds for blocks of the form LT . We also remark that the analysis is correct even if j or k is 0. j We proceed in a manner similar to the previous case. Consider the equation XLj = LT Y; where k X is an unknown k + 1 by j matrix and Y is an unknown k by j + 1 matrix. The equations are equivalent to

5.2

XLj

= LT Y and XLT = Lk Y j k

Y

X

; +1;

= Y ; ; = 1; : : :; k; = 1; : : :; j = Y ; +1; = 1; : : :; k; = 1; : : :; j Y ;1 = Y ;j+1 = 0; = 1; : : :; k Xk+1; = 0; = 1; : : :; j

This has only the trivial solution X = Y = 0 so that the interaction of Lj with LT is 0 and the k cointeraction is 0 ? (?1)(1) = 1. A similar examination of the equation XLT = Lk Y shows that the interaction of LT with Lk is j j j + k so the cointeraction is j + k ? (1)(?1) = j + k +1. We conclude that the combined cointeraction is j + k + 2.

5.3 Jordan Blocks and Singular Blocks

In one way, the computation involving Jordan blocks is easier since the interaction is equal to the cointeraction. (This is true simply because the Jordan block is square.) However, we must now allow for arbitrary eigenvalues. Assume that Jk is a single Jordan block of size k corresponding to the nite eigenvalue e. (We use e here so that there is no confusion with the indeterminate .) We consider solutions to XJk = Lj Y . The reader can verify that the dimension of the space of solutions is k. Indeed the rst row of the j + 1 by k matrix Y can be chosen arbitrarily and this determines the remaining elements as follows: Y 1 = Y11e ?1 , X is obtained from Y by deleting the last row, and eY ; + Y ; ?1 = Y +1; . An analogous, though simpler argument shows that the case of in nite eigenvalues gives the same 12

answer. (We can also resort to a Mobius transformation as well.) We conclude that the interaction of Jk with Lj is k. The interaction of Lj with Jk is readily shown to be 0. From the equation XLj = Jk Y; we can conclude that X is obtained from Y by deleting the last column, that the last column of Y is zero, and if the mth column of Y is 0, then so is the m ? 1st column of X and hence so is the m ? 1st column of Y . The cases XLT = JY and XJ = LT Y can be reduced to the previous cases by remembering j j that if J is a Jordan block, J T = PJP where P is the permutation that renumbers indices in backwards order. For example, the number of independent solutions to XLT = JY is the same as j the number of solutions to (Y T P )(PJ T P ) = (Lj X T P ). Let J + I be the entire non-singular portion of the Kronecker structure. If we assume that there are no in nite eigenvalues, then the equation X (J + I ) = (J + I )Y implies X = Y and then we are reduced to the case XJ = JX in Theorem 2.1. We remark that Theorem 2.1 tells us that there is no interaction among Jordan blocks with di erent eigenvalues. We omit the tedious algebra, but it is possible to show that an in nite eigenvalue behaves exactly as if it were nite. (A simpler argument would point out that we can rotate the Riemann sphere to insure that all the eigenvalues are nite, without changing the codimension count.) We conclude that the combined cointeractions of the non-singular portion of the pencil is exactly as in Theorem 2.1.

5.4 Jordan Blocks with other Jordan Blocks

5.5 Proof of Theorem 2.2

The proof follows from the analysis of the cases presented in Sections 5.1.1 through 5.1.4.

6 Proof of Theorem 2.2 Based on the Staircase Algorithm

We begin by reviewing the staircase algorithm. The version we use has three passes. Let A ? B be an m by n matrix pencil. The rst pass produces two sequences of numbers si and ri and returns a pencil A0 ? B 0 with no Lj blocks and no zero eigenvalues. The sequence satis es

s0 r0 s1 r1 s2 : : :;

where

si ? ri = the number of Li blocks and ri ? si+1 = the number of Ji0+1 blocks.

The algorithm is as follows.

13

Staircase algorithm for computing the Kronecker form for the 0 eigenvalue and Lj blocks

i = ?1 Atmp = A while Atmp not full rank i= i+1P i Let n0 = P?1 sj and ni = n ? n0 = #cols(Atmp) j =0 Let m0 = ij?1 rj and mi = m ? m0 = #rows(Atmp ) =0 Compute an ni by ni unitary matrix Q whose leading si = nullity(Atmp ) columns span the right null space of Atmp Let A = A diag(In0 ; Q) and B = B diag(In0 ; Q) Btmp = B(m0 + 1 : m ; n0 + 1 : n0 + si ) Compute an mi by mi unitary matrix P whose rst ri = rank(Btmp ) rows span the column space of Btmp Let A = diag(Im0 ; P ) A and B = diag(Im0 ; P ) B Let Atmp be the last mi ? ri rows and ni ? si columns of A

endwhile It is easy to see the nal A ? B is unitarily equivalent to the initial A ? B . We illustrate the nal form of A ? B with the following small example:

r0 r1 r2 m0

s0 s1 s2 s3 0 ? B00 A01 ? B01 0 ? B11 A12 ? B12 0 ? B22 A23 ? B23

n0 A0 ? B 0

On completion, the Bii blocks have full row rank, and the Ai;i+1 blocks have full column rank. The rst pass through the inner loop of the algorithm postmultiplies A and B by a unitary Q so A's leading s0 = nullity(A) columns are 0, and then premultiplies A and B by a unitary P so that B00 , the leading r0 by s0 submatrix of B , is full rank, and the remaining rows of the rst s0 columns of B are zero. We then repeat the process on the trailing m ? r0 by n ? s0 submatrix of A ? B to get s1 and r1. We continue until the trailing block of A has full rank (or is null). Just as with the Jordan form, each step of the algorithm incrementally builds a parameterization for the set of matrices of a given Kronecker form. Each step of the algorithm restricts the Kronecker form of the pencil to a set of higher codimension. The restrictions imposed at each step are independent for the same reason they were in the Jordan case, so we can just add codimensions. The increase in codimension at each step is given by Lemma 3.3, as the sum of the products of the row and column nullities of submatrices of A and B . Speci cally the mi by ni submatrix of A has column nullity si , rank ni ? si , row nullity mi + si ? ni , and so by Lemma 3.3 codimension (mi + si ? ni )si . Similarly the codimension due to B at step i is (mi ? ri)(si ? ri ). The rst pass through the algorithm determines the L and J 0 blocks so that the codimension due to these blocks is given by X f(mi + si ? ni )si + (mi ? ri)(si ? ri)g : (12) We proceed to show that (12) is the formula given in Theorem 2.2. For convenience we list our notation: 14

i

mi ni si ri li li0 ti u

number of rows in the lower right subpencil at step i = m ? ik?1 rk =0 P number of columns in the lower right subpencil at step i = n ? ik?1 sk =0 column nullity of Atmp at step i row rank of Btmp at step i number of Li blocks in the original pencil number of LT blocks in the original pencil i number of Ji0 blocks in the original pencil size of the regular structure corresponding to 6= 0.

P

6.1 Only left singular blocks

We begin by assuming that our pencil only contains left singular blocks. Let li denote the number of Li blocks. It is easy to show by induction that the algorithm computes

mi = ni = si = ri =

1 X

j =i

(j ? i)lj

1 X

j =i 1 X

(1 + j ? i)lj

j =i 1 X

lj lj :

j =i+1

To see this, rst check that m0 = m and n0 = n. Indeed it is obvious that m = jlj because P this counts the j rows in each Lj block. It is also obvious that n = (1 + j )lj because this counts the 1+ j columns of each Lj block. Just by looking at the form of an Lj block, we see that each left singular block makes a contribution of one to the column nullity of the pencil, thus s0 is the total number of left singular blocks. Finally, we have s0 ? r0 = l0 ; the number of L0 blocks. To check the validity of the formulas for arbitrary i proceed by induction using the de nition and properties of mi , ni , ri and si listed immediately above and at the beginning of Section 6. When there are only left singular blocks, we see that expression (12) evaluates to =

1 1 X X

P

This corresponds to the term i > j ( i ? j ? 1) from (6) using a di erent notation. In our current notation, (13) counts every pair (Li ; Lj ) for which j > i with the weight j ? i ? 1 because there are exactly lilj such pairs. For example, if we have two L1 blocks and two L5 blocks, then 1 = 1; 2 = 1; 3 = 5; and 4 = 5. In the current notation l1 = 2 and l5 = 2. Either way the sum is (5 ? 1 ? 1) = 3 four times i.e. 12. We now add the assumption that there are J 0 blocks as well. Let ti be the number of Ji0 blocks, i.e., Jordan blocks of size i corresponding to a zero eigenvalue. Again by induction it is possible to 15

P

(j ? i ? 1)lj : li i=0 j =i+1

(13)

6.2 Left singular blocks and J blocks

0

show

mi =

1 X

j =i

(j ? i)(lj + tj )

1 X

j =i

ni = m i + si = ri =

1 X

j =i 1 X

lj tj

lj +

1 X

j =i+1

j =i+1

(lj + tj ):

Now for this case Expression (12) evaluates to

=0 = +1 = = +1

80 1 1 0 1 9 1 1 1 1 = X <@ X A @ X X A X = : tj lj + tj + li (j ? i ? 1)(lj + tj ); i j i j i j i j i

= +1

(14)

which can readily be manipulated to be = +

1 1 X X

i=0 j =i+1

(

8 9 1 1 1 1 = X X <X X tj ) + : lj tk + li (j ? i ? 1)tj ; ; j i k i j i i

2 =0 = = +1 = +1

where is the same interaction among the left singular blocks as in Equation (13). We recognize P from De nition 3.6 that ( 1 i+1 tj )2 is wi2+1, the square of the i + 1'st Weyr characteristic of the j= P zero eigenvalue. From our new proof of Theorem 2.1 we know that 1 wi2+1 is the codimension i=0 due to the zero eigenvalue alone. Lastly, we must evaluate

=(

9 8 1 1 1 1 = X X <X X lj tk + li (j ? i ? 1)tj ; j i i :j i k i 1 1 X X i 1 X X tk + (k ? i ? 1)tk ) = li ( i j k j k i 8i 9 1 1 i 1 = X X < X k? X X X = li : tk + tk + (k ? i ? 1)tk ; i k j k i j k i 1 1 X X

=0 = = +1 = +1 =0 =0 = +1 1 = +1 =0 =1 =0 = +1 =0 = +1

= (size of Jordan structure for = 0)(number of left singular blocks). Therefore = + g i qi0 . We complete the rst pass through the algorithm by de ning li0 to denote the number of LT blocks, i P and u to be the size of the regular Jordan structure for 6= 0. Thus, u = i (pi ? qi0 ) includes the structure for = 1 which plays no special role during the rst pass through the algorithm. 16

i=0

li )(

k=1

ktk )

P

6.3 Arbitrary singular blocks and arbitrary Jordan structure

We once again omit the details, but it is possible to show by induction that the algorithm computes

mi = m0 + i ni = n 0 + i si = s i ri = ri0;

0

1 X

j =0 1 X

0 (j + 1)lj + u

j =0

jlj0 + u

where the superscript 0 indicates no right singular structure and no non-zero regular structure, i.e. as in the notation of Section 6.2. We now have that the codimension expression in (12) is

8 1 1 9 1 1 1 = X< X 0 X X X = + :( lj )( lj + tj ) + li ( (j + 1)lj0 + u); ; j j i i j i j

=0 =0 = = +1 =0

where is as in (14). With some algebraic manipulation, we obtain = +

1 X

i;j =0

li lj0 (i + j + 2) + u

( i + j + 2) + g

1 X

i=0

li + (

1 X

i=0

li0 )(

1 X

k=1

ktk ): qi0:

The terms here are the terms = +

X

i;j

X

i

(pi ? qi0) + h

X

i

6.4 Second and third passes through algorithm

The rst pass through the algorithm gives us a pencil A0 ? B 0 , which may have only LT blocks j and nonzero eigenvalues. We then run the algorithm on (B 0 ? A0)T , so that the indices that gave the right singular blocks before now give the left singular blocks. The indices that described = 0 now describe = 1. This algorithm returns a pencil with only a regular part that has no zero or in nite eigenvalues. If we reinvoke the previous results, we see that the second pass through the algorithms nearly completes the entire expression (6). The only gap is

X

62f0;1g

(q1 + 3q2 + 5q3 + : : :):

This is just the Jordan structure of the regular part other than the zero and in nite eigenvalues. This is covered in the third phase of the algorithm, completing the proof.

7 Examples, Observations About Genericity, and Applications to the Waterhouse Theorems

We illustrate how these theorems may be used with a number of examples: 17

1. Let A be a matrix all of whose eigenvalues are . The most generic such matrix, whose orbit has codimension n, is a single Jordan block. The least generic such matrix, with codimension 1 + 3 + 5 + : : : = n2 , i.e. dimension 0, is the single point I . P 2. Let A be a matrix with no multiple eigenvalues. The codimension of its orbit is then 1 or n. One might intuitively think of this as having speci ed the n eigenvalues, but no other information about the matrix. Indeed, if you do not wish to specify the value of an eigenvalue, the correct codimension for this unspeci ed eigenvalue is one less:

?1 + q ( ) + 3q ( ) + 5q ( ) + : : ::

1 2 3

In the Kronecker algorithm one sometimes speci es that that the eigenvalues are 0, 1 or \other". It would therefore be correct to subtract one for eigenvalues classi ed as \other". 3. Let the Kronecker structure of a particular 8 by 12 pencil be diag(L0 ; L2; L3; L3). Since this pencil has only Lj blocks, the entire codimension is to be found in cright. It is 1 + 2 + 2 = 5. Notice that the interactions of two Lj blocks that are equal or di er by only one, make no contribution to the codimension. If a pencil contains only blocks of the form L or L +1 , the codimension is 0. We have therefore observed

Corollary 7.1 The generic Kronecker structure for a matrix pencil with d = n ? m > 0 is

diag(L ; : : :; L ; L

+1

; : : :; L

+1

);

+1

where = bm=dc, the total number of blocks is d, while the number of L by m mod d (which is 0 when d divides m).

blocks is given

The same statement holds when d = m ? n > 0 if we replace the L and L +1 blocks by their transposes. Corollary 7.1 was obtained by Van Dooren, Wilkinson, and Wonham as discussed on page 3.55 of 15]. 4. Let an n by n matrix pencil have the Kronecker structure diag(Lj ,LT?j ?1 ), where 0 j < n n. From the cSing portion of the codimension, we learn that the orbit has codimension j + (n ? j ? 1) + 2 = n + 1. If a square pencil has any singular part at all, it is fairly easy to check that the smallest possible codimension is n + 1 and it must be of this form. We have thus reproduced a result of Waterhouse( 18]:

Corollary 7.2 The generic singular pencils of size n by n have Kronecker structures

diag(Lj ; LT?j ?1 ); n

where j = 0; : : :; n ? 1.

Intuitively, we might think of this as the n +1 conditions on the coe cients of that det(A ? B) = 0.) More generally, 18] has shown that if a square matrix has one Lr block and one LT block s and otherwise has a generic n ? r ? s ? 1 n ? r ? s ? 1 block (eigenvalues unspeci ed), then the codimension is (r + s + 2) + 2(n ? r ? s ? 1) = 2n ? (r + s). This too readily follows from our results. 18

1 1 5. If an 11 by 12 pencil has the Kronecker form diag(L1; LT ; L3; J5 ), where here J5 denotes a 1 single 5 by 5 Jordan block with eigenvalue 1, then cJor = 5, cRight = 1, cJor;Sing = 5 3 = 15, and cSing = 4 + 6 = 10 giving a total codimension of 31. 6. The 0 pencil has a Kronecker structure consisting of m LT blocks and n L0 blocks. The 0 codimension from cSing only is 2mn, i.e. the dimension is 0.

19

Some of this work was performed in Toulouse, indeed it was begun along Rue de Fermat, under the kind hospitality and support of CERFACS. We wish to particularly thank Mario Arioli, Dominique Bennett, and Iain Du . We further would like to thank the referees for their numerous comments which we feel have been a great improvement to the paper.

Acknowledgements

References

1] V.I. Arnold, On matrices depending on parameters, Russian Math. Surveys 26 (1971), 29{43. 2] R.A.Brualdi, The Jordan Canonical Form: an old proof, Amer. Math. Month. 94 (1987), 257267. 3] J. Demmel and B. Kagstrom, Accurate Solutions of Ill-posed Problems in Control Theory, SIAM J. Mat. Anal. Appl., 9 (1988), 126{145. 4] T. Fairgrieve, The application of singularity theory to the computation of the Jordan canonical form, unpublished M.Sc. thesis, Computer Science Dept., University of Toronto, Canada (1986) 5] F.R. Gantmacher, The Theory of Matrices, Vols. 1, 2, Chelsea, New York, 1959. 6] G.H. Golub and C.F. van Loan, Matrix Computations, Second Edition, Johns Hopkins University Press, Baltimore, 1989. 7] G.H. Golub and J.H. Wilkinson, Ill-conditioned eigensystems and the computation of the Jordan canonical form, SIAM Review 18 (1976), 578{619 8] B. Kagstrom, The generalized singular value decomposition and the general A ? B problem, BIT 24 (1985), 568{583. 9] B. Kagstrom, RGSVD: an algorithm for computing the Kronecker structure of reducing subspaces of singular A ? B pencils, SIAM J. Sci. Stat. Comp. 7 (1986), 185{211. 10] B. Kagstrom and A. Ruhe, An algorithm for numerical computation of the Jordan normal form of a complex matrix, ACM Trans. Math. Soft. 6 (1980), 398{419. 11] V.N. Kublanovskaya, On a method of solving the complete eigenvalue problem for a degenerate matrix, USSR Comp. Math. & Math. Phys. 6 (1968), 1{14. 12] C.C. MacDu ee, The Theory of Matrices, Springer-Verlag, Berlin, 1933. 13] A. Ruhe, An algorithm for the numerical determination of the structure of a general matrix, BIT 10, (1970), 196{216. 14] H.W.Turnbull and A.C. Aitken, An introduction to the theory of canonical matrices, Blackie 1932. 15] P. van Dooren, The Generalized Eigenstructure Problem, Electronic Sciences Lab { USCEE Report #503, PhD dissertation, University of Southern California, January 1979. 16] P. van Dooren, The computation of Kronecker's canonical form of a singular pencil, Lin. Alg. Appl. 27 (1979), 103-40. 17] P. van Dooren, The generalized eigenstructure problem in linear system theory, IEEE Trans. Aut. Cntl. AC-26 (1981), 111-128. 18] W.C. Waterhouse, The codimension of singular matrix pairs, Lin. Alg. Appl. 57 (1984), 227{ 245. 20

19] J. H. Wilkinson. Linear di erential equations and Kronecker's canonical form, in Recent Advances in Numerical Analysis, eds. C. de Boor and G. Golub, Academic Press, New York, (1978), 231{265. 20] J. H. Wilkinson. Kronecker's canonical form and the QZ algorithm, Lin. Alg. Appl. 28 (1979), 285{303.

21