Math. Control Signals Syst. (2010) 22:39–89 DOI 10.1007/s00498-010-0051-6 ORIGINAL ARTICLE

On the geometry of the generalized partial realization problem I. Baragaña · F. Puerta · X. Puerta · I. Zaballa

Received: 7 October 2008 / Accepted: 29 June 2010 / Published online: 15 July 2010 © Springer-Verlag London Limited 2010

Abstract The geometry of the set of generalized partial realizations of a finite nice sequence of matrices is studied. It is proved that this set is a stratified manifold, the dimension of their strata is computed and its connection with the geometry of the cover problem is clarified. The results can be applied, as a particular case, to the classical partial realization problem. Keywords (A, B)-controlled invariant subspace · Brunovsky indices · Smooth manifold · Grassmann manifold · Partial realization · Cover problem

I. Baragaña was partially supported by DGICYT MTM2007-67812-C02-01 and Gobierno Vasco GIC07/154-IT-327-07. F. Puerta was partially supported by DGICYT MTM2007-67812-C02-02. X. Puerta was partially supported by DGICYT MTM2007-67812-C02-02. I. Zaballa was partially supported by DGICYT MTM2007-67812-C02-01 and Gobierno Vasco GIC07/154-IT-327-07. I. Baragaña Departamento de Ciencias de la Computación e IA, Universidad del País Vasco, Apdo. 649, 20080 Donostia-San Sebastián, Spain e-mail: [email protected] F. Puerta (B) · X. Puerta Departament de Matemàtica Aplicada I, E.T.S. Enginyeria Industrial de Barcelona, UPC Institut d’Organització i Control(IOC) UPC, Diagonal 647, 08028 Barcelona, Spain e-mail: [email protected] X. Puerta e-mail: [email protected] I. Zaballa Departamento de Matemática Aplicada y EIO, Universidad del País Vasco, Apdo. 644, 48080 Bilbao, Spain e-mail: [email protected]

123

40

I. Baragaña et al.

1 Introduction Realization theory is a central topic in linear system theory but it also finds applications in other parts of applied mathematics (see, for example [19] and the references therein). It is not surprising then that since the first treatment of this problem by Kalman [21,22], many authors have investigated various aspects of the problem such as parametrizations, algorithms for constructing realizations, extensions to linear descriptor systems, topological and geometric aspects of the problem, etc. (see among others [4,5,16,19,23,25,34]). In 1978, Brockett [5] posed two problems on the geometry of the partial realization problem. One of them asked for studying the geometry of the real or complex sequences (h 0 , h 1 , . . . , h n−1 ) which admit a minimal realization of fixed order and the other about the geometry of the set of minimal systems that realize a given such a sequence. Brockett himself provided a first approach to the solution of the former problem and several years later the task was completed in [25]. The aim of the present paper is to provide with a differentiable structure the set of solutions of the generalized partial realization problem; a big generalization of Brockett’s second problem (see below). This objective can now be attained due to the attention that has been paid during the last decades to the general problem of endowing with a differentiable structure sets that, like the set of solutions of the partial realization problem, outstandingly appear in the Theory of Systems. For example, the set of orbits of controllable systems by the action of the general linear group [18], the set of controlled and conditioned invariant subspaces [8–10,26,27,30] or sets of matrices related to the observer problem [30]. Let us start by recalling that the minimal realization problem is to find for a given infinite sequence of matrices (K 1 , K 2 , . . .), K i ∈ F p×m (F = R or C), a linear system of least possible order d x(t) ˙ = F x(t) + Gu(t) y(t) = H x(t)

x(t) ∈ Fd , u(t) ∈ Fm , y(t) ∈ F p for all t

(1)

such that K 1 , K 2 , etc. are the coefficients of the Laurent series at infinity of its transfer function matrix K (s) = H (s Id − F)−1 G, i.e., K (s) =

∞ 

K i s −i .

i=1

If only finitely many parameter matrices (K 1 , . . . , K k ) are given then the problem is known as a minimal partial realization problem. Since the Laurent expansion of H (s Id − F)−1 G at infinity is H (s Id − F)−1 G =

∞  i=1

123

H F i−1 Gs −i ,

On the geometry of the generalized partial realization problem

41

the partial realization problem amounts to finding matrices (F, G, H ) such that K i = H F i−1 G, i = 1, . . . , k. The generalized partial realization problem was introduced by Antoulas (see [1]). Now a finite sequence of matrices L = (L 1 , . . . , L k ), is given which is nice in the sense that L i is of size ri × m, i = 1, . . . , k, and r1 ≥ r2 ≥ · · · ≥ rk . If i j is the ith row of L j then system (1) is a generalized partial realization of L if i j = h i F j−1 G, 1 ≤ j ≤ k, 1 ≤ i ≤ r j . In other words, for a given nice sequence L = (L 1 , . . . , L k ) and a given positive integer d, the generalized partial realization problem calls for a triple (F, G, H ), F ∈ Fd×d , G ∈ Fd×m and H ∈ F p×d ( p ≥ s1 ) such that L j = H j F j−1 G, 1 ≤ j ≤ k where H j is the submatrix of H formed by its r j first rows. It is clear that the (classical) partial realization problem corresponds to the case when p = r1 = r2 · · · = rk . An algebraic necessary and sufficient condition for this problem to have a nonempty set of solutions was given by Antoulas [1]. The aim of the present paper is, for a given nice sequence L and a positive integer d, to endow the set of solutions {(F, G, H ) ∈ Fd×d × Fd×m × F p×d : L j = H j F j−1 G, 1 ≤ j ≤ k}, whenever it is not empty, with a stratified differentiable structure and to give the dimension of each one of its strata. Our approach is based on the connection between the generalized partial realization and the so-called cover problems (see [1]): For a given controllable pair (A, B) and a subspace S of Fn , find all (A, B)-controlled invariant subspaces V such that S ⊂ V. The algebraic connection between these two problems was first showed by Antoulas [1]. Fuhrmann and Helmke [11] also pointed it out when studying the observer problem. Various geometric aspects of the solutions of this problem (closely related to the cover problem) were studied by Trumpf (see [30]) following the work by Fuhrmann and Helmke [9,10] on the geometry of the so called tight subspaces, an important subset of the set of all conditioned invariant subspaces. Tight subspaces are the duals of the coasting subspaces, name that Willems [31] gave to the (A, B)-controlled invariant subspaces whose intersections with Im B reduce to the zero vector. By using a different approach, the geometry of the set of all conditioned invariant subspaces was studied in full generality in [8,27] and that of the cover problem in [28]. However, and despite the close algebraic relationship between the generalized partial realization and the cover problems, the approach in [28] has shown not to be convenient to deal with the geometry of the former. A more fruitful approach is that of [10,30]. But then, in order to solve the problem in full generality, we need a differentiable structure for the set of all controlled (or conditioned) invariant subspaces and not only for the tight-conditioned subspaces. Relevant results in this respect are

123

42

I. Baragaña et al.

Theorem 2.1 of [9] and Theorem 7.6 of [10] where an homeomorphism between an orbit space of controllable pairs by the general linear group action and the set of tightconditioned subspaces is exhibited. Pursuing a similar idea, we will show in Sect. 3 that the set of all controlled invariant subspaces can be identified with a quotient space of observable matrix pairs. Unfortunately, it seems that this quotient space is not an orbit space by the action of a Lie group. Nevertheless, it will be shown in Sect. 6 that it can be provided with a differentiable structure of stratified manifold, each stratum being the set of controlled invariant subspaces with the same Brunovsky indices for the quotient. With basis on the results in that section the two main goals of this paper are reached: the set of solutions of the generalized partial realization of a given nice sequence is provided with the desired stratified differentiable structure (Sect. 7), and the relationship between this structure and that of the cover problem obtained in [28] is clarified (Sect. 8). The paper is organized as follows: Sect. 2 is dedicated to introduce the concepts and previous results that are needed to follow the paper. In particular, restrictions and quotients of a pair (A, B) with respect to a given (A, B)-controlled invariant subspace will play a major role. Also, if V is such a subspace, the non-negative integer dim(Im B ∩V) is crucial in our development because, as said above, dim(Im B ∩V) = 0 characterizes the coasting subspace. Next, following Antoulas, Fuhrmann and Helmke, for a given controllable pair (A, B) ∈ Fn×n × Fn×m we characterize the (A, B)-controlled invariant subspaces of dimension d as subspaces spanned by the columns of some truncated observability matrices that we denote by (F, H ), F ∈ Fd×d , H ∈ Fm×d . It will be shown (Sect. 2.4) that with the help of these matrices the generalized partial realization problem can be stated as follows: Given a nice sequence of matrices L = (L 1 , . . . , L k ) and a positive integer d, find matrices F, G and H such that (F, H )G = L =  T T T L 1 L 2 · · · L TK . In other words, find F and H such that the subspace spanned by the columns of L is contained in the subspace spanned by the columns of (F, H ) which, whenever this matrix has full column rank, is an (A, B)-controlled invariant subspace. This is actually a cover problem and shows the importance of classifying the observable pairs (F, H ) according to the controlled invariant subspaces spanned by the columns of (F, H ). This is accomplished in Sect. 3 where two observable pairs (F, H ) and (F  , H  ) are said to be -equivalent if (F, H ) and (F  , H  ) are full column rank matrices and their columns span the same subspace. This equivalence relation reduces to similarity when the subspaces are coasting. This is consistent with the referred Theorem 2.1 of [9] and Theorem 7.6 of [10]. In Sect. 4, we are led by the fact that the solutions of the cover problem can be given the structure of stratified manifold according to the Brunovsky indices of the quotient [28]. Thus an investigation is made of how the Brunovsky indices of the quotient of (A, B) with respect to a given controlled invariant subspace spanned by the columns of (F, H ) are reflected in this matrix. The following step (Sect. 5) is to study the geometry of the observable pairs (F, H ) for which the columns of (F, H ) span a d-dimensional (A, B)-controlled invariant subspace with fixed Brunovsky indices for the quotient. We will denote such a set by R(r , s), r being the sequence of Brunovsky indices of (A, B) and s the sequence of

123

On the geometry of the generalized partial realization problem

43

prescribed Brunovsky indices for the quotient. The main goals of this section are to prove that this set is a submanifold of Fd×d × Fm×d and to compute its dimension. Then in Sect. 6 an atlas of coordinate charts for the quotient space R(r , s)/ is obtained. As already mentioned, this allows to prove in Sect. 7 that the set of generalized partial realizations of any finite nice sequence of matrices can be provided with a structure of stratified manifold according to the Brunovsky indices of the quotient of (A, B) with respect to the subspace spanned by the columns of (F, H ). It will be also shown that each stratum is an embedded submanifold of R(r , s) and its dimension will be computed. Actually, all this is done in two different ways. First, a direct approach is used that is similar to the one that gives R(r , s) the above mentioned structure of differentiable manifold. A second proof is proposed in Sect. 8 that exploits the geometry of the solutions of the cover problem obtained in [28]. In the last section the usual realization problem and, in particular, the case when L i is 1 × 1, which corresponds to the second problem in [5], are considered. The general result is applied to these particular cases and the dimensions of the corresponding manifolds are computed. To finish this introduction, some words must be said about minimality of the realizations. This is a major topic in the literature about realizations with many results and algorithms (see [1,5,21,23,29] for example and in particular [12] where the minimality of the generalized partial realizations is investigated). However our approach avoids this question. The reason is that the results in this contribution hold for any realizations of any fixed order and so, in particular, for the minimal realizations. We do not propose any algorithms for computing the order of minimal generalized realizations (relevant results in this direction can be found, for example, in [1,32] and for minimal generalized partial realizations in [12]). Nevertheless, in some cases (see Example 9.1), the minimal order can be deduced from the result in Proposition 7.2. In our approach, given a nice sequence of matrices L = (L 1 , . . . , L k ), the orders of the generalized partial realizations of L are the dimensions of the non-zero controlled ⎡ ⎤ L1 ⎢ ⎥ invariant subspaces that contain the subspace spanned by the columns of L = ⎣ ... ⎦. Lk In other words, they are the dimensions of the solutions of a cover problem. An algebraic necessary and sufficient condition for the existence of solutions of a given dimension of the cover problem was provided in [28]. 2 Preliminaries 2.1 Notation and basic concepts As already said, F is the field of real or complex numbers. Fn×m denotes the set of stands for the set of matrices of Fn×m having rank k n × m matrices over F, Fn×m k and Gl(n, F) is the general linear group of all invertible n × n matrices. If A ∈ Fn×m , the same symbol A will be used for the linear map associated in a natural way to the matrix. For A ∈ Fn×m , A∗ will denote the transpose of A if F = R or its transpose conjugate if F = C.

123

44

I. Baragaña et al.

