Victor Gosea
email: gosea@mpi-magdeburg.mpg.de.

Mihaly Petreczky
email: mihaly.petreczky@ec-lille.fr.

Christophe Fiter
email: christophe.fiter@univ-lille1.fr.

Athanasios C Antoulas

) Ion

Balanced truncation for linear switched systems

Keywords: 93A15, 93A30, 93B11, 93C05, 93C10 1 Introduction

We propose a model order reduction approach for balanced truncation of linear switched systems. Such systems switch among a finite number of linear subsystems or modes.

We compute pairs of controllability and observability Gramians corresponding to each active discrete mode by solving systems of coupled Lyapunov equations. Depending on the type, each such Gramian corresponds to the energy associated to all possible switching scenarios that start or, respectively end, in a particular operational mode.

In order to guarantee that hard to control and hard to observe states are simultaneously eliminated, we construct a transformed system, whose Gramians are equal and diagonal. Then, by truncation, directly construct reduced order models. One can show that these models preserve some properties of the original model, such as stability and that it is possible to obtain error bounds relating the observed output, the control input and the entries of the diagonal Gramians.

cope with it, inclusion of more detail at the modeling stage is required, which inevitably leads to analyzing larger-scale, more complex dynamical systems. Such high dimensional systems are often linked to spatial discretization of underlying time-dependent coupled partial differential equations (PDE).

In broad terms, model order reduction (MOR) is concerned with finding efficient computational prototyping tools to replace such complex and large models by simpler and smaller models that capture their dominant characteristics. Such reduced order models (ROM) could be used as efficient surrogates for the original model, replacing it as a component in larger simulations. For details on different MOR techniques, we refer the readers to the book [START_REF] Antoulas | Approximation of Large-Scale Dynamical Systems[END_REF] and to the surveys [START_REF] Baur | Model order reduction for linear and nonlinear systems: a system-theoretic perspective[END_REF][START_REF] Benner | A survey of projection-based model reduction methods for parametric dynamical systems[END_REF].

Hybrid systems are a class of nonlinear systems which result from the interaction of continuous time dynamical subsystems with discrete events. These systems are hence described by both discrete and continuous states, inputs and outputs. The transitions between the discrete states may result in a jump in the continuous internal variable. The discrete dynamics is determined by a finite-state deterministic automaton equipped with outputs (the so-called Moore automaton).

Switched systems constitute a subclass of hybrid systems, in the sense that the discrete dynamics is simplified, i.e. any discrete state transition is allowed and the set of discrete events coincides with the set of discrete states.

A switched system is a dynamical system that consists of a finite number of subsystems and a logical rule that orchestrates switching between these subsystems. These subsystems or discrete modes are usually described by a collection of differential or difference equations. The discrete events interacting with the subsystems are governed by a piecewise continuous function, i.e. the switching signal.

One can classify switched systems based on the dynamics of their subsystems, for example continuous-time or discrete-time, linear or nonlinear and so on. In this work we analyze continuous-time linear switched systems (LSS) with reset maps (or coupling/switching matrices). The latter term refers to matrices that scale the continuous state at the switching times.

Hybrid and switched systems represent useful models for distributed embedded systems design where discrete controls are routinely applied to continuous processes. In particular, switched systems have applications in control of mechanical and aeronautical systems, power converters and also in the automotive industry. For a detailed characterization of theses classes of dynamical systems, we refer the readers to the books [START_REF] Liberzon | Switching in Systems and Control[END_REF][START_REF] Sun | Switched linear systems: control and design[END_REF][START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF][START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF]. In the past years, hybrid and switched systems have received increasing attention in the scientific community, which can be partly explained by the fast development of the switch control research area (see [START_REF] Driollet | Adaptive control using multiple models, switching and tuning[END_REF][START_REF] Vu | Input-to-state stability of switched systems and switching adaptive control[END_REF][START_REF] Landau | Multimodel Adaptive Control with Switching[END_REF]). In this context, adaptive control techniques based on switching between different controllers are used to achieve stability and improve transient response. The study of the properties of hybrid and switched systems includes such topics as stability (see [START_REF] Daafouz | Stability analysis and control synthesis for switched systems: a switched Lyapunov function approach[END_REF][START_REF] Vu | Input-to-state stability of switched systems and switching adaptive control[END_REF][START_REF] Sun | Switched linear systems: control and design[END_REF]), realization including observability/controllability (see [START_REF] Petreczky | Realization theory for linear and bilinear switched systems: formal power series approach -Part I: realization theory of linear switched systems[END_REF][START_REF] Petreczky | Observability of switched linear systems[END_REF]), analysis of switched DAEs (see [START_REF] Mehrmann | Hybrid systems of differential-algebraic equations -Analysis and numerical solution[END_REF][START_REF] Trenn | Switched differential algebraic equations[END_REF]) and numerical solutions (see [START_REF] Hamann | Numerical solution of hybrid systems of differential-algebraic equations[END_REF]).

In some cases, the complexity of verifying and assessing general properties of these systems is very high so that the use of these models is limited in applications where the size of the state space is large. A useful tool for dealing with such complexity is MOR. A very prolific MOR method that has been continuously developed over the years is balanced truncation (BT). It was initially introduced in the systems and control theory in [START_REF] Moore | Principal component analysis in linear systems: controllability, observability, and model reduction[END_REF][START_REF] Pernebo | Model reduction via balanced state space representation[END_REF]. The main idea behind BT is to transform a dynamical system to a balanced form defined in such a way that appropriately chosen controllability and observability Gramians are equal and diagonal. Then a reduced-order model is computed by truncating the states corresponding to the small diagonal elements of the Gramians. For more details on BT especially from a practical point of view (i.e. application to large scale systems, solution of Lyapunov equations etc.), see [START_REF] Mehrmann | Balanced truncation model reduction for large-scale systems in descriptor form[END_REF][START_REF] Benner | Model Order Reduction for Differential-Algebraic Equations: A Survey[END_REF].

In this paper we present a model order reduction algorithm for linear switched switched based on balanced truncation. We consider linear switched systems whose linear subsystems may have different state-space dimensions, and where the change of the discrete mode is accompanied with a change in the continuous state using linear reset maps. As it is usual in balanced truncation, the proposed method is based on the following steps. First, observability/controllability Gramians are calculated. Then, using these Gramians a state-space transformation is calculated such that after the application of this state-space transformation, the observability and controllability Gramians are equal to each other and they are diagonal. Finally, the reduced model is obtained by discarding those states which correspond to small diagonal elements (referred to as singular values) of these Gramians.

In this paper we propose the definition of new type of Gramians for LSS. More precisely, for each discrete mode we define observability/controllability Gramians.We propose two definitions of observability/controllability Gramians: one definition defines observability/controllability Gramians as solutions of an LMI, the other one defines them as solution of Sylvester equations. The latter Gramians satisfy the LMIs of the first definition. Note that both the LMIs and the Sylvester equations mix Gramians which belong to different discrete modes. The proposed Gramians exist even if the underlying LSS is not exponentially stable for all switching signals, but only for slow enough switching signals. Furthermore, we present an analytical error bound for the L 2 norm of the difference between the outputs of the original and reduced LSS. This error bound is formulated in terms of singular values of the Gramians. However, this error bound is valid only for slow enough switching signals, i.e., for switching signals with large enough dwell time. Recall that dwell time is the minimal amount of time spent in each discrete mode.

Considerable attention has been dedicated in recent years to the problem of MOR for linear switched system. The related work can be grouped into the following categories.

In [START_REF] Gao | Model simplification for switched hybrid systems[END_REF][START_REF] Zhang | µ-Dependent model reduction for uncertain discrete-time switched linear systems with average dwell time[END_REF][START_REF] Zhang | H-infinity model reduction for uncertain switched linear discrete-time systems[END_REF][START_REF] Zheng-Fan | Stability analysis and H∞ model reduction for switched discrete-time time-delay systems[END_REF] the matrices of the reduced order model were obtained by solving a set of LMIs, and the papers in this group differ from each other in the specific assumptions they imposed on the system at hand and the form of the LMIs employed. More precisely, for a given dimension of the reduced model and for a given error bound these papers propose a set of LMIs, solution of which can be used to calculate the matrices of the reduced order model. The L 2 gain of the system representing the difference between the input-output behavior of the original and the reduced model is then bounded by the fixed error bound. The advantage of [START_REF] Gao | Model simplification for switched hybrid systems[END_REF][START_REF] Zhang | µ-Dependent model reduction for uncertain discrete-time switched linear systems with average dwell time[END_REF][START_REF] Zhang | H-infinity model reduction for uncertain switched linear discrete-time systems[END_REF][START_REF] Zheng-Fan | Stability analysis and H∞ model reduction for switched discrete-time time-delay systems[END_REF] is that error bounds are available. The disadvantage is that the proposed conditions are only sufficient, and the trade-off between the dimension of the reduced model and the error bound is not clear. Moreove, the computational complexity of solving those LMIs might be to high. In contrast to [START_REF] Gao | Model simplification for switched hybrid systems[END_REF][START_REF] Zhang | µ-Dependent model reduction for uncertain discrete-time switched linear systems with average dwell time[END_REF][START_REF] Zhang | H-infinity model reduction for uncertain switched linear discrete-time systems[END_REF][START_REF] Zheng-Fan | Stability analysis and H∞ model reduction for switched discrete-time time-delay systems[END_REF], the current paper proposed a method, whose applicability depends on the existence of solution for a few simple LMIs which are necessary to find the observability/controllability Gramians. Once the existence of these Gramians is assured, the model reduction method can be applied. Moreover, there is an analytic error bound and the trade-off between the approximation error and the dimension of the reduced system is formalized in terms of the singular values of those Gramians. Furthermore, under some very mild assumptions, the Gramians can be obtained by solving Sylvester equations instead of LMIs. Another difference with respect to [START_REF] Gao | Model simplification for switched hybrid systems[END_REF][START_REF] Zhang | µ-Dependent model reduction for uncertain discrete-time switched linear systems with average dwell time[END_REF][START_REF] Zhang | H-infinity model reduction for uncertain switched linear discrete-time systems[END_REF][START_REF] Zheng-Fan | Stability analysis and H∞ model reduction for switched discrete-time time-delay systems[END_REF] is that we consider a more general class of switched systems: in contrast to [START_REF] Gao | Model simplification for switched hybrid systems[END_REF][START_REF] Zhang | µ-Dependent model reduction for uncertain discrete-time switched linear systems with average dwell time[END_REF][START_REF] Zhang | H-infinity model reduction for uncertain switched linear discrete-time systems[END_REF][START_REF] Zheng-Fan | Stability analysis and H∞ model reduction for switched discrete-time time-delay systems[END_REF] the switched systems considered are allowed to have reset maps and the linear subsystems may have different state-space dimensions.

In [START_REF] Papadopoulos | Model reduction of switched affine systems[END_REF], a model reduction method is proposed for switched systems with autonomous switching, i.e. switching which depends on continuous outputs. The proposed method is based on balanced truncation of the linear sub-models. However, [START_REF] Papadopoulos | Model reduction of switched affine systems[END_REF] proposes no error bounds. In contrast, in this paper we consider switched systems with external switching (the switching signal is an external input), and we provide analytic error bounds.

In [START_REF] Birouche | Gramian based approach to model order-reduction for discrete-time switched linear systems[END_REF][START_REF] Birouche | Model reduction for discrete-time switched linear time-delay systems via the H∞ stability[END_REF][START_REF] Birouche | Model order-reduction for discrete-time switched linear systems[END_REF] balanced truncation for discrete-time switched systems was studied. The balanced truncation was based on discarding those states which correspond to the small singular values of the Gramians. The Gramians themselves were defined as solutions of the LMIs. An analytic error bound based on singular values of the Gramians was provided. However, the model reduction procedure of [START_REF] Birouche | Gramian based approach to model order-reduction for discrete-time switched linear systems[END_REF][START_REF] Birouche | Model reduction for discrete-time switched linear time-delay systems via the H∞ stability[END_REF][START_REF] Birouche | Model order-reduction for discrete-time switched linear systems[END_REF] provided a reduced model whose linear subsystems at each discrete mode depended on the switching signal and often they may not exist. switching signal. More precisely, if q(k) denotes the discrete mode at time step k, the matrices of the reduced model had to satisfy Āq(k

) = L q(k+1) A q(k) R q(k) , Bq(k) = L q(k+1) B q(k) , Cq(k) = A q(k) R q(k)
, where (A q , B q , C q ) and ( Āq , Bq , Cq ) are the matrices of the linear subsystem associated with the discrete mode q for the original and reduced models respectively, and L q , R q are suitable matrices. For example, if the switching signal is 123121, then Ā2 = L 3 A 2 R 2 and Ā2 = L 1 A 2 R 2 has to hold simultaneously. In [START_REF] Birouche | Model reduction for discrete-time switched linear time-delay systems via the H∞ stability[END_REF][START_REF] Birouche | Model order-reduction for discrete-time switched linear systems[END_REF] no conditions are provided to guarantee that this is possible. Moreover, if we consider the switching signal 121124, then we get a different set of equalities which Ā2 should satisfy. That is, the model reduction algorithm of [START_REF] Birouche | Gramian based approach to model order-reduction for discrete-time switched linear systems[END_REF][START_REF] Birouche | Model reduction for discrete-time switched linear time-delay systems via the H∞ stability[END_REF][START_REF] Birouche | Model order-reduction for discrete-time switched linear systems[END_REF] need not always yield a well-posed switched system, even if the Gramians exist, moreover, the parameters of this switched system will depend on the switching signals. In contrast to [START_REF] Birouche | Gramian based approach to model order-reduction for discrete-time switched linear systems[END_REF][START_REF] Birouche | Model reduction for discrete-time switched linear time-delay systems via the H∞ stability[END_REF][START_REF] Birouche | Model order-reduction for discrete-time switched linear systems[END_REF], in this paper we deal with continuous-time switched systems, and the parameters of the reduced model do not depend on the timevarying switching signals (of course, the parameters of each linear subsystem will depend on the discrete mode the subsystem is associated with).

In [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF] a model reduction algorithm is proposed which is based on finding observability/controllability Gramians for each linear subsystem and then bringing them into a diagonal form by a common state-space transformation. Moreover, [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF] proposes necessary and sufficient conditions for the existence of such a transformation. In contrast to the current paper [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF] presents no error bound for the difference between the input-output behavior of the original and of the reduced model. Moreover, in contrast to [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF] we consider systems with reset maps and linear subsystems whose dimensions may vary according to the discrete state.

