Stability of reducing subspaces
Abstract
We characterize the stability of reducing subspaces of a rectangular matrix pencil of complex matrices λB − A, except for the special case in which the pencil has no eigenvalues and only has one row and one column minimal indices and both are different from zero.
Full text
We characterize the stability of reducing subspaces of a rectangular matrix pencil of complex matrices λB −A, except for the special case in which the pencil has no eigenvalues and only has one row and one column minimal indices and both are different from zero. Keywords: rectangular matrix pencils, Kronecker canonical form, reducing subspaces, deflating subspaces, stability, perturbation. MSC AMS: 15A22, 15A60, 47A55, 47A15, 93B10 1 Introduction Given two matrices A, B ∈Cm×n, we call matrix pencil the first order matrix polynomial λB −A. For simplicity, we will denote the set of matrix pencils of the form λB −A, with A, B ∈Cm×n, by P[λ]m×n. We define the normal rank of a pencil λB −A∈ P[λ]m×n, and we denote it by nrank(λB −A), to be the greatest order of the minors of λB −Athat are different from the zero polynomial. If m=nand nrank(λB −A) = n, the pencil λB −A∈ P[λ]m×n is said to be regular. Otherwise, the pencil is said to be singular. Note by C(λ) the field of rational fractions in λ. If we consider λB −Aas a linear map from the vector space C(λ)ninto C(λ)m, both over the field C(λ), we have nrank(λB −A) = dimC(λ)Im(λB −A), (see [4]). We define the nullity of λB −Aby ν(λB −A) := dimC(λ)Ker(λB −A). From n= dimC(λ)Ker(λB −A) + dimC(λ)Im(λB −A), ν(λB −A) = n−nrank(λB −A). ∗Work supported by the Spanish Ministry of Education and Science Project MTM2010– 19356–C02–01, and the Basque Government Projects GIC10/169–IT–361–10 and GIC13/IT– 710–13. †Department of Mathematical Engineering and Computer Science, The Public University of Navarre, Campus de Arrosad´ıa, 31006 Pamplona, Spain. [email protected] ‡Department of Applied Mathematics and Statistics, University of the Basque Country UPV/EHU, Faculty of Pharmacy, 7 Paseo de la Universidad, 01006 Vitoria-Gasteiz, Spain, [email protected], [email protected] 1 This is the accepted manuscript of the article that appeared in final form in Linear Algebra and its Applications 470 : 252-299 (2015), which has been published in final form at https://doi.org/10.1016/ j.laa.2014.10.026. © 2014 Elsevier under CC BY-NC-ND license (http://creativecommons.org/licenses/ by-nc-nd/4.0/) Stability of reducing subspaces∗ Gorka Armentia, † Juan-Miguel Gracia, ‡ Francisco-Enrique Velasco‡ October 4, 2014 Dedicated to Professor Leiba Rodman on the occasion of his 65th birthday Abstract
As usual we identify a matrix M∈Cm×nwith the linear map x7→ Mx from Cn≡Cn×1into Cm≡Cm×1. Let Nbe a subspace of Cn, we define M(N) as the subspace of Cmformed by all matrix products Mx with x∈ N. Van Dooren proved that dim(A(N) + B(N)) ≥dim N − ν(λB −A),(1) where A(N) + B(N) is the sum of these subspaces of Cm. See [17, Equation (2.16) on page 63 and in the line following (2.25 a) and (2.25 b) on page 65]. In the case the equality holds in (1), the subspace Nis called a reducing subspace for the pencil (see [17]) or, equivalently, that Nis a (λB −A)-reducing subspace. Observe that if the pencil is regular then ν(λB −A) = 0. So, in this case N is a reducing subspace if and only if dim(A(N) + B(N)) = dim N. These reducing subspaces are also called deflating subspaces for regular pencils (see [16]). In order to simplify here on, we will denote by (λB −A)(N) the subspace A(N) + B(N). We use the operator norm induced by the Euclidean norms on Cmand Cn, also called the spectral norm, kMk:= max x∈Cn kxk2=1 kMxk2. The gap between subspaces Mand N(in Cn) is defined as θ(M,N) := kPM−PNk where PMand PNare the orthogonal projectors on Mand N, respectively. Let λB −A∈ P[λ]m×na matrix pencil. A reducing subspace Nof Cnfor (λB −A) is said to be stable if for every ε > 0 there exists a δ > 0 such that every matrix pencil λB0−A0∈ P[λ]m×nthat satisfies kA0−Ak+kB0−Bk< δ has a (λB0−A0)-reducing subspace N0for which the inequality θ(N0,N)< ε holds. In the same way, we will say that the subspace Nof Cnis Lipschitz stable if there exist K, ε > 0 such that every matrix pencil λB0−A0∈ P[λ]m×n that satisfies kA0−Ak+kB0−Bk< ε has a (λB0−A0)-reducing subspace N0 for which the inequality θ(N0,N)≤K(kA0−Ak+kB0−Bk) holds. To simplify, we will often say that a subspace Nis (λB −A)-stable to mean that Nis a (λB −A)-reducing subspace and is stable to perturbations in the matrices Band A. For a clear motivation see Chapters 13 and 15 of [5]. A previous paper on this topic was published by the second and third authors [7]. A characterization of the stability or Lipschitz stability of deflating subspaces of a regular matrix pencil was already given there. In the current paper, we address this stability problem for the case of reducing subspaces of singular pencils. Before stating the main result of this paper, recall some properties of the pencils of matrices. Two matrix pencils λB −A, λD −C∈ P[λ]m×nare said to be strictly equivalent if there exist invertible matrices P∈Cm×m,Q∈Cn×nsuch that 2
λD −C=P(λB −A)Q. Remark that two strictly equivalent pencils have the same normal rank. Hence a subspace Nis (λB −A)-reducing if and only if the subspace Q−1(N) is (λD −C)-reducing. Set C:= C∪ {∞}. We will use the notation ∞B−A:= B. We will say that the element α∈Cis an eigenvalue of the pencil λB −Aif rank(αB −A)<nrank(λB −A). An eigenvalue αof λB −Ais finite if α∈C, and it is infinite if α=∞. We call spectrum of the pencil λB −Aand we denote it by Λ(λB −A), the set of its eigenvalues. It is a subset of C. The well-known Kronecker canonical form for the strict equivalence of matrix pencils is given in the following result. Lemma 1 (Kronecker canonical form [4]).Given a matrix pencil λB −A∈ P[λ]m×n, there always exist invertible matrices P∈Cm×m,Q∈Cn×n, such that P(λB −A)Qhas the form λBc−AcO O O λBr−ArO O O λBf−Af ,(2) where λBc−Ac= (O(n1−t0)×(t0−t1),diag(Lr1, Lr2, . . . , Lrt1)) ∈ P[λ](n1−t0)×n1; (3) Lri:= λ(Iri, O)−(O, Iri)∈ P[λ]ri×(ri+1); and the pencil λBr−Ar:= λN −I O O λI −J∈ P[λ]n2×n2,(4) with a nilpotent matrix N, is regular; and, lastly, λBf−Af:= O(s0−s1)×(m3−s0) diag(LT `1, LT `2, . . . , LT `s1)∈ P[λ]m3×(m3−s0).(5) Remark 2. The sequences (r1, r2, . . . , rt1, t0−t1 z }| { 0,...,0),(`1, `2, . . . , `s1, s0−s1 z }| { 0,...,0) are the column minimal indices and the row minimal indices, respectively. The elementary divisors of the matrices Nand J, are called infinite elementary divisors and finite elementary divisors, respectively, of the matrix pencil. Recall that Λ(λB −A) denotes the spectrum of the pencil λB −A, then Λ(λB −A) = Λ(λBr−Ar). Thus, a complete system of invariants for the strict equivalence of two matrix pencils is formed by the finite sequences of row and column minimal indices and the system of elementary divisors (finite and infinite). For some particular pencils some of these invariant can be absent. Strictly speaking it is not the same the set of row minimal indices and the sequence of row minimal indices. But from now on we will loosely speak and —for example— we will say that a pencil has two row minimal indices to mean that the sequence of row minimal indices has two terms, which might be equals. 3
Remark 3. Since t0=ν(λB −A), where t0is the number of column minimal indices (see [4]), from (1) we deduce that for each subspace Nof Cn, dim(A(N) + B(N)) ≥dim N − t0. Let Xbe a basis matrix of N. As dim(A(N) + B(N)) = rank(AX, BX) we have rank(AX, BX)≥rank(X)−t0.(6) As a consequence, the subspace Nis (λB −A)-reducing if and only if rank(AX, BX) = rank(X)−t0.(7) Recall that a matrix pencil λB −A∈ P[λ]m×nis said to be right regular if nrank(λB −A) = n, or equivalently ν(λB −A) = 0, or equivalently, it has no column minimal index. In an analogous way, we will say that a pencil λB −Ais left regular if λBT−ATis right regular, that is, if λB −Ahas no row minimal index. Another previous work on the topic of the stability of reducing subspaces was the one by Demmel in [2]. He studied the stability of some reducing subspaces for singular matrix pencils, but under additional conditions. We will explain it briefly. Let λB −Abe a singular pencil and let Nbe a reducing subspace for this pencil. Then, according to our notations, there is no loss of generality if we suppose that λB −Aand Nhave the form λB −A= λBc−AcO O O O λB1 r−A1 rλB2 r−A2 rO O O λB3 r−A3 rO O O O λBf−Af , N=* In1O O In2 O O O O +, where the (m1×n1)-pencil λBc−Aconly has column minimal indices, λBf−Af only has row minimal indices and the pencil λB1 r−A1 rλB2 r−A2 r O λB3 r−A3 r is regular, where λB1 r−A1 ris a pencil of size n2×n2. In [2] it is supposed that Λ(λB1 r−A1 r)∩Λ(λB3 r−A3 r) = ∅. Under these hypotheses, in Theorem 6, page 26 of [2], some results are given on the stability of the subspace N, but assuming also that the perturbed pencils have reducing subspaces of the same dimension as N. There is an ample literature on the use of reducing subspaces of matrix pencils as a tool for factorizing rational matrices and for solving Riccati equations. One can see many references in the book by Ionescu, Oarˇa and Weiss [10]. See also [13]. With theses notations, the main result of the paper is the following. 4
Theorem 4. Let λB −A∈ P[λ]m×nbe a singular matrix pencil. The following assertions are true: (1) If the pencil has row minimal indices, column minimal indices and eigenvalues, then no reducing subspace is stable. (2) If the pencil has no row minimal index, then the unique stable and Lipschitz stable reducing subspace is Cn. (3) If the pencil has no column minimal index, then the unique stable and Lipschitz stable reducing subspace is {0}. (4) If the pencil has column minimal indices and, at least, two row minimal indices, then no reducing subspace is stable. (5) If the pencil only has one row minimal index which is equal to zero, and has no eigenvalues, then the only stable and Lipschitz stable reducing subspace is Cn. (6) If the pencil only has one row minimal index which is different than zero, has not eigenvalues and has at least two column minimal indices, then no reducing subspace is stable. (7) If the pencil only has one row minimal index which is different than zero, and has one column minimal index, which is equal to zero, and has not eigenvalues, then the unique stable and Lipschitz stable reducing subspace is KerA. The organization of this paper is the following. In Section 2 algebraic properties of the reducing subspaces of pencils of linear maps are established. In Section 3, these properties are translated into terms of matrix pencils. In Section 4 the problem of the stability of reducing subspaces is addressed by means of converging sequences of matrix pencils and basis matrices of subspaces. In Sections 5 to 9 the proof of Theorem 4 (Main Theorem) is developed. In Section 5 Assertions (1), (2) and (3) of the Theorem are proved. In Sections 6, 7, 8 and 9 Assertions (4), (5), (6) and (7), respectively, are proved. 2 Properties of the reducing subspaces of linear map pencils In this section we give a characterization of the reducing subspaces for pencils of linear maps. Its proof will be made in the following section, translating these results to the matrix pencils. First, remark that the concepts of normal rank and reducing subspace can be extended to the case of a pair of linear maps. Let Uand Vbe vector spaces over Cand let A,B:U → V be linear maps. The normal rank of the pencil of linear maps λB−Ais defined by nrank(λB−A) := max z∈Crank(zB−A), where zB−A:U → V is a linear map for each z∈C. A pencil of linear maps λB−Ais said to be regular if dim U= dim Vand the linear map zB−A:U → V is invertible for every z∈C, except for at most a finite number of complex numbers. Otherwise, we will say that the pencil is singular. For each x∈ U we define (λB−A)(x) := B(x) + A(x). 5
From this definition it is deduced that for every subspace Nof U, (λB− A)(N) = B(N)+A(N). Therefore, the subspace Nof Uis said to be (λB−A)- reducing if dim(λB−A)(N) = dim N − min z∈CdimCKer(zB−A). To write the statements of the main theorems in this section, we need some previous definitions and notations. Let Ukdenote the Cartesian product U × · · · × U,k−times. Given a pair of linear maps A,B:U → V and α∈C, for k= 1,2,..., consider the linear maps Tk λB−A:Uk→ Vk+1,Pk,α λB−A,Pk,∞ λB−A:Uk→ Vk defined for x= (x1, x2, . . . , xk)∈ Ukby means of Tk λB−A(x) := (B(x1),−A(x1) + B(x2),...,−A(xk−1) + B(xk),−A(xk)) ,(8) Pk,α λB−A(x) := ((αB−A)(x1),B(x1)+(αB−A)(x2),...,B(xk−1)+(αB−A)(xk)) ,(9) Pk,∞ λB−A(x) := (B(x1),−A(x1) + B(x2),...,−A(xk−1) + B(xk)) .(10) Given x= (x1, x2, . . . , xk)∈ Uk, for i= 1,2, . . . , k we define the projections πk i(x) = xi. Now, for every α∈¯ C:= C∪ {∞} and k= 1,2, . . ., we define the subspaces: Sk λB−A:= k X i=1 πk iKer(Tk λB−A),(11) Sk,α λB−A:= k X i=1 πk iKer(Pk,α λB−A),(12) Dk λB−A:= Sk λB−A+X α∈Λ(λB−A) Sk,α λB−A.(13) With these notations we obtain the first result in this section. Theorem 5. Given two linear maps A,B:U → V, then (a) The subspaces Sn λB−Aand Dn λB−Aare (λB−A)-reducing. (b) For every (λB−A)-reducing subspace Nwe have Sn λB−A⊂ N ⊂ Dn λB−A. Remark 6. Theorem 5 will be proven by means of matrix pencils in Theorems 12 and 20 in Section 3. Proposition 7. To prove Theorem 5 there is no loss of generality if, instead of the linear map pencil λB−A, we consider the linear map pencil λD−C= P◦(λB−A)◦Q(with P,Qinvertible transformations of Vand U, respectively). Proof. Consider the linear maps Q1:Uk→ Ukand P1:Vk+1 → Vk+1 defined by Q1(x1, . . . , xk) := (Q(x1),...,Q(xk)) and P1(y1, . . . , yk+1) := (P(y1),...,P(yk+1)). 6
From (8) we immediately deduce Tk λD−C=P1◦Tk λB−A◦Q1. Therefore, Tk λB−A(x)=0⇔P1◦Tk λB−A◦Q1◦Q−1 1(x)=0⇔Tk λD−C◦Q−1 1(x) = 0. That is, Ker(Tk λD−C) = Q−1 1(Ker(Tk λB−A)). , from (11) we infer that Sk λD−C=Q−1(Sk λB−A).(14) Using the same arguments from (9), (10) and (12), we obtain Sk,α λD−C=Q−1(Sk,α λB−A), and substituing (14) in (13), we have Dk λD−C=Q−1(Dk λB−A).(15) As Nis a (λB−A)-reducing subspace if and only if Q−1(N) is (λD−C)- reducing, from (14) and (15) we conclude that Sn λB−Aand Dn λB−Aare (λB−A)- reducing if and only if Sn λD−Cand Dn λD−Care (λD−C)-reducing. Moreover it is clear that Sn λB−A⊂ N ⊂ Dn λB−Aif and only if Sn λD−C⊂Q−1(N)⊂ Dn λD−C. 2 For the second result we need some notations. Let Kbe a direct complement of Sn λB−Ain Dn λB−Aand let πK:Dn λB−A→ K be the projection over Kalong Sn λB−A. That is, Im πK=Kand KerπK=Sn λB−A. Denote HλB−A:= (λB−A)(Dn λB−A),MλB−A:= (λB−A)(Sn λB−A).(16) Now, let Lbe a direct complement of MλB−Ain HλB−Aand let πL:HλB−A→ Lbe the projection over Lalong MλB−A. With these notations, we have the following result. Theorem 8. Let A,B:U → V be linear maps. Then a subspace Nof Uis (λB−A)-reducing if and only if the subspace πK(N)of Kis deflating for the regular pencil πL◦(λB−A)|K:K → L. Remark 9. Theorem 8 will be proved in Theorem 20 in Section 3. Proposition 10. The conclusions of Theorem 8do not depend on the choice of the subspaces K,L. Proof. Let K1be another direct complement of Sn λB−Ain DλB−Aand let πK1:DλB−A→ K1be the projection over K1along Sn λB−A. In the same manner, let L1be another direct complement of MλB−Ain HλB−Aand let πL1:HλB−A→ L1be the projection over L1along MλB−A. Then, (see [15, Remark 2, p. 402]), there exist invertible linear maps Q:K → K1,P:L→L1 such that ∀x∈ K, x −Q(x)∈ Sn λB−A,∀y∈ L, y −P(y)∈ MλB−A,(17) 7
and moreover, πK1=Q◦πK, πL1=P◦πL.(18) See first that the pencils πL◦(λB−A)|Kand πL1◦(λB−A)|K1are strictly equivalent. So, one is regular if and only if the other is. Observe that Qare P are invertible, it suffices to see that P◦πL◦(λB−A)|K=πL1◦(λB−A)|K1◦Q. Given that πL1=P◦πLby (18), it is sufficient to prove that πL◦(λB−A)|K=πL◦(λB−A)|K1◦Q.(19) Let x∈ K. Then, as Q(x)∈ K1, to prove (19) it suffices to see that (πL◦ (λB−A))(x−Q(x)) = 0. But given that, by (17) , x−Q(x)∈ Sn λB−A, from the notations of (16) we see that (λB−A)(x−Q(x)) ∈ MλB−A. Therefore (πL◦(λB−A))(x−Q(x)) = 0, which proves (19). Now see that (πL1◦(λB−A))(πK1(N)) = (P◦πL◦(λB−A))(πK(N)).(20) As by (18), we have πK1(N) = Q(πK(N)) = πK(N)+(Q−I)(πK(N)), and πL1=P◦πL, we deduce that (πL1◦(λB−A))(πK1(N)) = (P◦πL◦(λB−A))(πK(N)) + (P◦πL◦(λB−A))((Q−I)πK(N)). (21) Now, as (17) implies (Q−I)(πK(N)) ⊂(Q−I)(K)⊂ Sn λB−A, from the notations of (16) we obtain (πL◦(λB−A))((Q−I)πK(N)) ⊂(πL◦(λB−A))(Sn λB−A) = πL(M(B,A)) = {0}. This last expression together with (21) yields (20). Finally, as πK1(N) = Q(πK(N)) with Qinvertible, we see that dim(πK1(N)) = dim(πK(N)). This fact together with (20) implies dim ((πL1◦(λB−A))(πK1(N))) = dim(πK1(N)) m dim ((P◦πL◦(λB−A))(πK(N))) = dim(πK(N)). Consequently, πK(N) is πL◦(λB−A)|K-deflating if and only if πK1(N) is πL1◦(λB−A)|K1-deflating. 2 Proposition 11. In the conclusions of Theorem 8there is no loss of generality if we consider the strictly equivalent pencil λD−C=P◦(λB−A)◦Q, with invertible transformations Pand Qof Vand U, respectively. Proof. Observe that from (14), (15) and (16) we obtain HλD−C=P(HλB−A),MλD−C=P(MλB−A).(22) Therefore, as Dn λB−A=Sn λB−A⊕ K and HλB−A=MλB−A⊕ L, from (14), (15) and (22) we deduce that 8
Dn λD−C=Sn λD−C⊕Q−1(K),HλD−C=MλD−C⊕P(L).(23) To prove the Proposition, see first that πQ−1(K)(Q−1(N)) = (Q−1◦πK)(N).(24) Let xbe a vector of N. Then, by 5(b), we see x=y+zwith y∈ Sn λB−A and z∈ K. Hence πK(x) = πK(z) = z. On the other hand, as Q−1(x) = Q−1(y) + Q−1(z), with Q−1(y)∈ Sn λD−Cand Q−1(z)∈Q−1(K), we infer that πQ−1(K)(Q−1(x)) = πQ−1(K)(Q−1(z)) = Q−1(z) = Q−1(πK(x)), which proves (24). Now consider the invertible linear maps Q−1 1:= Q−1|K:K → Q−1(K),P1:= P|L:L → P(L). With the notations of (16), see that πP(L)◦PHλB−A=P1◦πLHλB−A.(25) Let x=y+zbe a vector of HλB−Awith y∈ MλB−Aand z∈ L. Then, as πL(y) = 0 and πL(z) = z, we have P1(πL(x)) = P1(πL(y)) + P1(πL(z)) = P1(z) = P(z).(26) On the other hand, as y∈ MλB−A, by (22), we see that P(y)∈ MλD−C. Therefore πP(L)(P(y)) = 0. Moreover, since z∈ L, it follows P(z)∈P(L). Hence πP(L)(P(z)) = P(z). Thus πP(L)(P(x)) = P(z). This equality together with (26) proves (25). Now see that πP(L)◦(λD−C)Q−1(K)◦Q−1 1=P1◦πL◦(λB−A)|K.(27) Let x∈ K. Then, as Q−1 1(x) = Q−1(x)∈Q−1(K), we have (πP(L)◦(λD−C))(Q−1 1(x)) = (πP(L)◦P◦P−1◦(λD−C)◦Q−1)(x) = (πP(L)◦P◦(λB−A))(x). Therefore, using (25), we conclude that (πP(L)◦(λD−C))(Q−1 1(x)) = (P1◦πL◦(λB−A))(x). Hence, the pencils πP(L)◦(λD−C)Q−1Kand πL◦(λB−A)|Kare strictly equivalent. Therefore one is regular if and only if the other is too. Finally, from (27) we have (πP(L)◦(λD−C))(πQ−1(K)(Q−1(N)) = (P1◦πL◦(λB−A))(πK(N)), given that P1is invertible we deduce that the subspaces (πP(L)◦(λD−C))(πQ−1(K)(Q−1(N)) and (πL◦(λB−A))(πK(N)) have the same dimension. Moreover, from (24) we deduce that πQ−1(K)(Q−1(N)) and πK(N) have the same dimension, we conclude that πQ−1(K)(Q−1(N)) is πP(L)◦(λD−C)Q−1(K)-deflating if and only if πK(N) is πL◦(λB−A)|K-deflating. 2 9
hence, by Lemma 22 there exist invertible matrices Pand Qsuch that Bc= AcQ,Bf=PAfand Λ(P)∩Λ(Q) = ∅. As a consequence, n1−t0= rank AcAcQ AfY31 PAfY31= rank AcO AfY31 PAfY31 −AfY31Q. Therefore, since rank(Ac) = n1−t0, we have PAfY31 −AfY31Q=O. Now, as Λ(P)∩Λ(Q) = ∅, we see that AfY31 =O, and hence Y31 =O. To conclude the proof it suffices to prove that we can choose Y21 =O. Partitioning Y21 according to (43), Y21 = O V O W , as Y31 and Y32 are zero matrices, from (40), (41) and (43) we deduce that rank AcO O BcO O O Iq1O N3V N1O V O O N2V O O J3W O J1O O Iq2 J2W O O W O O =n1+q1+q2−t0. Therefore, as by Lemma 22 we have Bc=AcQfor some matrix Q, then n1−t0= rank AcAcQ V N2V J2W W = rank AcO V N2V−V Q J2W W −J2WQ . Hence, as rank(Ac) = n1−t0we have N2V−V Q =Oand W−J2WQ =O. Or equivalently WQ−1−J2W=O. Choosing Qin such a way that Λ(J2)∩ (Λ(Q)∪Λ(Q−1)) = ∅, we deduce that Vand Ware null matrices and therefore Y21 =O. The converse is immediate. 2 4 Properties of the stability In this section we give some auxiliary results about the stability of reducing subspaces. First, observe that from (7), if Xis a basis matrix of the subspace N, then Nis (λB −A)-reducing if and only if rank(AX, BX) = rank(X)−t0. This definition enables us to make a reformulation of the concept of stability and Lipschitz stability of a reducing subspace in terms of limits of sequences of matrices. To do so, we will use the following result on the convergence of a sequence of subspaces that one deduces straightforwardly from ([1], Section 1.5, p. 29–31), ([5], Theorem 13.5.1) and ([3], Theorem I-2-6). Proposition 23. Let Nbe a p-dimensional subspace of Cnand let {Nq}∞ q=1 be a sequence of subspaces of Cnthat converges to Nin the gap metric. Then, for each X∈Cn×p, basis matrix of N, there exist a sequence of matrices {Xq}∞ q=1 converging to X, two positive constants K1,K2, and a positive integer q0, such that for q≥q0,Xqis a basis matrix of Nq, and K1kXq−Xk ≤ θ(Nq,N)≤K2kXq−Xk. 16
From Proposition 23, we can reformulate the concept of stable and Lipschitz stable subspace in terms of the convergence of sequences of matrices. The result is the following. Proposition 24. Let λB −A∈ P[λ]m×nbe a matrix pencil and let Nbe a (λB −A)-reducing subspace such that dim N=p. Then Nis (λB −A)-stable if and only if for every basis matrix X∈Cn×pof N, and for every sequence of matrix pencils λBq−Aq→λB −A, there exist a sequence of matrices Xq→X and a positive integer q0, such that for q≥q0:Xqis a matrix of rank pand the subspace hXqiis (λBq−Aq)-reducing. Moreover, Nis (λB−A)-Lipschitz stable if and only if there exist a constant K > 0and a positive integer q0such that for q≥q0 kXq−Xk ≤ K(kAq−Ak+kBq−Bk). In addition, if X=Ip 0, then for q≥q0we can choose Xq=Ip Yq, where Yq→0. We will see some results that will simplify the statements of Theorem 4 and some proofs. The first is the following, which can be proved from Proposition 24 and using the techniques employed in the proof of Proposition 3.3 of [18]. Proposition 25. Let λB −A∈ P[λ]m×nbe a matrix pencil and let λD −C∈ P[λ]m×nbe a pencil strictly equivalent to λB −A; that is to say, λD −C= P(λB −A)Qwith P∈Cm×mand Q∈Cn×ninvertible matrices. Let Nbe a (λB −A)-reducing subspace. Then, Nis (λB −A)-stable (or Lipschitz stable) if and only if Q−1Nis (λB −A)-stable (or Lipschitz stable). Remark 26. As a consequence of this Proposition, when studying the stability (or Lipschitz stability) of a reducing subspace, no generality is lost if we consider another strictly equivalent pencil and the corresponding transformed subspace. To prove the following result we need some previous notations. Given a matrix pencil λB −A∈ P[λ]m×n, we denote by CS(λB −A) the set of all sequences of matrix pencils that converge to λB −A. Let ˜ CS(λB −A) be a subset of CS(λB −A). We will say that a set G ⊂ ˜ CS(λB −A) is a Lipschitz generator subset of ˜ CS(λB −A) if for every sequence {(Aq, Bq)}∞ q=1 ∈˜ CS(λB −A), there exist sequences {(λBq−Aq)}∞ q=1 ∈ G and {(Pq, Qq)}∞ q=1 converging to (Im, In), and there exist a positive integer number q0and a constant K > 0, that depends on the preceding sequences, such that for q≥q0, λBq−Aq=Pq(λBq−Aq)Qq, max{kPq−Imk,kQq−Imk} ≤ K(kAq−Ak+kBq−Bk). With the preceding notation we have the following proposition, whose demonstration is similar to that one of Proposition 3.5 of [8] using Proposition 25. 17
Proposition 27. Let λB −A∈ P[λ]m×nbe a matrix pencil, and let Nbe a (λB −A)−reducing subspace and Xa basis matrix of N. Let ˜ CS(λB −A)be a subset of CS(λB −A)and Ga Lipschitz generator subset of ˜ CS(λB −A). Then the assertions below are equivalent. (i) For every sequence {(λBq−Aq)}∞ q=1 ∈˜ CS(λB −A), there exist a sequence of matrices Xq→X, a constant K1>0and a positive integer q1, such that for q≥q1, the subspace hXqiis (λBq−Aq)−reducing, and kXq−Xk ≤ K1(kAq−Ak+kBq−Bk). (ii) For every sequence {(λBq−Aq)}∞ q=1 ∈ G, there exist a sequence of matrices Xq→X, a constant K2>0and a positive integer q2, such that for q≥q2, the subspace Xqis (λBq−Aq)−reducing, and kXq−Xk ≤ K2(kAq−Ak+kBq−Bk). In addition, if G1is a Lipschitz generator subset of Gthen G1is a Lipschitz generator subset of ˜ CS(λB −A). Remark 28. In the above results, the existence of a positive integer q0is required in such a way that the results are true for q≥q0. To simplify, without loss of generality, we will assume hereafter that q0= 1. 5 Proof of Theorem 4. Assertions (1), (2) and (3). To prove Assertions (1), (2) and (3) of Theorem 4, we need some lemmas. Let λB −Abe a pencil in the form (2) and let Nbe a subspace (λB −A)-reducing, which, by Theorem 20 can be put in the form (37). Lemma 29. With the previous notations, if the subspace Nis (λB −A)-stable, then hXiis (λBr−Ar)-stable subspace. Proof. Consider an arbitrary sequence of matrix pencils λBq r−Aq rconverging to λBr−Aras q→ ∞. From now on we will summarize this with the notation Sq→Lto mean that Sqis a sequence of mathematical objects converging to the limit Lwhen q→ ∞. Then λBq−Aq:= λBc−Ac0 0 0λBq r−Aq r0 0 0 λBf−Af →λB −A. Now, as Nis a subspace (λB −A)-stable, there exists a sequence of subspaces Nq→ N such that Nqis a (λBq−Aq)-reducing subspace for every q. By the form of λBq−Aq, from Theorem 20 we know that there exists a sequence of matrices Xq→Xwhere Nq=* In1O O Xq O O +, hXqibeing a (λBq r−Aq r)-deflating subspace. Hence the subspace hXqiis (λBr− Ar)-stable. 2 18
Remark 30. Observe that by [5, Theorem 14.3.1, p. 429] and [7], if hXiis (λBr−Ar)-stable, then hXiis isolated; that is, there exists a neighbourhood of the subspace hXisuch that the unique (λBr−Ar)-deflating subspace that is in this neighbourhood is hXiitself. Lemma 31. Consider a pencil λB −A∈ P[λ]m×nand a (λB −A)-reducing subspace N, both in the form λB −A= n1n2 m1λD −C O m2O λF −E,N=X O,(44) with X∈Cn1×pa matrix of rank p, the pencil λD −Cis left regular and the pencil λF −Eonly has row minimal indices. Then the subspace hXiis (λD −C)-reducing. Moreover, if the subspace Nis (λB −A)-stable, then hXi is (λD −C)-stable. Proof. As λD −Cis left regular and λF −Eonly has row minimal indices, it follows that ν(λB −A) = ν(λD −C). Hence, as Nis (λB −A)-reducing we have dim(A(N)+B(N)) = p−ν(λD−C). Therefore, from (44) we deduce that rank(CX, DX) = rank(X)−ν(λD −C), that is, hXiis (λD −C)-reducing. Consider now an arbitrary sequence λDq−Cq→λD−C. Then the sequence λBq−Aq=λDq−CqO O λF −E→λB −A, (45) and moreover, as λF −Eonly has row minimal indices, ν(λBq−Aq) = ν(λDq−Cq).(46) Now then, as Nis (λB−A)-stable, there exists a sequence of subspaces Nq→ N such that Nqis (λBq−Aq)-reducing for every q. Due to the form of λBq−Aq, given in (45), from Theorem 20 we see that there exists a sequence of matrices Xq→Xsuch that for every q Nq=Xq O.(47) Therefore, because Nqis a (λBq−Aq)-reducing subspace, from (46) it follows that dim(Aq(Nq) + Bq(Nq)) = p−ν(λDq−Cq). That is, from (45), (46) and (47), we infer that rank(Xq)−ν(λDq−Cq) = p−ν(λDq−Cq) = rank CqXqDqXq O O = rank(CqXq, DqXq). Hence hXqiis (λDq−Cq)-reducing for every q. Lastly, as Xq→Xwe have hXi is (λD −C)-stable. 2 Lemma 32. Consider a pencil λB −A∈ P[λ]m×nand a (λB −A)-reducing subspace N, both in the form λB −A= n1n2 m1λD −C O m2O λF −E,N=In1O O X,(48) 19
with X∈Cn2×pa matrix of rank p, the pencil λD −Cis left regular and the pencil λF −Eis right regular. Then the subspace hXiis (λF −E)-reducing. Moreover, if the subspace Nis (λB −A)-stable we have hXiis (λF −E)-stable. Proof. Observe first that ν(λB −A) = ν(λD −C) = n1−m1. Thus, as Nis (λB −A)-reducing, it follows that dim(A(N) + B(N)) = p+m1, and hence, from (48), we see that rank C O D O O EX O FX=p+m1. Therefore, as rank(C, D) = m1and ν(λF −E) = 0, we have rank(EX, FX) = p= rank(X)−ν(λF −E), that is, hXiis (λF −E)-reducing. Consider now an arbitrary sequence λFq−Eq→λF −E. Then the sequence λBq−Aq=λD −C O O λFq−Eq→λB −A, (49) and moreover, as λFq−Eqis right regular, ν(λBq−Aq) = ν(λD −C) = n1−m1.(50) Now, given that Nis (λB −A)-stable, from (48) we deduce that there exist two sequences of matrices, Xq→Xand Yq→O, such that for every qthe subspace Nq=In1O YqXq.(51) is (λBq−Aq)-reducing. Therefore, from (49) and (51) we infer that p+m1= rank C O D O EqYqEqXqFqYqFqXq≥rank(C, D)+rank(EqXq, FqXq). Now, as rank(C, D) = m1and ν(λFq−Eq) = 0 we have rank(EqXq, FqXq) = p= rank(Xq)−ν(λFq−Eq), therfore hXqiis (λFq−Eq)-reducing for every q. Finally, since Xq→X, it follows that hXiis (λF −E)-stable. 2 Lemma 33. Suppose that the matrix pencil λB −A∈ P[λ]m×nhas no row minimal indices. Then the unique (λB −A)-stable subspace is Cn. Proof. Let Nbe a (λB −A)-stable subspace. Given that the pencil has no row minimal indices, from Remark 26, (2) and Theorem 20 we can assume that λB −Aand Nare in the form λB −A= n1n2 m1λBc−AcO n2O λBr−Ar,N=* n1p n1In1O n2O X +,(52) where λBc−Acis a pencil with only column minimal indices, λBr−Aris a regular pencil, Xis a matrix of rank pand hXiis a (λBr−Ar)-deflating 20
subspace. Thus by [7] we can assume that λBr−Ar= λN1−Ip1λN3O O O λN2−Ir1O O O O λIp2−J1−J3 O O O λIr2−J2 , X = Ip1O O O O Ip2 O O , (53) with N1,N2and N3nilpotent matrices and p1+p2=p. Consider now two arbitrary sequences of matrices Eq→O∈Cq2×n1and Fq→O∈Cq1×n1. As the sequence λBq−Aq= λBc−AcO O O O O λN1−Ip1λN3O O λFqO λN2−Ir1O O O O O λIp2−J1−J3 EqO O O λIr2−J2 (54) converges to λB −Aand the subspace Nis (λB −A)-stable, it follows that there exist sequences of matrices Yq, Zq, Uq, Vq, Wq, Hqof adequate sizes, all of them converging to O, such that for every qthe subspace Nq=* In1O O O Ip1O YqUqWq O O Ip2 ZqVqHq +(55) is (λBq−Aq)-reducing, that is dim(Aq(Nq)+Bq(Nq)) = dim(Nq)−ν(λBq−Aq). But as the pencil λB −Ahas no row minimal indices, we have ν(λBq−Aq) = ν(λB −A) = n1−m1. Therefore dim(Aq(Nq)+Bq(Nq)) = n1+p+(n1−m1) = m1+p. Thus from (54) and (55) we conclude that rank n1p1p1n1p2p2 m1AcO O BcO O p1O Ip1O N3YqN1+N3UqN3Wq r1YqUqWqFq+N2YqN2UqN2Wq p2J3ZqJ3VqJ1+J3HqO O Ip2 r2Eq+J2ZqJ2VqJ2HqZqVqHq =m1+p. (56) Since rank(Ac) = rank(Bc) = m1, from (56) we see that rank Ip1O N1+N3UqN3Wq UqWqN2UqN2Wq J3VqJ1+J3HqO Ip2 J2VqJ2HqVqHq =p. Consequently, from (53), the subspace Mqgenerated by the columns of the matrix Xq= Ip1O UqWq O Ip2 VqHq 21
is (λBr−Ar)-stable. Hence, by Remark 30 we infer that hXqi=hXifor every q, and therefore the matrices of the sequences Uq, Vq, Wq, Hqare all zero. So, from (56) we deduce that rank n1n1 m1AcBc r1YqFq+N2Yq r2Eq+J2ZqZq =m1.(57) At this point, note that to prove the lemma it suffices to verify that r1=r2= 0. For the sake of contradiction, assume first that r1>0, then as rank(Ac) = rank(Bc) = m1, from (57) we deduce that rank AcBc YqFq+N2Yq=m1.(58) Now, by Lemma 22 there exists a matrix Q∈Cn1×n1with 0 ∈Λ(Q) such that Bc=AcQ. Then from (58) we immediately obtain m1= rank(Ac) = rank AcAcQ YqFq+N2Yq= rank AcO YqFq+N2Yq−YqQ, and hence Fq+N2Yq−YqQ=O. In conclusion, if it were true that r1>0, we would have proved that for every sequence of matrices Fq→Othere exits a sequence of matrices Yq→Osuch that for each qit satisfies Fq+N2Yq−YqQ= O, with Λ(N2)∩Λ(Q)6=∅, which is impossible. Therefore, r1= 0. If it were true that r2>0, as by Lemma 22 there exists a matrix Q∈Cn1×n1 with Λ(J2)∩Λ(Q)6=∅, so that Ac=BcQ, applying the previous reasoning we would lead to a contradiction. Thus r2= 0. 2 Lemma 34. Given a matrix pencil λB −A∈ P[λ]m×n, suppose that it has no column minimal indices. Then the unique (λB −A)-stable subspace is {0}. Proof. Let Nbe a (λB −A)-stable subspace. We can now proceed analogously to the proof of the previous lemma. So, we can assume that λB −Aand Nare in the form λB −A= n2n3 n2λBr−ArO m3O λBf−Af,N=* p n2X n3O+,(59) where λBr−Aris a regular pencil and hXiis a (λBr−Ar)-deflating subspace, both in the form (53). Moreover, λBf−Afis a pencil that only has row minimal indices. Now consider two arbitrary sequences of matrices Eq→O∈Cm3×p2and Fq→O∈Cm3×p1. As the sequence λBq−Aq= λN1−Ip1λN3O O O O λN2−Ir1O O O O O λIp2−J1−J3O O O O λIr2−J2O λFqO−EqO λBf−Af , (60) 22
converges to λB−Aand the subspace Nis (λB−A)-stable, there exist sequences of matrices Yq, Zq, Uq, Vq, Wq, Hq, of adequate sizes, that converge to O, such that for every qthe subspace Nq=* Ip1O UqWq O Ip2 VqHq YqZq +(61) is (λBq−Aq)-reducing; that is dim(Aq(Nq)+Bq(Nq)) = dim(Nq)−ν(λBq−Aq). But as the pencil λB −Ahas no column minimal indices, then ν(λBq−Aq) = ν(λB −A) = 0. Therefore dim(AqNq+BqNq) = p. Thus from (60) and (61) we see that rank p1p2p1p2 p1Ip1O N1+N3UqN3Wq r1UqWqN2UqN2Wq p2J3VqJ1+J3HqO Ip2 r2J2VqJ2HqVqHq m3AfYqEq+AfZqFq+BfYqBfZq =p. (62) Now, as the sequences Yq, Zq, Uq, Vq, Wq, Hqconverge to O, from (62) rank Ip1O N1+N3UqN3Wq UqWqN2UqN2Wq J3VqJ1+J3HqO Ip2 J2VqJ2HqVqHq =p; that implies for (53) that the subspace Mqgenerated by the matrix Xq= Ip1O UqWq O Ip2 VqHq is (λBr−Ar)-deflating. Hence, like in the previous lemma, all the terms of the sequences of matrices Uq, Vq, Wq, Hqare O. Thus from (62) we infer that rank p1p2p1p2 p1Ip1O N1O p2O J1O Ip2 m3AfYqEq+AfZqFq+BfYqBfZq =p; that is Fq+BfYq−AfYqN1=O, Eq+AfZq−BfZqJ1=O. (63) Now, by Lemma 22 there exist matrices P, Q ∈Cm3×m3with 0 ∈Λ(P) and Λ(J2)∩Λ(Q)6=∅such that Bf=PAfand Af=QBf. Then we immediately see from (63) that for every pair of sequences of matrices Eq, Fq→Othere are sequences Yq, Zq→Othat satisfy Fq+PAfYq−AfYqN1=O, Eq+QBfZq−BfZqJ1=O, 23
for every q. This contradicts to the choice of Pand Q. Consequently p1=p2= 0 and therefore N={0}.2 We are now ready to prove Assertions (1) (2) and (3) of Theorem 4. Proof Theorem 4: Assertions (1), (2) and (3). First, note that Assertions (2) and (3) follow straightforward from Lemmas 33 and 34, respectively. Second, to prove Assertion (1), by Remark 28, we can assume that λB −Ais in the form given in (2), with n1, n2, m3nonzero . Let Nbe a (λB−A)-reducing subspace. Then, by Theorem 20, we can assume that N=* n1p n1In1O n2O X m3O O +, where rank(X) = p. Suppose that Nis (λB −A)-stable. Hence, as the pencil diag(λBc−Ac, λBr−Ar) is left regular and the pencil λBf−Afonly has row minimal indices, applying Lemma 31, we deduce that the subspace In1O O X is diag(λBc−Ac, λBr−Ar)-stable. Therefore, by Lemma 33 we have X=In2. On the other hand, applying Lemma 32 to the pencils λBc−Ac(left regular) and diag(λBr−Ar, λBf−Af) (right regular), since Nis (λB −A)-reducing, we see that the subspace generated by the columns of the matrix In2 Ois diag(λBr−Ar, λBf−Af)-stable, which contradicts Lemma 34. 2 6 Proof of Theorem 4: Assertion (4). In this section we prove Assertion (4) of Theorem 4. Therefore in all the section we will assume that the pencil λB −Ahas row minimal indices, at least two column minimal indices, and no eigenvalues. The following result will allow us to simplify the proofs. Lemma 35. Let λB −A∈ P[λ]m×nbe a pencil without eigenvalues and let N be a (λB −A)−reducing subspace, which are given by λB −A= n1n2 m1λD −C0 n20λF −E,N=* p1p2 n1X0 n20Y+, where X, Y are matrices of full column rank. Let M:= hXi. Then if Nis (λB −A)−stable it follows that Mis (λD −C)−stable. Proof. Note that as the pencil λF −Ehas no eigenvalues, from (31) and (33) we see that Dk λB−A=Sk λB−A. Hence by Theorem 20 we infer that hYi=Dn λF −E=Sn λF −E.(64) 24
Consider now an arbitrary sequence λDq−Cq→λD −C. Then as the sequence λBq−Aq=λDq−Cq0 0λF −E converges to λB −Aand Nis (λB −A)−stable, there exist sequences Xq→X, Yq→Y,Zq→0, Vq→0, such that for every qthe subspace Nq:= XqZq VqYq (65) is (λBq−Aq)−reducing. Therefore, by Theorem 20, Nq⊂ Dn λBq−Aq. Now applying Lemma 14 and (64), we obtain Nq⊂ Dn λBq−Aq=Dn λDq−Cq O⊕O Dn λF −E⊂In1 O⊕O Y=In1O O Y . For this reason from (65) there exist matrices of adequate sizes Qi,i= 1,2,3,4, such that XqZq VqYq=In1O O Y Q1Q2 Q3Q4. Observe that Yq=Y Q4. Moreover, as Yq→Yand Yis of full column rank, we deduce that Q4is invertible. Hence, as Vq=Y Q3, it follows that Vq=YqQ−1 4Q3. Thus, in (65), if we subtract to the first column the second one multiplied by Q−1 4Q3we obtain Nq=Xq−ZqQ−1 4Q3Zq O Y Q4=Xq−ZqQ−1 4Q3ZqQ−1 4 O Y .(66) In the same way, from Theorem 20, Lemma 14 and (64) we obtain Nq⊃ Sn λBq−Aq=Sn λDq−Cq O⊕O Sn λF −E=Sn λDq−Cq O⊕O Y⊃O Y. From (66) we deduce that there exist matrices of adequate sizes P1, P2such that O Y=Xq−ZqQ−1 4Q3ZqQ−1 4 O Y P1 P2. Hence P2=Ip2and ZqQ−1 4=−(Xq−ZqQ−1 4Q3)P1. Therefore denoting ˜ Xq:= Xq−ZqQ−1 4Q3→X, from (66) we see that Nq=˜ XqO O Y . Finally, as Nqis (λB −A)−reducing rank Cq˜ XqO Dq˜ XqO O EY O F Y =p1+p2−ν(λDq−Cq)−ν(λF −E).(67) But given that hYiis a (λF−E)−reducing subspace, it follows that rank(EY, FY ) = p2−ν(λF −E). Thus from (67) we conclude that rank(Cq˜ Xq, Dq˜ Xq) = p1− ν(λDq−Cq); that is the subspace D˜ XqEis (λDq−Cq)−reducing. Consequently Mis (λD −C)−stable. 2 25
to prove the lemma we can assume that (G, H) = (G, H). Denote α:= (a1, a2,· · · , ah) with ai∈C1×ri. Then, because nrank(λD −C) = m, we have nrank λIr1−G1−H10 0 · · · 0 0 0 0 Ir2−G2−H2· · · 0 0 . . .. . .. . .. . ..... . .. . . 0 0 0 0 . . . Irh−Gh−Hh a10a20. . . ah0 =m. (73) Now, as (λIri−Gi,−Hi) = λ−1 0 . . . 0 0 0λ−1. . . 0 0 . . .. . .. . ..... . .. . . 0 0 0 . . . λ −1 , if we denote by ai:= (bi1, bi2, . . . , biri), making transformations by columns in the matrix of (73), we deduce that nrank 0−Ir10 0 · · · 0 0 000−Ir2· · · 0 0 . . .. . .. . .. . ..... . .. . . 0000. . . 0−Irh p1(λ)? p2(λ)? . . . ph(λ)? =r1+r2+· · ·+rh=m, with pi(λ) = bi1+bi2λ+· · · +biriλri−1. Therefore pi(λ) = 0, or equivalently α= 0. 2 Consider now a sequence λBq−Aq→λB −A. From (72), we can assume that for every q, λBq−Aq=λIq mβq αqδq−EqFq ηqθq. Now, as m= nrank(λBq−Aq)≥rank(Aq)≥rank(Eq, Fq)≥rank(E, F) = m, it is immediate to see that there exists a sequence of matrices Pq=Im0 ξq1→Im+1, such that for every q PqAq=EqFq 0 0 . Hence, by Proposition 27, it suffices to consider sequences of the form Pq(λBq− Aq) to study the stability of the subspace Cn, that is, λBq−Aq=λIq mβq αqδq−EqFq 0 0 →λB −A. (74) On the other hand, as the sequence of matrices Qq=(Iq m)−1−(Iq m)−1βq 0 1 →Im+1, 32
by Proposition 27 it is sufficient to consider sequences of the form (λBq−Aq)Qq; that is, from (74), λBq−Aq=λIm0 αqδq−EqFq 0 0 →λB −A. But, since m= nrank(λBq−Aq)≥rank(Bq)≥m, we have δq= 0, for every q. , λBq−Aq=λIm0 αq0−EqFq 0 0 . Now, since (Eq, Fq) is controllable and nrank(λB −A) = m, by Lemma 37 it follows that αq= 0 for every q. Hence, it suffices to consider sequences of the form λBq−Aq=λIm0 0 0−EqFq 0 0 . Finally, as rank(AqIn, BqIn) = m=n−ν(λBq−Aq), then the subspace Cnis (λBq−Aq)-reducing and, , Cnis (λB −A)-stable. 8 Proof of Assertion (6) of Theorem 4 In this section we will prove that if the pencil λB −A∈ P[λ]m×nhas only one row minimal index which is different than zero, at least two column minimal indices and no eigenvalues, then it has not any stable reducing subspace. First note that from Lemma 35, in an analogous way as in Remark 36, we can assume that λB −Aonly has two column minimal indices. Hence we consider three subcases: (a) two column minimal indices which are equal to zero; (b) one column minimal index which is equal to zero and another column minimal index which is different than zero; (c) both column minimal indices which are different than zero. 8.1 Two column minimal indices which are equal to zero Denote D:= Ik 0, C := 0 Ik∈C(k+1)×k, in this case we can assume that the pencil λB −Aand the unique reducing subspace Nare of the form λB −A=λ(0, D)−(0, C)∈ P[λ](k+1)×(2+k),N=I2 0, respectively. Consider the sequences of matrices aq= 1/q 0 0 0 . . .. . . 0 0 , bq= 0 0 . . .. . . 0 0 0 1/q ∈C(k+1)×2, the sequence λBq−Aq=λ(bq, D)−(aq, C) converges to λB −Aand moreover ν(λBq−Aq) = 1. Now, if Nis (λB −A)-stable, by Proposition 24 there exists a sequence of matrices Xq→0∈Ck×2such that for every qthe subspace 33
Nq=DI2 XqEis (λBq−Aq)-reducing; that is, dim(Aq(Nq) + Bq(Nq)) = 1. Therefore, if we define Xq:= (xq ij)1≤i≤k,j=1,2so that Nqcan be (λBq−Aq)- reducing, it must be satisfied rank 1/q 0xq 11 xq 12 xq 11 xq 12 xq 21 xq 22 . . .. . .. . .. . . xq k−1,1xq k−1,2xq k1xq k2 xq k1xq k20 1/q = 1. Hence xq ij = 0. Thus, we conclude that rank 1/q 0 0 1/q = 1, which is a contradiction. In conclusion, Nis not (λB −A)-stable. 8.2 One column minimal index which is equal to zero and another column minimal index which is different than zero Define λD −C:= λ[In,0] −[0, In] and λF −E:= λIm 0−0 Im, in this case it follows that the pencil λB −Aand its unique reducing subspace Nhave the form λB −A=0λD −C0 0 0 λF −E,N=* 1 0 0In+1 0 0 +, respectively. Consider the sequences aq= 1/q . . . 0 ∈C(m+1)×1, bq= 0· · · 0 0 . . ....0 0 0· · · 0 1/q ∈C(m+1)×(n+1). Then λBq−Aq=λ0D0 0bqF−0C0 aq0E→λB −A, and moreover ν(λBq−Aq) = 1. Hence, if Nis (λB −A)-stable, there exist sequences of matrices Xq→0∈Cm×1and Yq→0∈Cm×(n+1) such that the subspace Nq:= * 1 0 0In+1 XqYq +, is (λBq−Aq)-reducing; that is, dim(Aq(Nq) + Bq(Nq)) = n+ 1. Thus rank 0C0D aq+EXqEYqF Xqbq+FYq=n+ 1.(75) Define Xq:= (xq 1, xq 2, . . . , xq m)T. Then as rank C=n, from (75) we have 1≥rank(aq+EXq) = rank 1/q xq 1· · · xq m−1xq m xq 1xq 2· · · xq m0T . 34
Therefore xq i= 0 and Xq= 0. Now, denote by Yq n+1 := (yq 1, yq 2, . . . , yq m)Tthe last column of Yq. As rank D=n, from (75) we see that 1≥rank(aq, bq+FY q n+1) = rank 1/q 0· · · 0 0 yq 1yq 2· · · yq m1/qT , which is a contradiction. Thus, N=Cn+1 is not (λB −A)-stable. 8.3 Two column minimal indices which are different than zero. Define λD −C:= λ[In,0] −[0, In], λF −E:= λ[Ip,0] −[0, Ip] and λH −G:= λIm 0−0 Im, in this case we infer that the pencil λB −Aand its unique reducing subspace Nhave the form λB −A= λD −C0 0 0λF −E0 0 0 λH −G ,N=* In+1 0 0Ip+1 0 0 +, respectively. Consider the sequences aq= 1/q 0· · · 0 0 0 · · · 0 . . .. . ....0 0 0 · · · 0 ∈C(m+1)×(n+1), bq= 0· · · 0 0 . . ....0 0 0· · · 0 1/q ∈C(m+1)×(p+1). Then λBq−Aq=λ D0 0 0F0 0bqH − C0 0 0E0 aq0G →λB −A, and moreover, ν(λBq−Aq) = 1. Hence, if Nis (λB −A)-stable, there exist sequences of matrices Xq→0∈Cm×(n+1) and Yq→0∈Cm×(p+1) such that the subspace Nq:= * In+1 0 0Ip+1 XqYq + is (λBq−Aq)-reducing; that is, dim(Aq(Nq) + Bq(Nq)) = n+p+ 1. Therefore rank C0D0 0E0F aq+GXqGYqHXqbq+HYq =n+p+ 1. Denote by Xq= (xij) and Yq= (ykl), from the previous equality it follows that rank 0In0 0 In0 0 0 0 0 0 Ip0 0 Ip0 1/q 0···0 0 0 ···0x11 ···x1nx1,n+1 y11 ···y1py1,p+1 x11 x12 ···x1,n+1 y11 y12 ···y1,p+1 x21 ···x2nx2,n+1 y21 ···y2py2,p+1 . . .. . .. . .. . .. . .. . .. . .. . . xm1xm2···xm,n+1 ym1ym2···ym,p+1 0···0 0 0 ···0 1/q =n+p+1. 35
Observe now that, choosing the submatrix formed by the n+p+ 2 first columns, we deduce immediately that yi1= 0 for i= 1,2, . . . , m. In the same way, with the n+p+ 2 last columns we see that xi,n+1 = 0 for i= 1,2, . . . , m. Hence with the entries 1 corresponding to the places (n, n + 1) and (n+ 1,2n+ p+4) we can reduce the previous matrix to one on the same form, but reducing the sizes from nto n−1 and from pto p−1, and whose rank is n+p−1. Following this process we reach the case where at least one column minimal index is equal to zero, which is already solved in Subsections 8.1 and 8.2. 9 Proof of Assertion (7) of Theorem 4 In this section we will analyze the case of a matrix pencil with only one row minimal index which is different than zero, and one column minimal index which is equal to zero. Previously we will introduce some auxiliary results. We begin by stating some bounds about the maximum modulus of a root of a polynomial, that can be seen in [14], Section 8, pp. 243–247. Lemma 38. Let f(z) = a0+a1z+· · ·+an−1zn−1+znbe a polynomial of degree nwith coefficients in Cdistinct from the polynomial zn. Denote α:= max 0≤k≤n−1 n k−1 |ak|!1/(n−k) . Assume that znis a root of maximum modulus of f(z). Then (21/n −1)α < |zn| ≤ (21/n −1)−1α. In order to prove Lemma 41, we need the following two lemmas. The first one, Lemma 39, is deduced immediately from (34). Lemma 39. Consider the matrix pencil λB −A∈ P[λ]m×nand the matrix Tk λB−Adefined in (28). Then (i) If ν(Tk λB−A)=0, then λB −Ahas not any column minimal indices ≤k−1. (ii) If λB −A=λ(Ik,0) −(0, Ik)∈ P[λ]k×(k+1), then ν(Tp λB−A) = (0if p≤k 1if p≥k+ 1. The second one, Lemma 40, can be seen in [5], Theorem 13.5.1, p. 406. Lemma 40. Let F∈Cp×qand let X∈Cq×rbe a basis matrix of KerF. Consider a sequence Fq→Fsuch that, for every q,ν(Fq) = ν(F). Then there exist a sequence Xq→Xand a positive constant K1such that, for every q,Xq is a basis matrix of KerFqand kXq−Xk ≤ K1kFq−Fk. 36
Based on these results we will prove the following lemma. Lemma 41. Consider the pencil λB −A=λ(Ik,0) −(0, Ik)∈ P[λ]k×(k+1). Then for each sequence λBq−Aq→λB−Athere exist two sequences of matrices Pq→Ikand Qk→Ik+1 such that, for every q, we have P−1 q(λBq−Aq)Qq= λB −A; moreover, there exists a constant K > 0that satisfies max{kPq−Ikk,kQq−Ik+1k} ≤ K(kAq−Ak+kBq−Bk). Proof. Note first that by Lemma 39, ν(Tk+1 λB−A) = 1. Denote by {e1, e1, . . . , ek+1} the vectors of the canonical basis of Ck+1, it is clear that Ker(Tk+1 λB−A) = * ek+1 ek . . . e1 +.(76) Now consider a sequence λBq−Aq→λB −A. Since nrank(λBq−Aq) = k, it follows that the pencil λBq−Aqhas at least a column minimal index. Moreover, for every pwe have ν(Tp λBq−Aq)≤ν(Tp λB−A), by Lemma 39, it follows that the pencil λBq−Aqhas not any column minimal indices < k. That is, it has one column minimal index which is equal to k; hence ν(Tk+1 λBq−Aq) = ν(Tk+1 λB−A). Since Tk+1 λBq−Aq→Tk+1 λB−Aand for every qthe matrices Tk+1 λBq−Aqhave the same nullity, it follows from (76) and Lemma 40 that there exists a basis matrix of the subspace Ker(Tk+1 λBq−Aq) xq k+1 xq k . . . xq 1 converging to ek+1 ek . . . e1 such that kxq i−eik ≤ K1(kAq−Ak+kBq−Bk). Now let Pq:= (Aqxq 2,· · · , Aqxq k+1), Qq:= (xq 1,· · · , xq k+1). It is obvious that P−1 q(λBq−Aq)Qq=λB−Aand kQq−Ik+1k ≤ K1(kAq−Ak+ kBq−Bk). It suffices to demonstrate that kPq−Ikk ≤ K2(kAq−Ak+kBq−Bk) to conclude the proof of the lemma. In fact, denoting by (f1, f2, . . . , fk) the canonical basis of Ck, it follows that kPq−Ikk ≤ k+1 X i=2 kAqxq i−fi−1k= k+1 X i=2 kAqxq i−Aeik. Now kAqxq i−Aeik ≤ kAqxq i−Aqeik+kAqei−Aeik≤kAqkkxq i−eik+kAq−Akkeik ≤(kAq−Ak+kAk)kxq i−eik+kAq−Ak ≤ K2(kAq−Ak+kBq−Bk), 2 With these previous results we are ready to prove Assertion (7) of Theorem 4. Proof of Assertion (7) of Theorem 4 37
Define D:= In 0and C:= 0 In, both matrices of C(n+1)×n. Hence, λB −A=λ(0, D)−(0, C)∈ P[λ](n+1)×(n+1). The unique reducing subspace of λB −Ais N=he1i, with e1the first canonical vector of Cn+1. Note that ν(λB −A) = 1. Now consider a sequence (λBq− Aq)→(λB −A). Then, by Lemma 40 and by Proposition 27, when studying the Lipschitz stability of the subspace N, no generality is lost if we only consider sequences of the form λBq−Aq=λ(εq, D)−(δq, C). Operating with the columns of D, by Proposition 27, we can assume that λBq−Aq=λ0In aq0−bq0 HqIn,(77) with Hq= (cq 1, cq 2, . . . , cq n)T∈Cn. Note that making row operations it is immediate to see that det(λBq−Aq) = aqλn+1 − n X i=1 cq iλi−bq. Therefore, ν(λBq−Aq) = 1 if and only if aq=bq=cq i= 0, which is equivalent to λBq−Aq=λB−A. For this case, it is clear that Nq=Nis a reducing subspace for λBq−Aq. Thus, from here on, we will assume that ν(λBq−Aq) = 0. In order to prove that Nis Lipschitz stable, it suffices to find sequences of complex numbers xq i,i= 1,2, . . . , n, such that for every q, the subspace Nq:= * 1 xq 1 xq 2 . . . xq n + is (λBq−Aq)−reducing; that is, since ν(λBq−Aq) = 0, it follows that dim Aq(Nq)+ Bq(Nq) = 1 holds. Or, which is the same, from (77) rank bqxq 1 cq 1+xq 1xq 2 cq 2+xq 2xq 3 . . .. . . cq n−1+xq n−1xq n cq n+xq naq = 1,(78) and, moreover, that there exists a constant K > 0 such that, |xq i| ≤ K(kBq−Bk+kAq−Ak), i = 1,2, . . . , n. (79) Note first that if aq= 0, it suffices to take xq i= 0 for each i. On the other hand, if bq= 0, it is sufficient to choose xq i=−cq ifor each i. Hence, we will assume that aqbq6= 0. In order for (78) to hold, since aq6= 0, we search for the xq iin such a way that the first column is proportional to the second one. Note 38
that the proportionality factor is bq 1/xq 1. Now, doing operations in (78), by a induction process it is proved that xq k= (xq 1)k+ k−1 X i=1 cq ibi−1 q(xq 1)k−i bk−1 q , k = 2,3, . . . , n, (80) and for xq 1we have (xq 1)n+1 + n X i=1 cq ibi−1 q(xq 1)n−i+1 −aqbn q= 0.(81) Consider the polynomial fq(z) := zn+1 + n X i=1 cq ibi−1 qzn−i+1 −aqbn q. We find a bound for the maximum modulus of its roots. Define Bk n+1 := n+1 k−1/(n−k+1), by Lemma 38, α= max{B0 n+1 |aqbn q|1/(n+1), B1 n+1 |cq nbn−1 q|1/n,..., . . . , |Bk n+1 |cq n−k+1bn−k q|1/(n−k+1), . . . , Bn n+1 |cq 1|}.(82) After that, we choose xq 1as one of the roots of f(z) that have maximum modulus. By Lemma 38 and (82) it is clear that xq 1satisfies (79). Let k∈ {2,3, . . . , n}. Then, combining (80) and (81) we infer that xq k=− n X i=k cq ibi−1 q(xq 1)n−i+1 −aqbn q bk−1 q(xq 1)n+1−k=− n X i=k cq ibi−k q (xq 1)i−k+aqbn−k+1 q (xq 1)n−k+1 .(83) In order to conclude this case, it suffices to see that each summand of (83) is bounded by K(kBq−Bk+kAq−Ak), for a positive constant K. First, by Lemma 38 and (82) it follows that there exists a positive constant Lsuch that |xq 1|−1≤L|aqbn q|−1/(n+1). Therefore, aqbn−k+1 q (xq 1)n−k+1 ≤L aqbn−k+1 q (aqbn q)(n−k+1)/(n+1) =Lak/(n+1) qb(n−k+1)/(n+1) q≤K(kBq−Bk+kAq−Ak). Second, following Lemma 38 and (82) again, we see that there exists a positive constant Lisuch that |xq 1|−1≤Li|cq ibi−1 q|−1/i. Thus, cq ibi−k q (xq 1)i−k ≤Li cq ibi−k q (cq ibi−1 q)(i−k)/i =Li(cq i)k/ib(i−k)/i q≤K(kBq−Bk+kAq−Ak). 2 Acknowledgement The authors thank the referee for the detailed help in improving the writing of this article. 39
References [1] F. Chatelin: Valeurs propres de matrices, Masson, Paris, 1988. [2] J.W. Demmel, B. K˚agstr¨om: Computing stable eigendecompositions of matrix pencils. Linear Algebra Appl. 88-89 (1987) 139–186. [3] J. Ferrer, M.I. Garc´ıa, F. Puerta: Differentiable families of subspaces, Linear Algebra Appl.,199 (1994) 229–252. [4] F. R. Gantmacher: Th´eorie des matrices I, II, Dunod, Paris, 1966. [5] I. Gohberg, P. Lancaster, L. Rodman: Invariant subspaces of matrices with applications, John Wiley, New York, 1986. [6] J.M. Gracia, I. de Hoyos: Safety neighbourhoods for the Kronecker canonical form, (1998). Report. http://www.vc.ehu.es/campus/centros/farmacia/deptos-f/depme/root98_2.dvi. [7] J.M. Gracia, F.E. Velasco: Stability of invariant subspaces of regular matrix pencils, Linear Algebra Appl.,221 (1995) 219–226. [8] J.M. Gracia, F.E. Velasco: Lipschitz stability of controlled invariant subspaces, Linear Algebra Appl.,434 (2011) 1137–1162. [9] I. de Hoyos: Perturbaci´on de matrices rectangulares y haces de matrices, Ph. D. Thesis, University of the Basque Country UPV/EHU, Bilbao, 1990. [10] V. Ionescu, C. Oarˇa, M. Weiss: Generalized Riccati theory and robust control: A Popov function approach, Wiley, New York, 1999. [11] N. Karkanias, G. Kalogeropoulos: On the Segre, Weyr characteristic of right (left) regular matrix pencils, Int. J. Control,44, no. 4 (1986), 9911015. [12] N. Karkanias, G. Kalogeropoulos: Right, left characteristic sequences and column, row minimal indices of a singular pencil, Int. J. Control,47, no. 4 (1988), 937–946. [13] C. Oarˇa, P. Van Dooren: An improved algorithm for the computation of structural invariants of a system pencil and related geometric aspects. Systems and Control Letters, 30 (1997) 39–48. [14] Q. I. Rahman, G. Schmeisser: Analytic theory of polynomials, Clarendon Press, Oxford, 2002. [15] L. Rodman: Stable invariant subspaces modulo a subspace, Operador Theory: Advances and Applications,19 (1986) 399–413. [16] W. G. Stewart: On the sensitivity of the eigenvalue problem Ax =λBx, SIAM J. Numer. Anal.,9(1972) 669–686. [17] P. Van Dooren: Reducing subspaces: definitions, properties and algorithms, in the book Matrix pencils, Lectures Notes in Mathematics No. 973, Springer, Berlin, Heidelberg, 1983. 40
[18] F.E. Velasco: Stable subspaces of matrix pairs, Linear Algebra Appl., 301(1999)15–49. 41