For X ∈ Fn×m , [X ] will be the subspace generated by the columns of X . We denote by Grd (Fn ) the Grassmann manifold of d-dimensional subspaces of Fn . In this paper differentiable manifold means C ∞ -manifold and if M is a differentiable manifold, a submanifold of M is always an embedded submanifold of M. As usual, we will say that (A, B) ∈ Fn×n × Fn×m is controllable if rank C(A, B) = n, where   C(A, B) = B AB . . . An−1 B ∈ Fn×nm is the controllability matrix of (A, B). For simplicity we will assume that B has full column rank and so m ≤ n. ¯ B) ¯ ∈ Fn×n × Fn×m are said to be feedback Two pairs of matrices (A, B), ( A, equivalent if there exist matrices P ∈ Gl(n, F), Q ∈ Gl(m, F) and R ∈ Fm×n such that    P 0   . A¯ B¯ = P −1 A B R Q A complete system of invariants for the feedback equivalence of controllable pairs is given by the controllability indices (see [29, Sec. 4.2] for a definition). These form a partition of the order of the controllable system; i.e., if k1 ≥ · · · ≥ km ≥ 0 are the controllability indices of (A, B) ∈ Fn×n × Fn×m then k1 + · · · + km = n. Recall that given a sequence of non-negative integers a = (a1 , a2 . . .) whose components are almost all zero but not necessarily ordered, its conjugate sequence, that will be denoted by b = (b1 , b2 . . .), is defined as follows: bi = #{ j; a j ≥ i}, i ≥ 1. where # stands for cardinality. If (k1 , . . . , km ) is the sequence of controllability indices (k j = 0 for j > m) then the elements of its conjugate sequence (r1 , r2 , . . . , rn ) (notice that r j = 0 for j > k1 ) are called the Brunovsky indices of (A, B). They can be explicitly characterized in terms of ranks of matrices related to (A, B) [6]: i 

  r j = rank B AB . . . Ai−1 B , 1 ≤ j ≤ n.

(2)

j=1

By convenience, throughout this paper we will invert the order of the partition  = · · · = rn , then the non-negative (r1 , . . . , rn ). If r1 ≥ · · · ≥ rk > 0 = rk+1 integers  , 1 ≤ i ≤ k. ri = rk−i+1

will be called Brunovsky indices of (A, B). Thus, rk ≥ rk−1 ≥ · · · ≥ r1 . A pair of matrices (F, H ) ∈ Fd×d × Fm×d is observable if the pair (F ∗ , H ∗ ) ∈ d×d × Fd×m is controllable. The observability indices and the Brunovsky indices F

123

On the geometry of the generalized partial realization problem

45

of (F, H ) are, respectively, the controllability indices and the Brunovsky indices of (F ∗ , H ∗ ). ¯ H¯ ) ∈ Fd×d × Fm×d are said to be similar if there exists Two pairs (F, H ), ( F, ¯ H¯ ) = (P F P −1 , H P −1 ). P ∈ Gl(d, F) such that ( F, 2.2 Invariant subspaces, restrictions and quotients This sections is dedicated to introduce some very basic properties of the restrictions and quotients of a given matrix pair (A, B) with respect to an (A, B)-controlled invariant subspace. Although these concepts are scattered and sometimes implicit in the literature (see, for example [33, p. 92]), they were formalized in [2] in the context of P, Q-blocks [14,15] and in a bases free more general context in [8,26]. Restrictions of a pair (C, A) to a conditioned invariant subspace are also present in [9–11]. The results in this section can be proved using different techniques. In order to be as concise as possible we will adopt the approach in [26]. It consists in identifying   (A, B) with the singular pencil s In − A B . In doing so, two linear maps can be associated to (A, B) in a natural way: the natural projection π : Fn+m → Fn and f : Fn+m → Fn defined by f (x, y) = Ax + By, x ∈ Fn , y ∈ Fm . Then, related to V, two pairs of linear maps ( f¯, π¯ ) and ( f˜, π˜ ) can be defined rendering the following diagram commutative f¯, π¯

→ V π −1 (V) ∩ f −1 (V) ∩ ∩ → Fn f, π Fn+m ↓ ↓ f˜, π˜ Fn+m /π −1 (V) ∩ f −1 (V) → Fn /V

The vertical arrows are the natural projections, f¯, π¯ are the restrictions of f, π , respectively, and f˜, π˜ the corresponding maps induced on the quotients. Notice that, while π˜ is always surjective, π¯ need not be so. We recall that V is said to be (A, B)-controlled invariant if A(V) ⊂ V + Im B. For other equivalent conditions see [26].

−1 f (V) can If V is a controlled invariant subspace, a basis w of Ker π = Ker π be extended to bases (w, y) of Ker π and (u, w) of π −1 (V) f −1 (V) in such a way that (u, v, w, y) is a basis of Fn+m (see [26]). Then π(u) is a basis of V, (π(u), π(v)) is a basis of Fn and the matrix representation of f, π and f , π with respect to these bases are, respectively, ⎤ ..   ⎣ F A3 . G B3 ⎦ , In 0 .. 0 A2 . 0 B2 ⎡

(3)

and 

   F G , Id 0 .

123

46

I. Baragaña et al.

The size of F is d × d and if dim Ker π¯ = q then G ∈ Fd×q . It can be seen that dim(Im B ∩ V) = dim Ker π and so q ≤ d and G is a full column rank matrix. As said in Sect. 1, this number q will play an crucial role in this paper. With the corresponding bases in the quotient spaces, the matrix representations of  f, π are 

   A2 B2 , In−d 0 ,

where A2 ∈ F(n−d)×(n−d) and B2 ∈ F(n−d)×(m−q) . Similarly to the previous case, m − q ≤ n − d and B2 has full column rank. Pair (F, G) is said to be a pair restriction of (A, B) to V and (A2 , B2 ) a pair restriction of (A, B) to Fn /V or a quotient of (A, B) with respect to V. We collect all these observations in the following lemma. Lemma 2.1 With the above notation, matrices G and B2 have full column rank. Hence G and B2 are injective. Remark 2.2 As mentioned in Sect.1, the coasting subspaces are those for which Im B∩ V = {0}; i.e., q = 0. This means that an (A, B)-controlled invariant subspace is coasting if and only if its restriction is an autonomous system. Now, if X is the matrix whose columns are the vectors  of π(u), then  the matrix whose X 0 0 columns are the vectors of (u, w) has the form with a matrix whose S Q Q columns form a basis of Ker π. With these ideas in mind the following result can be proved: Proposition 2.3 Let V be a d-dimensional subspace of Fn and (A, B) ∈ Fn×n ×Fn×m and q = dim(Im B ∩ V). Then m×d , (i) V is controlled invariant if and only if there are matrices X ∈ Fn×d d ,S ∈F m×q d×d d×q Q ∈ Fq , F ∈ F and G ∈ F such that V = [X ] and the following equality holds    X 0   AB =X F G (4) S Q

(ii) (F, G) is a pair restriction of (A, B) to V if and only if there exist matrices m×d , Q ∈ Fm×q such that V = [X ] and condition (4) holds X ∈ Fn×d q d ,S ∈ F true. Furthermore, once X , S and Q have been fixed, (F, G) is uniquely determined by (4). Remark 2.4 (i) A similar result can be given in terms of quotients. For example, (n−d)×n V is (A, B)-controlled invariant if and only if there are matrices Y ∈ Fn−d , (m−q)×m

R ∈ F(m−q)×n , P ∈ Fm−q , A2 ∈ F(n−d)×(n−d) and B2 ∈ F(n−d)×(m−q) such that V = Ker Y and the following equality holds      Y 0 Y A B = A2 B2 . (5) R P

123

On the geometry of the generalized partial realization problem

47

(ii) According to (3) there are matrices T ∈ Gl(n, F), Z ∈ Gl(m, F) and U ∈ Fm×n such that ⎡

⎤ ..     T 0 F A . G B Id 3 3⎦ −1 −1 ⎣ A B and T X = = T .. 0 U Z 0 A2 . 0 B2

(6)

Recall that first of these two identities means that (A, B) and  F A3 G B3 , are feedback equivalent. 0 A2 0 B2 We will need the following result that follows from Proposition 2.3. Proposition 2.5 Let V be an (A, B)-controlled invariant subspace and (F, G) a pair restriction of (A, B) to V. Then (F  , G  ) is a pair restriction of (A, B) to V if and only if (F, G) and (F  , G  ) are feedback equivalent. Remark 2.6

(i) With the above notation, if X  = X P, then 

    P 0 F  G  = P −1 F G , W T

for some matrices T , invertible, and W . (ii) In a similar way one can prove that any two quotient pairs of (A, B) with respect to V are feedback equivalent. 2.3 Pairs defining invariant subspaces As a first step in the study of the geometry of the generalized partial realization problem, we will have to gain some insight into the knowledge of the geometry of the set of controlled invariant subspaces. The following straightforwardly proved result says that the substitution of the given pair (A, B) by anyone in its feedback equivalence orbit is allowed. Proposition 2.7 If (A, B) and (A , B  ) are feedback equivalent with 

A

B



=P

−1



  P 0 AB R Q

then V is (A, B)-controlled invariant if and only if P −1 (V) is (A , B  )-controlled invariant. In particular, we can work with a canonical form for this equivalence relation. We will see in Sect. 2.4 that we can assume that (A, B) is controllable and in the so-called Brunovsky dual form. If r0 = 0 < r1 ≤ r2 ≤ r2 ≤ · · · ≤ rk = m are the Brunovsky

123

48

I. Baragaña et al.

indices of (A, B), this pair is feedback equivalent to a pair of the form ⎛⎡ 0 ⎜⎢ ⎜⎢ 0 ⎜⎢ ⎜⎢· · · ⎜⎣ ⎝ 0 0

E r1 0 ··· 0 0

0 E r2 ··· 0 0

⎤ ⎡ 0 ··· 0 ⎢ 0 ··· 0 ⎥ ⎥ ⎢ ⎢ .. ··· ··· ⎥ ⎥,⎢ ⎢ . · · · Erk−1 ⎦ ⎣ 0 ··· 0 Er

⎤⎞ ⎥⎟ ⎥⎟ ⎥⎟ ⎥⎟ ⎥⎟ ⎦⎠ k

  where Eri = Iri 0 ∈ Fri ×ri+1 , i = 1, . . . , k − 1, Erk = Irk . A pair with this shape will be said to be a pair in Brunovsky dual form. Notice that r1 + · · · + rk = n, the size of the state matrix A. Following the ideas in [1] (see also [11,30] for the dual case of conditioned invariant subspaces) we aim to characterize the controlled invariant subspaces in terms of observable pairs. The following notation will be used: For a sequence of non-negative F ∈ Fd×d⎤, Hi ∈ F(ri −ri−1 )×d , integers r0 = 0 < r1 ≤⎡r2 ≤ ⎤ · · · ≤ rk = m, if ⎡ H1 H1 F i−1 ⎢ H2 ⎥ ⎢ H2 F i−2 ⎥ ⎢ ⎥ ⎢ ⎥ i = 1, . . . , k and H = ⎢ . ⎥, then i (F, H ) = ⎢ ⎥, i = 1, . . . , k, and .. ⎣ .. ⎦ ⎣ ⎦ . H Hi ⎤ k 1 (F, H ) ⎢2 (F, H )⎥ ⎢ ⎥ (F, H ) = ⎢ ⎥. Observe that the size of H is m × d, the size of i (F, H ) .. ⎣ ⎦ . ⎡

k (F, H ) is ri × d and the size of (F, H ) is (r1 +· · · +rk ) × d. We will remove the reference to the pair (F, H ) when there is no risk of confusion and we will write , i ,…instead of (F, H ), i (F, H ),… From now on and unless otherwise said (A, B) will be assumed to be controllable and in Brunovsky dual canonical form. If rank  = d then the map Im B ∩ [] → [∗1 , . . . , ∗k−1 ]⊥ ⊂ Fd defined by α −→ α is an isomorphism. Hence dim[∗1 , . . . , ∗k−1 ] = d − q

(7)

rank k ≥ q

(8)

so that

The following result plays a fundamental role in what follows (compare with Theorem 2.15 in [1], Theorem 4.1 in [11], Theorem 7.4 in [10] or Proposition 5.2 in [30]).

123

On the geometry of the generalized partial realization problem

49

Proposition 2.8 Let (A, B) be in Brunovsky dual form and r0 = 0 < r1 ≤ · · · ≤ rk its Brunovsky indices. Then a d-dimensional subspace V of Fn is controlled invariant if and only if there exist matrices F and H such that V = [(F, H )]. Proof According to Proposition 2.3 V is controlled invariant if and only if there are m×d , Q ∈ Fm×q , F ∈ Fd×d and G ∈ Fd×q such that matrices X ∈ Fn×d q d , S ∈ F V = [X ] and Eq. (4) holds. Solve this matrix equation for (A, B) in Brunovsky dual form. It is easily seen that if Hi denotes the submatrix of X formed by the rows r1 + · · · + ri−1 + ri−1 + 1, . . . , r1 + · · · + ri−1 + ri then X = (F, H ). Conversely, if V = [(F, H )], put X = (F, H ) and S = k+1 (F, H ) = m×q d×q k (F, H )F and choose matrices Q ∈ Fq and G ∈ Fq such that Q = k (F, H )G (such matrices always exist). It is clear that (i) of Proposition 2.3 is satisfied with (A, B) in Brunovsky dual form and the result follows.   Remark 2.9 (i) If h i denotes the ith row of H , i = 1 . . . , m, and k1 ≥ · · · ≥ km > 0 are the controllability indices of (A, B) then, bearing in mind that ki is the number of Brunovsky indices, r j bigger than or equal to i, it can be seen that the rows of k (F, H ) are h 1 F k1 −1 , . . . h m F km −1 . (ii) If X = (F, H )P, with P ∈ Gl(d, F) then [X ] = [(F, H )], so that there exists (F  , H  ) such that X = (F  , H  ). In fact, we can take, for example, F  = P −1 F P, H  = H P. (iii) The pairs (F, H ) for which the columns of (F, H ) generate a controlled invariant subspace must be observable. In fact if the size of F is d and no controllability index of (A, B) is bigger than d then, by remark (i) above, (F, H ) is a matrix formed by some rows of the observability matrix of (F, H ). Since (F, H ) has full column rank, (F, H ) must be observable. And if some controllability indices of (A, B) are bigger than d, Hamilton–Cayley Theorem yields the same conclusion. (iv) From (7) a new characterization of the coasting subspaces arises: these are those (A, B)-controlled invariant subspaces ((A, B) in Brunovsky dual form) generated by the columns of matrices of the form ⎤ that the rows of ⎡ (F, H ) such 1 (F, H ) ⎥ ⎢ .. k (F, H ) linearly depend on the rows of ⎣ ⎦. This is essentially . k−1 (F, H ) the definition of coasting subspace given, by duality, in [10,11].

Proposition 2.8 shows a close relationship between pairs (F, H ) defining (A, B)controlled invariant subspaces and restrictions of (A, B) to those subspaces. We analyze now a little closer this relationship. Let V be a d-dimensional (A, B)-controlled invariant subspace. We know that V = [(F, H )] for some F ∈ Fd×d and H ∈ Fm×d . Proposition 2.8 shows that F is the state matrix of a restriction of (A, B) to V. How can a matrix G be found such that (F, G) is a pair restriction of (A, B) to V? It turns out that if G is a matrix whose columns form a basis of [∗1 , . . . , ∗k−1 ]⊥ , X = (F, H ), S = k (F, H )F and Q = k (F, H )G then    (F, H )   0 AB = (F, H ) F G (9) k (F, H )F k (F, H )G

123

50

I. Baragaña et al.

⎡

⎤ 0 ⎢ .. ⎥ ⎢ ⎥ Furthermore, since G = ⎢ . ⎥, we conclude that rank Q = q. Then, by applying ⎣ 0 ⎦ k G (ii) of Proposition 2.3 the following result follows Proposition 2.10 Let V be a d-dimensional (A, B)-controlled invariant subspace and (F, H ) an observable pair such that V = [(F, H )]. Then relations (7) and (8) hold. d×q And if G ∈ Fk is a solution of the matrix equations i G = 0 for 1 ≤ i ≤ k − 1, then (F, G) is a restriction of (A, B) to V satisfying (9). The restrictions for which i G = 0, 1 ≤ i ≤ k − 1, will play a special role and we will give them a particular name Definition 2.11 (F, G) will be said to be a restriction of (A, B) to V with respect to the pair (F, H ) if i (F, H )G = 0 for i = 1, . . . , k − 1. In the sequel the pair (A, B) will be understood to be fixed and the reference to it will be often removed. Thus, for example, we will talk about “restrictions to V with respect to (F, H )” understanding that it is a restriction of (A, B) to V. 2.4 Controlled invariant subspaces and the generalized partial realization problem We show now how controlled invariant subspaces are related to the partial realization problem. Recall from the introduction that the generalized partial realization problem is stated as follows (the order of the indices is reversed to accommodate the notation to the previous section): Given a sequence of matrices L = (L 1 , L 2 , . . . , L k ) with L j ∈ Frk− j+1 ×δ and m = rk ≥ rk−1 ≥ · · · ≥ r1 and a positive integer d, find matrices (F, M, H ) ∈ Fd×d × Fd×δ × Fm×d such that L j = H j F j−1 M, 1 ≤ j ≤ k where H j is the submatrix of H formed by its rk− j+1 first rows. For j = 1, . . . , k put ⎡ ⎢ ⎢ Lj = ⎢ ⎣

⎤

L j1 L j2 .. .

⎥ ⎥ ⎥, ⎦

L ji ∈ F(ri −ri−1 )×δ , (r0 := 0),

L j,k− j+1 ⎡

L j1

⎤

⎢ L j−1,2 ⎥ ⎢ ⎥ Lˆ j = ⎢ . ⎥ ∈ Fr j ×δ , ⎣ .. ⎦ L1 j

123

⎡ˆ ⎤ L1 ⎢ Lˆ 2 ⎥ ⎢ ⎥ Lˆ = ⎢ . ⎥ ⎣ .. ⎦ Lˆ k

On the geometry of the generalized partial realization problem

51

and ⎡

⎤ H11 ⎢ H12 ⎥ ⎢ ⎥ H = H1 = ⎢ . ⎥ . ⎣ . ⎦ H1k It is easily seen that L j = H j F j−1 M for j = 1, . . . , k is equivalent to Lˆ 1 = H11 M,

ˆL 2 = H11 F M, H12 

⎡

⎤ H11 F 2 Lˆ 3 = ⎣ H12 F ⎦ M, . . . H13

That is to say, if and only if Lˆ = (F, H )M. Now, let (A, B) be the controllable pair in Brunovsky dual form with r0 = 0 < r1 ≤ r2 ≤ · · · ≤ rk as Brunovsky indices. Since the (A, B)-controlled invariant subspaces are spanned by the columns of matrices of the form (F, H ), we conclude that there exist matrices (F, M, H ) such that Lˆ = (F, H )M if and only if the subspace spanned by the columns of Lˆ is contained in the (A, B)-controlled invariant subspace generated by the columns of (F, H ). Two consequences can be extracted from the above remark: We can always assume that (A, B) is a controllable pair in Brunovsky dual canonical form with r0 = 0 < r1 ≤ r2 ≤ · · · ≤ rk as Brunovsky indices. And second, it shows how closely related are the cover and the generalized partial realization problem. It was proved in [28] that the solutions of the former can be endowed with a structure of stratified manifold, each stratum being the set of (A, B)-controlled invariant subspaces with the same Brunovsky indices of the quotient. Hence, we can expect to be able to provide with a similar structure the solutions of the latter. This is the idea that leads us in the upcoming developments. First of all we aim to classify the observable pair (F, H ) according to the (A, B)controlled invariant subspaces spanned by the columns of (F, H ). This is accomplished in the next section. 3 The space d,m / By dualizing the results in [10, Th. 7.6] in order to be applied to controlled invariant subspaces, we find that the set of coasting subspaces is homeomorphic to an orbit ⎡ space of observable pairs under similarity: the observable pairs (F, H ) such that ⎤ 1 (F, H ) ⎥ ⎢ .. rank ⎣ ⎦ = d or, by (iv) of Remark 2.9, q = dim(Im B∩[(F, H )]) = 0. .

k−1 (F, H ) It is also shown in the same paper that if

d,m = {(F, H ) ∈ Fd×d × Fm×d ; rank (F, H ) = d}

123

52

I. Baragaña et al.

and Invd (A, B) = {V ∈ Grd (Fn ); V is controlled invariant} then the map ρ :

d,m −→ Invd (A, B) Gl(d, F)

given by ρ([F, H ]) = [(F, H )] ([F, H ] the similarity orbit of (F, H )) is a surjective algebraic map but it is not a bijection, in general. In this section we aim to identify Invd (A, B) with a quotient space of observable pairs in fully generality; i.e., when q ≥ 0. In addition, we will show that any two equivalent pairs can be obtained from one each other by elementary operations and a representative can be chosen in each class that presents an observability-like reduced form. First we define an equivalence relation -to be called -equivalence- in the open set d,m in a natural but, at first sight, unhelpful way: 

(F, H ) ∼ (F  , H  ) if and only if [(F, H )] = [(F  , H  )].  If (F, H ) ∈ d,m then (F, H ) will denote the equivalence class of (F, H ) and d,m / the quotient set of d,m by the -equivalence relation. This definition and Proposition 2.8 yields Proposition 3.1 With the above notation, the map ϕ : Invd (A, B) −→ d,m /  defined by ϕ(V) = (F, H ), where V = [(F, H )], is bijective. It turns out that there is a nice characterization of the -equivalence in terms of the special restrictions of Definition 2.11. Proposition 3.2 Let V = [(F, H )] be a controlled invariant subspace and (F, G) a restriction of (A, B) to V with respect to (F, H ) ∈ d,m . If (F  , G  ) is feedback equivalent to (F, G) with 

    P 0 F  G  = P −1 F G , R Q

P ∈ Gl(d, F), R ∈ Fq×d , Q ∈ Gl(q, F) and H  = H P, then the following properties hold: (i) (F, H ) and (F  , H  ) are -equivalent. (ii) (F  , G  ) is a restriction of (A, B) to V with respect to (F  , H  ).

123

On the geometry of the generalized partial realization problem

Proof

53

(i) It suffices to prove that (F  , H  ) = (F, H )P, and this is equivalent to show that H j (F  )i− j = H j F i− j P, 1 ≤ j ≤ i, 1 ≤ i ≤ k. Let i ∈ {1, . . . k}. If j = i, this is true by hypothesis. Let now i > j. Then, again by hypothesis, F  = P −1 F P + P −1 G R, G  = P −1 G Q, and H j (F  )i− j = H j P(P −1 (F + G R P −1 )P)i− j = H j (F + GT )i− j P, where T = R P −1 . Thus H j (F  )i− j = H j (F i− j + p(F, G, T ))P where p(F, G, T ) is a sum of products of the form F  GT S with  < i − j and S is a product of powers of F and GT . Then from Definition 2.11 we conclude that H j F  G = 0. Hence H j (F  )i− j = H j F i− j P

as desired. (ii) It follows at once because i (F  , H  )G  = i (F, H )G Q = 0, 1 ≤ i ≤ k − 1.   The following characterization of the -equivalence follows from Propositions 2.5 and 3.2. Proposition 3.3 Let (F, H ), (F  , H  ) ∈ d,m and (F, G), (F  , G  ) restrictions to V = [(F, H )] and V  = [(F  , H  )] with respect to (F, H ) and (F  , H  ), respectively. Then (F, H ) and (F  , H  ) are -equivalent if and only if 

    P 0 F  G  = P −1 F G R Q

and H  = H P, for some matrices P ∈ Gl(d, F), R ∈ Fq×d , Q ∈ Gl(q, F).

123

54

I. Baragaña et al.

By recalling that the coasting subspaces are those for which the restriction is an autonomous system, we easily conclude that, for this type of subspaces, -equivalence reduces to similarity as claimed in the introduction. Our aim now is to obtain special representatives in each -equivalence class. Let (F, H ) ∈ d,m and let h i be the ith row of H . It is always possible to choose d independent rows of (F, H ) of the form h 1 , h 1 F, . . . , h 1 F 1 −1 , . . . , that there h m , h m F, . . . , h m F m −1 where i ≥ 0 and i = 0 means ⎡ ⎤ are no rows 1 ⎥ ⎢ of the form h i , h i F, . . .. Since rank k (F, H ) ≥ q and rank ⎣ ... ⎦ = d − q (see k−1

⎤ 1 ⎥ ⎢ (7)), we can always select q independent rows in k (F, H ) and d − q in ⎣ ... ⎦. k−1 Thus the following definition makes sense. ⎡

Definition 3.4 We say that (h 1 , h 1 F, . . . , h 1 F 1 −1 , . . . , h m , h m F, . . . , h m F m −1 ) is a nice basis of the vector space generated by the rows of (F, H ) if d − q of its vectors are rows of ⎤ ⎡ 1 (F, H ) ⎥ ⎢ .. ⎦ ⎣ . k−1 (F, H )

and the remaining q are rows of k (F, H ). The indices 1 , . . . , m are called the indices of the nice basis. Theorem 3.5 Let (F, H ) ∈ d,m and (h 1 , h 1 F . . . , h 1 F 1 −1 , . . . , h m , h m F, . . . , h m F m −1 ) a nice basis of the vector space generated by the rows of (F, H ). Let h i F i =

j −1 m  

ai js h j F s

j=1 s=0

where by agreement

−1

s=0

:= 0. Then

 H ) ∈ d,m with the following form: 1. (F, H ) is similar to a pair ( F,  = (H i j )1≤i, j≤m  = (F i j )1≤i, j≤m , H F where

⎡

0 ⎢ .. ii = ⎢ (i) F ⎢ . ⎣ 0 aii0

123

⎤ ⎡ 0 1 ··· 0 ⎢ .. .. . . .. ⎥ . . . ⎥ i j = ⎢ ⎥ ∈ Fi ×i , F ⎢ . ⎣ 0 0 ··· 1 ⎦ ai j0 aii1 · · · aiii −1  × i j F ,

⎤ ··· 0 .. ⎥ .. . . ⎥ ⎥ ∈ ··· 0 ⎦ · · · ai j j −1

On the geometry of the generalized partial realization problem

55

  ii = 10 · · · 0 ∈ F1×i , H i j = 0 ∈ F1× j if i > 0, (ii) H   i j = ai j0 · · · ai j j −1 ∈ F1× j if i = 0. H 2. (F, H ) is -equivalent to a pair (Fr , Hr ) ∈ d,m with the following form: Fr = (Fi j )1≤i, j≤m , Hr = (Hi j )1≤i, j≤m 

0 Ii −1 ∈ Fi ×i , Fi, j = 0 ∈ Fi × j if i = ki , 0 0 ii , Fi j = F i j if i < ki , (ii) Fii = F i j , 1 ≤ i, j ≤ m. (iii) Hi j = H

where

(i) Fii =

 G)  is an observability Proof 1. This is a very well-known result. Actually, ( F, reduced form of (F, H ). 2. Let P be a matrix whose rows are h 1 , h 1 F, . . . , h 1 F 1 −1 , . . . , h m , h m F, . . . ,   H ) = (F, H )P −1 , and so (F, H ) ∼  H ). h m F m −1 . Then ( F, ( F, Let (F, G) be a restriction of (A, B) to [(F, H )] with respect to (F, H ) and  G)  the restriction corresponding to the change of bases defined by ( F, 

    P −1 0   F G =P F G 0 Ip

 = P F P −1 , G  = P G. Denote That is to say, F ⎤ ⎡ ⎤ hi P1 ⎢ hi F ⎥ ⎥ ⎢ ⎥ ⎢ P = ⎣ ... ⎦ with Pi = ⎢ ⎥ , 1 ≤ i ≤ m. .. ⎦ ⎣ . Pm h i F i −1 ⎡

Since i (F, H )G = 0 for 1 ≤ i ≤ k − 1 and recalling (see Remark 2.9 (i)) that the rows of k (F, H ) are of the form h i F ki −1 , we conclude that if i < ki , then Pi G = 0 and if i = ki , then ⎡ ⎢ ⎢ Pi G = ⎢ ⎣

0 .. . 0 h i F ki −1 G

⎤ ⎥ ⎥ ⎥. ⎦

Hence ⎡ ⎤  G1 ⎢ ⎢ .. ⎥  i = 0 if i < ki and G i = ⎢ G = ⎣ . ⎦ with G ⎢ ⎣ m G ⎡

0 .. . 0 h i F ki −1 G

⎤ ⎥ ⎥ ⎥ if i = ki . ⎦

123

56

I. Baragaña et al.

 = rank G = q. Hence, the rows h i F ki −1 G such that h i F ki −1 belong But rank G to the nice basis, are linearly independent. Let Q 1 be the inverse of the matrix formed by the rows h i F ki −1 G. Then ⎤ G1 . ⎥ Q1 = ⎢ G ⎣ .. ⎦ with G i = 0 ⎡

⎡

Gm

0 ⎢ G i = ⎣ ...

··· .. .

0 .. .

··· .. .

⎤ 0 .. ⎥ .⎦

if i < ki and

if i = ki .

0 ··· 1 ··· 0

+ G Q1 R Then, it is clear that there exists a matrix R ∈ Fq×d such that if Fr = F  and Hr = H , the pair (Fr , Hr ) has the form claimed in the theorem. Moreover     Id 0     . Fr G Q 1 = F G Q1 R Q1    H ) and so (Fr , Hr ) ∼ By Proposition 3.2, (Fr , Hr ) ∼ ( F, (F, H ).

 

Definition 3.6 If (Fr , Hr ) has the form of item 2 of above Theorem 3.5, it will be said to be in reduced form. If (Fr , Hr ) is a pair in reduced form and it is -equivalent to (F, H ) then it will be called the reduced form of (F, H ) with respect to . Notice that once the indices  are fixed, the reduced form is uniquely determined.  H ) will be called The scalars ai js appearing in a reduced form (Fr , Hr ) or in ( F,   parameters of (Fr , Hr ) or of ( F, H ), respectively.  in the Remark 3.7 It is worth-noticing that taking into account the form of matrix G proof of Theorem 3.5, the non-compulsory zero parameters in the reduced form are  H ) except the parameters corresponding to i = ki . those of the pair ( F, 4 The Brunovsky indices of the quotient and a new reduced form In order to approach a method for providing the set of solutions of the generalized partial realization problem with a similar differentiable structure as that of the solutions of the cover problem, we must know how the Brunovsky indices of the quotient are reflected in (F, H ). This section is devoted to answer this question and provide a reduced form for each class of -equivalent pair with the same Brunovsky indices for the quotient. Let V be a fixed (A, B)-controlled invariant subspace with dim V = d and q = dim(Im B ∩ V). Recall (Remark 2.6 (ii)) that all pairs restrictions of (A, B) to Fn /V are feedback equivalent and so, they have the same controllability and Brunovsky indices.

123

On the geometry of the generalized partial realization problem

57

Let the Brunovsky indices of the fixed controllable pair in Brunovsky dual form (A, B) be r = (r1 , . . . , rk ), 0 = r0 < r1 ≤ · · · ≤ rk and denote the Brunovsky indices of any quotient of (A, B) with respect to V by s = (s1 , . . . , sk ), 0 = s0 = s1 = · · · = sk−l < sk−l+1 ≤ · · · ≤ sk . Recall that B is assumed to have full column rank and so rk = m and by Lemma 2.1, if (A2 , B2 ) is any quotient of (A, B) with respect to V then rank B2 = m − q. But, by the definition of the Brunovsky indices (see (2)), rank B2 = sk . Hence sk = m − q

(10)

In this paper we will use indistinctly the notation r for the partition r = (r1 , . . . , rk ) and for the set r = {r1 , . . . , rk } when this has a meaning; i.e., all elements are distinct. It is known (see [2,7,11]) that ri ≥ si , 1 ≤ i ≤ k. The main goals in this section are to give a new characterization of (s1 , . . . , sk ) in terms of a basis of V and to produce new reduced forms for the -equivalence of pairs (F, H ) when the quotient of (A, B) with respect to [(F, H )] has s1 , . . . , sk as Brunovsky indices. Proposition 4.1 Let V be a controlled invariant subspace with s1 ≤ · · · ≤ sk as Brunovsky indices of the restriction of (A, B) to Fn /V and let (F, H ) ∈ d,m be a pair such that V = [(F, H )]. If qi = ri − si , 1 ≤ i ≤ k, then ⎤ 1 (F, H ) ⎥ ⎢ .. q1 + · · · + qi = rank ⎣ ⎦ , 1 ≤ i ≤ k. . ⎡

(11)

i (F, H )

To prove this proposition we need the following lemma Lemma 4.2 Let V be a controlled invariant subspace with s1 ≤ · · · ≤ sk as n×d such that Brunovsky indices of the restriction of (A, B) to Fn /V and  let  X ∈  F rank X = d and [X ] = V. Then the Brunovsky indices of A, B X are 0 ≤ s1 ≤ · · · ≤ sk−1 ≤ sk + d and the following relation holds d+

k 

  s j = rank B X AB · · · Ak−i−1 B , 0 ≤ i ≤ k − 1.

j=i+1

Proof Let T ∈ Gl(n, F), Z ∈ Gl(m, F) and U ∈ Fm×n matrices such that (see Remark 2.4)

123

58

I. Baragaña et al.

T Denote

 −1

⎤ ⎡ ..    T 0 . G B F A I 3 3⎦ −1 ⎣ AB and T X = d = .. 0 U Z 0 A2 . 0 B2 

  G B3 Id F A3 = X . = A , = B, 0 A2 0 B2 0

Then

⎡

⎤ T 0 0   A B X ⎣ U Z 0 ⎦ = A B  X  . T 0 0 Id     So (A, B X ) and (A , B  X  ) are feedback equivalent and they have the same Brunovsky indices. But     rank B X · · · A j B A j X = rank B  X  · · · A j B  A j X    = d + rank B2 A2 B2 · · · A2j B2  −1



=d+

k 

si , 1 ≤ j ≤ k

i=k− j

and, since A(V) ⊂ V + Im B, we have that     rank B X AB AX · · · A j B A j X = rank B X AB A2 B · · · A j B .  

Now the lemma follows easily. Proof of Proposition 4.1 From the previous lemma we have d+

k  j=i+1

  s j = rank B (F, H ) AB · · · Ak−i−1 B ⎤ 0 · · · 0 0 1 .. . . . . . ⎥ . .. .. .. ⎥ . ⎥ · · · · · · · · · Iri+1 0 i+1 ⎥ ⎥ .. .. . . . . . ⎥ . .. .. .. ⎥ . . ⎥ Irk−1 0 · · · 0 0 k−1 ⎦ 0 0 · · · 0 0 k ⎡ ⎤ 1 ⎢ .. ⎥ = rk + · · · + ri+1 + rank ⎣ . ⎦ ⎡

0 ⎢ .. ⎢ . ⎢ ⎢· · · = rank ⎢ ⎢ .. ⎢ . ⎢ ⎣0 Irk

0 .. .

i

and the claimed relation follows.

123

 

On the geometry of the generalized partial realization problem

59

Remark 4.3 It is clear that (11) is equivalent to ⎡ ⎤ ⎤ 1 (F, H ) 1 (F, H ) ⎢ ⎥ ⎥ ⎢ .. .. qi = rank ⎣ ⎦ − rank ⎣ ⎦. . . i (F, H ) i−1 (F, H ) ⎡

This implies that qi ≤ rank i (F, H ). In particular, bearing in mind (10), q = m − sk = rk − sk = qk ≤ rank k (F, H ). Since we will deal with controlled invariant subspaces having s as Brunovsky indices of any of its quotients, a refinement in the definition of a nice basis given in Definition 3.4 is needed. Let (F, H ) ∈ d,m , h 1 , . . . , h m the rows of H and h 1 , h 1 F, . . . , h 1 F 1 −1 , . . . , h m , h m F, . . . , h m F m −1

(12)

d linearly independent rows of (F, H ) (recall that i = 0 means that there are not vectors of the form h i , h i F, . . .). Then, since rank i (F, H ) ≥ qi and qk = q, the following definition makes sense. Definition 4.4 We say that (12) is a (r , s)- nice basis for [(F, H )] or simply for (F, H ) if in this basis there are qi vectors belonging to the block i (F, H ), 1 ≤ i ≤ k. Then we say that  = (1 , . . . , m ) are the indices of the (r , s)-nice basis. If there is no risk of confusion we also refer to  as a set of indices with regard to (F, H ). Let us describe a method of obtaining (r , s)-nice basis. We will use the following notation: if i = (i 1 , . . . , ir ) is a sequence of positive integers such that 1 ≤ i 1 < · · · < ir ≤ p, then A(i) will denote the r × d submatrix of A ∈ F p×d formed by the rows in i. Choose q1 linearly independent rows of 1 = H1 and let them be m 1 = (m 11 , m 12 , . . . , m 1q1 ), 1 ≤ m 11 < m 12 < · · · < m 1q1 ≤ r1 . Thus q1 = rank 1 (F, H ) = rank (m 1 ), ⎡ ⎤ 1 (m 1 ) 1 = rank ⎣1 (m 1 )F ⎦ . q1 + q2 = rank 2 H2 

H1 F , say m 2 = H2 (m 21 , m 22 , . . . , m 2q2 ), 1 ≤ m 21 < m 22 < · · · < m 2q2 ≤ r2 , by selecting q12 rows in 1 (m 1 )F and q22 rows in H2 such that q12 + q22 = q2 and 

Next we choose q2 linearly independent rows in 2 =

 q1 + q2 = rank

 1 1 (m 1 ) = rank . 2 2 (m 2 )

123

60

I. Baragaña et al.

Notice that q1 ≥ q12 and m 2 ∩ {1, . . . , r1 } ⊂ m 1 . Continuing this way we will obtain an (r , s)-nice basis for (F, H ). In general, ⎤ ⎡ ⎤ 1 (m 1 ) 1 ⎢ ⎥ ⎢ ⎥ q1 + · · · + qi = rank ⎣ ... ⎦ = rank ⎣ ... ⎦ , ⎡

i

i (m i )

m i+1 ∩ {1, . . . , ri } ⊂ m i , 1 ≤ i ≤ k − 1, q1i + · · · + qii = qi , 1 ≤ i ≤ k (q11 := q1 ) and qii ≥ qii+1 ≥ · · · ≥ qik , 1 ≤ i ≤ k. When we take an (r , s)-nice basis instead of a nice basis (Definition 3.4) some coefficients ai js in the reduced forms obtained in Theorem 3.5 must be compulsory zero. In order to compute the number of parameters in this case, it is convenient to introduce a notation for the rows of (F, H ): • m i = (m i1 , m i2 , . . . , m iqi ) are the rows of i (F, H ) which are in the (r , s)-nice basis (simply, nice basis, in the sequel), 1 ≤ i ≤ k, and m = (m 1 , . . . , m k ) ⎤ 1 ⎢ ⎥ pi are the rows of ⎣ ... ⎦ in the nice basis; i.e., pi = m 1 ∪ (r1 + m 2 ) ∪ · · · ∪ ⎡

•

i i integer (r1 + · · · + ri−1 + m i ), 1 ≤ i ≤ k, where, for a positive ⎡ ⎤ x, x + m = 1 ⎢ ⎥ (x + m i1 , . . . , x + m iqi ). Thus # p = q1 + . . . + qi = rank ⎣ ... ⎦. Put i

i

p = ( p 1 , . . . , p k ). • t i := {1, . . . , ri } \ m i are the rows of i (F, H ) which are not in the nice basis, 1 ≤ i ≤ k. One has t i−1 ⊂ t i

and

#t i = ri − qi = si , 1 ≤ i ≤ k (t 0 := ∅).

Put t = (t 1 , . . . , t k ).

123

On the geometry of the generalized partial realization problem

61

• n i := t i \ t i−1 = (n i1 , . . . , n i,si −si−1 ), are the rows of the form h j F  j appearing in i (F, H ), 1 ≤ i ≤ k. We also define n k+1 = {1, . . . , m} \ t k . Notice that, actually, n k+1 = m k . Set n = (n 1 , . . . , n k+1 ). With this notation i (n i j ) = h n i j F

n i j

, 1 ≤ i ≤ k + 1; 1 ≤ j ≤ si − si−1 (sk+1 := rk ),

where k+1 = k F.  H ) appear the components of the rows of i (n i ), 1 ≤ i ≤ k + 1, as linear In ( F, ⎡ ⎤ 1 ⎢ .. ⎥ combinations of the rows of the nice basis. These are exactly the rows of ⎣ . ⎦ which i

are in ( pi ): ⎤ 1 (m 1 ) ⎥ ⎢ ( pi ) = ⎣ ... ⎦ . ⎡

i (m i )

Thus there are matrices i j ∈ F(si −si−1 )×q j such that   i (n i ) = Ai1 Ai2 · · · Aii ( pi ), 1 ≤ i ≤ k. In addition   k+1 (n k+1 ) = Ak+1,1 Ak+1,2 · · · Ak+1,k ( p k ) with Ak+1, j ∈ F(rk −sk )×q j .  H ) Once the index set  and the matrices Ai j are known, the reduced form ( F, defined in the first item of Theorem 3.5 is completely determined. That is to say  H ) is characterized by  and the matrix Proposition 4.5 ( F, ⎡

A11 A21 .. .

⎢ ⎢ ⎢ ⎢ ⎢ ⎣ Ak1 Ak+1,1

⎤ 0 ··· 0 A22 · · · 0 ⎥ ⎥ .. .. ⎥ ∈ Fm×d . .. . . . ⎥ ⎥ Ak2 · · · Akk ⎦ Ak+1,2 · · · Ak+1,k

123

62

I. Baragaña et al.

 H ) is Corollary 4.6 The number of parameters in ( F, dm −

k−1 

(si − si−1 )(qi+1 + · · · + qk ) =

i=1

k 

(si − si−1 )(q1 +· · ·+qi )+(rk − sk )d.

i=1

Example 4.7 Suppose r = (3, 5, 6), s = (1, 3, 4). Then q = (2, 2, 2) and ⎤ H1 ⎡ ⎤ ⎢ H1 F ⎥ ⎥ ⎢ 1 ⎢ H2 ⎥ ⎥ ⎢ ⎦ ⎣  = 2 = ⎢ H1 F 2 ⎥ ⎥ ⎢ 3 ⎣ H2 F ⎦ H3 ⎡

⎡

⎤ h1 ⎢ h2 ⎥ ⎢ ⎥ ⎢ h3 ⎥ ⎢ ⎥ ⎢ h1 F ⎥ ⎢ ⎥ ⎢ h2 F ⎥ ⎢ ⎥ ⎢ h3 F ⎥ ⎢ ⎥ ⎢ h4 ⎥ ⎢ ⎥. =⎢ ⎥ ⎢ h5 ⎥ ⎢h 1 F 2 ⎥ ⎢ ⎥ ⎢h 2 F 2 ⎥ ⎢ ⎥ ⎢h 3 F 2 ⎥ ⎢ ⎥ ⎢ h4 F ⎥ ⎢ ⎥ ⎣ h5 F ⎦ h6 If a nice basis with regard to (F, H ) is, say, {h 1 , h 1 F, h 1 F 2 , h 2 , h 4 , h 4 F}, then  = (3, 1, 0, 2, 0, 0), m = ((1, 2), (1, 4), (1, 4)), p = ((1, 2), (1, 2, 4, 7), (1, 2, 4, 7, 9, 12)), t = ((3), (2, 3, 5), (2, 3, 5, 6)), n = ((3), (2, 5), (6), (1, 4)). This means that h 3 = a1 h 1 + a4 h 2 h 2 F = b1 h 1 + b2 h 1 F + b4 h 2 + b5 h 4 h 5 = c1 h 1 + c2 h 1 F + c4 h 2 + c5 h 4

123

On the geometry of the generalized partial realization problem

63

h 6 = d1 h 1 + d2 h 1 F + d3 h 1 F 2 + d4 h 2 + d5 h 4 + d6 h 4 F h 1 F 3 = e1 h 1 + e2 h 1 F + e3 h 1 F 2 + e4 h 2 + e5 h 4 + e6 h 4 F h 4 F 2 = g1 h 1 + g2 h 1 F + g3 h 1 F 2 + g4 h 2 + g5 h 4 + g6 h 4 F Thus ⎡

0 ⎢0 ⎢ ⎢ e1 ⎢ ⎢ b1 ⎢ ⎢0  ⎢ ⎢ g1  F =⎢ ⎢1  H ⎢ ⎢0 ⎢ ⎢a ⎢ 1 ⎢0 ⎢ ⎣c

⎡

⎤

1 0 e2 b2 0 g2

0 1 e3 0 0 g3

0 0 e4 b4 0 g4

0 0 e5 b5 0 g5

0 0 0 0 1 c2 d1 d2

0 0 0 0 0 d3

0 1 a4 0 c4 d4

0 0 0 1 c5 d5 d6

0 0⎥ ⎥ e6 ⎥ ⎥ 0⎥ ⎥ 1⎥ ⎥ g6 ⎥ ⎥, 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎦

1 ⎢0 ⎢ ⎢a1 ⎢ ⎢0 ⎢ ⎢b1 ⎢ ⎢∗ ⎢ ⎢  H ) = ⎢ 0 ( F, ⎢c1 ⎢ ⎢0 ⎢ ⎢∗ ⎢ ⎢∗ ⎢ ⎢0 ⎢ ⎣∗ d1

0 0 0 1 b2 ∗ 0 c2 0 ∗ ∗ 0 ∗ d2

0 0 0 0 0 0 0 0 1 ∗ ∗ 0 ∗ d3

0 1 a4 0 b4 ∗ 0 c4 0 ∗ ∗ 0 ∗ d4

0 0 0 0 b5 ∗ 1 c5 0 ∗ ∗ 0 ∗ d5

⎤ 0 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥. 0⎥ ⎥ 0⎥ ⎥ ∗⎥ ⎥ ∗⎥ ⎥ 1⎥ ⎥ ∗⎦ d6

 H ) is characterized by  and the matrix The pair ( F, ⎡

a1 ⎢b1 ⎢ ⎢ c1 ⎢ ⎢d1 ⎢ ⎣ e1 g1

a4 b4 c4 d4 e4 g4

0 b2 c2 d2 e2 g2

0 b5 c5 d5 e5 g5

0 0 0 d3 e3 g3

⎤ 0 ⎡ 0⎥ A11 ⎥ ⎢ A21 0⎥ ⎥=⎢ ⎣ A31 d6 ⎥ ⎥ ⎦ A41 e6 g6

0 A22 A32 A42

⎤ 0 0 ⎥ ⎥. A33 ⎦ A43

As we have seen in the proof of Theorem 3.5 the last rows of Fii and Fi j corresponding to i = ki are 0 in (Fr , Hr ). Notice that these rows correspond just to the vectors of the nice basis in the block k (F, H ). So Proposition 4.8 (Fr , Hr ) is characterized by  and the matrix ⎡

A11 ⎢ A21 ⎢ ⎢ .. ⎣ .

0 A22 .. .

··· ··· .. .

0 0 .. .

⎤ ⎥ ⎥ ⎥ ∈ Fsk ×d . ⎦

Ak1 Ak2 · · · Akk

Corollary 4.9 The number of parameters of (Fr , Hr ) is k  (si − si−1 )(q1 + · · · + qi ). i=1

123

64

I. Baragaña et al.

Remark 4.10 Notice that in the reduced form (Fr , Hr ) the rows containing parameters in Fr correspond to the vectors h j F  j with 0 <  j < k j and the rows containing parameters in Hr correspond to the vectors h j with  j = 0. Example 4.11 Let (F, H ) with r = (1, 2, 3, 5), ⎤ h1 ⎢ h1 F ⎥ ⎥ ⎢ ⎢ h2 ⎥ ⎥ ⎢ ⎢h 1 F 2 ⎥ ⎥ ⎢ ⎢ h2 F ⎥ ⎥ ⎢ ⎥ (F, H ) = ⎢ ⎢ h3 ⎥ ⎢h 1 F 3 ⎥ ⎥ ⎢ ⎢h F 2 ⎥ ⎢ 2 ⎥ ⎢h F ⎥ ⎢ 3 ⎥ ⎣ h4 ⎦ ⎡

h5 and take s = (0, 1, 2, 4), so that q = (1, 1, 1, 1). If a (r , s)-nice basis is (h 1 , h 2 , h 2 F, h 4 ), then 1 = 1, 2 = 2, 3 = 0, 4 = 1, 5 = 0, and the components of the vectors h 1 F, h 3 , h 2 F 2 , h 5 appear in the reduced form: h 1 F = a1 h 1 + a2 h 2 h 3 = a3 h 1 + a4 h 2 + a5 h 2 F h 2 F 2 = a6 h 1 + a7 h 2 + a8 h 2 F + a9 h 4 h 5 = a10 h 1 + a11 h 2 + a12 h 2 F + a13 h 4 Hence, the (r , s)-reduced form is ⎡ ⎢ ⎢ ⎢ ⎢  ⎢ ⎢ Fr =⎢ ⎢ Hr ⎢ ⎢ ⎢ ⎢ ⎣

123

⎤ 0 0 1 0 ⎥ ⎥ a8 a9 ⎥ ⎥ 0 0 ⎥ ⎥ 0 0 0 ⎥ ⎥ 1 0 0 ⎥ ⎥ a4 a5 0 ⎥ ⎥ 0 0 1 ⎦ a11 a12 a13

a1 a2 0 0 a6 a7 0 0 1 0 a3 0 a10

On the geometry of the generalized partial realization problem

65

Hence ⎡

A11 ⎢ A21 ⎢ ⎣ A31 A41

0 A22 A32 A42

0 0 A33 A43

⎤ ⎡ ⎡ ⎤ 0 a1 A A 0 0 21 22 ⎢ a3 0 ⎥ ⎥ = ⎣ A31 A32 A33 0 ⎦ = ⎢ ⎣ a6 0 ⎦ A41 A42 A43 A44 A44 a10

a2 a4 a7 a11

0 a5 a8 a12

⎤ 0 0 ⎥ ⎥ a9 ⎦ a13

and the number of parameters of (Fr , Hr ) is 1 × 2 + 1 × 3 + 2 × 4 = 13.

5 The manifold R(r, s) The following step in our program is to endow the set of observable pairs that produce (A, B)-controlled invariant subspaces with fixed Brunovsky indices for the quotient with a differentiable structure. The set of such pair will be denoted by R(r , s). It will plays a fundamental role because the geometry of the solutions of the generalized partial realization problem is very much based on the differentiable structure of R(r , s). Definition 5.1 We denote by R(r , s) the set of pairs (F, H ) ∈ Fd×d × Fm×d such that ⎡

⎤ 1 (F, H ) ⎢ ⎥ .. rank ⎣ ⎦ = q1 + · · · + qi , qi = ri − si . . i (F, H )

R(r , s) is the set of pairs (F, H ) such that V = [(F, H )] is a controlled invariant subspace whose quotients with respect to V have s1 ≤ · · · ≤ sk as Brunovsky indices. It is clear that R(r , s) ⊂ d,m . Our aim is to prove that R(r , s) is a differentiable manifold (if F = C we mean a complex manifold). We will make use of the following notation: for a matrix X the symbol X (i 1 : i 2 , j1 : j2 ) represents the submatrix of X formed by the rows i 1 , i 1 + 1, . . . , i 2 and the columns j1 , j1 + 1, . . . , j2 of X . To begin with, we restrict ourselves to a subset of R(r , s), that will be denoted P(r , s), formed by the pairs (F, H ) ∈ R(r , s) such that for i = 1, . . . , k there exist non-negative integers q1i , q2i ,…, qii such that (i) q1i + · · · + qii = qi . (Recall that q11 = q1 ). (ii) qii ≥ qii+1 ≥ · · · ≥ qik .

123

66

I. Baragaña et al.

(iii) If pi = q1 + · · · + qi and i j = Hi F j−i then ⎡

⎤ 11 (1 : q1 , 1 : pi ) ⎢12 (1 : q12 , 1 : pi )⎥ ⎢ ⎥ ⎢22 (1 : q22 , 1 : pi )⎥ ⎢ ⎥ ⎢ ⎥ .. ⎢ ⎥ . ⎢ ⎥ = 0. det ⎢ ⎥ (1 : q , 1 : p )  1i i ⎥ ⎢ 1i ⎢ 2i (1 : q2i , 1 : pi ) ⎥ ⎢ ⎥ ⎢ ⎥ .. ⎣ ⎦ . ii (1 : qii , 1 : pi ) In words, P(r , s) is the set of observable pairs (F, H ) such that V = [(F, H )] is controlled invariant with s1 ≤ · · · ≤ sk as the Brunovsky indices of the quotients with respect to V and that admits an (r , s)-nice basis with m i = (1, . . . , q1i , r1 + 1, . . . , r1 + q2i , . . . , ri−1 + 1, . . . , ri−1 + qii ), 1 ≤ i ≤ k. We fix a pair (F, H ) ∈ P(r , s) and for this pair we fix a set of integers qi j satisfying the above conditions. Then we define the following subset of Fn×d : ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨

⎡

⎤ X 11 ⎢ X 12 ⎥ ⎢ ⎥ ⎢ X 22 ⎥ ⎢ ⎥ ⎢ .. ⎥ ⎢ . ⎥ n×d (ri −ri−1 )×d ⎥ W = X =⎢ : det ⎢ X 1k ⎥ ∈ F , X i j ∈ F ⎪ ⎢ ⎪ ⎥ ⎪ ⎢ X 2k ⎥ ⎪ ⎪ ⎢ ⎪ ⎥ ⎪ ⎢ . ⎥ ⎪ ⎪ . ⎪ ⎣ ⎪ . ⎦ ⎪ ⎩ X kk ⎫ ⎤ ⎡ X 11 (1 : q1 , 1 : pi ) ⎪ ⎪ ⎪ ⎪ ⎢ X 12 (1 : q12 , 1 : pi )⎥ ⎪ ⎪ ⎥ ⎢ ⎪ ⎪ ⎢ X 22 (1 : q22 , 1 : pi )⎥ ⎪ ⎪ ⎥ ⎢ ⎪ ⎪ ⎥ ⎢ .. ⎬ ⎥ ⎢ . ⎥ = 0, 1 ≤ i ≤ k . ×⎢ ⎢ X 1i (1 : q1i , 1 : pi ) ⎥ ⎪ ⎪ ⎥ ⎢ ⎪ ⎪ ⎢ X 2i (1 : q2i , 1 : pi ) ⎥ ⎪ ⎪ ⎥ ⎢ ⎪ ⎪ ⎥ ⎢ .. ⎪ ⎪ ⎦ ⎣ ⎪ . ⎪ ⎭ X ii (1 : qii , 1 : pi ) It is clear that this is an open set of Fn×d . Let ϕ : Fd×d × Fd×m → Fn×d (X, Y )  (X, Y )

123

On the geometry of the generalized partial realization problem

67

Since ϕ is a continuous map, U = ϕ −1 (W )

(13)

is open in Fd×d × Fd×m and (F, H ) ∈ U . Our aim is to construct a submersion from U to a space of matrices so that its zero level set is U ∩ P(r , s). This will prove that P(r , s) is a smooth manifold. Next we will show that this is not only true for a pair (F, H ) ∈ P(r , s) but for any pair (F, H ) ∈ R(r , s). Notice that U ∩ P(r , s) = U ∩ R(r , s). In order to construct this map we have to closely analyze the matrices belonging to V = ϕ(U ∩ R(r , s)). ⎡ ⎤ 11 ⎢ .. ⎥ ⎢ . ⎥ ⎢ ⎥ ⎥ Take a matrix  = ⎢ ⎢1k ⎥ ∈ V . Notice that  = (X, Y ) for some (X, Y ) ∈ U ∩ ⎢ . ⎥ ⎣ .. ⎦ kk P(r , s). Let us begin analyzing the block 11 . We have that det (1 : q1 , 1 : q1 ) = 0. Write # 1 1$

11 12 11 = 1 1

21 22

1 =  (1 : q , 1 : q ) and 1 =  (q + 1 : r , q + 1 : d). As 1 is with 11 11 1 1 11 1 1 1 22 11 invertible, there exists a non-singular matrix P such that

0 I q1 11 P = 1 1 −1 1 − 1 1 −1 1 .

21 11 22 21 11 12 

−1

1 1 1 1 = 0. In other words, the Hence rank   1 111 = q1 if and only if 22 − 21 11 1 12 1 if and only if 1 − 1 rows of 21 22 depend linearly of the rows of 11 12 22 21 1

11

−1 1

12

= 0.

⎡

⎤ 11 Let us analyze now the block 2 = ⎣12 ⎦. We know that its rank is q1 + q2 = p2 . 22  1 1  1 1 Since the rows of 21

22 depend linearly of the rows of 11

12 , the last r1 − q1 rows of 12 also depend linearly of the preceding ones. Hence, when computing the rank of 2 the r1 − q1 last rows of 11 and 12 can be removed. Put ⎡

⎡ ⎤ ⎤ 11 (1 : q1 , 1 : p2 ) 11 (1 : q1 , 1 : p2 + 1 : d) 2 2 = ⎣12 (1 : q12 , 1 : p2 )⎦ = ⎣ 12 (1 : q12 , p2 + 1 : d) ⎦

11

12 22 (1 : q22 , 1 : p2 ) 22 (1 : q22 , p2 + 1 : d)   12 (q12 + 1 : q1 , 1 : p2 ) 12 (q12 + 1 : q1 , p2 + 1 : d) 2 2 = =

22

21 22 (q22 + 1 : r2 − r1 , 1 : p2 ) 22 (q22 + 1 : r2 − r1 , p2 + 1 : d)

123

68

I. Baragaña et al.

and

2 =

# 2 2$

11 12 2 2

21 22

Once the last r1 − q1 rows has been eliminated from 11 and 12 , the matrix 2 is 2 up to a reordering of their rows. Then rank 2 = p2 if and only if rank 2 = p2 . 2  = 0 so that reasoning as in the previous case, we have rank  = p if But det 11 2 2 2 − 2 2 −1 2 = 0. and only if 22 21 11 12 In general, for i = 1, . . . , k we have ⎤ 11 ⎢12 ⎥ ⎥ ⎢ ⎢22 ⎥ ⎥ ⎢ ⎢ .. ⎥ ⎥. i = ⎢ . ⎥ ⎢ ⎢ 1i ⎥ ⎥ ⎢ ⎢ . ⎥ ⎣ .. ⎦ ⎡

ii

Define qii−1 := ri − ri−1 (q10 := r1 ) and ⎤ 11 (1 : q11 , 1 : pi ) ⎢12 (1 : q12 , 1 : pi )⎥ ⎥ ⎢ ⎢22 (1 : q22 , 1 : pi )⎥ ⎥ ⎢ ⎥ ⎢ .. ⎥ ⎢ . ⎥ ⎢ =⎢ ⎥ (1 : q , 1 : p )  1i i ⎥ ⎢ 1i ⎢ 2i (1 : q2i , 1 : pi ) ⎥ ⎥ ⎢ ⎥ ⎢ .. ⎦ ⎣ . ⎡

i

11

⎡

⎡

ii (1 : qii , 1 : pi )

⎤ 1i (q1i + 1 : q1i−1 , 1 : pi ) ⎢2i (q2i + 1 : q2i−1 , 1 : pi )⎥ ⎢ ⎥ i

21 =⎢ ⎥ .. ⎣ ⎦ . ii (qii + 1 : qii−1 , 1 : pi )

11 (1 : q11 , pi + 1 : d) 12 (1 : q12 , pi + 1 : d) 22 (1 : q22 , pi + 1 : d) .. .

⎤

⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ i ⎥ ⎢

12 = ⎢ ⎥ (1 : q , p + 1 : d)  1i i ⎥ ⎢ 1i ⎢ 2i (1 : q2i , pi + 1 : d) ⎥ ⎥ ⎢ ⎥ ⎢ .. ⎦ ⎣ . ii (1 : qii , 1 : pi + 1 : d) ⎡ ⎤ 1i (q1i + 1 : q1i−1 , pi + 1 : d) ⎢2i (q2i + 1 : q2i−1 , pi + 1 : d)⎥ ⎢ ⎥ i

22 =⎢ ⎥ .. ⎣ ⎦ . ii (qii + 1 : qii−1 , pi + 1 : d)

Finally we set

i =

# i $ i

11 12 i i

21 22

.

Recall that qii ≥ qii+1 ≥ · · · ≥ qik . When qi−1 = qi we understand that the submatrices i (qi + 1 : qi−1 , 1 : pi ) and i (qi + 1 : qi−1 , pi + 1 : d) are i and i , respectively. We apply the same empty or, in other words, they are not in 21 22

123

On the geometry of the generalized partial realization problem

69

i y i . Notice also that for i = k, convention if some qi = 0 in the matrices 11 12 k k

12 and 22 has no columns ( pk = q1 + · · · + qk = d). In this case the condition −1

k − k k k

22 21 11 12 = 0 is meaningless but we will agree, if it is necessary, that it holds. Notice that the same could happen when i is less than k, depending on the Brunovsky indices of the quotient. In summary, i = 0 Theorem 5.2 (X, Y ) ∈ U ∩ P(r, s) if and only if (X, Y ) is such that det 11 i − i i and 22 21 11

−1 i

12

= 0 for i = 1, . . . , k.

We are going to define now a differentiable map from U to a space of matrices. Let i i i Z i = 22 − 21

11

−1 i

12 ,

i = 1, . . . , k − 1.

The size of Z i is the following: • Number of rows : (q1i−1 − q1i ) + (q2i−1 − q2i ) + · · · + (qii−1 − qii ) = qi−1 + ri − ri−1 − qi = (ri − qi ) − (ri−1 − qi−1 ) = si − si−1 . • Number of columns: d − pi = qi+1 + · · · + qk . Define :  : U → Fs1 ×(d−q1 ) × F(s2 −s1 )×(d− p2 ) × · · · × F(sk−1 −sk−2 )×qk (X, Y ) → (Z 1 , Z 2 , . . . , Z k−1 )

(14)

This map is well defined and differentiable in every point of U . Our objective is to show that it is a submersion in every point (F, H ) ∈ U ; and, in particular, in the fixed pair (F, H ). In fact, we have the following Lemma 5.3 With the above notation rank d(F,H ) =

k−1  (si − si−1 )(d − pi ). i=1

Proof First of all recall that if ϕ : M → M is defined by ϕ( ) = −1 where M is an open set of invertible matrices, then dϕ (S) = − −1 S −1 . Then if X and Y are small enough matrices (F + X, H + Y ) − (F, H ) i i i i i i −1 i i i = ( 22 + S22 − ( 21 + S21 )( 11 + S11 ) ( 12 + S12 ) − 22 i i −1 i + 21 ( 11 ) 12 )i=1...k−1 i i i i −1 i −1 i i −1 i i = (S22 − ( 21 + S21 )(( 11 ) − ( 11 ) S11 ( 11 ) + · · · )( 12 + S12 ) i i −1 i + 21 ( 11 ) 12 )i=1...k−1 ,

# where i (X, Y ) =

i Si S11 12 i Si S21 22

#

$ is defined in a similar way as i =

i i

11 12 i i

21 22

$ .

123

70

I. Baragaña et al.

Hence, for any X ∈ Fd×d and Y ∈ Fd×(d+m) , i i i −1 i d(F,H ) (X, Y ) = (S22 − 21 ( 11 ) S12 i i −1 i i −1 i i i −1 i + 21 ( 11 ) S11 ( 11 ) 12 − S21 ( 11 ) 12 )i=1...k−1

i are free the lemma follows. Taking into account that the parameters in S22

 

Corollary 5.4 If (F, H ) ∈ P(r , s) then there exists an open set U in Fd×d × Fm×d k−1 such that (F, H ) ∈ U and U ∩R(r , s) is a submanifold of U of codimension i=1 (si − si−1 )(d − pi ). We are going now to prove that any pair (F, H ) ∈ R(r , s) admits a neighborhood U such that U ∩ R(r , s) is a submanifold of U . Lemma 5.5 For any (F, H ) ∈ R(r , s) there exist permutation matrices P and Q such that (P T F P, Q H P) ∈ P(r , s). Proof Take a (r , s)-nice basis with respect to (F, H ). This means that there are qi = ri − si rows of the block i (F, H ) corresponding to this basis. Let q ji the number of rows that have been chosen in block H j F i− j . Then q1i + · · · + qii = qi and qii ≥ qii+1 ≥ · · · ≥ qik . Consider now the block Hi , i = 1, . . . , k. Let h i1 , . . . , h i,t be the rows of Hi having  as indices of the nice basis (i.e., h j F −1 is in the nice basis but h j F  is not). It is clear that there exists a permutation matrix Q i such that in Q i Hi the first tk rows are h ik1 , . . . , h iktk , the following are h ik−11 , . . . , h ik−1tk−1 , and so on. It is also clear that the rows of Q i Hi F  that are in the nice basis are the first ones. If we put Q = Diag(Q 1 , . . . , Q k ) we have that the qi j first rows of the block i j of (F, Q H ) are linearly independent. Concerning the columns, there exists a permutation matrix P1 such that the first q1 columns of 1 P1 are linearly independent, there exists a permutation matrix P2 such that the first p2 = q1 + q2 columns of 

 1 I 0 P1 q1 2 0 P2

123

On the geometry of the generalized partial realization problem

71

are linearly independent, and so on. That is to say, there exists a permutation matrix P such that if  = (F, Q H )P then ⎤ 11 (1 : q1 , 1 : pi ) ⎢12 (1 : q12 , 1 : pi )⎥ ⎥ ⎢ ⎢22 (1 : q22 , 1 : pi )⎥ ⎥ ⎢ ⎥ ⎢ .. ⎥ ⎢ . ⎥ det ⎢ ⎢ 1i (1 : q1i , 1 : pi ) ⎥ = 0. ⎥ ⎢ ⎢ 2i (1 : q2i , 1 : pi ) ⎥ ⎥ ⎢ ⎥ ⎢ .. ⎦ ⎣ . ⎡

ii (1 : qii , 1 : pi )

But (F, Q H )P = (P T F P, Q H P). Consequently, (P T F P, Q H P) ∈ P(r , s)   for some integers q ji . Now, let (F, H ) ∈ R(r , s) and P and Q permutation matrices such that (P T F P, Q H P) ∈ P(r , s). By Corollary 5.4 there is an open set U in Fd×d × Fm×d such that (P T F P, Q H P) ∈ U and U ∩ R(r , s) is a submanifold of U . Since the following map is a linear isomorphism f : Fd×d × Fm×d → Fd×d × Fm×d (X, Y ) → (P T X P, QY P) it follows that U  = f −1 (U ) is an open set in Fd×d × Fm×d containing (F, H ). If  is the mapping defined in (14) then  ◦ f : U  → Fs1 ×(d−q1 ) × F(s2 −s1 )×(d− p2 ) × · · · × F(sk−1 −sk−2 )×qk is a submersion whose zero level is U  ∩ R(r , s). Hence, every point of R(r , s) has a open neighborhood U  in Fd×d × Fm×d such that U  ∩ R(r , s) is a submanifold of U  . The following theorem has been proved Theorem 5.6 R(r , s) is a submanifold of Fd×d × Fm×d and dim R(r , s) = d(m + d) −

k−1  (si − si−1 )(d − pi ). i=1

6 The manifold R(r, s)/ In order to prove that the set of solutions of the generalized realization problem is a stratified manifold we need to provide the quotient space R(r , s)/ of R(r , s) by the -equivalence with a differentiable structure. This can be done actually in two different ways. The first one is to use the bijection of Proposition 3.1. With the notation in Sect. 4,

123

72

I. Baragaña et al.

let Jnv(r , s) be the set of d-dimensional controlled invariant subspaces having as quotient n a pair with Brunovsky indices m−q = sk ≥ · · · ≥ sk−l+1 > sk−l = 0 = · · · = 0, i=1 si = n − d, ri ≥ si , 1 ≤ i ≤ k. Denote Inv(r , s) the set of (n − d)-dimensional (B ∗ , A∗ )-conditioned invariant subspaces having s as Brunovsky indices of the restriction. A parametrization of all (C, A)-conditioned invariant subspaces was obtained in [11] and it was shown in [8] that Inv(r , s) is a differentiable manifold of dimension k  (si − si−1 )(q1 + · · · + qi ). dim Inv(r , s) = i=1

and in [27] a coordinate atlas, and hence a parametrization, was obtained. Since the map V → V ⊥ is a diffeomorphism from Grd (Fn ) to Grn−d (Fn ), the set Jnv(r , s) inherits, in a natural way, the structure of a differentiable manifold such that dim Jnv(r , s) = dim Inv(r , s). Then the map ϕ in Proposition 3.1 induces a bijection, also denoted by ϕ ϕ : Jnv (r , s) −→ R(r , s)/

(15)

Through this bijection it is possible to provide R(r , s)/ with a structure of differentiable manifold. We will need, however, a coordinate chart around each point of R(r , s)/ in order to prove that the set of generalized partial realizations is a stratified manifold. Thus we will proceed as in [27]. Given  = (1 , . . . m ), indices of a (r , s)-nice basis for (F, H ), we know that 

(F, H ) ∼ (Fr , Hr ) where (Fr , Hr ) is in reduced form. The number of parameters of (Fr , Hr ) has been computed in Corollary 4.9 and it is exactly dim Inv(r , s). This coincidence leads us to think that the parameters of (Fr , Hr ) may play the role of local coordinates for the controlled invariant subspace associated to the equivalence class. In fact, (i) If  are the indices of a nice basis for (F, H ) they are also the indices of a nice basis for every pair in a small enough neighborhood of (F, H ) in R(r , s). 

(ii) If  are the indices of a nice basis for (F, H ) and (F, H ) ∼ (F  , H  ) then  are also the indices of a nice basis for (F  , H  ). (iii) If (F, H ), (F  , H  ) ∈ R(r , s) are in reduced form with the same set of indices 

and (F, H ) ∼ (F  , H  ) then (F, H ) = (F  , H  ). 

The first two items are easily concluded. As for item (iii), if (F, H ) ∼ (F  , H  ), there exists P ∈ Gl(d, F) such that (F, H )P = (F  , H  ). But, as the two pairs are in reduced form with the same set of indices, the submatrices of (F, H ) and (F  , H  ) formed by the rows corresponding to the nice basis are the same. Hence P = Id and our claim follows.  So, we can associate to each -equivalence class (F, H ) ∈ R(r , s)/ a pair in reduced form (Fr , Hr ). This pair depends only on the set of indices of the nice basis

123

On the geometry of the generalized partial realization problem

73

and on the parameters, but not on the representative (F, H ). Furthermore, there exists an open neighborhood of (F, H ) such that every pair in this neighborhood admits the same set of indices. Let I be the set of all possible indices of (r , s)-nice bases. This is a finite set that admits an explicit characterization: If  = (1 , . . . , m ) are the indices of an (r , s)-nice basis, k = (k1 , . . . , km ) the conjugate partition of (r1 , . . . , rk ), (c1 , . . . , cm ) the conjugate partition of (s1 , . . . , sk ) and k −  the conjugate partition of k −  = (k1 − 1 , . . . , km − m ) then I = { = (1 , . . . , m ); 0 ≤ i ≤ ki , 1 ≤ i ≤ m and k −  = s} = { = (1 , . . . , m ); there exists a permutation σ of {1, . . . , m} such that ki ≥ cσ (i) and i = ki − cσ (i) , 1 ≤ i ≤ m}.

(16)

Notice that k −  is, in general, an unordered partition. For  ∈ I define U = {(F, H ) ∈ R(r , s); (F, H ) admits  as indices of a nice basis}. Then {U ;  ∈ I} is a finite open covering of R(r , s). We consider in R(r , s)/ the final topology with regard to the natural projection  = π : R(r , s) −→ R(r , s)/. Then, since U = π −1 (π(U )), one has that {U π(U );  ∈ I} is an open covering of R(r , s)/. Let  = dim Inv(r , s). N This is the number of parameters of a reduced form. For each  ∈ I we define a map 

 : U −→ F N

in the following way: With the notation in Proposition 4.8, for every (F, H ) ∈ U ,   (F, H ) is the point in F N defined by arranging the elements of (A11 , A21 , A22 , . . . , Ak1 , . . . , Akk ) in some specific order. Let us denote this point by (A11 , A21 , A22 , . . . , Ak1 , . . . , Akk ).  induces a map 

 −→ F N θ : U defined by

 H ) = (A11 , A21 , A22 , . . . , Ak1 , . . . , Akk ). θ (F, Lemma 6.1 (i) θ is an homeomorphism.  ∩ U  = ∅ then θ ◦θ −1 : θ (U  ∩ U  ) −→ θ (U  ∩ U  ) is a differentiable (ii) If U  map.

123

74

Proof

I. Baragaña et al.

(i) The continuity of θ follows taking into account that, in the notation of the proof of Theorem 3.5, the map (F, H ) → (P F P −1 , H P −1 ) (see Remark 3.7) is continuous and that the topology of R(r , s)/ is a final topology. Let us see   that θ−1 is also continuous. Take a ∈ F N and a sequence (a p ), a p ∈ F N having limit a. Denote (Fr , Hr ) and (Fr , Hr ) p the reduced forms in R(r , s) with index  and parameters a and a p , respectively. Since, in the Frobenious norm, (Fr , Hr ) − (Fr , Hr ) p  = a − a p 

the sequence (Fr , Hr ) p in R(r , s) has limit (Fr , Hr ). Then we conclude that θ−1 is continuous by the continuity of π . (ii) This property follows taking into account that the map (F, H ) → (P F P −1 , H P −1 ) is not only continuous but also differentiable.    , θ )∈I defines a coordinate atlas in R(r , s)/. This lemma shows that the family (U We provide this space with the unique differentiable structure defined by extending  , θ )∈I to a maximal coordinate atlas. In summary (U Proposition 6.2 R(r , s)/ is a differentiable manifold such that dim R(r , s)/ = dim Inv(r , s) =

k 

(si − si−1 )(q1 + · · · + qi )

i=1

and for each  ∈ I, the map  −→ F N θ : U defined by  θ (F, H ) = (A11 , A21 , A22 , . . . , Ak1 , . . . , Akk ) is a coordinate chart. 7 The manifold of generalized partial realizations As stated in Sect. 1, the main goal of this paper is to study the geometry of the generalized partial realizations introduced by Antoulas in [1]. We recall the definition ⎡ ⎤ L1 ⎢ ⎥ Definition 7.1 Let L = (L 1 , . . . , L k ), L i ∈ Fri ×δ , i = 1, . . . , k, L = ⎣ ... ⎦. We say Lk × × is a generalized partial realization of L if that (F, H, M) ∈ (F, H )M = L, with rank (F, H ) = d. (L) will denote the set of generalized partial realizations of L. Fd×d

123

Fm×d

Fd×δ

On the geometry of the generalized partial realization problem

75

Notice that since (F, H ) is a full rank matrix, M is uniquely determined by L. Hence (L) can be identified with the set R(L) = {(F, H ) ∈ Fd×d × Fm×d ; (F, H )M = L for some M ∈ Fd×δ , rank (F, H ) = d}. If we denote R(r , s; L) = R(L) ∩ R(r , s) then R(L) = ∪s R(r , s; L) where s runs over the partitions of n − d compatible with r ; that is, si ≤ ri , 1 ≤ i ≤ k. Our aim is to prove that if R(r , s; L) = ∅ then it is a submanifold of R(r , s). We need some additional notation. Decompose the matrix L ∈ Fn×δ as follows: ⎤ L 11 ⎢ L 21 ⎥ ⎥ ⎢ ⎢ L 22 ⎥ ⎥ ⎢ ⎢ .. ⎥ ⎥, L=⎢ . ⎥ ⎢ ⎢ L k1 ⎥ ⎥ ⎢ ⎢ . ⎥ ⎣ .. ⎦ ⎡

L i j ∈ F(r j −r j−1 )×δ

L kk and form the matrices   L 1 = L 11 L 21 · · · L k1 ∈ Fr1 ×kδ , ⎡ ⎤ L 11 L 21 · · · L k−1,1 L 2 = ⎣ L 21 L 31 · · · L k,1 ⎦ ∈ F(r1 +r2 )×(k−1)δ , . . . , L k = L . L 22 L 32 · · · L k,2 In general, ⎡

L 11 ⎢ L 21 ⎢ ⎢ L 22 ⎢ ⎢ .. i L =⎢ ⎢ . ⎢ L i1 ⎢ ⎢ . ⎣ ..

L 21 L 31 L 32 .. . L i+1,1 .. .

L ii L i+1,i

⎤ · · · L k−i+1,1 · · · L k−i+2,1 ⎥ ⎥ · · · L k−i+2,2 ⎥ ⎥ ⎥ .. .. ⎥ ∈ F(r1 +···+ri )×(k−i+1)δ , 1 ≤ i ≤ k. . . ⎥ · · · L k,1 ⎥ ⎥ ⎥ .. .. ⎦ . . · · · L k,i

(17)

We need, first of all, a condition for R(r , s; L) not to be empty.

123

76

I. Baragaña et al.

Proposition 7.2 With the notation of Sect. 4, R(r , s; L) = ∅ if and only if there exists a set of indices  ∈ I such that rank L i = rank L i ( pi ), 1 ≤ i ≤ k.

(18)

where I is the set defined in (16). Proof Assume that R(r , s; L) = ∅ and let (F, H ) ∈ R(r , s; L). Then (F, H )M = L for some M ∈ Fd×δ and ⎡

1 M 1 F M ⎢2 M 2 F M ⎢ Li = ⎢ . .. ⎣ .. . i M i F M

⎤ . . . 1 F k−i M . . . 2 F k−i M ⎥ ⎥ ⎥ = i C, 1 ≤ i ≤ k, .. .. ⎦ . . . . . i F k−i M

⎡

⎤ 1 ⎢2 ⎥   ⎢ ⎥ where i = ⎢ . ⎥ and C = M F M . . . F k−i M . ⎣ .. ⎦

i Let  ∈ I be a set of indices of an (r , s)-nice basis for (F, H ). Then rank i = rank i ( pi ) (see Sect. 4) and there exists a matrix X ∈ F(r1 +···+ri )×(q1 +···+qi ) such that i = X i ( pi ). Hence L i = i C = X i ( pi )C = X L i ( pi ).

It follows that rank L i = rank L i ( pi ). Conversely, if there exists a set of indices  ∈ I satisfying (18), then there are matrices Ai j ∈ F(si −si−1 )×q j , 1 ≤ j ≤ k, such that   L i (r1 + · · · + ri−1 + n i ) = Ai1 Ai2 · · · Aii L i ( pi ), 1 ≤ i ≤ k.

(19)

Therefore, ⎡

L(r1 + · · · + r j + m 1 ) L(r1 + · · · + r j+1 + m 2 ) .. .

⎤

⎥ ⎥ ⎥, ⎦ i L(r1 + · · · + ri+ j−1 + m ) 0 ≤ j ≤ k − 1; 1 ≤ i ≤ k − j.

 ⎢ ⎢ L(r1 +. . .+ri+ j−1 +n i ) = Ai1 Ai2 · · · Aii ⎢ ⎣

123

(20)

On the geometry of the generalized partial realization problem

77

Consider the matrix ⎡

A11 ⎢ A21 ⎢ ⎢ .. ⎣ .

0 A22 .. .

··· ··· .. .

0 0 .. .

⎤ ⎥ ⎥ ⎥ ∈ Fsk ×d . ⎦

(21)

Ak1 Ak2 · · · Akk

By Proposition 4.8, we can identify it with a pair (Fr , Hr ) in reduced form with respect to . Then (Fr , Hr ) ∈ R(r , s) and   j j i (n i )Fr = Ai1 Ai2 · · · Aii ( pi )Fr , 0 ≤ j ≤ k − 1; 1 ≤ i ≤ k − j. That is to say, ⎡ ⎢  ⎢ (r1 +· · ·+ri+ j−1 +n i ) = Ai1 Ai2 · · · Aii ⎢ ⎣

(r1 + · · · + r j + m 1 ) (r1 + · · · + r j+1 + m 2 ) .. .

⎤ ⎥ ⎥ ⎥ , (22) ⎦

(r1 + · · · + ri+ j−1 + m i ) 0 ≤ j ≤ k − 1; 1 ≤ i ≤ k − j. Let M := ( p k )−1 L( p k ) ∈ Fd×δ . Then L( p k ) = ( p k )M,

(23)

L(r1 + · · · + r j−1 + m j ) = (r1 + · · · + r j−1 + m j )M, 1 ≤ j ≤ k.

(24)

and so

Let us see that M = L, so (Fr , Hr ) ∈ R(r , s; L). Notice that {1, . . . , r j } = m j ∪ n j ∪ n j−1 ∪ · · · ∪ n 1 , 1 ≤ j ≤ k. Then, we must prove that L(r1 + · · · + r j−1 + n i ) = (r1 + · · · + r j−1 + n i )M, 1 ≤ j ≤ k; 1 ≤ i ≤ j,

123

78

I. Baragaña et al.

which is equivalent to L(r1 + · · · + ri+ j−1 + n i ) = (r1 + · · · + ri+ j−1 + n i )M, 0 ≤ j ≤ k − 1; 1 ≤ i ≤ k − j.  

This can be proved by induction on j.

Remark 7.3 Observe that, given (F, H ) ∈ R(r , s) and a set of indices  ∈ I of an (r , s)-nice basis for (F, H ), if we identify the reduced form (Fr , Hr ) of (F, H ) with respect to  with the matrix (21) then (F, H ) ∈ R(r , s; L) if and only if (19) holds. Let N=

k 

(si − si−1 ) rank L i .

(25)

i=1

Our main result is Theorem 7.4 If R(r , s; L) = ∅, then R(r , s; L) is a submanifold of R(r , s) and dim R(r , s; L) = dim R(r , s) − N . Proof Assume that R(r , s; L) = ∅. In order to prove that R(r , s; L) is a differentiable manifold of dimension dim R(r , s) − N , we fix a pair (F0 , H0 ) ∈ R(r , s; L) and for this pair we fix a set of indices, , of an (r , s)-nice basis. Let U = {(F, H ) ∈ R(r , s) : (F, H ) admits  as indices of an (r , s)-nice basis} and recall (Proposition 6.2) that if 

 −→ F N θ : U is defined by

 H ) = (A11 , A21 , A22 , . . . , Ak1 , . . . , Akk ) θ (F,  , θ ) is a coordinate chart of R(r , s)/ around (F then (U 0 , H0 ). We are going to define a differentiable map  from U into a space of matrices such that  will have constant rank, N , and such that R(r , s; L) ∩ U will be a level set of . This will prove that R(r , s; L) is an embedded submanifold of R(r , s) of codimension N . First, we consider the restriction of the natural projection π : R(r , s) −→ R(r , s)/ to U ; i.e., π:

123

 U −→ U  (F, H ) → (F, H )

On the geometry of the generalized partial realization problem

79

And second, if (F, H ) ∈ U , we identify the reduced form (Fr , Hr ) of (F, H ) with respect to  with the matrix (21). By Remark 7.3, (F, H ) ∈ R(r , s; L) if and only if   L i (r1 + · · · + ri−1 + n i ) = Ai1 Ai2 · · · Aii L i ( pi ), 1 ≤ i ≤ k. Let us define the following set of matrices ⎧ ⎪ ⎪ ⎪ ⎨

⎡

X 11 0 · · · ⎢ X 21 X 22 · · · ⎢ C := X = ⎢ . .. . . ⎪ ⎣ .. . . ⎪ ⎪ ⎩ X k1 X k2 · · ·

0 0 .. . X kk

⎫ ⎪ ⎪ ⎪ ⎬

⎤

⎥ ⎥ ⎥ ∈ Fsk ×d ; X i j ∈ F(si −si−1 )×q j , 1 ≤ j ≤ i ≤ k ⎪ ⎦ ⎪ ⎪ ⎭

  that we identify with F N , N = dim R(r , s)/. Define (s1 −s0 )×kδ × F(s2 −s1 )×(k−1)δ × · · · × F(sk −sk−1 )×δ β:C ⎡ −→ F ⎤ X 11 0 · · · 0 ⎢ X 21 X 22 · · · 0 ⎥ ⎢ ⎥ ⎢ .. .. . . .. ⎥ → (Z 1 , . . . , Z k ) ⎣ . . . ⎦ . X k1 X k2 · · · X kk

where   Z i = X i1 · · · X ii L i ( pi ), 1 ≤ i ≤ k. This map β is linear, hence differentiable, and it has constant rank rank β =

k k   (si − si−1 ) rank L i ( pi ) = (si − si−1 ) rank L i = N . i=1

i=1

 , θ )∈I is a coordinate chart around (F Finally, since (U 0 , H0 ) in R(r , s)/, we have that the map  −→ C  θ : U ⎡

A11 ⎢ A21 ⎢  (F, H ) → ⎢ . ⎣ ..

0 A22 .. .

··· ··· .. .

0 0 .. .

⎤ ⎥ ⎥ ⎥ ⎦

Ak1 Ak2 · · · Akk

is a diffeomorphism. Hence, the map  −→ F(s1 −s0 )×kδ × F(s2 −s1 )×(k−1)δ × · · · × F(sk −sk−1 )×δ α = β ◦ θ : U    (F, H ) → (A11 L 1 ( p 1 ), . . . , Ak1 . . . Akk L k ( p k ))

123

80

I. Baragaña et al.

is differentiable and has constant rank N . Therefore  = α ◦ π : U −→ F(s1 −s0 )×kδ × F(s2 −s1 )×(k−1)δ × · · · × F(sk −sk−1 )×δ defined by   (F, H ) = (A11 L 1 ( p 1 ), . . . , Ak1 . . . Akk L k ( p k )) is differentiable, has constant rank and −1 (L 1 (n 1 ), L 2 (r1 + n 2 ) . . . , L k (r1 + · · · + rk−1 + n k )) = R(r , s; L) ∩ U . This completes the proof that R(r , s; L) is an embedded submanifold of R(r , s) of codimension N .   8 The geometry of the cover and generalized partial realization problems As said in Sect. 1, there is a close relationship between both the cover and the generalized partial realization problems. Indeed, as remarked in Sect. 6, R(r , s)/ can be endowed with a differentiable structure through the bijection (15). We will show that this bijection is, in fact, a diffeomorphism so that R(r , s)/ and Jnv(r , s) can be identified. Thanks to this identification and taking into account the differentiable structure of the solutions of the (dual) cover problem obtained in [28] an alternative proof of Theorem 7.4 can be provided. The notation of Sects. 6 and 7 will be adopted. be the map defined by ψ(F, H ) = (F, H ) Lemma 8.1 Let ψ : R(r , s) −→ Fn×d d and denote R = Im ψ. Then (i) R is a submanifold of Fn×d d . (ii) The natural projection πR : R −→ Jnv(r , s), πR ((F, H )) = [(F, H )], is a submersion. Proof Consider the diagram Fn×d d ↓π Jnv(r , s) ⊂ Grd (Fn ) −1 where π(X ) = [X ], X ∈ Fn×d d . Then R = π (Jnv(r , s)) and the lemma follows taking into account that π is a submersion.  

Next, we will prove that the projection π : R(r , s) −→ R(r , s)/

(26)

is a submersion. For the proof of this assertion we will use the manifold R(r , s)/ Gl(d, F).

123

On the geometry of the generalized partial realization problem

81

Lemma 8.2 The action of Gl(d, F) on R(r , s) defined by (P, (F, H )) −→ (P F P −1 , H P −1 ) is free and proper. Proof It follows taking into account that this action on d,m is free and proper.

 

Corollary 8.3 The quotient space R(r , s)/ Gl(d, F) is a differentiable manifold such that (i) The natural projection p : R(r , s) −→ R(r , s)/ Gl(d, F) is a submersion. (ii) dim R(r , s)/ Gl(d, F) = dim R(r , s) − d 2 . Notice that the equivalence relation associated to the action of Gl(d, F) on R(r , s) is just the similarity. Hence, given (F, H ) ∈ R(r , s) and a set of indices  admissible by  H ) of Theorem 3.5 Its number (F, H ), a reduced form for this relation is the pair ( F, of parameters is (Corollary 4.6) % = dm − N

k−1  (si − si−1 )(qi+1 + · · · + qk ). i=1

An easy computation shows that % = dim R(r , s) − d 2 = dim R(r , s)/ Gl(d, F). N Then in a similar way as for the coordinate atlas of R(r , s)/, we have the following result % = p(U ),  ∈ I and Proposition 8.4 With the notation in Proposition 4.5, let U % N % % θ : U → F defined by  % θ ((F, H )) = (A11 , A21 , A22 , . . . , Ak+1,1 , . . . , Ak+1,k )  where (F, H ) denotes the orbit of (F, H ) under the action of Gl(d, F). Then the family % % (U , θ )∈I is a coordinate atlas for R(r , s)/ Gl(d, F). Let us consider now the natural map τ τ : R(r , s)/ Gl(d, F) −→ R(r , s)/   defined by τ ((F, H )) = (F, H ). Then we have Lemma 8.5 The map τ is a submersion.   Proof Taking coordinate charts around (F, H ) and (F, H ) as defined in Proposi%  tion 8.4 and Lemma 6.1 it is clear that τ is a linear projection from F N to F N , so that τ is, indeed, a submersion.  

123

82

I. Baragaña et al.

Now, our claim that π , (26), is a submersion follows easily. In fact we have the factorization of π R(r , s) −→ R(r , s)/ Gl(d, F) −→ R(r , s)/ that is, π = τ ◦ p. Hence we have proved the following Proposition 8.6 The projection π : R(r , s) −→ R(r , s)/ is a submersion. Remark 8.7 The reader can check that dim R(r , s)/ = sk d −

k−1 

si qi+1 .

i=1

Analogously, it can be shown that dim R(r , s) = d(m + d) −

k−1 

si qi+1 .

i=1

Hence, dim R(r , s) − dim R(r , s)/ = d 2 + (m − sk )d. Notice that, as it should be, this is just the dimension of the fiber of the projection R(r , s) −→ R(r , s)/ (see Proposition 3.3 and recall that sk = m − q). Proposition 8.8 The bijection ϕ : Jnv(r , s) → R(r , s)/  V = [(F, H )]  (F, H) is a diffeomorphism. Proof We prove first that ϕ is continuous. Let V ∈ Jnv(r , s) and let V p be a sequence in Jnv(r , s) such that lim V p = V. We will show that lim ϕ(V p ) = ϕ(V). Let σ be a local section around V of the submersion πR : R −→ Jnv(r , s). Then σ (V) = lim σ (V p ). Let (F, H ), (F p , H p ) ∈ R(r , s) such that σ (V) = (F, H ), σ (V p ) = (F p , H p ). If  is a set of indices for (F, H ) then, for p big enough, (F p , H p ) ∈ U because lim (F p , H p ) = (F, H ) and U is an open set. Denote (Fr , Hr ) and (F pr , H pr ) the corresponding reduced forms of (F, H ) and (F p , H p ). Let P be the matrix in the proof of Theorem 3.5 (with an analogous meaning for Pp ). We have (F, H ) = (Fr , Hr )P

123

On the geometry of the generalized partial realization problem

83

and (F p , H p ) = (F pr , H pr )Pp . But lim Pp = P because the rows of P are rows of (F, H ). So lim (F pr , H pr ) = (Fr , Hr ). Now, ϕ(V) = ϕ([(F, H )]) = ϕ([(Fr , Hr )]) = (F r , Hr ) and analogously,   , θ ) is the coordinate chart of R(r , s)/ correspond, H pr ). If (U ϕ(V p ) = (F pr  . ing to  then (F r , Hr ), (F pr , H pr ) ∈ U Let us take a close look at the matrix (Fr , Hr ) when (Fr , Hr ) is in reduced form (see Examples 4.7 and 4.11): the elements of matrices Ai j of free parameters appear explicitly in (Fr , Hr ) as entries of this matrix. Hence, lim (F pr , H pr ) =  (Fr , Hr ) implies lim θ (F pr , H pr ) = θ (F r , Hr ) so that ϕ is continuous. −1 Now, if V = ϕ (U ), {V ;  ∈ I} is an open covering of Jnv(r, s) and the map

   α : V → F N , N = dim Jnv(r , s), defined by α (V) = α ([(F, H )]) = θ ((F, H )) is well defined and bijective. Let us see that α is a differentiable map. Take V ∈ V −1 and σ a local section around V, σ : W → πR (V ) with V ∈ W ⊂ V . If we  −1 N  define β : πR (V ) → F by β ((F, H )) = θ ((F, H )) , β is a differentiable map and it is clear that α |W = β ◦ σ . Hence α is differentiable as claimed. Now, the differentiability of ϕ follows easily.  → H ) ∈ R(r , s)/ and  σ :W Let us see now that ϕ −1 is differentiable. Take (F,  R(r , s) a local section around (F, H ) of the submersion π : R(r , s) −→ R(r , s)/. Let ψ : R(r , s) −→ R be the differentiable map defined by ψ(F, H ) = (F, H ). σ = ϕ −1 |W Then πR ◦ ψ ◦  &:

ψ R(r , s) −→  σ ↑  W

R ↓ πR

ϕ −1 −→ Jnv(r , s)

Hence ϕ −1 is differentiable as claimed.

 

Let Invn−d (B ∗ , A∗ ) be the set of (B ∗ , A∗ )-conditioned invariant subspaces of codimension d, and set Invn−d (B ∗ , A∗ ; S) = {V ∈ Inv(B ∗ , A∗ ); V ⊂ S}.

123

84

I. Baragaña et al.

' ∗ ∗ Then, one has Invn−d (B ∗ , A∗ ) = s Inv(r , s) and Invn−d (B , A ; S) = ' s Inv(r , s; S) where Inv(r , s; S) = {V ∈ Inv(r , s); V ⊂ S} and s runs over the partitions of n − d compatible with r . The following theorem is proved in [28]. Theorem 8.9 Inv(r , s; S) is a submanifold of Inv(r , s). If we write Jnv(r , s; L) = {V ∈ Jnv(r , s); [L] ⊂ V}, the diffeomorphism between Grn−d (Fn ) and Grd (Fn ) defined by V → V ⊥ induces a bijection ⊥ : Inv(r , s; [L]⊥ ) −→ Jnv(r , s; L) Likewise the diffeomorphism ϕ in (15) induces a bijection  : Jnv(r , s; L) → R(r , s; L)/

(27)

Proposition 8.10 If we provide Jnv(r , s; L) and R(r , s; L)/ with the differentiable structure induced by ⊥ and , respectively, then Jnv(r , s; L) is a submanifold of Jnv(r , s) and R(r , s; L)/ is a submanifold of R(r , s)/. Recall the definition of L i , i = 1, . . . , k and N given in (17) and (25), respectively. Theorem 8.11 If R(r , s; L) = ∅ then R(r , s; L) is a submanifold of R(r , s) and dim R(r , s; L) = dim R(r , s) − N . Proof Taking into account that the projection π : R(r , s) −→ R(r , s)/ is a submersion and that R(r , s; L)/ is a submanifold of R(r , s)/ (Proposition 8.10) we conclude that R(r , s; L) = π −1 (R(r , s; L)/) is a submanifold of R(r , s) and dim R(r , s; L) = dim R(r , s; L)/ + dim R(r , s) − dim R(r , s)/. But dim R(r , s; L)/ = dim Jnv(r , s; L) = dim Inv(r , s; [L]⊥ ) = dim Inv(r , s; Ker L ∗ ). It was proved in [28, Prop. 6.2] that (notice that we have inverted the usual order for the partitions r and s) ( k ) k       ∗ dim Inv(r , s; Ker L ) = (s j − s j+1 ) (ri+ j−1 − si+ j−1 ) − rank H j (L ) , ∗

j=1

123

i=1

On the geometry of the generalized partial realization problem

85

where r j = rk− j+1 , s j = sk− j+1 , 0 ≤ j ≤ k and, for 1 ≤ j ≤ k, ⎡

L ∗k1

⎢ L ∗k−1,1 ⎢ H j (L ∗ ) = ⎢ .. ⎣ . L ∗k− j+1,1

. . . L ∗k,k− j+1 L ∗k−1,1 . . . L ∗k−1,k− j+1 L ∗k−2,1 .. .. .. . . . . . . L ∗k− j+1,k− j+1 L ∗k− j+1,1

. . . L ∗k−1,k− j . . . L ∗k−2,k− j .. .. . . . . . L ∗k− j+1,k− j

⎤ . . . L ∗j,1 . . . L ∗j−1,1 ⎥ ⎥ .. .. ⎥ . . . ⎦ ∗ . . . L 1,1

We have that rank H j (L ∗ ) = rank L k− j+1 , 1 ≤ j ≤ k, and so dim Inv(r , s; Ker L ∗ ) =

j k   (s j − s j−1 )( qi − rank L j ). j=1

i=1

Therefore, taking into account that dim R(r , s)/ =

k  (s j − s j−1 )(q1 + · · · + q j ) j=1

 

the theorem follows.

One could proceed exactly in the opposite direction in order to provide Jnv(r , s; L) with a differentiable structure out of that obtained in Section 7 for R(r , s; L). In fact, with the differentiable structure of Theorem 7.4 in R(r , s; L) we could provide R(r , s; L)/ with a differentiable structure through a coordinate atlas as in Section 6, and then use bijection  in (27). 9 The classical partial realization problem In this section we apply the results of Sect. 7 (or 8) to the classical partial realization problem. Recall (see Sect. 1) that this problem corresponds to the case when r1 = · · · = rk = m. Thus we assume that a sequence of matrices L = (L 1 , . . . , L k ) with L i ∈ Fm×δ , all of the same size is given and form the matrix ⎡

⎤ L1 ⎢L 2⎥ ⎢ ⎥ L = ⎢ . ⎥ ∈ Fn×δ , ⎣ .. ⎦ Lk with n = km.

123

86

I. Baragaña et al.

As already said, we take r1 = · · · = rk = m. Thus ⎡ ⎢ ⎢ (F, H ) = ⎢ ⎣

H HF .. .

⎤ ⎥ ⎥ ⎥. ⎦

H F k−1 and i (F, H ) = H F i−1 . Hence (F, H ) ∈ R(r , s) if and only if ⎡ ⎤ ⎤ H 1 (F, H ) ⎢ HF ⎥ ⎢ ⎥ ⎥ ⎢ .. q1 + · · · + qi = rank ⎣ = rank ⎢ .. ⎥ , 1 ≤ i ≤ k. ⎦ . ⎣ . ⎦ i (F, H ) H F i−1 ⎡

So R(r , s) is the set of observable pairs (F, H ) ∈ d,m with Brunovsky indices

q = (q1 , . . . , qk ), q1 ≥ · · · ≥ qk ,

k 

qi = d.

i=1

We will denote this set by d,m (q). First, according to Theorem 5.6, d,m (q) is a submanifold of Fd×d × Fm×d and

dim d,m (q) = d(m + d) − ( = d 2 +m d −

k−1  i=1 k−1  i=1

si qi+1 = d(m + d) − ) qi+1 +

k−1  (m − qi )qi+1 i=1

k−1 

qi qi+1 = d 2 +

i=1

k−1 

qi qi+1 , (q0 =: m).

i=0

The set of the usual partial realizations of L = (L 1 , . . . , L k ) can be identified with the set R(L) = {(F, H ) ∈ d,m ; L i = H F i−1 M, 1 ≤ i ≤ k for some M ∈ Fd×δ }. We denote R(r , s; L) = R(L) ∩ d,m (q) by d,m (q; L). Then

dim d,m (q; L) = dim d,m (q) −

k−1  i=0

123

(qi − qi+1 ) rank L i+1

On the geometry of the generalized partial realization problem

87

where ⎡

L1 L2 ⎢L 2 L 3 ⎢ Li = ⎢ . .. ⎣ .. . L i L i+1

⎤ · · · L k−i+1 · · · L k−i+2 ⎥ ⎥ im×(k−i+1)δ , 1 ≤ i ≤ k. .. ⎥ ∈ F .. ⎦ . . · · · Lk

By Proposition 7.2, if d,m (q; L) = ∅ then rank L i ≤ q1 + · · · + qi , 1 ≤ i ≤ k. In particular, if m = 1, i. e. ⎤ L1 ⎢L2⎥ ⎢ ⎥ L = ⎢ . ⎥ ∈ Fn×δ , ⎣ .. ⎦ ⎡

L i ∈ F1×δ ,

Ln we have that k = n, s1 = · · · = sd = 0, sd+1 = · · · = sn = 1, q1 = · · · = qd = 1, qd+1 = · · · = qn = 0, d,1 (q) = d,1 and d,1 (q; L) = R(L). Notice that, if δ = m = 1 then we deal with Problem 2 of [5]. For 1 ≤ δ ≤ d, dim d,1 = d + 2

n−1 

qi qi+1 = d 2 + d.

i=0

If d = n then dim R(L) = dim d,1 = d 2 + d. If d < n then dim R(L) = dim d,1 − rank L d+1 = d 2 + d − rank L d+1 where ⎡ ⎢ ⎢ L d+1 = ⎢ ⎣

L1 L2 .. . L d+1

⎤ L 2 · · · L n−d L 3 · · · L n−d+1 ⎥ ⎥ (d+1)×(n−d)δ . .. . . .. ⎥ ∈ F . . . ⎦ L d+2 · · · L n

123

88

I. Baragaña et al.

Observe that, by Proposition 7.2, R(L) = ∅ if and only if ⎡

rank L d+1

L1 L2 ⎢L2 L3 ⎢ = rank ⎢ . .. ⎣ .. . L d L d+1

⎤ · · · L n−d · · · L n−d+1 ⎥ ⎥ .. ⎥ . .. . . ⎦ · · · L n−1

⎡ ⎤ 1 ⎢1⎥ ⎢ ⎥ 5×1 ⎥ Example 9.1 (see Example 5.1 of [1]) Let L = ⎢ ⎢1⎥ ∈ F . Then, ⎣2⎦ 1   L1 = 1 1 1 2 1 , ⎡

1 ⎢ 1 L4 = ⎢ ⎣1 2

⎤ 1 1⎥ ⎥, 2⎦ 1

 L2 =



1112 , 1121

⎡

⎤ 111 L 3 = ⎣1 1 2⎦ , 121

L5 = L .

  rank L 1 = 1, rank L 2 = 2 > rank 1 1 1 2 , ⎡  1 111 3 4 , rank L = 2 = rank ⎣1 rank L = 3 > rank 112 1

⎤ 1 1⎦ . 2

Thus R(L) = ∅ if and only if d ≥ 3. • If d = 3, then dim R(L) = 12 − rank L 4 = 10. • If d = 4, then dim R(L) = 20 − rank L 5 = 19. • If d = 5, then dim R(L) = 30. References 1. Antoulas AC (1983) New results on the algebraic theory of linear systems: the solution of the cover problem. Linear Algebra Appl 50:1–43 2. Baragaña I, Zaballa I (1995) Block similarity invariants of restrictions to (A, B)-invariant subspaces. Linear Algebra Appl 220:31–62 3. Basile G, Marro G (1992) Controlled and conditioned invariants in linear system theory. Prentice-Hall, Englewood Cliffs 4. Bosgra OH (1983) On parametrizations for the minimal partial realization problem. Syst Control Lett 3:181–187 5. Brockett RW (1978) The geometry of the partial realization problem. In: Proceedings of the 17th IEEE conference on decision and control. San Diego, CA, pp 1048–1052 6. Brunovsky P (1970) Classification of linear controllable systems. Kybernetica (Praga) 3(6):173–188 7. Compta A, Ferrer J (1997) On (A, B)t -invariant subspaces having extensible Brunovsky bases. Linear Algebra Appl 255:185–201

123

On the geometry of the generalized partial realization problem

89

8. Ferrer J, Puerta F, Puerta X (1998) Differentiable structure of the set of controllable (A, B)t -invariant subspaces. Linear Algebra Appl 275–276:161–177 9. Fuhrmann PA, Helmke U (1997) A homeomorphism between observable pairs and conditioned invariant subspaces. Syste Control Lett 30:217–223 10. Fuhrmann PA, Helmke U (1999) On the parametrization of conditioned invariant subspaces. In: Advances in Mathematical Systems Theory, Workshop in honor of D. Hinrichsen’s 60th birthday, 20–23 April 1999, Borkum Island 11. Fuhrmann PA, Helmke U (2001) On the parametrization of conditioned invariant subspaces and observer theory. Lin Algebra Appl 332–334:265–353 12. Gohberg I, Kaashoek MA, Lerer L (1991) A directional partial realization problem. Syst Control Lett 17:305–314 13. Gohberg I, Lancaster P, Rodman L (1986) Invariant subspaces of matrices with applications. Wiley, New York 14. Gohberg I, Kaashoek MA, van Schagen F (1980) Similarity of operator blocks and canpnical forms. I. General results, feedback equivalence and Kronecker indices. Integr Equ Oper Theory 3:359–396 15. Gohberg I, Kaashoek MA, van Schagen F (1995) Partially specified matrices and operators: classfication, completion, applications. Birkh˘auser, Basel 16. Gragg WB, Lindquist A (1983) On the partial realization problem. Linear Algebra Appl 50:277–319 17. Guillemin V, Pollack A (1974) Differential topology. Prentice-Hall, Englewood Cliffs 18. Helmke UU (1993) The Cohomology of moduli spaces of linear dynamical systems. In: Regensburger Mathematische Schriften, vol 24, Department of Mathematics 19. Hinrichsen D, Manthey W, Helmke U (2001) Minimal partial realization by descriptor systems. Linear Algebra Appl 326:45–84 20. Kailath T (1980) Linear systems. Prentice-Hall, New Jersey 21. Kalman RE (1976) Realization theory of linear dynamical systems. In: Control theory and topics in functional analysis. II. I.A.E.A., Vienna, pp 235–256 22. Kalman RE (1979) On partial realizations, transfer functions and canonical forms. Acta Polytech Scand Math Comput Sci Ser 31:9–32 23. Kuijper M (1997) An algorithm for constructing a minimal partial realization in the multivariable case. Syst Control Lett 31:225–233 24. Lee JM (2003) Introduction to smooth manifolds. Springer, New York 25. Manthey W, Helmke U, Hinrichsen D (1992) Topological aspects of the partial realization problem. Math Control Signal Syst 5:117–149 26. Puerta F, Puerta X (2002) On the geometry of the set of controllability subspaces of a pair (A, B). Linear Algebra Appl 351–352:585–599 27. Puerta F, Puerta X, Zaballa I (2001) A coordinate atlas of the manifold of observable conditioned invariant subspaces. Int J Control 74(12):1226–1238 28. Puerta F, Puerta X, Zaballa I (2006) On the geometry of the solutions of the cover problem. SIAM J Control Optim 45(2):389–413 29. Sontag ED (1990) Mathematical control theory. Springer, New York 30. Trumpf J (2002) On the geometry and parametrization of almost invariant subspaces and observer theory. Ph.D. thesis, Universität Würzburg 31. Willems JC (1980) Almost A mod B-invariant susbspaces. Asterisque 75–76:239–248 32. Woerdeman HJ (1989) Minimal competions for block matrices. Linear Algebra Appl 121:105–122 33. Wonham WM (1985) Linear multivariable control. A geometric approach. Springer, New York 34. Zazworsky RM, Jensen D, Baker WP (1979) The set of all minimal partial realizations. IEEE Trans Automat Control 24(6):966–970

123