In [START_REF] Bastug | Model reduction by nice selections for linear switched systems[END_REF][START_REF] Bastug | Model reduction of linear switched systems and LPV state-space models[END_REF][START_REF] Scarciotti | Model reduction for hybrid systems with state-dependent jumps[END_REF] model reduction procedures based on moment matching is proposed. In contrast to the current paper, those methods do not allow for analytical error bounds. However, in [START_REF] Bastug | Model reduction by nice selections for linear switched systems[END_REF][START_REF] Bastug | Model reduction of linear switched systems and LPV state-space models[END_REF] it is guaranteed that the reduced model will have the same input-output behavior for certain switching signals. As to [START_REF] Scarciotti | Model reduction for hybrid systems with state-dependent jumps[END_REF], in contrast to the present paper, it considers switched systems with autonomous switching and it proposed a model reduction procedure which guarantees that the reduced model has the same steady-state output response to certain inputs as the original model.

In [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF][START_REF] Shaker | Generalized gramian framework for model/controller order reduction of switched systems[END_REF][START_REF] Shaker | Model reduction of switched systems based on switching generalized gramians[END_REF] model reduction based on generalized observability/reachability Gramians are proposed. The method of [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF][START_REF] Shaker | Generalized gramian framework for model/controller order reduction of switched systems[END_REF][START_REF] Shaker | Model reduction of switched systems based on switching generalized gramians[END_REF] applies only to quadratically stable linear switched systems. Here, quadratic stability means that there exists a common quadratic Lyapunov function for all the linear subs-systems. Quadratic stability is known to be sufficient but not necessary for the linear switched system to be exponentially stable for any switching signal and zero continuous input. The Gramians at hand are solutions of a certain LMI. After calculating a solution of the LMI, a linear state-space transformation is applied to the original model such that the observability Gramian becomes diagonal and equals the controllability Gramian. Then the states corresponding to small singular values of these Gramians are thrown away. Furthermore, in [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF] an analytical error bound is presented which involves the singular values of the Gramians. The current paper can be seen as an improvement upon [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF][START_REF] Shaker | Generalized gramian framework for model/controller order reduction of switched systems[END_REF][START_REF] Shaker | Model reduction of switched systems based on switching generalized gramians[END_REF]. The algorithm proposed in this paper can be applied to switched systems which are not quadratically stable, and like in [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF][START_REF] Shaker | Generalized gramian framework for model/controller order reduction of switched systems[END_REF][START_REF] Shaker | Model reduction of switched systems based on switching generalized gramians[END_REF] there is a clear error bound and trade-off between the size of the reduced order model and approximation error. However, the price we pay for it is that the error bound is valid only for switching signals with a sufficiently large dwell time. Another improvement upon [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF][START_REF] Shaker | Generalized gramian framework for model/controller order reduction of switched systems[END_REF][START_REF] Shaker | Model reduction of switched systems based on switching generalized gramians[END_REF] is that we consider switched systems with reset maps and with linear subsystems whose dimensions are not necessarily the same.

The definitions of Gramians proposed in this paper are inspired by the definitions previously encountered for the case of bilinear and stochastic systems (see [START_REF] Benner | Dual pairs of generalized lyapunov inequalities and balanced truncation of stochastic linear systems[END_REF][START_REF] Zhang | On H 2 model reduction of bilinear systems[END_REF]).

Finally, it is worth mentioning that MOR for LSS is related to the notion of approximate bisimulation introduced in [START_REF] Girard | Approximate simulation relations for hybrid systems[END_REF]. The paper [START_REF] Girard | Approximate simulation relations for hybrid systems[END_REF] does not directly address model reduction. Instead, it proposes a definition of simulation relations among hybrid systems. Informally, an approximate simulation relation between two hybrid systems is a multivalued map between their state spaces, which approximately respects the dynamics and the output map of the systems at hand. As a consequence, if two hybrid systems are related by an approximation simulation relation, then their outputs will be close to each other. If one of the hybrid systems has a simpler structure, for example, it is a finite-state transition system, then the existence of a approximation simulation relation allows to use the simple system for control synthesis or verification. While the general goal of model reduction and of finding approximate simulation relations is the same (both aim at replacing a complex model by a simpler one), the details a very different. In particular, in model reduction, the aim is to replace a model with a model of the same type but with less states.For example, a switched system is replaced by another switched system with a smaller number of states. In contrast, the goal in using approximate simulation relations is to replace a hybrid/nonlinear system by a finite-state transition system, which is approximately similar to the original system. A formal comparison between classical model reduction approaches and the ideas of [START_REF] Girard | Approximate simulation relations for hybrid systems[END_REF] would certainly be very useful, but it would go beyond the scope of this paper.

The paper is organized as follows; in the second section, we introduce continuoustime linear switched systems in a formal way. Furthermore, we provide a characterization of input-output mappings in time domain corresponding to such systems. Section 3 describes the procedure of constructing infinite energy Gramians for the simplified case with only two discrete modes. Next, in Section 4 we provide a system theoretic interpretation of such Gramians (for the general case with D modes). Furthermore, we formally introduce the balancing algorithm followed by the MOR step, i.e. the truncation. A measure of the quality of approximation by reduction is provided by means of a error bound. Additionally, we investigate the possibility of preserving system theoretic properties such as stability, for the reduced system. Section 5 is designated for the numerical experiments while a summary of the findings and the conclusion are presented in Section 6.

Linear switched systems

Definition 1 A continuous time linear switched system (LSS) is a control system of the form:

Σ : ẋ(t) = A σ(t) x(t) + B σ(t) u(t), x(t) = x 0 , y(t) = C σ(t) x(t), (1)
where Ω = {1, 2, . . . , D}, D > 1, is a set of discrete modes, σ(t) is the switching signal, u is the input, x is the state, and y is the output.

The system matrices bA q ∈ R n q ×n q , B q ∈ R n q ×m , C q ∈ R p×n q , where q ∈ Ω, correspond to the linear system active in mode q ∈ Ω, and x 0 is the initial state. We consider the E q matrices to be invertible. Furthermore, the transition from one mode to another is made via the so called switching or coupling matrices K q 1 ,q 2 ∈ R n q 2 ×n q 1 where q 1 , q 2 ∈ Ω.

Remark 1

The case for which the coupling is made between identical modes is excluded, Hence, when q 1 = q 2 = q, consider that the coupling matrices are identity matrices, i.e. K q,q = I n q .

The notation Σ = (n 1 , n 2 , . . . , n D , {(A q , B q , C q )|q ∈ Ω}, {K q i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ) is used as a short-hand representation for LSSs described by the equations in [START_REF] Antoulas | Approximation of Large-Scale Dynamical Systems[END_REF]. The vector n = n 1 n 2 • • • n D is the dimension (order) of Σ.

The restriction of the switching signal σ(t) to a finite interval of time [0, T ] can be interpreted as finite sequence of elements of Ω × R + of the form:

ν(σ) = (q 1 , t 1 )(q 2 , t 2 ) . . . (q k , t k ),
where q 1 , . . . , q k ∈ Ω and 0 < t

1 < t 2 < • • • < t k ∈ R + , t 1 + • • • + t k = T , such
that for all t ∈ [0, T ] we have:

σ(t) =        q 1 if t ∈ [0, t 1 ], q 2 if t ∈ (t 1 , t 1 + t 2 ], . . . q i if t ∈ (t 1 + . . . + t i-1 , t 1 + . . . + t i-1 + t i ], for 2 i k.
In short, by denoting T i := t 1 + . . .

+ t i-1 + t i , T 0 := 0, T k := T , write σ(t) = q 1 if t ∈ [0, T 1 ], q i if t ∈ (T i-1 , T i ], i > 2. ( 2
)
Intuitively, the switching signal defined above specifies that in the interval [T i-1 , T i ) the mode q i is active and hence the continuous state and output change according to the linear system associated with this mode, i.e., ẋ(t) = A q x(t) + B q u(t), y(t) = C q i x(t).

(3)

Remark 2 (The number of entries of the vector x(t) changes with time) Note that the continuous state depends on the discrete mode, in fact, the dimension of the space it belongs to changes when the discrete mode changes. This is due to the fact that the state-space dimension of linear systems associated with different modes can be different.

Note that in order to define x, the equations (3) are not sufficient, as the initial state of the differential equation in ( 3) is not specified. This calls for a careful and formal definition of what we mean by a solution of an LSS. To this end, denote by P C(R + , R n ), P c (R + , R n ), the set of all piecewise-continuous, and piecewiseconstant functions, respectively.

Definition 2 A tuple (x, u, σ, y), where x :

R + → D i=1 R n i , u ∈ P C(R + , R m ), σ ∈ P c (R + , Ω), y ∈ P C(R + , R p
) is called a solution, if the following conditions simultaneously hold:

1. The restriction of x(t) to [T i-1 , T i ) is differentiable, and satisfies ẋ(t) = A q i x(t)+ Bu(t), and x(T i ) = K q i ,q i+1 lim t T i x(t).

2. For all t ∈ R + , y(t) = C σ(t) x(t) holds.

Remark 3 (Existence and uniqueness of solution)

The solution of a linear switched system is unique for every initial state, continuous input and switching signal. More precisely, for every initial state x 0 , input signal u and switching signal σ, there exists a unique function x : R + → D i=1 R n i , and y : R + → R p which satisfies the conditions of Definition 2, and such that x(0) = x 0 . It is sufficient to show that there exists a unique function x : R + → D i=1 R n i such that x(0) = x 0 and which satisfies the conditions of Definition 2. In order to show existence, for every i ∈ N, define the functions z i : [T i-1 , T i ] → R n i recursively as follows: let z 0 : [0, T 1 ] → R n i be the solution of the differential equation ż1 (t) = A q 1 z 1 (t) + B q 1 u(t) with the initial state z 1 (0) = x(0), and if z i is defined, then let z i+1 be the solution of the differential equation żi+1 (t) = A q i+1 z i+1 (t) + B q i+1 u(t) with the initial state z i+1 (T i ) = K q i ,q i+1 z i (T i ). Define now x by x(t) = z i (t) for all t ∈ [T i-1 , T i ) for all i ∈ N. It is clear that x satisfies Definition 2. Assume that x : R + → D i=1 R n i satisfies the conditions of Definition 2 and x(0) = x(0). We will show by induction that for every i ∈ N, the restrictions of x and x to [T i , T i+1 ) are equal. Indeed, for i = 0, consider he restriction of x to [0, T 1 ) is a solution of the differential equation ż1 (t) = A q 1 z 1 (t) + B q 1 u(t) with the initial condition z 1 (0) = x(0) = x(0), and hence by the uniqueness of solutions of differential equations, restriction of x to [0, T 1 ) equals the restriction of z 1 to [0, T 1 ), and the latter equals the restriction of x to [0, T 1 ). Assume that the induction hypothesis is true for i ≤ k. In particular, this implies that the restrictions of x and x to [T k , T k+1 ) are equal. In particular, lim

t T k+1 x(t) = lim t T k+1
x(t), and hence x(T k+1 ) =

K q k+1 ,q k+2 lim t T k+1 x(t) = K q k+1 ,q k+2 lim t T k+1
x(t) = x(T k+1 ). Since the restrictions of x and x to [T k+1 , T k+1 ) are solutions of the same differential equation żk+1 (t) = A q k+1 z k+1 (t)+B q k+1 u(t) with the same initial condition z k+1 (T k+1 ) = x(T k+1 ) = x(T k+1 ), by uniqueness of the solution of a differential equation, the restrictions of x and x to [T k+1 , T k+2 ) are equal. The switching matrices K q i ,q i+1 allow having different dimensions for the subsystems active in different modes. If the K q i ,q i+1 matrices are not explicitly given, it is considered that they are identity matrices.

The input-output behavior of an LSS system can be described in time domain using the mapping f (u, σ). This particular map can be written in generalized kernel representation (as suggested in [START_REF] Petreczky | Realization theory for linear hybrid systems[END_REF]) using the unique family of analytic functions: g q 1 ,...,q k : R k + → R p and h q 1 ,...,q k : R k + → R p×m with q 1 , . . . , q k ∈ Ω, k 1 such that for all pairs (u, σ) and for T = t 1 + t 2 + • • • + t k we can write:

f (u, σ)(t) = gq 1 ,...,q k (t 1 , ..., t k ) + k i=1 t i 0 hq i ,q i+1 ,...,q k (t i -τ, t i+1 , . . . , t k )u(τ + T i-1 )dτ, ( 4
)
where the functions g, h are defined for k 1, as follows,

gq 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = Cq k e Aq k t k Kq k-1 ,q k e Aq k-1 t k-1 Kq k-2 ,q k-1 • • • Kq 1 ,q 2 e Aq 1 t 1 x 0 , (5) hq 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = Cq k e Aq k t k Kq k-1 ,q k e Aq k-1 t k-1 Kq k-2 ,q k-1 • • • Kq 1 ,q 2 e Aq 1 t 1 Bq 1 . (6)
In the rest of the paper, we will make the following assumption.

Assumption 21 If Σ is an LSS of the form (3), we assume that for all q = 1, . . . , D, A q is stable, i.e. all eigenvalues of A q have a strictly negative real part.

Assumption 21 implies that each linear subsystem of the LSSs are stable. However, this does not imply that the LSS at hand is stable for any switching signal, see [START_REF] Liberzon | Switching in Systems and Control[END_REF][START_REF] Sun | Switched linear systems: control and design[END_REF][START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF][START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF] for counter-examples.

Remark 4 (Role of minimallity) Since in this paper we aim at proposing a MOR method for LSS, it is natural to discuss the issue of LSS of minimal order realizing a certain input-output function. Indeed, transforming an LSS to a minimal order one, while preserving its input-output behavior could be a first step towards model order reduction. There exists a complete realization theory and a minimization algorithm for linear switched systems [START_REF] Petreczky | Partial-realization theory for linear switched systems -a formal power series approach[END_REF][START_REF] Petreczky | Realization theory for linear and bilinear switched systems: formal power series approach -Part I: realization theory of linear switched systems[END_REF]. According to this theory, a linear switched system is called minimal, if the sum of the dimensions of its LTI subsystems is minimal among all the linear switched systems describing the same input-output function. It is also shown that minimality is equivalent to observability and reachability of the linear switched system. Here, observability means that any non-zero continuous state will yield a non-zero output for a suitable switching signal, and reachability means that the span of all states reached by varying continuous input and switching signals is the whole state-space. It is well known [START_REF] Petreczky | Partial-realization theory for linear switched systems -a formal power series approach[END_REF][START_REF] Petreczky | Realization theory for linear and bilinear switched systems: formal power series approach -Part I: realization theory of linear switched systems[END_REF] that a linear switched system can be observable (respectively reachable), without any of its LTI sub-systems being observable (respectively reachable). Based on this observation, it can be shown by means of counter-examples that minimality of a linear switched system does not imply that of its LTI sub-systems, i.e., it can happen that a linear switched system is minimal, but the LTI subsystems are not. For this reason we do not assume minimality of the LTI subsystems, as it would exclude a large class of input-output behaviors which are realizable by linear switched systems.

In particular, [START_REF] Petreczky | Partial-realization theory for linear switched systems -a formal power series approach[END_REF][START_REF] Petreczky | Realization theory for linear and bilinear switched systems: formal power series approach -Part I: realization theory of linear switched systems[END_REF] propose algorithms for transforming a linear switched system to a minimal one, while preserving its input-output function. Hence, that minimization algorithm can be considered as a primitive model reduction algorithms, which eliminates those states which do not contribute to the input-output behavior of the system. Note that the minimization algorithm produces a system whose input-output behavior is exactly the same as that of the original system, while the goal of model reduction is to produce a system whose input-output behavior is sufficiently close, but not necessarily the same as that of the original system. Since the former goal is a special case of the latter one, minimization algorithms can be viewed as subclasses of model reduction algorithms. However, since they aim at preserving exactly the same input-output behavior, they tend to produce too large systems.

Naturally, before applying any model reduction to a linear switched system, one can use the minimization algorithm of [START_REF] Petreczky | Partial-realization theory for linear switched systems -a formal power series approach[END_REF][START_REF] Petreczky | Realization theory for linear and bilinear switched systems: formal power series approach -Part I: realization theory of linear switched systems[END_REF] to obtain a smaller linear switched system model.

However, in this paper we prefer not to restrict attention to minimal LSS, as it is not necessary and in fact would lead to technical complications. More precisely, the proposed algorithm could yield non-minimal models, even if applied to minimal LSS. Since the main analytical result of the paper is proven using repeated application of the model reduction procedure for eliminating one single state, assuming minimality could lead to technical difficulties. Indeed, if our assumptions include minimality of the LSS at hand, then after applying the model reduction procedure to eliminate one state, we might end up with an LSS which is not minimal. Then, we could no longer apply the same model reduction algorithm to this reduced LSS. We could minimize this reduced LSS. However, for the proof we need this LSSs to be balanced with Gramians which are diagonal and which are sub-matrices of the balanced Gramians of the original LSS. It is not clear if applying the minimization algorithm will preserve these properties.

The remark that the proposed algorithm may result in non-minimal LSS might seem counter-intuitive. Intuitively, the proposed algorithm, like all the other balanced truncation algorithms, will eliminate certain poorly controllable and poorly observable states. However, we have no proof that the proposed algorithm will eliminate unobservable or unreachable states. In fact, it is known that the balanced truncation algorithm from [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF] may result in non-minimal models. Note that in our algorithm we require that the observability and reachability Gramians are positive definite. While in the LTI case this would imply minimality of the LTI system, it is not clear if our assumptions imply minimality of the switched system. In fact, the counter-example of [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF] is a strong indication that this is not the case. However, since the Gramians proposed in this paper are different from that of [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF], formally we cannot be certain. All these issues require further research.

Energy Gramians for LSS for two modes

The purpose of this section is to provide some intuition behind the general definition of Gramians which will be presented in Section 4 later on. For simplicity of the exposition, we first consider the simplified case D = 2 (the LSS system switches between two modes only). This situation is encountered in most of the numerical examples in the literature we came across. see Section 4.

Setup and notations

Assume that there are two discrete modes, i.e., D = 2. Depending on the values of the switching signal σ(t), the original system Σ switches between the following subsystems,

Σ 1 : ẋ1 (t) = A 1 x 1 (t) + B 1 u(t), y(t) = C 1 x 1 (t). or Σ 2 : ẋ2 (t) = A 2 x 2 (t) + B 2 u(t), y(t) = C 2 x 2 (t), , (7)
where dim(Σ 1 ) = n 1 (i.e.

x 1 ∈ R n 1 and A 1 ∈ R n 1 ×n 1 , B 1 , C T 1 ∈ R n 1 ) and also dim(Σ 2 ) = n 2 (i.e. x 2 ∈ R n 2 and E 2 , A 2 ∈ R n 2 ×n 2 , B 2 , C T 2 ∈ R n 2 )
. Notice that we allow both the two subsystems to be written in descriptor format (having possibly singular E matrix).

Denote, for simplicity, with K 1 the coupling matrix when switching from mode 1 to mode 2 (instead of K 1,2 ) and, with K 2 , the coupling matrix when switching from mode 2 to mode 1 (instead of K 2,1 ) with

K 1 ∈ R n 2 ×n 1 and K 2 ∈ R n 1 ×n 2 .
In the following, for the first two levels we present the generalized kernels, which were previously defined in (6), i.e., Level 1 :

h 1 (t 1 ) = C 1 e A 1 t 1 B 1 , h 2 (t 2 ) = C 2 e A 2 t 1 B 2 . , Level 2 : h 1,2 (t 1 , t 2 ) = C 1 e A 1 t 1 K 2 e A 2 t 2 B 2 , h 2,1 (t 1 , t 2 ) = C 2 e A 2 t 1 K 1 e A 1 t 2 B 1 .
Consider a LSS system Σ as described in (1) with two operational modes, i.e D = 2 and

Ω = {1, 2}. Consider dim(Σ k ) = n k for k = 1, 2 and let K 1 ∈ R n 2 ×n 1 and K 2 ∈ R n 1 ×n 2 be the coupling matrices.
Definition 3 For ν ∈ {1, 2}, let Ω ν,+ and Ω +,ν be the ordered sets containing all tuples that can be constructed with symbols from the alphabet Ω = {1, 2} and that start (and respectively end ) with the symbol ν. Also, no two consecutive characters are allowed to be the same. Hence, explicitly write the new introduced sets as follows:

Ω 1,+ = {(1), (1, 2), (1, 2, 1), . . .}, Ω 2,+ = {(2), (2, 1), (2, 1, 2), . . .}, (8)
Ω +,1 = {(1), (2, 1), (1, 2, 1), . . .}, Ω +,2 = {(2), (1, 2), (2, 1, 2), . . .}. (9)
Definition 4 Let the i th unit vector of length k be denoted with

e i = [0, . . . , 1, . . . , 0] T ∈ R k , e i ( ) = 1, if = i and e i ( ) = 0, else.
In some contexts we may use the alternative notation e i,k to emphasize its dimension k. The identity matrix I k ∈ R k×k can be written as

I k = [e 1,k e 2,k . . . e k,k ].
Also, let 0 k, ∈ R k× be an all zero matrix. When k = , we use the notation 0 k =∈ R k×k or simply 0 when the dimension is clearly inferred.

Level k switching -an intermediate step

Reachability Gramians

Introduce the following level k energy functional g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) : R k → R n q 1 ×m , corresponding to the switching sequence (q 1 , q 2 , . . . , q k ) ∈ Ω k , as

