Finite dimensional interconnections and stabilization of 2D behaviors

Finite dimensional interconnections and stabilization of 2D behaviors Diego Napp and Paula Rocha Abstract— This paper deals with discrete two-dimensional behaviors which are described by linear systems of partial difference equations with constant coefficients. Within the behavioral framework a natural concept of interconnection has been introduced by J.C.Willems, called regular interconnection. We investigate regular interconnections that yield finite dimensional behaviors, and prove that when a finite dimensional behavior can be achieved from a given behavior Bby regular interconnection then the controllable part of Bis rectifiable. We apply this result to characterize all stabilizable behaviors. I. INTRODUCTION As is well known, the central idea in the behavioral approach to control is the one of interconnection. This consists in the interconnection of a given behavior to be controlled B (the plant) with a suitable behavior (the controller), in order to obtain a desired behavior Bd. If this is possible, we say that Bdis implementable from B. In this paper we focus on a particular kind of interconnection that is called regular interconnection. In such interconnection, the restrictions imposed on the plant by the controller are independent of the restrictions already present in the plant, as happens, for instance, in a feedback interconnection (see [6]). More concretely, we are interested in studying regular interconnections that yield finite dimensional behaviors, i.e., we wish to characterize the behaviors from which a finite dimensional behavior is implementable by regular interconnection. This can be seen as a relaxation of the control objective of implementing the zero behavior by regular interconnection from a given behavior B, a problem that has already been addressed in [8]. In this sense, regular implementability of a finite dimensional behavior can be regarded as almost regular implementability of zero. On the other hand our problem is related with the stabilization of 2D behaviors. Indeed the classical stabilization problem can be reformulated in terms of interconnections as the search for a controller behavior whose interconnection with the given behavior yields a stable one. In this context, a behavior that admits a stabilizing controller is said to be stabilizable. Using a notion of stability defined with respect to a specified stability region by adapting the ideas in [5] to the discrete case, it was recently proven, in [7], that the stable behaviors considered there have the property of being finite dimensional linear subspaces of (Rq)Z2 .Thus, the possibility of stabilizing a behavior Bis strictly connected with the Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal. [email protected], [email protected] regular implementation of a finite dimensional behavior from B. A complete characterization of the stabilization property was given in [7] under the assumption that the controllable part of the given behavior B, denoted by Bc, is rectifiable, i.e., is a direct summand of (Rq)Z2. This is a very strong property and allows to derive several results that are in general only valid for the one dimensional case (1D), such as, for instance the existence of a decomposition of the behavior into the direct sum of its controllable part and an autonomous part. However, in this paper we prove that if a finite dimensional behavior is implementable by regular interconnection from a given behavior B, then Bcis rectifiable. As a consequence of this result we conclude that the assumption about the rectifiability of Bc, used in [8] in order to obtain several results on stabilization, is indeed not restrictive since it is a necessary condition for stabilization. The outline of the paper is as follows. We begin by introducing some necessary background from the field of 2D discrete behavioral theory. Most of this material is standard, centering around concepts such as autonomy, controllability and rectifiability. Section 3 is devoted to an exposition of regular interconnection and finite dimensional behaviors. Finally, in Section 4 we introduce the notions of stable and stabilizable behavior and obtain a characterization of all stabilizable behaviors. II. PRELIMINARIES In order to state more precisely the questions to be considered, we introduce some preliminary notions and results. We consider 2D behaviors Bdefined over Z2that can be described by a set of linear partial difference equations, i.e., B= ker R(σ, σ−1) := {w∈ U | R(σ, σ−1)w≡0}, where Uis the trajectory universe, here taken to be (Rq)Z2, σ= (σ1, σ2),σ−1= (σ−1 1, σ−1 2), the σi’s are the elementary 2D shift operators (defined by σiw(k) = w(k+ei), for k∈Z2, where eiis the ith element of the canonical basis of Z2) and R(s, s−1)is a 2D Laurent-polynomial matrix known as representation of B. Since there is no ambiguity, we will sometimes drop the reference to the variables (s, s−1)and write, for instance, Rfor R(s, s−1). Instead of characterizing Bby means of a representation matrix R, it is also possible to characterize it by means of its orthogonal module Mod(B), which consists of all the 2D Laurent-polynomial rows r(s, s−1)∈R1×q[s, s−1]such that B⊂ker r(σ, σ−1), and can be shown to coincide with the R[s, s−1]-module RM(R)generated by the rows of R, i.e., Mod(B) = RM(R(s, s−1)) and therefore there is a one-to-one correspondence between Band Mod(B). It turns out that sums and intersections of behaviors can be formulated in terms of the corresponding modules. Theorem 1: [13, pag.1074] Let B1and B2be two 2D behaviors. Then, B1+B2and B1∩B2are also 2D behaviors and 1) Mod(B1+B2) = Mod(B1)∩Mod(B2) 2) Mod(B1∩B2) = Mod(B1) + Mod(B2) The notions of controllability and autonomy play an important role in the sequel. Definition 2: A behavior B⊂(Rq)Z2is said to be controllable if for all w1,w2∈Bthere exits δ > 0such that for all subsets U1,U2⊂Z2with d(U1, U2)> δ, there exists aw∈Bsuch that w|U1=w1|U1and w|U2=w2|U2. It was shown (see [10]) that this is equivalently to say that R1×q[s, s−1]/Mod(B)is a torsion free R[s, s−1]-module. On the other hand, we say that a behavior is autonomous if it has no free variables (or inputs). B= ker R(σ, σ−1)is autonomous if and only if R(s, s−1)has full column rank (over R[s, s−1]), [11]. In the 1D case, all autonomous behaviors are finitedimensional vector spaces. For general multidimensional variable behaviors this is no longer true. In fact, an autonomous multidimensional behavior that is finitedimensional is called strongly autonomous in [5]. In order to characterize strong controllability we recall the definition of zero of a Laurent-polynomial matrix. Given a 2D Laurent-polynomial matrix R(s, s−1)with full column rank, a zero of Ris defined as λ∈(C\ {0})2such that rank R(λ, λ−1)<rank R(s, s−1), where, the first rank is taken over Cand the second one over R[s, s−1]. Theorem 3: (see [4, Th.17, Th.28] [11, Cor.1 pag. 141]) Let B= ker Rbe a 2D behavior. Then the following are equivalent. 1) Bhas finite dimension, 2) R1×q[s, s−1]/Mod(B)has finite dimension, 3) for all i= 1,2there exists a non-zero polynomial pi(σi)∈R[si, s−1 i]such that pi·(R1×q[s, s−1]/Mod(B)) = 0, 4) Rhas full column rank and Bhas a finite number of zeros. As also shown in [11], every 2D behavior Bcan be decomposed into a sum B=Bc+Ba, where Bcis the controllable part of B(defined as the largest controllable sub-behavior of B) and Bais a (non-unique) autonomous sub-behavior said to be an autonomous part of B. Remark 4: It is important to remark that if B= ker R and Bc= ker Rcthen the rank of Rand the rank of Rc must coincide. Indeed, by [3, Th. 2.69] the number of free variables (inputs) in a behavior B= ker R∈(Rq)Z2is given by q-rank R. On the other hand by [8, Cor. 2.10], Band Bc must have the same number of inputs. If the controllable-autonomous decomposition happens to be a direct sum decomposition, i.e., if B=Bc⊕Ba, we say that the autonomous part of Bais an autonomous direct summand of B. An interesting case is when the controllable part Bcis rectifiable. A 2D behavior B= ker R(σ, σ−1)⊂(Rq)Z2is said to be rectifiable if there exists an invertible operator U(σ, σ−1), where U(s, s−1)is a 2D Laurent-polynomial matrix, such that U(σ, σ−1)(B) := {Uw |w∈B}={v|RU−1v= 0} is equal to ker[Il0], where Ilis the l×lidentity matrix, for some l∈ {1, . . . , q}. The following theorem shows several characterizations of rectifiable behaviors that have been appeared in several papers. Theorem 5: (see [8, Lemma 2.12] and [12, Th. 9 and Th. 10, page 819]) Let B= ker Rbe a behavior. Then the following are equivalent. 1) Bis rectifiable, 2) Ris zero left prime (ZLP), 3) Bis direct summand of (Rq)Z2, 4) R1×q[s, s−1]/Mod(B)is free. When a rectifying operator exists, it is possible to take advantage of the simplified form of the rectified behaviors in order to derive various results. In particular, it is not difficult to obtain the next proposition. Proposition 6: Let B= ker R(σ, σ−1)⊂(Rq)Z2be a 2D behavior with rectifiable controllable part Bcand U(σ, σ−1)be a corresponding rectifying operator such that U(σ, σ−1)(Bc) = ker[Il0]. Then the following are equivalent. 1) B=Bc⊕Ba 2) Ba= ker  P0 X Iq−lU, with P(s, s−1)such that RU−1= [P0] and X(s, s−1)an arbitrary Laurent-polynomial matrix of suitable size. Note that the behaviors Baof Proposition 6 always exist and are autonomous. Thus, this result states that every behavior with rectifiable controllable part has autonomous direct summands and, moreover, gives a parametrization for all such summands. This yields the following parametrization of U(B). Corollary 7: Let B= ker R(σ, σ−1)⊂(Rq)Z2be a 2D behavior with rectifiable controllable part Bcand U(σ, σ−1)be a corresponding rectifying operator such that U(σ, σ−1)(Bc) = ker[Il0]. Then U(B) = 0 (Rq−l)Z2⊕Il Yker P, with P(s, s−1)such that RU−1= [P0] and Y(s, s−1)an arbitrary Laurent-polynomial matrix of suitable size. Example 8: Let Bbe a 2D behavior represented by B= ker s1−1s1s2 2−s2 2−1 + s1s1s2−s2 0s1+s2−s1−s2. Choose the unimodular matrix U−1=  1−s2 2−1−s2 2−s2−1 0 1 1 0 0 1   in order to obtain U(Bc) = ker RcU−1= ker 100 010 and U(B)=  0 0 (R)Z2 ⊕  1 0 0 1 y1y2  ker s1−1 0 0s1+s2 where y1, y2are arbitrary Laurent-polynomials. III. CONTROL,REGULAR INTERCONNECTIONS AND Bc Given two behaviors B1and B2their interconnection is defined as the intersection B1∩B2. This interconnection is said to be regular if Mod(B1)∩Mod(B2) = {0}. Regular interconnections correspond to a lack of overlapping between the laws of the interconnected behaviors and play an important role in behavioral control, [9], [13], [6], [1]. The following result can be found in, for instance, [8, Lemma 3, pag 115]. Lemma 9: Given the two behaviors B1= ker R1and B2= ker R2, the following are equivalent. 1) B1∩B2is a regular interconnection, 2) B1+B2= (Rq)Z2, 3) rank R1+ rank R2= rank R1 R2 Thus in a regular interconnection, the controller imposes restrictions which are not already present in the plant. In this sense a feedback controller is a simple example of a regular interconnection where the controller imposes restrictions only on the plant input, which in the plant is unrestricted. Example 10: Let B1a behavior represented by B1= ker s1s1s20 s1+s20 1  and B2= ker 101be two behaviors. Then the interconnection of B1and B2is regular, i.e., Mod(B1)∩ Mod(B2) = {(0,0,0)}. Based on the notion of behavior interconnection it is possible to formulate a control problem in set theoretic terms. Indeed, if Bis the behavior of the system to be controlled (the plant) and Kis the set of all signals compatible with the additional restrictions to be imposed on w, i.e., the controller, then the resulting controlled behavior is given by the interconnection B∩ K (1) of the behaviors Band K. Thus, in the behavioral setting, a control problem consists in, given a desired controlled behavior Bd, finding a controller Ksuch that its interconnection (1) with the plant behavior Bresults in Bd. In case this interconnection is regular, the controller is called a regular controller and the desired behavior Bdis said to be achievable or implementable by regular interconnection. The following necessary condition for implementation by regular interconnection has been derived in [8, Th. 4.5, pag 124]. Theorem 11: Let Band Bdbe two behaviors. Then if Bdis implementable by regular interconnection from Bthen B=Bc+Bd. Based on the result it is possible to show the next Lemma. Lemma 12: Let Band Kbe two 2D behaviors. If the intersection of Band Kis regular then is also the interconnection between Bcand K. Proof: Let B∩ K =Bdwith regular interconnection, i.e. Mod(B)⊕Mod (K) = Mod(Bd). Using Theorem 11 we have that B=Bc+Bdor equivalently Mod(B) = Mod(Bc)∩Mod(Bd) = Mod(Bc)∩(Mod(B)⊕Mod(K)). Since Mod(B)∩Mod(K) = {0}and Mod(Bc)∩Mod(K)⊂ Mod(B)we obtain that Mod(Bc)∩Mod(K) = {0} Example 13: Let Band Kas in Example 10. It is easy to see that Bc= ker 1s20 s1+s20 1 . As expected from Lemma 12, we have that Mod(Bc)∩ Mod(K) = 0 i.e. the interconnection with the controllable part is also regular. Lemma 12 shows that the controllable part of a behavior plays an important role in the context of regular interconnections. Since a controller which does not interconnect with Bcin a regular way, is not a regular controller. Moreover, the following two lemmas, which hold only for the 2D case, will be used to show that the controllable part of Bmust be rectifiable if a strongly controllable (finite dimensional) behavior can be implemented from Bby regular interconnection. Lemma 14: (see [2, Th.12]) Let Bbe a behavior. Then there exists a unique (up to isomorphism) free R[s, s−1]-module Mod(B)+⊂R1×q[s, s−1]such that Mod(B)+/Mod(B)has finite dimension. Note that Mod(B)+is the smallest free module containing Mod(B)and its computation can be effectively implemented, see [2] Lemma 15: (see [2, Cor.23]) Let Bbe a behavior and Bd⊂Bbe a sub-behavior. Then there exists Bcsuch that (B∩Bc)/Bdhas finite dimension if and only if Mod(B)+ is direct summand of Mod(Bd)+. Theorem 16: Let Bbe a behavior. If there exists a controller behavior Ksuch that Bfd =B∩ K is finite dimensional (strongly autonomous) and the interconnection is regular then Bcis rectifiable. Proof: Applying Lemma 15 with Bd= 0 one obtains that Mod(B)+is direct summand of Mod(0)+=R1×q[s, s−1]. Define B+as the unique behavior such that Mod(B)+= Mod(B+). By Theorem 1, Bis direct summand of R1×q[s, s−1]. Thus, by Theorem 5, B+is a rectifiable behavior and therefore also controllable. We have that for the 2D case Mod(Bc)is free (see [3, Th.7.42]) and since Mod(B)+is the largest free module containing Mod(B)we have that Bc⊂B⊂B. Further Bcis the largest controllable sub-behavior which implies B+⊂Bcand therefore Bc=B+is rectifiable.  Remark 17: Note that, according to [8], rectifiability is equivalent to the possibility of obtaining the zero behavior by regular interconnection. Therefore, the possibility of obtaining a finite dimensional behavior by regular interconnection from Bcan be regarded as almost regular interconnection to zero, since it represents the implementation of the zero behavior up to a finite dimensional one. Equivalently, by Theorem 16 and Corollary 7, the regular implementation of a finite dimensional behavior can also be seen as almost rectificability since Bcan be written as B=Bc⊕Bfd where Bfd is a finite dimensional behavior and Bcis rectifiable, i.e., Bcoincides with a rectifiable behavior up to a finite dimensional one. IV. STABILITY AND STABILIZABILITY A discrete 1D behavior B⊂(Rq)Zis said to be stable if all its trajectories tend to the origin as time goes to infinity. In the 2D case, we shall define stability with respect to a specified stability region, as in [7] by adapting the ideas in [5] to the discrete case. For this purpose we identify a direction in Z2with an element d= (d1, d2)∈Z2whose components are coprime integers, and define a stability cone in Z2as the set of all positive integer linear combinations of 2linearly independent directions. Given a stability cone S⊂Z2, a trajectory w∈(Rq)Z2is said to be S-stable if it tends to zero along every half line in S. By a half-line associated with a direction d∈Z2we mean the set of all points of the form αd where αis a nonnegative integer; clearly, the half-lines in a stability cone Sare the ones associated with the directions d∈S. A behavior Bis S-stable if all its trajectories are S-stable. It turns out that stable behaviors on (Rp)Z2must be finite dimensional. Lemma 18: ([7, Lemma 2]) Every 2D behavior B⊂ (Rq)Z2which is stable with respect to some stability cone Sis a finite dimensional linear subspace of the trajectory universe, (Rq)Z2. In order to characterize stability, we introduce some preliminary notation. Given two elements λ= (λ1, λ2)∈C2and k= (k1, k2)∈Z2, we define λk:= λk1 1λk2 2. Now, let Bbe an autonomous behavior. Since the set of zeros of the different representations of Bcoincide, we may define the set N(B)of zeros of the behavior Bas the set of zeros of any of its kernel representations. As pointed out in Theorem 3, Bis finite dimensional if and only of N(B)is a finite set. In the sequel, whenever we refer to N(B)we implicitly suppose that Bis autonomous. Theorem 19: ([7, Th. 8]) Let B⊂(Rq)Z2be a behavior, and let Sbe a stability cone. The the following are equivalent: 1) Bis S-stable 2) N(B)is finite and for every zero λ∈ N(B)and every direction d∈S, |λd|<1. If we call λ∈C2is S-stable if for every direction d∈S, |λd|<1, Theorem 19 can be rephrased as: Bis S-stable if and only if it has a finite number of zeros and these zeros are S-stable. This is of crucial importance for the study of stability and stabilizability. As for stabilization, our definition of S-stabilizability is similar to the one proposed in [5], but has the extra requirement of regularity. Definition 20: Given a stability cone S⊂Z2, we say that a behavior B⊂(Rq)Z2is S-stabilizable if there exists an S-stable sub-behavior Bs⊂Bthat is achievable from B by regular interconnection. The following theorem provides a characterization of all stabilizable behaviors. Theorem 21: Let B= ker R(σ, σ−1)⊂(Rq)Z2be a behavior and S⊂Z2be a stability cone. Then the following statements are equivalent. 1) Bis S-stabilizable 2) Bcis rectifiable and if Uis a rectifiable operator such that RU = [P0] then ker P(σ, σ−1)is S-stable. 3) Bcis rectifiable and every autonomous direct summand of Bis stable. Proof: 1⇒2: Assume that Bis S-stabilizable. Then, by Lemma 18 and Theorem 16, Bcis rectifiable. If B= ker R= ker PRcwith Rcsuch that Bc= ker Rcand U is a rectifying operator for Bcthen PRc=P(I0)U, U(B) = ker(P0) and U(Bc) = ker(I0). If K= ker(K1K2)Uis a controller behavior such that its interconnection with Bis regular and yields an autonomous behavior then, by Lemma 9, rank P0 K1K2= rank (P0) + rank (K1K2). On the other hand, Pmust have full column rank (by remark 4) as well as K2(otherwise U(B∩ K) = ker P0 K1K2would not be full column rank) and therefore we have that rank P0 K1K2= rank P+ rank K2. Thus rank K2= rank (K1K2). In particular this implies that for all λ∈C2 K1(λ, λ−1) = K2(λ, λ−1)·Lλ for some matrix Lλwith complex entries. Assume now that Pis not stable. Then rank P(λ∗,(λ∗)−1)<rank P(σ, σ−1) =: `for some λ∗ such that |λ∗d|≮1and some d∈S. Hence M: = P(λ∗,(λ∗)−1) 0 K1(λ∗,(λ∗)−1)K2(λ∗,(λ∗)−1) =P(λ∗,(λ∗)−1) 0 K2(λ∗,(λ∗)−1)·LλK2(λ∗,(λ∗)−1) =P(λ∗,(λ∗)−1) 0 0K2(λ∗,(λ∗)−1) I0 LλI and since rank P(λ∗,(λ∗)−1)< ` it follows that rank M < `, implying that U(B∩ K)and hence B∩ K is not stable. In this way, we conclude that if Bis S-stabilizable then Pmust be stable, i.e., 1⇒2. 2⇒1: Because we can take Ksuch that U(K) = ker(0 I). 2⇒3: According to [7, Proposition 1] the autonomous direct summands B∗of B(in the case Bcis rectifiable) are such that U(B∗) = ker P0 X I with Pas before, and Xan arbitrary L-polynomial matrix of suitable size. Thus if Pis stable so are all the autonomous direct summands of B. 3⇒2: Obvious, taking into account the form of the autonomous direct summands of B.  We conclude this paper giving two easy examples. Example 22: Let Bbe the behavior considered in Example 8. Then U(B)a=  1 0 0 1 y1y2  ker s1−1 0 0s1+s2 where y1, y2are arbitrary Laurent-polynomials. Since U(B)ais not finite dimensional then Bais not finite dimensional and therefore not stable (with respect to any stability cone). Hence we have that Bis not stabilizable since not every autonomous direct summand of Bis stable. Example 23: Let a behavior Bbe represented by B= ker Rand Sthe positive orthant, where R=    0 1 0 0 s1s2 20 0 0 s1−2 2s1−s2 1s1−1 20 0s1−s3 2s2−1 40     . Clearly, another representation of Bis B= ker     0 1 0 0 1 0 0 0 0 0 s1−1 20 0 0 s2−1 40     . Further, Bc= ker   1000 0100 0010   is rectifiable. Hence, Bis stabilizable since B= ker(P0) with ker P= ker     0 1 0 1 0 0 0 0 s1−1 2 0 0 s2−1 4     a stable behavior. V. ACKNOWLEDGMENTS The authors gratefully acknowledge that this work was supported by Fundação para a Ciência e Tecnologia (FCT). REFERENCES [1] A.A. Julius, J.C. Willems, M.N. Belur, and H.L. Trentelman. The canonical controllers and regular interconnection. Systems Control Lett., 54(8):787–797, 2005. [2] D. Napp Avelli. Almost direct sum decomposition and implementation of 2D behaviors. Math. Control Signals Systems, 21(1):1–19, 2009. [3] U. Oberst. Multidimensional constant linear systems. Acta Appl. Math., 20(1-2):1–175, 1990. [4] U. Oberst. Finite-dimensional systems of partial differential or difference equations. Adv. in Appl. Math., 17(3):337–356, 1996. [5] H. Pillai and S. Shankar. A behavioral approach to control of distributed systems. SIAM J. Control Optim., 37(2):388–408, 1998. [6] P. Rocha. Feedback control of multidimensional behaviors. Systems & Control Letters, 45:207–215, 2002. [7] P Rocha. Stabilization of multidimensional behaviors. in Multidimens. Systems Signal Process., 19:pp. 273–286, 2008. [8] P. Rocha and J. Wood. Trajectory control and interconnection of 1D and nD systems. SIAM J. Control Optim., 40(1):107–134, 2001. [9] J.C. Willems. On interconnections, control, and feedback. IEEE Trans. Automat. Control, 42(3):326–339, 1997. [10] J. Wood, E. Rogers, and D.H. Owens. Controllable and autonomous nDlinear systems. Multidimens. Systems Signal Process., 10(1):33– 69, 1999. [11] E. Zerz. Primeness of multivariate polynomial matrices. Systems Control Lett., 29(3):139–145, 1996. [12] E. Zerz. Multidimensional behaviours: an algebraic approach to control theory for PDE. Internat. J. Control, 77(9):812–820, 2004. [13] E. Zerz and V. Lomadze. A constructive solution to interconnection and decomposition problems with multidimensional behaviors. SIAM J. Control Optim., 40(4):1072–1086, 2001/02.