g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = e A q 1 t 1 K q 2 ,q 1 e A q 2 t 2 K q 3 ,q 2 • • • K q k ,q k-1 e A q k t k B q k . ( 10
)
By fixing the first element of the tuple (q 1 , q 2 , . . . , q k ), i.e., q 1 ∈ {1, 2}, note that (q 1 , q 2 , . . . , q k ) can either be an element of Ω 1,+ or of Ω 2,+ (as introduced in Definition 4).

If we choose q 1 = 1, then it follows that (q 1 , q 2 , . . . , q k ) ∈ Ω 1,+ . Examples of energy functionals associated to sequences from Ω 1,+ , are for instance the following

g r 1 (t 1 ) = e A 1 t 1 B 1 , g r 1,2 (t 1 , t 2 ) = e A 1 t 1 K 2 e A 2 t 2 B 2 , g r 1,2,1 (t 1 , t 2 , t 3 ) = e A 1 t 1 K 2 e A 2 t 2 K 1 e A 1 t 3 B 1 , . . .
In general, define the level k infinite Gramian corresponding to mode q 1 ∈ {1, 2} as

P (k) q 1 = ∞ 0 • • • ∞ 0 g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) T dt 1 dt 2 . . . dt k . (11)
Note that due to Assumption 21, the infinite integrals in ( 11) are well defined. By making use of the recurrence relation

g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = e A q 1 t 1 K q 2 ,q 1 g r q 2 ,q 3 ,...,q k (t 2 , t 3 , . . . , t k ),
it follows that the k th Gramian corresponding to mode 1 (or respectively mode 2) can be written in terms of the (k -1) th Gramian corresponding to mode 2 (or mode 1), as

P (k) q 1 = ∞ 0 • • • ∞ 0 e A q 1 t 1 K q 2 ,
q 1 g r q 2 ,...,q k (t 2 , . . . , t k ) g r q 2 ,...,q k (t 2 , . . . , t k )

T e A q 1 t 1 K q 2 ,q 1 T dt 1 . . . dt k = ∞ 0 e A q 1 t 1 K q 2 ,q 1 ∞ 0 g q 2 ,...,q k (t 2 , . . . , t k ) g r q 2 ,...,q k (t 2 , . . . , t k ) T dt 2 . . . dt k K T q 2 ,q 1 e A T q 1 t 1 dt 1 = ∞ 0 e A q 1 t 1 K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 dt 1 . (12)
Next introduce the linear reachability Gramians for the case with no switching. They are denoted with P (1) q , corresponding to mode q ∈ {1, 2}, and can be defined as

P (1) q = ∞ 0 g r q (t) g r q (t) T dt = ∞ 0 e A q t B q B T q e A T q t dt. ( 13
)
It is a well known result that P

(1) q satisfies the following Lyapunov equation:

A q P (1) q + P (1) q A T q + B q B T q = 0. ( 14
)
Proposition 1 With Assumption 21,the level k reachability Gramians corresponding to modes 1 and 2 from (11) are the unique solutions of the recursive systems of linear equations:

A 1 P (k) 1 + P (k) 1 A T 1 + K 2 P (k-1) 2 K T 2 = 0, (15)
A 2 P (k) 2 + P (k) 2 A T 2 + K 1 P (k-1) 1 K T 1 = 0, (16)
where k > 1 and P

q 1 is as in [START_REF] Gao | Model simplification for switched hybrid systems[END_REF].

Proof of Proposition 2. By multiplying the equality in [START_REF] Chahlaoui | A collection of benchmark examples for model reduction of linear time invariant dynamical systems[END_REF] with A q 1 to the left and with A T q 1 to the right, we write

A q 1 P (k) q 1 + P (k) q 1 A T q 1 = ∞ 0 A q 1 e A q 1 t 1 K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 dt 1 + ∞ 0 e A q 1 t 1 K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 A T q 1 dt 1 = ∞ 0 d dt 1 e A q 1 t 1 K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 dt 1 = -K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 .
Hence it follows that, for q 1 , q 2 ∈ {1, 2} with q 1 = q 2 , we write

A q 1 P (k) q 1 + P (k) q 1 A T q 1 + K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 = 0,
which proves the statements in ( 15) and ( 16).

Observability Gramians

Define the level k energy functional g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 ) : R k → R p×n q 1 , corresponding to the switching sequence (q k , . . . , q 2 , q 1 ) ∈ Ω k , as

g o q k ,q k-1 ,...,q 1 (t k , . . . , t 2 , t 1 ) = Cq k e Aq k t k Kq k-1 ,q k e Aq k-1 t k-1 Kq k-2 ,q k-1 • • • Kq 1 ,q 2 e Aq 1 t 1 (17)
By fixing the last element of the tuple, i.e., q 1 ∈ {1, 2}, note that (q k , . . . , q 2 , q 1 ) can either be an element of Ω +,1 or of Ω +,2 (as introduced in Definition 4).

If q 1 = 1 is chosen, then it follows that (q k , q k-1 , . . . , q 1 ) ∈ Ω 1,+ . Examples of energy functionals associated to sequences from Ω +,1 , are the following

g o 1 (t 1 ) = C 1 e A 1 t 1 , g o 2,1 (t 2 , t 1 ) = C 2 e A 2 t 2 K 1 e A 1 t 1 , g o 1,2,1 (t 3 , t 2 , t 1 ) = C 1 e A 1 t 3 K 2 e A 2 t 2 K 1 e A 1 t 1 , . . .
Define level k infinite Gramian corresponding to mode q 1 ∈ {1, 2} as

Q (k) q 1 = ∞ 0 • • • ∞ 0 g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 ) T g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 )dt 1 . . . dt k . (18
) Note that the infinite integrals in [START_REF] Landau | Multimodel Adaptive Control with Switching[END_REF] are well-defined due to Assumption 21. By using the following recurrence relation, g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 ) = g o q k ,...,q 3 ,q 2 (t k , . . . , t 3 , t 2 ) K q 1 ,q 2 e A q 1 t 1 , the k th observability Gramian corresponding to mode 1 (or respectively mode 2) can be written in terms of the (k -1) th observability Gramian corresponding to mode 2 (or respectively mode 1), as

Q (k) q 1 = ∞ 0 • • • ∞ 0 K q 1 ,
q 2 e A q 1 t 1 T g o q k ,...,q 2 (t k , . . . , t 2 ) T g o q k ,...,q 2 (t k , . . . , t 2 )

K q 1 ,q 2 e A q 1 t 1 dt 1 . . . dt k = ∞ 0 e A T q 1 t 1 K T q 1 ,q 2 ∞ 0 g o q k ,...,q 2 (t k , . . . , t 2 ) T g o q k ,...,q 2 (t k , . . . , t 2 )dt 2 . . . dt k K q 1 ,q 2 e A q 1 t 1 dt 1 = ∞ 0 e A T q 1 t 1 K T q 1 ,q 2 Q (k-1) q 2 K q 1 ,q 2 e A q 1 t 1 dt 1 . (19)
The linear observability Gramian (for the case with no switching) Q

(1) q which corresponds to mode q ∈ {1, 2}, can be written as

Q (1) q = ∞ 0 g o q (t) T g o q (t)dt = ∞ 0 e A T q t C T q C q e A q t dt. ( 20
)
It is a well known result that Q

(1) q satisfies the following Lyapunov equation:

A T q Q (1) q + Q (1) q A q + C T q C q = 0. ( 21
)
Proposition 2 With Assumption 21, the level k observability Gramians corresponding to modes 1 and 2 defined in [START_REF] Landau | Multimodel Adaptive Control with Switching[END_REF] are the unqiue solution of the recusive systems of linear equations

A T 1 Q (k) 1 + Q (k) 1 A 1 + K T 1 Q (k-1) 2 K 1 = 0, (22)
A T 2 Q (k) 2 + Q (k) 2 A 2 + K T 2 Q (k-1) 1 K 2 = 0, (23)
where the starting point is represented by the linear Gramians (with no switching) Ω

(1) q 1 in ( 21) that correspond to the first level.

Proof of Proposition 4. By multiplying the identity in [START_REF] Liberzon | Switching in Systems and Control[END_REF] with A T q 1 to the left and with A q 1 to the right, we write

A T q 1 Q (k) q 1 + Q (k) q 1 A q 1 = ∞ 0 A T q 1 e A T q 1 t 1 K T q 1 ,q 2 Q (k-1) q 2 K q 1 ,q 2 e A q 1 t 1 dt 1 + ∞ 0 e A T q 1 t 1 K T q 2 ,q 1 Q (k-1) q 2 K q 1 ,q 2 e A q 1 t 1 A q 1 dt 1 = ∞ 0 d dt 1 e A T q 1 t 1 K T q 1 ,q 2 Q (k-1) q 2 K q 1 ,q 2 e A q 1 t 1 dt 1 = -K T q 1 ,q 2 Q (k-1)
q 2 K q 2 ,q 1 .
Hence it follows that, for q 1 , q 2 ∈ {1, 2} with q 1 = q 2 , we write

A T q 1 Q (k) q 1 + Q (k) q 1 A q 1 + K T q 1 ,q 2 Q (k-1) q 2 K q 1 ,q 2 = 0.
which proves the statements in ( 22) and (23).

Infinite Gramians and Lyapunov equations

Next, we will propose a definition of reachability/observability Gramians which collects level k reachability/observability Gramians. We will start with reachability Gramians.

Definition 5 Introduce the infinite reachability Gramian P q 1 corresponding to mode q 1 ∈ {1, 2} of the LSS system Σ as

Pq 1 = ∞ k=1 ∞ 0 • • • ∞ 0 g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) T dt 1 . . . dt k , ⇒ P q 1 = ∞ k=1 P (k) q 1 = P (1) q 1 + P (2) q 1 + . . . , (24)
in terms of the multivariate functions g r q in (10) or matrices P (k) [START_REF] Birouche | Model order-reduction for discrete-time switched linear systems[END_REF].

q 1 in
Note that P q 1 is computed by taking into account the inner products of energy functionals associated to all possible switching sequences (of any length k) that start in mode q 1 . Definition 6 Introduce the infinite observability Gramian Q q 1 corresponding to mode q 1 ∈ {1, 2} of the LSS system Σ as

Qq 1 = ∞ k=1 ∞ 0 • • • ∞ 0 g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 ) T g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 ) dt 1 dt 2 . . . dt k Q q 1 = ∞ k=1 Q (k) q 1 = Q (1) q 1 + Q (2) q 1 + . . . (25)
Note that Q q 1 is computed by taking into account the inner products of energy functionals associated to all possible switching sequences (of any length k) that end in mode q 1 . Note that the existince of the newly defined Gramians is not evident. The following result from [START_REF] Zhang | On H 2 model reduction of bilinear systems[END_REF] addresses the existence of the newly defined Gramians. In a nutshell, it states that this holds if the norm of the coupling matrices is sufficiently small. In order to state this result, we need the following notation. Write the matrices {P q , A q , B q , C q }, q ∈ {1, 2} and {K q 1 ,q 2 }, q 1 , q 2 ∈ {1, 2} in block-diagonal format, as

X D = X 1 0 0 X 2 , X ∈ {A, B, C, P}, K D = 0 K 1 K 2 0 . ( 26
) Proposition 3 If A D is stable and K D = max( K 1 , K 2 ) √ 2α β , (27)
where α, β > 0 are such that e A D t βe -αt . for all t ∈ R +1 , then the infinite sums in (24)-( 25) are absolutely summable, and hence the reachability and observability Gramians in ( 24) -( 25) exist.

Infinite reachability/observability Gramians satisfy Sylvester equations.

Proposition 4 Assume (27) of Proposition 3 holds. Then the infinite reachability Gramians defined in (24) satisfy the following system of generalized coupled Lyapunov equations

A 1 P 1 + P 1 A T 1 + K 2 P 2 K T 2 + B 1 B T 1 = 0, A 2 P 2 + P 2 A T 2 + K 1 P 1 K T 1 + B 2 B T 2 = 0. ( 28
)
Proof of Proposition 5. By adding the equalities stated in ( 15) and ( 16) for k > 2 as well as the one corresponding to k = 1 (in ( 13)), it follows that

Aq 1 P (1)
q 1 + P

(1)

q 1 A T q 1 + Bq 1 B T q 1 + ∞ k=2 Aq 1 P (k) q 1 + Pq 1 A T q 1 + Kq 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 = 0 ⇒ A q 1 ∞ k=1 P (k) q 1 + ∞ k=1 P (k) q 1 A T q 1 + K q 2 ,q 1 ∞ k=1 P (k) q 1 K T q 2 ,q 1 + B q 1 B T q 1 = 0. ⇒ A q 1 P q 1 + P q 1 A T q 1 + K q 2 ,q 1 P q 1 K T q 2 ,q 1 + B q 1 B T q 1 = 0 ∀q 1 = q 2 ∈ {1, 2},
which shows the validity of the equalities introduced in (28).

Proposition 5 Assume (27) of Proposition 3 holds. Then the infinite observability Gramians defined in [START_REF] Papadopoulos | Model reduction of switched affine systems[END_REF], satisfy the following system of generalizaed coupled Lyapunov equations

A T 1 Q 1 + Q 1 A 1 + K T 1 Q 2 K 1 + C T 1 C 1 = 0, A T 2 Q 2 + Q 2 A 2 + K T 2 Q 1 K 2 + C T 2 C 2 = 0, (29)
in terms of the multivariate functions g o q in (10) and matrices Q

(k) q 1 in (18).
Proof of Proposition 6. By adding the equalities stated in ( 22) and ( 23) for k > 2 as well as the one corresponding to k = 1 (in [START_REF] Mehrmann | Balanced truncation model reduction for large-scale systems in descriptor form[END_REF]), it follows that

A T q 1 Q (1) q 1 + Q (1) q 1 A q 1 + C T q 1 C T q 1 + ∞ k=2 A T q 1 Q (k) q 1 + Q q 1 A q 1 + K T q 1 ,q 2 Q (k-1) q 2 K q 1 ,q 2 = 0 ⇒ A T q 1 ∞ k=1 Q (k) q 1 + ∞ k=1 Q (k) q 1 A q 1 + K T q 1 ,q 2 ∞ k=1 Q (k) q 1 K q 1 ,q 2 + C T q 1 C q 1 = 0. ⇒ A T q 1 Q q 1 + Q q 1 A q 1 + K T q 1 ,q 2 Q q 1 K q 1 ,q 2 + C T q 1 C q 1 = 0 ∀q 1 = q 2 ∈ {1, 2},
which shows the validity of the equalities presented in [START_REF] Petreczky | Partial-realization theory for linear switched systems -a formal power series approach[END_REF].

Remark 5 Instead of solving the two equations in (29) separately, one can solve one equation

A D P D + P D A T D + K D P D K T D + B D B T D = 0, (30)
and recover the reachability Gramians P 1 and P 2 as block diagonal entries of P D .

Remark 6 Additional to [START_REF] Pernebo | Model reduction via balanced state space representation[END_REF], write the matrices {Q q }, q ∈ {1, 2} in block-diagonal format, as

Q D = Q 1 0 0 Q 2 .
Hence, instead of solving the two equations in [START_REF] Petreczky | Partial-realization theory for linear switched systems -a formal power series approach[END_REF] separately, one can solve one equation

A T D Q D + Q D A D + K T D Q D K D + C T D C D = 0, (31)
and recover the observability Gramians as the block diagonal entries of Q D .

For high order examples, it is not trivial to solve such generalized Lyapunov equations as [START_REF] Petreczky | Observability of switched linear systems[END_REF] and [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF]. A possible approach is to approximate these solutions with truncated sums of positive definite matrices,

P D ≈ H k=1 P (k) D , Q D ≈ H k=1 Q (k) D , H 1, ( 32
)
where

P (k) D and Q (k)
D can be written as solutions of regular Lyapunov equations,

A D P (k) D + P (k) D A D + K D P (k-1) D K T D = 0, A T D Q (k) D + Q (k) D A D + K T D Q (k-1) D K D = 0, k 2.
For practical applications, solving many such Lyapunov equations is expensive. One can compute low rank factors instead of the full solutions to speed up the calculations ad avoid memory problems (for example, by using the toolbox in [START_REF] Saak | The Matrix Equations Sparse Solvers Library[END_REF]).

Extension to LSS with D ≥ 2 modes

Below, we extend the definitions of reachability/observability Gramians presented above for the case D = 2 to the general case of D > 2 modes. To this end, let Ω = {1, 2, . . . , D}, D 2 and fix the starting mode q 1 ∈ Ω. Introduce the switching scenario (q 1 , q 2 , . . . , q k ) ∈ Ω k . Since we exclude equal neighboring modes, i.e. q j = q j+1 , 1 j k -1, it follows that there are (D -1) k-1 ways of choosing such a switching sequence (q 1 , q 2 , . . . , q k ). For D = 2, there was only one possible sequence chosen uniquely.

For general number of modes D, we have to take into consideration the inner products corresponding to all sequences. Hence we adapt the definition of P (k) q 1 from (11) as follows

P (k) q 1 = ∞ 0 • • • ∞ 0 D q 2 =1, q 2 =q 1 . . . D q k =1, q k =q k-1 g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) T dt 1 dt 2 . . . dt k . ( 33
)
where g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) : R k + → R n q 1 ×m is defined in the exactly same way as in [START_REF] Birouche | Model reduction for discrete-time switched linear time-delay systems via the H∞ stability[END_REF], but now for the general case of D ≥ 2, i.e., g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = e A q 1 t 1 K q 2 ,q 1 e A q 2 t 2 K q 3 ,q 2

• • • K q k ,q k-1 e A q k t k B q k .
Note that the infinite integrals in [START_REF] Sandberg | Model reduction for linear time-varying systems[END_REF] are well defined, due to Assumption 21. Again, one can write a recurrence relation by fixing the mode indexes q 3 , . . . , q k , g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = D q 2 =1, q 2 =q 1 e A q 1 t 1 K q 2 ,q 1 g r q 2 ,q 3 ,...,q k (t 2 , t 3 , . . . , t k ).

Next, it follows that the k th reachability Gramian corresponding to mode q 1 can be written in terms of the (k -1) th reachability Gramians corresponding to modes Ω \ {q 1 }, as

P (k) q 1 = ∞ 0 D q 2 =1, q 2 =q 1 e A q 1 t 1 K q 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 dt 1 . (34)
Similarly, we adapt the definition of

Q (k)
q 1 from (18) as follows

Q (k) q 1 = ∞ 0 • • • ∞ 0 D q 2 =1, q 2 =q 1 . . . D q k =1, q k =q k-1 g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) T dt 1 dt 2 . . . dt k . ( 35
)
where g o q k ,...,q 2 ,q 1 (t k , . . . , t 2 , t 1 ) : R k → R p×n q 1 is defined as in [START_REF] Shaker | Model reduction of switched systems based on switching generalized gramians[END_REF], i.e.,

g o q k ,q k-1 ,...,q 1 (t k , . . . , t 2 , t 1 ) = Cq k e Aq k t k Kq k-1 ,q k e Aq k-1 t k-1 Kq k-2 ,q k-1 • • • Kq 1 ,q 2 e Aq 1 t 1 (36)
Similarly to the reachability Gramians, k th observability Gramian corresponding to mode q 1 can be written in terms of the (k-1) th observability Gramians corresponding to modes Ω\{q 1 }, as

Q (k) q 1 = ∞ 0 D q 2 =1, q 2 =q 1 (Kq 2 ,q 1 e Aq 1 t 1 ) T P (k-1) q 2 Kq 2 ,q 1 e A T q 1 t 1 dt 1 . (37)
Note that the infinite integrals in (33)- [START_REF] Shaker | Generalized gramian framework for model/controller order reduction of switched systems[END_REF] are well defined, due to Assumption 21. Again, one can write a recurrence relation by fixing the mode indexes q 3 , . . . , q k , g r q 1 ,q 2 ,...,q k (t 1 , t 2 , . . . , t k ) = D q 2 =1, q 2 =q 1 e Aq 1 t 1 Kq 2 ,q 1 g r q 2 ,q 3 ,...,q k (t 2 , t 3 , . . . , t k ).

Next, it follows that the k th reachability and observability Gramian corresponding to mode q 1 can be written in terms of the (k -1) th reachability respectively observability Gramians corresponding to modes Ω \ {q 1 }, as

P (k) q 1 = ∞ 0 D q 2 =1, q 2 =q 1 e Aq 1 t 1 Kq 2 ,q 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 dt 1 .Q (k) q 1 (38) = ∞ 0 D q 2 =1, q 2 =q 1 (Kq 2 ,q 1 e Aq 1 t 1 P (k-1) q 2 K T q 2 ,q 1 e A T q 1 t 1 dt 1 . ( 39
)
Definition 7 Define the infinite reachability Gramian corresponding to mode q 1 ∈ Ω, as

Pq 1 = ∞ k=1 P (k) q 1 . ( 40
)
Definition 8 Define the observability Gramians as

Qq 1 = D q 1 =1 Q (k) q 1 . (41)
Similarly to the case of D = 2, the question of existence of infinite reachability/observability Gramians arises. It turns out that there exist an extension of Proposition 3 to the general case D 2. Again, the justification of what we propose comes from Theorem 2 in [START_REF] Zhang | On H 2 model reduction of bilinear systems[END_REF], which addresses the existence of bilinear infinite Gramians for MIMO systems. In order to present the announced result, we need the following notation, which is an extension of (26) defined for D = 2 Let τ n k : {1, . . . , n} → {1, . . . , n} be a cyclic permutation of index k where k ∈ {0, 1, . . . , n -1}. The explicit rule is given by τ n k ( ) = mod(k + , n), ∈ {1, . . . , n}, while the permutation τ n k can also be written as,

τ n k = 1 2 . . . n mod(k + 1, n) mod(k + 2, n) . . . mod(k + n, n) , ( 42
) mod : {1, . . . , 2n-1} → {1, . . . , n}, mod(k, n) =      k, if 1 k n -1 n, if k = n k -n, if n + 1 k 2n -1 .
Introduce the permutation matrix Φ n k ∈ R n×n corresponding to τ n k , that has the th row equal to the unit vector e

T τ n k ( ),n . Note that Φ n k Φ n n-k = I n and (Φ n k ) T = Φ n n-k , k ∈ {0, .
. . , n}. For example, write

τ 3 0 = 1 2 3 1 2 3 , τ 3 1 = 1 2 3 2 3 1 , τ 3 2 = 1 2 3 3 1 2 , and Φ 3 2 =   0 0 1 1 0 0 0 1 0   .
For all X ∈ {A, B, C, P, Q} and k ∈ {1, . . . , D -1}, consider the notations

X D =      X 1 0 . . . 0 0 X 1 . . . 0 0 0 . . . 0 0 0 . . . X D      , K D k = ΦD k       K 1,τ D D-k (1) 0 . . . 0 0 K 2,τ D D-k (2) . . . 0 0 0 . . . 0 0 0 . . . K D,τ D D-k (D)       , (43) where
ΦD k ∈ R D i=1 n i × D
i=1 n i is a block-permutation matrix written in terms of Φ D k , by replacing its one entries with identity matrices I n i of appropriate dimensions. For example, choose D = 3 and k = 2, and write the matrix Φ3 2 as:

Φ3 2 =   0 0 I n 2 I n 3 0 0 0 I n 1 0   ∈ R (n 1 +n 2 +n 3 )×(n 1 +n 2 +n 3 ) .
Note that, following the definition of Φ n k , we can write that Φ3 2 = Φ n 1 +n 2 +n 3 n 1 +n 3 .

Proposition 6 Assume that

A D is stable and Γ √ 2α β , (44)
where

Γ = D-1 k=1 K D k K T D k
and the scalars α, β. α, β > 0 are such that e A D t βe -αt holds for all t ∈ R + . Then the infinite sums (33)-( 35) are absolutely convergent, and hence the reachability Gramians in [START_REF] Sandberg | Model reduction for linear time-varying systems[END_REF] and observability Grammia (41) are well-defined.

Hence, the existence of the new proposed Gramians is assured when, basically, the norm of the coupling matrices is sufficiently small. Note also that, if D = 2, the exact result from ( 27) is obtained. Note that we can generalize the results form Remark 3 and 4 for the case with D modes. Moreover, the equations satisfied by the reachability Gramians P i , for i ∈ {1, 2, . . . , D} can be extended from (28), as follows

A i P i + P i A T i + D j=1, j =i K j,i P j K T j,i + B i B T i = 0, (45)
if the condition (44) of Proposition ( 6) holds. Similarly, if the condition (44) of Proposition ( 6) holds, then the system of generalized Lyapunov equations

A T i Q i + Q i A i + D j=1, j =i K T i,j Q j K i,j + C T i C i = 0. ( 46
)
is satisfied by the matrices Q i , ∈ Ω.

Remark 7 One can rewrite the D equations stated in (45) as one equation in the following way,

A D P D + P D A T D + D-1 k=1 K D k P D K T D k + B D B T D = 0. ( 47
)
Remark 8 Similarly, we can rewrite the equations in (46) as only one equation,

A T D Q D + Q D A D + D-1 k=1 K T D k Q D K D k + C T D C D = 0. (48)
The Gramians introduced in Definition 7 and 8 are mainly going to be used for the original possibly large-scale system. In this case, we would like to avoid computing the Gramians as solutions of LMIs (as in [START_REF] Petreczky | Balanced truncation for linear switched systems[END_REF]). Additionally, we present a more relaxed definition of Gramians which will turn out to be useful for model reduction.

Definition 9 Let M > 0 be a constant The collection of matrices {P i > 0} D i=1 is said to be M -relaxed reachability Gramians, if they satisfy the following collection of LMI, ∀i ∈ {1, 2, . . . , D} :

A i P i + P i A T i + M P i + B i B T i < 0 ∀q ∈ {1, 2, . . . , D} : D i=1,i =q K i,q P i K T i,q > 0 (49)
Similarly, collection of matrices {Q i > 0} D i=1 is said to be M -relaxed reachability Gramians, if they satisfy the following collection of LMI. ∀i ∈ {1, 2, . . . , D} :

A T i Q i + Q i A i + M Q i + C T i C i < 0, ∀q ∈ {1, 2, . . . , D} : D i=1,i =q K T q,i Q i K T i,q > 0 (50)
Note that there might exist several M -relaxed reachability/observability Gramians.

Remark 9 (Relationship between Gramians and relaxed Gramians) Let {P q } D q=1 be infinite reachability Gramians according to Definition 7 and assume that for all q ∈ {1, 2, . . . , D}, D i=1,i =q K i,q P i K T i,q is strictly positive definite. Then for all q ∈ {1, 2, . . . , Q} there exists M q > 0such that D i=1,i =q K i,q P i K T i,q > M q P q and hence, by taking M = min D q=1 M q , {P q } D q=1 satisfy (49) for a suitable constant M > 0. Similarly, if {Q q } D q=1 are infinite observability Gramians according to Definition 8, and assume that for all q ∈ {1, 2, . . . , D}, D i=1,i =q K T q,i Q i K T i,q is strictly positive definite. Then there exists a constant M > 0 such that {Q q } D q=1 satisfy (50) for a suitable constant M > 0. That is, under mild assumptions, infinite reachability (resp. observability) Gramians are also M -relaxed reachability (resp. observability) Gramians for a suitable constant M > 0. Note that the converse is not necessarily true.

Main results

In this section, we will provide a collection of results that involve the new defined infinite Gramians. In particular, these results will correspond to the more general case with D discrete modes, as presented in Definition 7, 8 and 9. In this section, we will assume the following.

Assumption 51 There exist M > 0 and positive definite matrices {P q } D q=1 , {Q q } D q=1 such that they satisfy (49) -(50). In particular, if Assumption 51 holds, then the sets of M -relaxed reachability and observability Gramians are not empty. Moreover, in this case, all the linear subsystems are stable, i.e. Assumption 21 holds. Finally, if there exists infinite reachability and observability Gramians {P q } D q=1 , {Q q } D q=1 , for which D i=1,i =q K i,q P i K T i,q > 0, D i=1,i =q K T q,i Q i K T i,q > 0, for all q = 1, 2, . . . , D, then by Remark 9 they satisfy Assumption 51.

Energy bounds relating the input or output signals

First, we present the system theoretic interpretation approach; one can write upper and lower bounds of the energy of observation and respectively, of the energy of control in terms of the quantities Q i and P i .

Observability Gramians

Lemma 1 Consider an LSS Σ as defined in (1) which satisfies Assumption 51. Consider the M -relaxed observability Gramians {Q q } D q=1 from Assumption 51. Then, there exists a dwell time µ > 0 such that for any switching signal in (2), with t i µ, ∀i 1, and zero input u(t) = 0, the following holds

x(0) T Q q 1 x(0) t 0 y T (s)y(s)ds, ∀t > 0, ( 51
)
where q 1 ∈ Ω represents the index of the first discrete mode in which Σ operates.

Proof of Lemma 1. It is easy to see that K T i,j Q j K i,j , i, j = 1, . . . , D are positive semi-definite, hence there scalars γ i,j > 0 to satisfy the following inequalities

γ i,j K T i,j Q j K i,j < Q i . Introduce γ = min i,j∈Ω, i =j γ i,j and M = min i∈Ω M i .
Choose the minimal dwell times as µ = -ln γ M . For any piecewise continuous switching signal σ : R → Ω satisfying the conditions in (2) and with minimal dwell time µ, we will prove the bound stated in (51). Recall that Q q satisfies (50). Let x(t) the corresponding solution to (1), and also introduce the functions V, W : R n i → R as

V (x(t)) = x T (t)Q q 1 x(t), t ∈ [0, t 1 ) x T (t)Q q i x(t), t ∈ [T i-1 , T i ), i 2 , ( 52
) W (x(t)) = e M t x(t) T Q q 1 x(t), t ∈ [0, t 1 ) e M (t-T i-1 ) V (x(t)), t ∈ [T i-1 , T i ), i 2 , (53)
where T i = i =1 t . By considering the uncontrolled case, the input function is considered to be u(t) = 0, ∀t. Using that dx(t) dt = A q i x(t), write the derivative of

V (t) from (52) for t ∈ [T i-1 , T i ), ∂V (x(t)) ∂t = dx T (t) dt Q q i x(t) + x T (t)Q q i dx(t) dt = x T (t) A T q i Q q i + Q q i A q i x(t).
For t ∈ [T i-1 , T i ), compute the time derivative of W (x(t)) as defined in (3) in terms of the one corresponding to V (x(t)), as

∂W (x(t)) ∂t = M e M (t-T i-1 ) V (x(t)) + e M (t-T i-1 ) ∂V (x(t)) ∂t = e M (t-T i-1 ) M V (x(t)) + x T (t) A T q i Q q i + Q q i A q i x(t) = e M (t-T i-1 ) x T (t) A T q i Q q i + Q q i A q i + M Q i x(t). (54)
By substituting the inequality in (50) into the above relation (54), and using that

y(t) = C i x(t), t ∈ [T i-1 , T i ), it follows that ∂W (x(t)) ∂t -e M (t-T i-1 ) y(t) T y(t). (55)
Introduce the following notation

x(T + i ) = lim t T i x(t), V (x(T + i )) = lim t T i V (x(t)), W (x(T + i )) = lim t T i W (x(t)). (56)
By the inequality (55

) from T i-1 to t ∈ [T i-1 , T i ), it follows that W (x(t)) -W (x(T + i-1 )) - t T i-1 e M (s-T i-1 ) y(s) T y(s)ds - t T i-1
y(s) T y(s)ds.

(57) From ( 52) and (53), it follows that

W (x(T i )) = e M (T i -T i-1 ) V (x(T i )) = e M t i V (x(T i )), (58)
and additionally, using that x(T + i ) = K q i ,q i+1 x(T i ), write

W (x(T + i )) = V (x(T + i )) = x T (T i )K T q i ,q i+1 Q q i+1 K q i ,q i+1 x(T i ). ( 59
)
From (??) and (59) and using that γ = min i,j∈Ω, i =j γ i,j , write

W (x(T + i )) 1 γ x(T i ) T Q i x(T i ) = 1 γ V (x(T i )). ( 60
)
By combining ( 58) and ( 60), we can write

W (x(T + i )) e -M t i γ W (x(T i )). ( 61
)
Since switching signals σ with minimal dwell time µ are considered, it follows that

t i µ ⇒ e -M t i γ e -M µ
γ . Since, by definition µ = -ln γ M , we get that e -M t i γ 1. Therefore, from (61), write

W (x(T + i )) W (x(T i )). ( 62
)
Putting together the inequalities in ( 57) and ( 62), it follows that

W (x(T i )) -W (x(T i-1 )) - T i T i-1 y(s) T y(s)ds. ( 63
)
Now using the convention T 0 = 0 and adding all the inequalities in (63), we obtain

i=1 W (x(T i )) -W (x(T i-1 )) - i=1 T i T i-1 y(s) T y(s)ds ⇒ W (x(T )) -W (x(0)) - T 0 y(s) T y(s)ds. ( 64
)
Since W (x(T )) = e M t x T (T )Q q x(T ) 0, from (64) it follows that,

W (x(0)) T 0 y(s) T y(s)ds, ∀ 0. ( 65
)
Now using that W (x(0)) = x(0) T Q q 1 x(0), the result in (51) is hence proven.

Reachability Gramians

Lemma 2 Consider an LSS Σ as defined in (1) which satisfies Assumption 51 holds. Let {P q } D q=1 be the M -relaxed reachability Gramians from Assumption 51. Then, there exists µ > 0 such that for any switching signal in (2), with minimal dwell time µ (i.e. t i µ) and x(0) = 0, the following bound holds

x T (T )P -1 q x(T ) T 0 u T (s)u(s)ds. ( 66
)
Proof of Lemma 2. Since for every i = j ∈ Ω, K j,i P -1 j K T j,i are positive semidefinite, there exist scalars γ i,j > 0, such that γ i,j K j,i P -1 j K T j,i < P -1 i . Introduce γ = min i,j∈Ω, i =j γ i,j and let µ = -ln γ M . For any piecewise continuous switching signal σ : R → Ω satisfying the conditions in (2) and with minimal dwell time µ, we will prove the bound stated in (66). Recall that P q satisfies (49). By multiplying the inequality (49) with P -1 i both to the left and to the right, we write

A T i P -1 i + P -1 i A i + M P -1 i + P -1 i B i B T i P -1 i 0. ( 67
)
Let x(t) be the corresponding solution to (1), and also introduce the function

V : R n i → R as V (x(t)) = x T (t)P -1 q 1 x(t), t ∈ [0, t 1 ), x T (t)P -1 q i x(t), t ∈ [T i-1 , T i ), i 2 . ( 68
)
Using that ẋ(t) = A q i x(t) + B q i u(t) and the definition of V (x(t)) in ( 68), for t ∈ [T i-1 , T i ), we have

∂V (x(t)) ∂t = dx T (t) dt P -1 q i x(t) + x T (t)P -1 q i dx(t) dt = x T (t) A T q i P -1 q i + P -1 q i A q i x(t) + 2x(t) T P -1 q i B q i u(t),
and by using the inequality in (67), it follows that

∂V (x(t)) ∂t + M V (x(t)) -x(t) T P -1 q i B q i B T q i P -1 q i x(t) + 2x(t) T P -1 q i B q i u(t) = -B T q i P -1 q i x(t) -u(t) 2 2 + u(t) T u(t). (69)
Hence, the following inequality holds as,

∂V (x(t)) ∂t + M V (x(t)) u(t) T u(t), t ∈ [T i-1 , T i ). ( 70
) By denoting W (x(t)) = e M (t-T i ) V (x(t)), for t ∈ [T i-1 , T i ), it follows that ∂W (x(t)) ∂t = e M (t-T i ) ∂V (x(t)) ∂t + M V (x(t)) , (71)
and by combining ( 70) and (71) and integrating from T i-1 to t, we obtain

W (x(t)) -W (x(T + i-1 )) t T i-1 e M (s-T i ) u T (s)u(s)ds. ( 72
)
Following same line of thought as in Section 4.1.1, one can show that W (x(T + i )) W (x(T i )). By combining this statement with the inequality in (72), and by using the fact that e M (s-T i ) 1, ∀s ∈ [T i-1 , T i ), one can write

W (x(T i )) -W (x(T i-1 )) T i T i-1 e M (s-T i ) u T (s)u(s)ds T i T i-1 u T (s)u(s)ds since s -T i 0 ⇒ i=1 W (x(T i )) -W (x(T i-1 )) i=1 T i T i-1 u T (s)u(s)ds ⇒ W (x(T )) -W (x(0)) T 0 u T (s)u(s)ds. ( 73
)
Since x(0) = 0, it follows that W (x(0)) = 0. Also, from the definition of the function W, it is clear that W (x(T )) = V (x(T )) = x T (T )P -1 x(T ). Hence, from (73), we directly conclude that

x T (T )P -1 q x(T )

T 0 u T (s)u(s)ds, ∀ 1, ( 74
)
which proves the result in (66).

Balancing transformation and truncation

In this section, we introduce the procedure for model order reduction by balanced truncation, and we prove a bound of the approximation error.

Procedure 51 Let Σ = (n 1 , n 2 , . . . , n D , {(A q , B q , C q )|q ∈ Ω}, {K q i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ) be a linear switched system. A balanced realization of Σ is denoted with the similar notation Σ = (n 1 , n 2 , . . . , n D , {( Āq , Bq , Cq )|q ∈ Ω}, { Kq i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ) and can be constructed as follows 1. Compute M -relaxed reachability {P q > 0} D q=1 Gramians which satisfy (49) and M -relaxed observability Gramians {Q q > 0} D q=1 which (50). 2. Find square factor matrices U q so that P q = U q U T q . Additionally, compute the eigenvalue decomposition of the symmetric matrix U T q Q q U q , as

U T q Q q U q = V q Λ 2 q V T q ,
where Λ q is a diagonal matrix with the real entries sorted in decreasing order. 3. Construct the transformation matrices S q ∈ R n q ×n q as follows

S q = Λ 1/2 q V T q U -1 q . ( 75
)
4. The matrices corresponding to the balanced realization Σ are computed in the following way (for any q, q 1 , q 2 ∈ Ω) Āq = S q A q S -1 q , Bq = S q B q , Cq = C q S -1 q , Kq 1 ,q 2 = S q 2 K q 1 ,q 2 S -1 q 1 . (76)

Proposition 7 Condsider the matrices Pq = S q P q S T q , Qq = S -1 q T Q q S -1 q , q = 1, 2, . . . , D. Then for every q = 1, 2, . . . , D, Pq = Λ q = Qq , and { Pq } D q=1 , { Qq } D q=1 are M -relaxed reachability and observability Gramians respectively of Σ.

Proof To prove these results, proceed as follows

S q P q S T q = Λ 1/2 q V T q U -1 q U q U T q Λ 1/2 q V T q U -1 q T = Λ 1/2 q V T q V q Λ 1/2 q = Λ q ,
and similarly for the observability transformed Gramian. The following result holds for any i ∈ Ω:

Āi Λ i + Λ i ĀT i + M Λ i + Bi BT i < 0, D j=1,i =j Kj,i Λ j KT j,i > 0, ( 77
) ĀT i Λ i + Λ i Āi + M Λ i + CT i Ci < 0, D j=1, j =i KT i,j Λ j Ki,j > 0. ( 78
)
We will prove only the first inequality since the proof for the second is similar. By multiplying the equation in (49) corresponding to mode i with S i to the left and with S T i to the right, we write

S i A i P i S T i + S i P i A T i S T i + M S i P i S T i + S i B i B T i S T i < 0 ⇒ S i A i S -1 i S i P i S T i + S i P i S T i (S -1 i ) T A T i S T i + M S i P i S T i + S i B i B T i S T i < 0 ⇒ Āi Λ i + Λ i ĀT i + M Λ i + Bi BT i < 0.
Finally, if we multiply D i=1,i =j K j,i P j K T j,i > 0 by S i in the left and by S T i on the right, it follows

S i D j=1,i =j K j,i P j K T j,i S T i > 0 =⇒ D j=1,i =j (S i K j,i S -1 j )(S j P j S T j )((S -1 j ) T K T j,i S T i ) = D j=1,i =j Kj,i Λ j KT j,i > 0.
That is, (77) holds.

After the system is rewritten in the equivalent balanced realization, the next step will be to construct a reduced order system by eliminating states similar as to the linear case with no switching. One can partition the balanced realization of the original LSS Σ in the following way

Āi = Ā11 i Ā12 i Ā21 i Ā22 i , Bi = B1 i B2 i , Ci = C1 i C2 i , Ki,j = K11 i,j K12 i,j K21 i,j K22 i,j , (79)
where

Ā11 i ∈ R r i ×r i , K11 i,j R r j ×r i , B1 i ∈ R r i , C1 i ∈ R 1×r i .
The truncation orders are chosen to be less than the dimensions of the subsystems, i.e. r i n i .

Definition Consider as given an original LSS Σ and the balanced equivalent system Σ corresponding to Σ for which the system matrices are split as in (79). Let Σ = (r 1 , r 2 , . . . , r D , {( Âq , Bq , Ĉq )|q ∈ Ω}, { Kq i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ), be a reduced linear switched system for which the system matrices are written as follows

Âq = Ā11 q , Bq = B1 i , Ĉq = C1 q , Kq 1 ,q 2 = K11 q 1 ,q 2 , (80)
where r q n q and q, q 1 , q 2 ∈ Ω.

By writing the dynamics of both the original balanced system Σ and the reduced system Σ, as

ẋ(t) = Āq i x(t) + Bq i u(t), ẋ(t) = Âq i x(t) + Bq i u(t), t ∈ (T i-1 , T i ], (81)
and continuing with the transition of the state variable from mode q i to mode q i+1 at time T i again for both systems

x(T + i ) = Kq i ,q i+1 x(T i ), x(T + i ) = Kq i ,q i+1 x(T i ), ( 82
)
we finally conclude that the original output and the one corresponding to the reduced LSS are written as

ȳ(t) = Cq i x(t) = C q i x(t) = y(t), ŷ(t) = Ĉq i x(t). ( 83
)
We also partition the balanced Gramians corresponding to the system Σ as

Λ i = Λi 0 0 Λi , Λi ∈ R r i , Λi ∈ R n i -r i . (84)
By plugging in the matrices in ( 79) and (84), into the equation ( 77)-( 78), it follows that

Âi Λi + Λi ÂT i + M Λi + Bi BT i < 0 r i D j=1,i =j Kj,i Λj KT j,i > 0 r i ( 85
) ÂT i Λi + Λi Âi + M Λi + ĈT i Ĉi < 0 r i D j=1,i =j KT j,i Λj Kj,i > 0 r i . (86)
Hence, the reduced-order diagonal matrices Λi , i ∈ Ω are also M -relaxed reachability/observability Gramians of the reduced system Σ.

Error bound

In this section we present a bound on the L 2 norm of the difference between the observed outputs corresponding to the original LSS and to the reduced LSS. We will show that this bound depends on the L 2 norm of the chosen control input and on the neglected elements of the balanced reduced Gramians. Some of the derivations presented here are inspired from techniques used prior in the dissertations [START_REF] Sandberg | Model reduction for linear time-varying systems[END_REF][START_REF] Besselink | Model reduction for nonlinear control systems with stability preservation and error bounds[END_REF] and in the more recent contribution [START_REF] Benner | Dual pairs of generalized lyapunov inequalities and balanced truncation of stochastic linear systems[END_REF], that provides a bound for BT applied to stochastic systems.

We assume that all pairs of the original Gramians (P i , Q i ), defined as the solutions of the equations ( 45) and (46), are transformed through the corresponding balanced transformations V i , into (Λ i , Λ i ) where Λ i are diagonal matrices (i ∈ Ω).

Recall the inequalities (77) and (78). By multiplying the firts inequality of (77) with Λ -1 to the left and to the right, one can again write that

ĀT i Λ -1 i + Λ -1 i Āi + M Λ -1 i + Λ -1 i Bi BT i Λ -1 i < 0. (87)
From ( 87) and (78) it directly follows that the following relations hold for any vectors z and v

2( Āi z + Bi v)Λ -1 i x v 2 2 -M z T Λ -1 i z, (88)
2z T ĀT i Λ i z -Ci z 2 2 -M z T Λ i z. (89)
Next, for all i ∈ {1, 2, . . . , D}, proceed to partition the transformed Gramians Λ i

Λ i = Λi 0 0 β i , β i ∈ R. (90)
Let β = max i∈Ω β i . By splitting the state variable x(t) as x(t) = x1 (t) x2 (t) T , with

x1 (t) ∈ R n-1 , x2 (t) ∈ R, introduce real valued vectors x o (t) = x1 (t) -x(t) x2 (t) , x c (t) = x1 (t) + x(t) x2 (t) . (91)
Note that the following holds:

y(t) -ŷ(t) = C q i x o (t), t ∈ (T i-1 , T i ].
Define the function V : R n × R n → R as follows

V (x o (t), x c (t)) = x o (t) T Λ q i x o (t) + β 2 q i x c (t) T (t)Λ -1 q i x c (t), t ∈ (T i-1 , T i ]. ( 92
)
Lemma 3 The temporal derivative of the function V, as defined in (92), satisfies

∂V (x o (t), x c (t)) ∂t -M V (t) + 4β 2 u(t) 2 2 -y(t) -ŷ(t) 2 2 . ( 93
)
Proof of Lemma 3. By putting together (79), ( 80) and (81) and by using the notation in (91), we can write that

ẋo (t) = A q i x o (t) + 0 B 2 q i (t) u(t) + 0 A 21 q i (t) x(t), (94) ẋc
(t) = A q i x c (t) + 2B 2 q i u(t) - 0 B 2 q i (t) u(t) + 0 A 21 q i (t) x(t). (95)
By using (94) and the inequality in (89), one can write that

d dt xo(t) T Λq i xo(t) = 2x T o (t)Λq i xo(t) + 2 0 B 2 q i u(t) + A 21 q i x(t) T Λq i xo(t) -M x T o (t)Λq i xo(t) -Cq i xo(t) 2 2 + 2αo = -M x T o (t)Λ -1 q i xo(t) -y(t) -ŷ(t) 2 2 + 2αo, (96) where
= 0 B 2 q i u(t) + A 21 q i x(t) T Λq i 0 0 βq i x1 (t) -x(t) x2 (t) = βq i B 2 q i u(t) + A 21 q i x(t) T x2 (t) (97)
Similarly, by using (95) and the inequality in (88) for z = x c (t) and v = 2u(t) , one can show that

d dt xc(t) T Λ -1 q i xc(t) = 2 Aq i xc(t) + Bq i 2u(t) Λ -1 q i xo(t)- (98) 2 0B 2 q i u(t) + Ā21 q i x(t) T Λ -1 q i xc(t) -M x T c (t)Λ -1 q i xc(t) + 4 u(t) 2 2 -2αc,
where

αc = 0 B 2 q i u(t) + A 21 q i x(t) T Λ-1 q i 0 0 β -1 q i x1 (t) + x(t) x2 (t) = β -1 q i B 2 q i u(t) + A 21 q i x(t) T x2 (t) (99)
From ( 97) and (99), observe that α o = β 2 q i α c . Hence, by adding the inequality in (96) with the one in (98) multiplied by β 2 q i , it follows that

d dt x o (t) T Λ q i x o (t) + β 2 q i d dt x c (t) T Λ -1 q i x c (t) -M x o (t) T Λ q i x o (t) + β 2 q i x c (t) T Λ -1 q i x c (t) -y(t) -ŷ(t) 2 2 + 4β 2 q i u(t) 2 2 ,
and by using the definition of V (t) in (92), it automatically proves the result in (93).

Introduce the concatenation of the state variables and of the coupling matrices corresponding to the (balanced) original and reduced systems,

t ∈ (T -1 , T ] x(t) = x(t) x(t) ∈ R 2n q i -1 , Kq i ,q i+1 = Kq i ,q i+1 0 0 Kq i ,q i+1 ∈ R 2n q i -1×2n q i -1 .
(100) From ( 82) and (100), it follows that x(T + i ) = Kq i ,q i+1 x(T i ). Note that the function V : R n × R n → R defined in (92), can also be written as a function of x(t), as

V (x(t)) = x(t) T Rq i x(t) = x(t) x(t) T Rq i x(t) x(t) , t ∈ (T i-1 , T i ], (101)
where the matrices Rq ∈ R 2n q -1×2n q -1 are defined for any q ∈ Ω, as

Rq =   Λq 0 -Λq 0 βq 0 -Λq 0 Λq   + β 2 q    Λ-1 q 0 Λ-1 q 0 βq 0 Λ-1 q 0 Λ-1 q    =    Λq + β 2 q Λ-1 q 0 -Λq + β 2 q Λ-1 q 0 2βq 0 -Λq + β 2 q Λ-1 q 0 Λq + β 2 q Λ-1 q    . (102)
First, we present a result for one step reduction. The L 2 norm of the output error computed as the differences between the original output and the output corresponding to the reduced system is bounded by the norm of the input.

Theorem 1 Let Σ = (n 1 , n 2 , . . . , n D , {(A q , B q , C q )|q ∈ Ω}, {K q i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ) be a linear switched system. Assume that Σ satisfies Assumption 51. Let Σ be a reduced order system obtained from Σ via the proposed balancing and truncation procedure,

Σ = (n 1 -1, n 2 -1, . . . , n D -1, {( Âq , Bq , Ĉq )|q ∈ Ω}, { Kq i ,q i+1 |q i , q i+1 ∈ Ω}, x0 ).
Consider any control inputs u(t) ∈ L 2 (R m ) and denote with y(t) and ŷ(t) the outputs of the systems Σ and, respectively Σ for the zero state case (i.e., x(0) = 0). Then, there exists µ > 0 such that for any switching signal with minimal dwell time µ (i.e. t i > µ, ∀i), so that

y -ŷ 2 2β u 2 . ( 103
)
Proof of Theorem 1. Choose µ = -ln γ M as the minimal dwell time for the switching signal σ(t), where γ ∈ (0, 1) is such that γ KT q,q Rq Kq,q < Rq , q, q ∈ {1, 2, . . . , D}. Such a constant γ > 0 exists, since the matrices Rq are strictly positive definite q = 1, . . . , D.

Introduce the function

W (x(t)) = e M (t-T i-1 ) V (x(t)), for t ∈ (T i-1 , T i ]. It follows that ∂W (x(t)) ∂t = e M (t-T i-1 ) ∂V (x(t)) ∂t + M V (x(t)) . (104)
Let

Θ(t) = 4β 2 u(t) 2 2 -y(t) -ȳ(t) 2 2 .
From ( 93) and (104), we write that

∂W (x(t)) ∂t e M (t-T i-1 ) Θ(t), t ∈ (T i-1 , T i ]. (105)
Repeating the reasoning from the proof of Lemma 2, it follows that xT (T ) Rq x(T )

T 0 Θ(s)ds, ∀ 1. (106)
Since Rq > 0, then T 0 Θ(s)ds 0, ∀ 1. By allowing T → ∞ and by using the definition of the function Θ, we can write

4β 2 ∞ 0 u(s) 2 2 ds ∞ 0 y(s) -ŷ(s) 2 2 ds.
Hence, the result in (103) has been proven.

Remark 10 By partitioning the set of discrete modes in two disjoint subsets, as Ω = {1, 2, . . . , D} = Ω 1 Ω 2 , we emphasize two different cases when reducing the system Σ q ∈ Ω 1 ⇒ perform reduction by 1 of the LTI subsystem in mode q, q ∈ Ω 2 ⇒ do not change the LTI in mode q.

(107) Next, introduce the balanced Gramians corresponding to the two subsets, as

Λ = Λ 0 0 β , for ∈ Ω 1 , and Λ = Λ , for ∈ Ω 2 . ( 108
)
We that the bound in (103) still holds for the setup that was introduced in (107), as follows

y -ŷ 2 2β u 2 , β = max ∈Ω 1 β . (109)
Here, the selection of the scalar β is restricted only to diagonal Gramians corresponding to the discrete modes from Ω 1 . The proof is similar to the one just presented and will be skipped for brevity reasons.

Next, we will present a more general result by extending Theorem 1 from one step reduction to reduction to any dimension by allowing possibly different reduction levels for each active mode q ∈ Ω. Consider that the diagonal Gramians associated to the original and reduced systems can be written as

Λ q =    σ q,1 0 . . . 0 σ q,n q    ∈ R n q ×n q , Λq =    σ q,1 0 . . . 0 σ q,r q    ∈ R r q ×r q . ( 110
)
for q ∈ {1, 2, . . . , D} and σ q,1 σ q,2 . . . σ q,r q . . . σ q,n q > 0. For ∈ {1, 2, . . . , ξ}, introduce the following diagonal matrices

Λq =    σ q,1 0 . . . 0 σ q,n q -i+1    , if i n q -r q , Λq =    σ q,1 0 . . . 0 σ q,r q    , if i > n q -r q (111
) Similarly, let Âq ∈ R r q, ×r q, , Bq ∈ R r q, ×m q , Ĉq ∈ R p q ×r q, , Kq 1 ,q 2 ∈ R r q 2 , ×r q 1 , , be the (1, 1) blocks of the matrices defined in (79);

Āq = Âq , Bq = Bq , Cq = Ĉq , Kq 1 ,q 2 = Kq 1 ,q 2 . ( 112
)
for r q, = n q -, if n q -r q r q , if > n q -r q .

Definition 11 Using the matrices introduced in (112), construct the family of reduced linear switched systems { Σ | 0 ξ} with ξ = max q∈Ω (n q -r q ), as Σ = (r 1, , r 2, , . . . , r D, , {( Âq , Bq , Ĉq )|q ∈ Ω}, { Kq i ,q i+1 |q i , q i+1 ∈ Ω}, x0 ).

Note that for = 0, the element Σ0 coincides to the original LSS in balanced format, i.e. Σ0 = Σ. Moreover, when = ξ, it follows that Σξ = Σ, with Σ as introduced in Definition 13.

Proposition 8 If Σ satisfies Assumption 51, then so do { Σ | 0 ≤ ≤ ξ}.

Proof From (85) -( 86) it follows that Σ has a non-empty set of M -relaxed reachability and observability Gramians, since Λq , q = 1, 2, . . . , D are M -relaxed reachability and observability Gramians of Σ . Hence, Assumption 51 holds.

Theorem 2 Let Σ = (n 1 , n 2 , . . . , n D , {(A q , B q , C q )|q ∈ Ω}, {K q i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ) be a linear switched system and let Σ be a reduced order system obtained from Σ introduced in Definition . Assume that Σ satisfies Assumption 51. Consider the control input u ∈ L 2 (R m ) and denote with y and ŷ the outputs of the systems Σ and, respectively Σ for the zero state case (i.e., x(0) = 0). Then, there exists µ > 0 such that for any switching signal with minimal dwell time µ (i.e.

t i > µ, ∀i), so that y -ŷ 2 2β u 2 , (114)
where β = ξ =1 η , η = max n q -r q , q∈Ω σ q,n q -+1 .

Proof of Theorem 2. We start by applying the result of Theorem 1 (for one step reduction) as adapted in Remark 10 (allowing adjustable reduction levels for different modes), to Σ -1 and Σ for all ∈ {1, 2, . . . , ξ}. Consider the following two subsets of Ω,

Ω 1 = {q ∈ Ω | n q -r q }, Ω 2 = {q ∈ Ω | > n q -r q }.
Note that Σ is the result of a one-step reduction applied to Σ -1 and by Proposition 8 it satisfies Assumption 51. Next, denote with ŷ and ŷ -1 the outputs corresponding to the systems Σ and, respectively Σ -1 for input u ∈ L 2 , switching signal σ(t) with minimal dwell time µ and initial zero states. From (109), it follows that ŷ -1 -ŷ 2 2η u 2 .

(115) For = 0, the output ŷ0 coincides to the output of the original LSS in balanced format, i.e. ŷ0 = y. Furthermore, when = ξ, it follows that ŷξ = ŷ, with ŷ as in Section 4.3, i.e. the output of the reduced-order LSS Σ from Definition 13. By adding the inequalities in ( 115) for all values of in {1, . . . , ξ}, it follows that

ξ =1 ŷ -1 -ŷ 2 2 ξ =1 η u 2 ⇒ ξ =1 (ŷ -1 -ŷ ) 2 2β u 2 ⇒ ŷ0 -ŷξ 2 2β u 2 ,
which implies that the result in (114) is thus proven.

Example 1 To clarify the notation used in the proof of Theorem 2, we present a simple example for D = 3, i.e. Ω = {1, 2, 3}. Assume n q = 3, ∀q ∈ Ω and the choose reduction orders 1,3 and respectively, 2 for modes 1,2 and respectively, 3. Also, note that ξ = max q∈Ω (n q -r q ) = 2.

q 1 2 3 n q 3 3 3 r q 1 3 2 n q -r q 2 0 1 ⇒      Ω 0 1 = {1, 2, 3}, Ω 0 2 = ∅ Ω 1 1 = {1, 3}, Ω 1 2 = {2} Ω 2 1 = {1}, Ω 2 2 = {2, 3} and
r q, = 0 = 1 = 2 q = 1 3 2 1 q = 2 3 3 3 q = 3 3 2 2
The r q, represent the intermediate reduction orders for each subsystem. Moreover, the transition of the diagonal Gramians Λq for ∈ {0, 1, 2} is made as follows:

Step = 0 → At this step, write the original balanced Gramians 0 Λq = Λ q , q ∈ Ω.

0 Λ1 =   σ 1,1 0 0 0 σ 1,2 0 0 0 σ 1,3   , 0 Λ2 =   σ 2,1 0 0 0 σ 2,2 0 0 0 σ 2,3   , 0 Λ3 =   σ 3,1 0 0 0 σ 3,2 0 0 0 σ 3,3   .
Step = 1 → Error bound: ŷ0 -ŷ1 2 2 max(σ 1,3 , σ 3,3 ) u 2 .

1 Λ1 = σ 1,1 0 0 σ 1,2 , 1 Λ2 =   σ 2,1 0 0 0 σ 2,2 0 0 0 σ 2,3   , 1 Λ3 = σ 3,1 0 0 σ 3,2 .
Step = 2 → Error bound: ŷ1 -ŷ2 2 2σ 1,2 u 2 .

2 Λ1 = σ 1,1 , 2 Λ2 =   σ 2,1 0 0 0 σ 2,2 0 0 0 σ 2,3   , 2 Λ3 = σ 3,1 0 0 σ 3,2 .
By combining the two inequalities from steps 1 and 2, it follows that

y -ŷ 2 2 max(σ 1,3 , σ 3,3 ) + σ 1,2 u 2 .
Remark 11 (Choice of the model order) The idea behind the choice of the model order of the reduced system is the following. After bringing the original model to balanced form, as described in Procedure 1, we choose each integer r q in such a manner that the diagonal elements σ q,r q +1 , . . . , σ q,n q -r q are small, more precisely, such that β = ξ =1 η , η = max n q -r q , q∈Ω σ q,n q -+1 is small, where ξ = max q∈Ω (n q -r q ). The choice of the model order is not unique. First, it is determined by how much approximation error we would like, and it represents a trade-off between the order of each linear subsystem and the bound β of the estimation error. However, even if we fix the approximation error, there are several choices of the dimensions of the linear subsystems of the reduced model. For example, assume for example that we are dealing with two modes D = 2, n 1 = 5, n 2 = 3, σ 1,1 = 20, σ 1,2 = 10, σ 1,3 = 5, σ 1,4 = 0.08, σ 1,5 = 0.02 and σ 2,1 = 30, σ 2,2 = 0.9, σ 2,3 = 0.1. Then, if we set r 1 = 3 and r 2 = 3, then ξ = 2, and the guaranteed error bound is β = σ 1,4 + σ 1,5 = 0.1. However, we can achieve the same error bound by choosing r 1 = 5 and r 2 = 2. That is, the same approximation error can be achieved either by discarding 2 states in the linear system associated with mode 1, or discarding 1 state in the linear system associated with mode 2. However, if we are satisfied with an error bound β = 0.2, then we could take r 1 = 3 and r 2 = 2, i.e., we discard 2 states from the linear system associated with mode 1 and we discard 1 state from the linear system associated with mode 2. Indeed, in this case then the analytical error bound will be β = σ 1,4 + σ 1,5 + σ 2,3 + σ 2,2 = 0.2.

Using Gramians instead of M -relaxed Gramians

Computing M -relaxed Gramians requires solving LMIs and it is computationally demanding. Moreover, M -relaxed Gramians are not unqiue. Hence, instead of using M -relaxed Gramians, it could be more advantegeous to use infinite reachability and observability Gramians defined in Definition 7-8. Note that by Remark 9, if {P q } D q=1 , {Q q } D q=1 are infinite reachability and observability Gramians and

D i=1,i =q K i,q P i K T i,q > 0, D i=1,i =q K T q,i Q i K T i,q > 0
, for all q = 1, 2, . . . , D, then by Remark 9 the infinite reachability and observability Gramians are also Mrelaxed reachability and observability Gramians respectively. Hence, the balanced truncation procedure presented in Subsection 5.2 can be applied to infinite reachability and observability Gramians. More precisely, let Σ = (n 1 , n 2 , . . . , n D , {(A q , B q , C q )|q ∈ Ω}, {K q i ,q i+1 |q i , q i+1 ∈ Ω}, x 0 ) be an LSS, and let {P q } D q=1 , {Q q } D q=1 be infinite reachability and observability Gramians. Let us apply Procedure 51 to Σ using the Gramians {P q } D q=1 , {Q q } D q=1 . The balanced LSS Si is such that the matrices Pq = S q P q S T q , Qq = S -1 q T Q q S -1 q are diagonal and equal to Λ q , q = 1, 2, . . . , D. Moreover, the matrices Λ q = Pq , Qq are also infinite reachability and observability Gramians as they satisfy

Āi Λ i + Λ i ĀT i + D j=1, j =i Kj,i Λ j KT j,i + Bi BT i = 0, (116)
ĀT i Λ i + Λ i Āi + D j=1, j =i KT i,j Λ j Ki,j + CT i Ci = 0. (117)
Let Σ be the reduced LSS obtained according to the Definition 2, using the infinite reachability and observability Gramians Pq = Qq = Λ q , q = 1, 2, . . . , D. Note that the reduced Gramians Λq , q = 1, 2, . . . , D are no longer infinite reachability and observability Gramians. More precisely, they satisfy the following inequalities

Âi Λi + Λi ÂT i + D j=1, j =i Kj,i Λj KT j,i + Bi BT i < 0 r i ( 118
) ÂT i Λi + Λi Âi + D j=1, j =i KT i,j Λj Ki,j + ĈT i Ĉi < 0 r i . (119)
However, even though the reduced Gramians Λi are not infinite reachability and observability Gramians of the reduced order LSS, the error bound of Theorem 2 still applies. In fact, this was exactly the motivation behind introducing relaxed Gramians. Recall that the proof of the error bound in Theorem 2 relies on repeated application of Theorem 1 and on the fact that truncated LSS are also balanced. The latter presents an error bound for the case when only one state is discarded from each linear subsystem during the truncation step. Theorem 1 remains true even when the balanced truncation procedure is formulated only for infinite reachability/observability Gramians instead of the relaxed ones. However, if the balanced truncation was formulated only for infinite reachability and observability Gramians as opposed to relaxed reachability and observability Gramians, then repeated application of Theorem 1 would no longer be possible, as the truncated LSS would not be balanced (since the truncated matrices Λq do not satisfy the definition of infinite reachability/observability Gramians).

Stability preservation

Stability preservation is a very sought after property when devising MOR techniques. As pointed out in [START_REF] Liberzon | Switching in Systems and Control[END_REF], a switched system is stable if all individual subsystems are stable and the switching is sufficiently slow to permit the transient effects to vanish after each switching time. In this book, Chapter 3.2 presents stability under slow switching with multiple Lyapunov functions. We present a definition of stability in a uniformly exponentially sense and with imposing again the condition of a minimal dwell time µ. This definition was initially introduced in [START_REF] Liberzon | Switching in Systems and Control[END_REF]. Moreover, we will show that the reduced order models constructed through the proposed balancing reduction technique, satisfy the conditions of this particular type of stability.

Definition 12 A linear switched system Σ as described in (1), is uniformly exponentially stable with dwell time µ if there exist constants K, M > 0 such that for any solution (x, u, σ, y), the inequality holds for any t 0,

x(t) 2 Ke -αt x(0) 2 . ( 120
)
for a control input considered to be zero (i.e. u = 0) and the switching signal σ(t) having minimum dwell time µ > 0.

Lemma 4 Consider an LSS Σ which satisfies Assumption 51. There exists a constant µ > 0 such that Σ is uniformly exponentially stable with some dwell time µ.

Proof of Lemma 4. Let γ be such that γK T q 1 ,q 2 Q q 2 K q 1 ,q 2 < Q q 1 for all q 1 , q 2 ∈ {1, 2, . . . , D}. Since by Assumption 51 K T q 1 ,q 2 Q q 2 K q 1 ,q 2 > 0, such a constant γ > 0 exists. Let µ = -lnγ 2M , and hence

e -0.5M µ K T q 1 ,q 2 Q q 2 K q 1 ,q 2 < Q q 1 . (121)
Let (x, u, σ, y) be a solution of the LSS with u = 0 and switching signal σ = (q 1 , t 1 )(q 2 , t 2 ) . . . with minimum dwell time µ > 0 (i.e.

t i µ, ∀i). Again, set V(x(t)) = x T (t)Q q i x(t), ∀t ∈ (T i-1 , T i ]. From (50), it directly follows that ∂V (x(t)) ∂t -M V (x(t)). Next, introduce the function W (x(t)) = e M (t-T i-1 ) V (x(t)) = e M (t-T i-1 ) x T (t)Q q i x(t), ∀t ∈ [T i-1 , T i ),
and hence, the inequality ∂W (x(t)) ∂t 0 holds. Using the same notations as in (56), we get that W (x(t)) W (x(T

+ i-1 )) ⇒ e M (t-T i-1 ) V (x(t)) V (x(T + i-1 )). Then V (x(t)) e -M (t-T i-1 ) V (x(T + i-1 )), ∀t ∈ (T i-1 , T i ]. (122)
Now using that x(T + i-1 ) = K q i-1 ,q i x(T i-1 ), write

V (x(T + i-1 )) = x T (T i-1 )K T q i-1 ,q i Q q i K q i-1 ,q i x(T i-1 ). (123)
From ( 121) and (123), we get that

V (x(T + i-1 )) e 0.5M µ x T (T i-1 )Q i-1 x(T i-1 ) = e 0.5M µ V (x(T i-1 )). (124)
By plugging in t = T i in (122) and using (124), it follows that

V (x(T i )) e -M t i +0.5M µ V (x(T i-1 )). ( 125
)
By putting all the relations in (125) together (k ∈ {1, 2, . . . , i}), write that

V (x(T i )) e -M (t i -0.5µ) V (x(T i-1 )) e -M (t i +t i-1 -µ) V (x(T i-2 )) . . . e -M (T i -0.5iµ) V (x(0)). ( 126
)
Since t > T i-1 = i-1 k=1 t k and by using the fact that the system has minimum dwell time µ in each operational mode, i.e. t k µ, it follows that t > (i -1)µ. Furthermore, by putting together (122), ( 124) and ( 126), the results hold ∀t ∈

[T i-1 , T i ), V (x(t)) e -M (t-T i-1 ) e 0.5M µ e -M (T i-1 -(0.5i-1)µ) V (x(0)) = e -M (t-0.5(i-1)µ) V (x(0)) = e -M t e 0.5M (i-1)µ V (x(0)) = e -M t e 0.5M t V (x(0)) =e -0.5M t V (x(0)). (127)
In the last step, we used that t ≥ 0.5(i -1)µ. Choose , φ > 0 such that for all q ∈ {1, 2, . . . , D}, the following inequality holds for

2 Q q I n q φ 2 Q q . ( 128
)
Since Q q > 0, such a choice of , φ always exists. From (127) and (128), it follows that for all t ∈ (T i-1 , T i ]

x(t) 2 2 = x(t) T x(t) φ 2 x(t) T Q q i x(t) = φ 2 V (x(t)) φ 2 e -0.5M t V (x(0)) = φ 2 e -0.5M t x(0) T Q q 1 x(0) φ 2 2 e -0.5M t x(0) 2 2 .
By choosing K = φ 2 2 , α = 0.5M the result of Lemma 4 is proven (from Definition 15).

From Proposition 8 and Lemma 4 we can conclude the following.

Corollary 1 If Assumptions 51 hold for the original LSS model Σ, then Σ is exponentially stable with dwell time µ > 0, and the reduced-order LSS model Σ, defined Defininition 2, is also exponentially stable with the same dwell time µ.

6 Examples 6.1 First example -a small system with 3 modes Consider the case for which D = 3. The reachability grammmians P i , i ∈ {1, 2, 3}, satisfy the following equations

A 1 P 1 + P 1 A T 1 + K 2,1 P 2 K T 2,1 + K 3,1 P 3 K T 3,1 + B 1 B T 1 = 0, A 2 P 2 + P 2 A T 2 + K 1,2 P 1 K T 1,2 + K 3,2 P 3 K T 3,2 + B 2 B T 2 = 0, A 3 P 3 + P 3 A T 3 + K 1,3 P 1 K T 1,3 + K 2,3 P 2 K T 2,3 + B 3 B T 3 = 0.
which can be compactly written as

A D P D + P D A T D + K D 1 P D K T D 1 + K D 2 P D K T D 2 + B D B T D = 0, (129)
where A D , B D and P D are as in [START_REF] Pernebo | Model reduction via balanced state space representation[END_REF] and also

K D 1 =   0 K 2,1 0 0 0 K 3,2 K 1,3 0 0   , K D 2 =   0 0 K 3,1 K 1,2 0 0 0 K 2,3 0   . (130)
Similarly, the observability grammmians Q i , i ∈ {1, 2, 3}, satisfy the following equations

A T 1 Q 1 + Q 1 A 1 + K T 1,2 Q 2 K 1,2 + K T 3,1 Q 3 K T 3,1 + C T 1 C 1 = 0, A T 2 Q 2 + Q 2 A 2 + K T 2,1 Q 1 K 1,2 + K T 2,3 Q 3 K 2,3 + C T 2 C 2 = 0, A T 3 Q 3 + Q 3 A 3 + K T 3,1 Q 1 K 3,1 + K T 3,2 Q 2 K 3,2 + C T 3 C 3 = 0,
which can also be compactly written as

A T D Q D + Q D A D + K T D 1 Q D K D 1 + K T D 2 Q D K D 2 + C T D C D = 0, (131)
where A D , C D and Q D are block diagonal as in [START_REF] Zhang | H-infinity model reduction for uncertain switched linear discrete-time systems[END_REF] and K D i as in (130) for i ∈ {1, 2}. Choose the following system matrices for Σ, as

A 1 =   -1 0 0 0 -8 0 0 0 -5   , A 2 =   -2 0 0 0 -9 0 0 0 -6   , A 3 =   -4 0 0 0 -3 0 0 0 -7   , B 1 =   1 2 -1   , B 2 =   1 -1 3 2   , B 3 =   -1 2 -2 1   ,            C 1 = -1 1 5 2 , C 2 = 1 2 -7 2 , C 3 = -3 2 1 -1 2 , M =   1 -1 0 0 2 -3 1 0 1 2   , N =   0 2 -1 2 1 1 -1 0 0 -3   ,    K 1,2 = M/7, K 2,3 = M/4, K 3,1 = M/6, K 2,1 = N/5, K 3,2 = N/3, K 1,3 = N/2.
Next, compute the balanced diagonal Gramians Λ i as, As for Example 4.1, consider the values of the reduced orders for the three subsystems, as r 1 = 1, r 2 = 3 and r 3 = 2. We recover the system matrices of the reduced LSS Σ as, From Example 4.1, it follows that the following bound holds, i.e. yŷ 2 2 max(σ 1,3 , σ 3,3 ) + σ 1,2 u 2 = 2(0.0816 + 0.0419) = 0.2471 u 2 .

Consider the switching signal σ(t) depicted in Fig. 1, which is characterized by the sequence of elements (1, t 1 )(3, t 2 )(1, t 3 )(2, t 4 ) . . . (2, t 9 )(3, t 10 ) with dwell times t 0 = 0s and t 10 = 15s. By choosing the control input as u(t) = 1/2 sin(20t)e -t/2 + 1/20e -t/2 , and performing a time domain simulation, we display in Fig. 1, the outputs of the original and reduced systems Σ and Σ. The absolute value of the difference between the two outputs is presented in Fig. 2. For the next experiment, consider the CD player system from the SLICOT benchmark examples for MOR (see [START_REF] Chahlaoui | A collection of benchmark examples for model reduction of linear time invariant dynamical systems[END_REF]). This linear system of order 120 has two inputs and two outputs. We consider that, at any given instance of time, only one input and one output are active (the others are not functional due to mechanical failure). For instance, consider mode j to be activated whenever the j th input and the j th output are simultaneously failing (where j ∈ {1, 2}).

In this way, we construct an LSS system with two operational modes. Both subsystems are stable SISO linear systems of order 120, i.e. we can write n 1 = n 2 = 120. This initial linear switched system (which will be denoted with Σ) is reduced by means of the new balanced truncation procedure (which we refer to in the following as BT1) to obtain ΣBT 1 and also by means of the balancing method proposed in [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF] (which we refer to in the following as BT2) to obtain ΣBT 2 . In the later reference, it has been shown that, if certain conditions are satisfied (see Corollary IV.3 in [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF]), a simultaneous balanced truncation technique can be applied to LSS. In most practical examples, the existence of a global transformation matrix is not guaranteed. Hence, in [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF], the authors propose instead a method of balancing the so-called average Gramians, i.e. P avg = 1 D D i=1 P i and

Q avg = 1 D D i=1 Q i .
We first proceed with a frequency domain simulation. By varying the frequency variable ω in the interval [10 0 , 10 6 ]rad/sec, we compute the frequency response corresponding to mode j ∈ {1, 2}, i.e. the magnitude of the function H j = C j (ωI n j -A j ) -1 B j , in the specified frequency range. The frequency response of the two original subsystems is depicted in Fig. 3. Next, we compute reduced order models using both of the reduction methods discussed above, i.e. BT1 and BT2. The truncation orders for the reduced systems are chosen to be the same for each mode, i.e k 1 = k 2 = 33. In Fig. 2, we depict the magnitude of the frequency domain approximation error between the original system Σ and the reduced ones, i.e.

ΣBT 1 and ΣBT 2 . The figure presents the error for each mode, separately.

Let Σ j be the subsystem of the LSS Σ that corresponds to mode j ∈ {1, 2}, as introduced in (7). The same applies for the notations ΣBT Error in frequency domain -mode 2

BT1 BT2

Fig. 4 Approximation error in frequency domain denote the mode j subsystem corresponding to the LSS ΣBT 1 and, respectively, to the LSS ΣBT 2 .

Next, for both reduction methods, we compute the relative approximation errors for both modes. This is performed with respect to the H κ norm, where κ ∈ {2, ∞}. More specifically, the value of ΣBT 1 j -Σ j H κ / Σ j H κ is calculated for the BT1 method, while ΣBT 2 j -Σ j H κ / Σ j H κ is calculated for the BT2 method.

The numerical results are presented in Tab. 1. Note that, for both types of norms and for each of the two operational modes, the balanced truncation method we propose produces lower errors than those of the one introduced in [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF]. Table 1 Relative approximation error for the two modes in the H 2 and H∞ norms As for the first example, we compare the time domain response of the original linear switched system with the ones corresponding to the two reduced models. We use the same signal as in Section 5.1 as control input, i.e. u(t) = 1/2 sin(20t)e -t/2 + 1/20e -t/2 . The switching times t i are randomly chosen within [0,10]sec so that t i > 0.5sec, ∀i.

The switching signal σ is depicted in the upper part of Fig. 5, while in the lower part of Fig. 5, the outputs of the three LSS (original one and the two reduced ones) are displayed.

Notice that the output of the original system Σ is well approximated when using any of the two MOR methods.

Finally, by inspecting the time domain error between the original response and the one corresponding to the two reduced models (depicted in Fig. 6), observe that the new proposed method generally produces better results. The error curve corresponding to the BT1 method is below the error curve corresponding to the BT2 method for most of the points on the time axis.

We conclude that the new proposed balancing method produces better results than the one proposed in [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF], in the sense that the original output is better approximated for this particular choice of LSS and control input. Moreover, our Error Output error between the original system and the reduced ones

BT1 BT2
Fig. 6 Time domain approximation error method can be applied to LSS with subsystems having different dimensions n i , i ∈ Ω and provide reduced order models again with possibly different dimensions r i , i ∈ Ω in different modes. The other method is constrained to having n 1 = . . . = n D so that the computation of the average Gramians P av and Q av is possible. Also, for BT2 it is assumed that a common Lyapunov function exists, which is arguably restrictive. Moreover, another advantage is that one can derive an error bound of the output error for the new proposed method, as presented in Section 4.2.1. This is also true for the second method proposed in [START_REF] Monshizadeh | A simultaneous balanced truncation approach to model reduction of switched linear systems[END_REF].

Conclusion

In the current work, we have proposed a balanced truncation procedure for the class of linear switched systems which is based on the computation of infinite energy Gramians. These special matrices can be computed by solving generalized Lyapunov equations instead of solving systems of LMIs. The new balancing method has several advantages. We provided connections between the new Gramians and system theoretical quantities (observation and energy), by means of lower or upper bounds. Moreover, it turned out that an error bound involving the inputs, outputs and the truncated entries of the Gramians, could be derived. Finally, by applying the proposed procedure, the reduced order LSS can be proven to be uniformly exponentially stable with certain minimum dwell time, given that the original LSS also had this property.

Fig. 1

 1 Fig.1Switching signal σ(t) and output y(t) corresponding to both Σ and Σ

4 Fig. 2

 42 Fig. 2 Absolute value of the output error: |y -ŷ|

Fig. 3

 3 Fig. 3 Frequency response of the original subsystems

  Fig. 5 Time domain simulation

Note that if A D is stable, then there always exist constants α, β > 0 such that e A D t βe -αt holds