Mihály Petreczky
email: mihaly.petreczky@centralelille.fr

Laurent Bako
email: laurent.bako@ec-lyon.fr

On the notion of persistence of excitation for linear switched systems

The paper formulates the concept of persistence of excitation for discrete-time linear switched systems, and provides sufficient conditions for an input signal to be persistently exciting. Persistence of excitation is formulated as a property of the input signal, and it is not tied to any specific identification algorithm. The results of the paper rely on realization theory and on the notion of Markov-parameters for linear switched systems.

Introduction

The paper formulates the concept of persistence of excitation for discrete-time linear switched systems (abbreviated by DTLSSs). DTLSSs are one of the simplest and best studied classes of discrete-time switched systems, [START_REF] Sun | Switched linear systems : control and design[END_REF].

A DTLSS is a discrete-time switched system, such that the continuous sub-system associated with each discrete state is linear. The switching signal is viewed as an external input, and all linear systems live on the same input-output-and state-space.

We define persistence of excitation for input signals. More precisely, we will call an input signal persistently exciting for an input-output map, if the response of the input-output map to that particular input determines the input-output map uniquely. In other words, the knowledge of the output response to a persistently exciting input should be sufficient to predict the response to any input.

Persistence of excitation is essential for system identification and adaptive control. Normally, in system identification the system of interest is tested only for one input sequence. One of the reason for this is that our notion of the system entails a fixed initial state. However, any experiment changes that particular initial state and it is in general not clear how to reset the system to a particular initial state. The objective is to find a system model based on the response to the chosen input. However, the knowledge of a model of the system (including the initial state) immediately implies that the response of the system to any input is known. Hence, intuitively it is clear that persistence of excitation of the input signal is a prerequisite for a successful identification of a model.

Note that persistence of excitation is a joint property of the input and of the input-output map. That is, a particular input might be persistently exciting for a particular system and might fail to be persistently exciting for another system. In fact, it is not a priori clear if any system admits a persistently exciting input. This calls for investigating classes of inputs which are persistently exciting for some broad classes of systems.

In the existing literature, persistence of excitation is often defined as a specific property of the measurements which is sufficient for the correctness of some identification algorithm. In contrast, in this paper we propose a definition of persistence of excitation which is necessary for the correctness of any identification algorithm. Obviously, the two approaches are complementary. In fact, we hope that the results of this paper can serve as a starting point to derive persistence of excitation conditions for specific identification algorithms.

Contribution of the paper

We define persistence of excitation for finite input sequences and persistence of excitation for infinite input sequences.

We show that for every input-output map which is realizable by a reversible DTLSS, there exists a finite input sequence which is persistently exciting for that particular input-output map. A reversible DTLSS is a DTLSS such that its continuous dynamics is invertible. Such systems arise naturally by sampling continuous-time systems. In addition, we define the class of reversible input-output maps and show that there is a finite input sequence which is persistently exciting for all the input-output maps of that class. Moreover, we present a procedure for constructing such an input sequence.

We show that there exists a class of infinite input sequences which are persistently exciting for all the input-output maps which are realizable by a stable DTLSS. The conditions which the input sequence must satisfy is that each subsequence occurs there infinitely often (i.e. the switching signal is rich enough) and that the continuous input is a colored noise. Hence, this result is consistent with the classical result for linear systems.

It might be appealing to interpret the conditions above as ones which ensure that one stays in every discrete mode long enough and the continuous input is persistently exciting in the classical sense. One could then try to identify the linear subsystems separately and merge the results. Unfortunately, such an interpretation is in general incorrect. The reason for this is that there exists a broad class of input-output maps which can be realized by a linear switched system but not by a switched system whose linear subsystems are minimal, [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF]. The above scheme obviously would not work for such systems. In fact, for such systems one has to test the system's response not only for each discrete mode, but for each combination of discrete modes.

The main idea behind the definition of persistence of excitation and the subsequent results is as follows. From realization theory [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF] we know that the knowledge of (finitely many) Markovparameters of the input-output map is sufficient for computing a DTLSS realization of that map. Hence, if the response of the input-output map to a particular input allows us to compute the necessary Markov-parameters, then we can compute a DTLSS representation of that map. This can serve as a definition of persistence of excitation. We call an input sequence persistently exciting, if the Markov-parameters of the input-output map can be computed from the response of the map to that input. We call an infinite sequence input persistently exciting, if from a large enough finite initial part of the response one can compute an arbitrarily precise approximation of the Markovparameters. Since the realization algorithm for DTLSS is continuous in the Markov-parameters, it means that a persistently exciting infinite input sequence allows the computation of an arbitrarily precise approximation of a DTLSS realizing the input-output map.

Motivation of the system class The class of DTLSSs is the simplest and perhaps the best studied class of discrete-time switched systems.

In addition to its practical relevance, it also serves as a convenient starting point for theoretical investigations. In particular, any piecewise-affine hybrid system can be viewed as a feedback interconnection of a DTLSS with an event generating device. Hence, identification of a piecewiseaffine system is related to the problem of closed-loop identification of a DTLSS. For the latter, it is indispensable to have a good notion of persistence of excitation. For this reason, we believe that the results of the paper will be relevant not only for identification of DTLSSs, but also for identification of piecewise-affine hybrid systems with autonomous switching.

Related work Identification of hybrid systems is an active research area, with several significant contributions, without claiming completeness see [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Ma | Identification of deterministic switched arx systems via identification of algebraic varieties[END_REF][START_REF] Hashambhoy | Recursive identification of switched ARX models with unknown number of models and unknown orders[END_REF][START_REF] Ma | A closed form solution to the identification of hybrid ARX models via the identification of algebraic varieties[END_REF][START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Juloski | Comparison of four procedures for the identification of hybrid systems[END_REF][START_REF] Ferrari-Trecate | A clustering technique for the identification of piecewise-affine systems[END_REF][START_REF] Juloski | A bayesian approach to identification of hybrid systems[END_REF][START_REF] Juloski | Observer design and identification methods for hybrid systems: Theory and experiments[END_REF][START_REF] Hashambhoy | Recursive identification of switched ARX models with unknown number of models and unknown orders[END_REF][START_REF] Bako | Identification of switched linear state space models without minimum dwell time[END_REF][START_REF] Bako | Online structured subspace identification with application to switched linear systems[END_REF][START_REF] Roll | Identification of piecewise affine systems via mixed-integer programming[END_REF][START_REF] Fox | Bayesian nonparametric learning of complex dynamical phenomena[END_REF][START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF][START_REF] Paoletti | Input/ouput realization of piecewise affine state space models[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Lauer | Hybrid System Identification: Theory and Algorithms for Learning Switching Models[END_REF][START_REF] Breschi | Learning hybrid models with logical and continuous dynamics via multiclass linear separation[END_REF] and the references therein. While enormous progress was made in terms of efficient identification algorithms, the fundamental theoretical limitations and properties of these algorithms are still only partially understood.

In particular, there are few results on consistency of system identification algorithms, i.e., [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF][START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF], and the ones which are available tend to concentrate on switched ARX systems [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF].

The papers [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF] impose conditions on the measured data, i.e., inputs, outputs, (possibly switching signals), which are sufficient for consistency of some system identification algorithm. These conditions could be viewed as persistence of excitation conditions, and they are referred to as such in some of the cited papers. In particular, the papers [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF] impose conditions on the measured data which ensures that there are no multiple switched ARX models which fit the data. However, this approach cannot be extended to state-space representations, as they are never unique: application of a state-space isomorphism always yields a state-space representation which is different from the original one but generates exactly the same data. The paper [START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF] imposes a condition that certain matrices formed by the underlying hidden states are full rank.

The common drawback of the conditions of the papers [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF][START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF] is that these conditions do not depend only on the input and switching sequence, but also on the output and even the underlying unobserved state. However, it is not clear how to design the system identification experiment so that the generated data satisfies those conditions: even if the inputs can be chosen arbitrarily, there are no guarantees that the resulting output will satisfy those persistence of excitation conditions. That is, the definition of persistence of excitation proposed in the cited literature does not possess one important feature of the traditional definitions of persistence of excitation, namely, the existence of a suitable input guaranteeing that the data from the system identification experiment is persistently exciting. This means that the conditions of [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF][START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF] are not directly helpful for designing system identification experiments. In principle, it could not be excluded that in general it is not possible to design good system identification experiments which would result in persistently exciting data as defined in [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Vidal | Recursive identification of switched ARX systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Hiskens | Identifiability of hybrid system models[END_REF][START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF][START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF][START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF].

Fortunately, the results of the paper show that this is not the case, and it is possible to design system identification experiments which generate rich enough data for identification. That is, the main contribution of the present paper with respect to the existing literature lies in proving formally that for linear switched state-space models it is possible to design a system identification experiment which is persistently exciting, i.e., which allows the design of consistent system identification algorithms. By designing a system identification experiment we mean choosing an input and a switching signal. In other words, we show that for any linear switched system satisfying some mild conditions, there exists a switching signal and an input which allows us to identify the system parameters. To the best of our knowledge, this result is new.

For linear systems, persistence of excitation has thoroughly been investigated, see for example [START_REF] Ljung | System Identification: Theory for the user[END_REF][START_REF] Willems | A note on persistency of excitation[END_REF] and the references therein.

The paper is an extension of [START_REF] Petreczky | On the notion of persistence of excitation for linear switched systems[END_REF]. The main difference with respect to [START_REF] Petreczky | On the notion of persistence of excitation for linear switched systems[END_REF] is that the present paper contains detailed proofs and the presentation has been improved. A preliminary version of this paper appeared in the form of a technical report [START_REF] Petreczky | On the notion of persistence of excitation for linear switched systems[END_REF].

Outline of the paper §2 presents the formal definition of DTLSSs and it formulates the major system-theoretic concepts for this system class. §3 presents a brief overview of realization theory for DTLSSs. §4 presents the main contribution of the paper. Notation 1. Denote by N the set of natural numbers including 0. The notation described below is standard in automata theory, see [START_REF] Gécseg | Algebraic theory of automata[END_REF][START_REF] Eilenberg | Automata, Languages and Machines[END_REF]. Consider a set X which will be called the alphabet. Denote by X * the set of finite sequences of elements of X. Finite sequences of elements of X are referred to as strings or words over X. Each non-empty word w is of the form w = a 1 a 2 • • • a k for some a 1 , a 2 , . . . , a k ∈ X. The element a i is called the ith letter of w, for i = 1, . . . , k and k is called the length of w. We denote by the empty sequence (word). The length of word w is denoted by |w|; note that | | = 0. We denote by X + the set of non-empty words, i.e. X + = X * \ { }. We denote by wv the concatenation of word w ∈ X * with v ∈ X * . For each j = 1, . . . , m, e j is the jth unit vector of R m , i.e. e j = (δ 1,j , . . . , δ n,j ), δ i,j is the Kronecker symbol.

Linear switched systems

In this section we present the formal definition of DTLSSs along with a number of relevant system-theoretic concepts for DTLSSs . Definition 1. Recall from [START_REF] Petreczky | Identifiability of discrete-time linear switched systems[END_REF] that a discrete-time linear switched system (abbreviated by DTLSS), is a discrete-time control system of the form

Σ x t+1 = A qt x t + B qt u t y t = C qt x t . (1)
Here Q = {1, . . . , D} is the finite set of discrete modes, D is a positive integer, q t ∈ Q is the switching signal, u t ∈ R is the continuous input, y t ∈ R p is the output and A q ∈ R n×n , B q ∈ R n×m , C q ∈ R p×n are the matrices of the linear system in mode q ∈ Q.

Notation 2. We will use Σ = (n, {A q , B q , C q } q∈Q ) as a short-hand notation for a DTLSS Σ of the form (1).

Throughout the section, Σ denotes a DTLSS of the form [START_REF] Sun | Switched linear systems : control and design[END_REF]. The inputs of Σ are the continuous inputs {u t } ∞ t=0 and the switching signal {q t } ∞ t=0 . The state of the system at time t is x t . Note that any switching signal is admissible and that the initial state is assumed to be zero. We use the following notation for the inputs of Σ.

Notation 3 (Hybrid inputs). Denote U = Q × R m .
We denote by U * (resp. U + ) the set of all finite (resp. finite and non-empty) sequences of elements of U.

Notation 4 (Concatenation of hybrid inputs). In order to avoid confusion with the notation for concatenation of finite sequences of discrete modes, we will use the symbol to denote the concatenation of two sequences from U * . The concatenation operation on U * is the same as the standard one used for finite sequences of the elements of an arbitatry set, see Notation 1.

In particular, any element w of U + can be represented as the concatenation of some elements (q 0 , u 0 ), . . . , (q t , u t ) of U for some t ≥ 0, i.e.,

w = (q 0 , u 0 ) (q 1 , t 1 ) • • • (q t , u t ) (2)
The input w from (2) describes the scenario, when the discrete mode q i and the continuous input u i are fed to Σ at time i, for i = 0, . . . , t.

Next, we define the state and output of (1), if the latter is started from some initial state.

Definition 2 (State and output). Consider a state x init ∈ R n . For any w ∈ U + of the form (2), denote by x Σ (x init , w) the state of Σ at time t + 1, and denote by y Σ (x init , w) the output of Σ at time t, if Σ is started from x init and the inputs {u i } t i=0 and the discrete modes {q i } t i=0 are fed to the system.

That is, x Σ (x init , w) is defined recursively as follows; x Σ (x init , ) = x init , and if w = v (q, u) for some (q, u) ∈ U, v ∈ U * , then

x Σ (x init , w) = A q x Σ (x init , v) + B q u. If w ∈ U + and w = v (q, u), (q, u) ∈ U, v ∈ U * , then y Σ (x init , w) = C q x Σ (x init , v).
We will call Σ observable, if for any two distinct initial states x 1 , x 2 ∈ R n , x 1 = x 2 , there exists an input w ∈ U + (w being possibly dependent on x 1 and x 2 ), such that y Σ (x 1 , w) = y Σ (x 2 , w). We say that Σ is reachable from the initial state x init , if the reachable set {x Σ (x init , w) | w ∈ U * } equals R n . We say that Σ is span-reachable from the initial state x init , if the linear span of the reachable set {x Σ (x init , w) | w ∈ U * } equals R n . Note that reachability from an initial state implies span-reachablity. We say that Σ is controllable, if for any initial state x init there exists an input w = w(x init ) ∈ U + , such that x Σ (x init , w) = 0, i.e., if any state of Σ can be driven to zero. From [START_REF] Sun | Switched linear systems : control and design[END_REF] it follows that if the matrix A q is invertable for all q ∈ Q, then Σ is controllable, if and only if it is reachable from the initial state zero. Moreover, for such systems a state is either reachable from zero, or cannot be influenced by continuous inputs.

So far we have defined states and outputs generated from a certain initial state. In order to define the input-output behavior of a DTLSS, we have to either fix an initial state, or consider the input-output behavior induced by all initial states. The latter approach is more elegant, but it requires elements of the behavioral approach and the corresponding realization theory. Moreover, this approach is less common for system identification, as typical system identification experiments involve output responses generated from one single initial state. For this reason, we will fix an initial state when defining the input-output behavior of a DTLSS.

In order to simplify the discussion, in the sequel we will consider DTLSSs with zero initial state. This assumption allows us to avoid technical and notational complications. In addition to simplicity, there are other arguments in favor of assuming zero initial state. First, from a practical point of view, this assumption can be made for stable DTLSSs without loss of generality, as for such systems the effect of the non-zero initial state on the measured output response will not be detectable in the long run. In turn, identification of unstable state-space representations is known to be problematic in practice, even for the linear case. Another argument in favor of zero initial state is that for DTLSSs for which the matrices A q , q ∈ Q are invertable controllability implies reachability from the zero initial state. More precisely, state components which are not reachable from the zero initial state cannot be influenced by continuous inputs. In turn, for controllable DTLSS, the input-output behavior from any non-zero initial state can be viewed as the shifted behavior of the input-output behavior induced by the zero initial state.

Most of the results of this paper hold only for DTLSSs with zero initial state. We will discuss possible extensions to the case of non-zero initial state, when applicable.

Definition 3 (Input-output map). The map f Σ : U + → R p , ∀w ∈ U + : f Σ (w) = y Σ (0, w), is called the input-output map of Σ.
That is, the input-output map of Σ maps each sequence w ∈ U + to the output generated by Σ under the hybrid input w, if started from the zero initial state. The definition above implies that the input-output behavior of a DTLSS can be formalized as a map

f : U + → R p . (3)
The value f (w) for w of the form (2) represents the output of the underlying black-box system at time t, if the continuous inputs {u i } t i=0 and the switching sequence {q i } t i=0 are fed to the system. Next, we define when a general map f of the form (3) is adequately described by the DTLSS Σ, i.e. when Σ is a realization of f . Definition 4 (Realization). The DTLSS Σ is a realization of an input-output map f of the form (3), if f equals the input-output map of Σ, i.e. f = f Σ .

In order to be coherent with our choice of zero initial state, in the sequel we will use the following terminology: we will say that a DTLSS Σ is reachable respectively span-reachable, if it is reachable respectively span-reachable from the zero initial state.

Finally, in the sequel we will need the notions of dimension, minimality and isomorphism, which will be recalled below, for a more complete discussion on these concepts, see [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF]. Definition 5 (Dimension). The dimension of Σ, denoted by dim Σ, is the dimension n of its state-space. Definition 6 (Minimality). Let f be an input-output map. Then Σ is a minimal realization of f , if Σ is a realization of f , and for any DTLSS Σ which is a realization of f , dim Σ ≤ dim Σ.

Definition 7 (DTLSS isomorphism). Consider a DTLSS Σ 1 of the form (1) and a DTLSS Σ = (n, { Âq , Bq , Ĉq } q∈Q ). An invertable n × n matrix S is said to be an isomorphism from Σ to Σ, if ∀q ∈ Q : SA q S -1 = Âq , Bq = SB q , C q S -1 = Ĉq .

If there exists an isomorphism from Σ to Σ, then Σ and Σ are said to be isomorphic.

Overview of realization theory

Below we present an overview of the results on realization theory of DTLSSs along with the concept of Markov-parameters. For more details on the topic see [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF]. In the sequel, Σ denotes a DTLSS of the form (1), and f denotes an input-output map f :

U + → R p .
For our purposes the most important result is the one which states that a DTLSS realization of f can be computed from the Markov-parameters of f . In order to present this result, we need to define the Markov-paramaters of f formally. Denote Q k, * = {w ∈ Q * | |w| ≥ k}. Define the maps S f j : Q 2, * → R p , j = 1, . . . , m as follows; for any v = σ 1 . . . σ |v| ∈ Q * with σ k ∈ Q, and for any q, q 0 ∈ Q,

S f j (q 0 vq) = f (q 0 , e j ) (q, 0) if v = f (q 0 , e j ) (σ 1 , 0) . . . (σ |v| , 0) (q, 0) if |v| ≥ 1 (4)
with e j ∈ R m is the vector with 1 as its jth entry and zero everywhere else. Define

S f (v) = S f 1 (v) . . . S f m (v) ∈ R p×m for all v ∈ Q * . The collection of values {S f (v)} v∈Q * is called the Markov-parameters of f .
The functions S f j , j = 1, . . . , m can be viewed as input responses. The interpretation of S f j will become more clear after we define the concept of a generalized convolution representation. Note that the values of the Markov-parameters can be obtained from the values of f . Definition 8 (Convolution representation). The input-output map f has a generalized convolution representation (abbreviated as GCR), if for all w ∈ U + of the form (2), f (w) can be expressed via the Markov-parameters of f as follows:

f (w) = t-1 k=0 S f (q k q k+1 • • • q t )u k Remark 1. If f has a GCR, then the Markov-parameters of f determine f uniquely.
The motivation for introducing GCRs is that existence of a GCR is a necessary condition for realizability by DTLSSs. Moreover, if f is realizable by a DTLSS, then the Markov-parameters of f can be expressed as products of the matrices of its DTLSS realization. In order to formulate this result more precisely, we need the following notation. Notation 5. Consider the collection of n × n matrices A σ , σ ∈ X. For any w ∈ Q * , the n × n matrix A w is defined as follows. If w = , then A is the identity matrix.

If w = σ 1 σ 2 • • • σ k ∈ X * , σ 1 , • • • σ k ∈ X, k > 0, then A w = A σ k A σ k-1 • • • A σ1 . (5)
Lemma 1. The map f is realized by the DTLSS Σ if and only if f has a GCR and for all v ∈ Q * , q, q 0 ∈ Q,

S f j (q 0 vq) = C q A v B q0 e j , j = 1, . . . , m. (6)
Next, we define the concept of a Hankel-matrix. Similarly to the linear case, the entries of the Hankel-matrix are formed by the Markov parameters. For the definition of the Hankel-matrix of f , we will use lexicographical ordering on the set of sequences Q * .

Remark 2 (Lexicographic ordering). Recall that Q = {1, . . . , D}. We define a lexicographic ordering ≺ on Q * as follows. For any v, s ∈ Q * , v ≺ s if either |v| < |s| or 0 < |v| = |s|, v = s and for some l ∈ {1, . . . , |s|}, v l < s l with the usual ordering of integers and v i = s i for i = 1, . . . , l -1. Here v i and s i denote the ith letter of v and s respectively. Note that ≺ is a complete ordering and

Q * = {v 1 , v 2 , . . .} with v 1 ≺ v 2 ≺ . . .. Note that v 1 = and for all i ∈ N, q ∈ Q, v i ≺ v i q.
In order to simplify the definition of a Hankel-matrix, we introduce the notion of a combined Markov-parameter.

Definition 9 (Combined Markov-parameters). A combined Markov

-parameter M f (v) of f indexed by the word v ∈ Q * is the following pD × Dm matrix M f (v) =      S f (1v1), • • • , S f (Dv1) S f (1v2), • • • , S f (Dv2) . . . • • • . . . S f (1vD), • • • , S f (DvD)      (7)
Definition 10 (Hankel-matrix). Consider the lexicographic ordering ≺ of Q * from Remark 2. Define the Hankel-matrix H f of f as the following infinite matrix

H f =      M f (v 1 v 1 ) M f (v 2 v 1 ) • • • M f (v k v 1 ) • • • M f (v 1 v 2 ) M f (v 2 v 2 ) • • • M f (v k v 2 ) • • • M f (v 1 v 3 ) M f (v 2 v 3 ) • • • M f (v k v 3 ) • • • . . . . . . • • • . . . • • •      ,
i.e. the pD × (mD) block of H f in the block row i and block column j equals the combined Markovparameter M f (v j v i ) of f . The rank of H f , denoted by rankH f , is the dimension of the linear span of its columns.

The main result on realization theory of DTLSSs can be stated as follows.

Theorem 1 ([2]

).

1. The map f has a realization by a DTLSS if and only if f has a GCR and rankH f < +∞. 2. A minimal DTLSS realization of f can be constructed from H f and any minimal DTLSS realization of f has dimension rankH f . 3. A DTLSS Σ is a minimal realization of f if and only if Σ is span-reachable, observable and it is a realization of f . Any two DTLSSs which are minimal realizations of f are isomorphic.

Note that Theorem 1 shows that the knowledge of the Markov-parameters is necessary and sufficient for finding a state-space representation of f . In fact, similarly to the continuous-time case [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF], we can even show that the knowledge of finitely many Markov-parameters is sufficient. This will be done by formulating a realization algorithm for DTLSSs, which computes a DTLSSs realization of f based on finitely many Markov-parameters of f .

In order to present the realization algorithm, we need the following notation. Notation 6. Consider the lexicographic ordering ≺ of Q * and recall that

Q * = {v 1 , v 2 , . . . , } where v 1 ≺ v 2 • • • . Denote by N(L) the number of sequences from Q * of length at most L. It then follows that |v i | ≤ L if and only if i ≤ N(L). Definition 11 (H f,L,M sub-matrices of H f ). For L, K ∈ N define the integers I L = N(L)pD and J K = N(K)mD Denote by H f,L,K the following upper-left I L × J K sub-matrix of H f ,      M f (v 1 v 1 ) M f (v 2 v 1 ) • • • M f (v N(K) v 1 ) M f (v 1 v 2 ) M f (v 2 v 2 ) • • • M f (v N(K) v 2 ) . . . . . . • • • . . . M f (v 1 v N(L) ) M f (v 2 v N(L) ) • • • M f (v N(K) v N(L) )      .
Notice that the entries of H f,L,K are Markov-parameters indexed by words of length at most

L + K, i.e. H f,L,K is uniquely determined by {M f (v i )} N(L+K) i=1 .
The promised realization algorithm is Algorithm 1, which takes as input the matrix H f,N,N +1 and produces a DTLSS. Note that the knowledge of H f,N,N +1 is equivalent to the knowledge of the finite sequence

{M f (v i )} N(2N +1) i=1
of Markov-parameters. The correctness of Algorithm 1 is stated below.

Theorem 2. If rankH f,N,N = rankH f , then Algorithm 1 returns a minimal realization Σ N of f . The condition rankH f,N,N = rankH f holds for a given N , if there exists a DTLSS realization Σ of f such that dim Σ ≤ N + 1.
The proof of Theorem 2 is completely analogous to its continuous-time counterpart [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF]. Theorem 2 implies that if f is realizable by a DTLSS, then a minimal DTLSS realization of f is computable from finitely many Markov-parameters, using Algorithm 1. In fact, if f is realizable by a DTLSS of dimension n, then the first

N(2n -1) Markov-parameters {M f (v i )} N(2n-1) i=1 uniquely determine f . Algorithm 1 Inputs: Hankel-matrix H f,N,N +1 . Output: DTLSS Σ N 1: Let n = rankH f,N,N +1 . Choose a tuple of integers (i 1 , . . . , i n ) such that the columns of H f,N,N +1 indexed by i 1 , . . . , i n form a basis of ImH f,N,N +1 .
Let O be I N × n matrix formed by these linearly independent columns, i.e. the rth column of O equals the i r th column of H f,N,N +1 . Let R ∈ R n×J N +1 be the matrix, rth column of which is formed by coordinates of the rth column of H f,N,N +1 with respect to the basis consisting of the columns i 1 , . . . , i n of H f,N,N +1 , for every r = 1, . . . , J N +1 . It then follows that H f,N,N +1 = OR and rankR = rankO = n. 2: Define R ∈ R n×J N as the matrix formed by the first J N columns of R. 3: For each q ∈ Q, let R q ∈ R n×J N be such that for each i = 1, . . . J N , the ith column of R q equals the r(i)th column of R. Here r(i) ∈ {1, . . . , J N +1 } is defined as follows. Consider the decomposition i = (r -1)mD + z for some z = 1, . . . , mD and r = 1, . . . , N(N ). Consider the word v r q and notice that |v

r q| ≤ N + 1. Hence, v r q = v d for some d = 1, . . . , N(N + 1). Then define r(i) as r(i) = (d -1)mD + z. 4: Construct Σ N of the form (1) such that B 1 , . . . , B D = the first mD columns of R (8)
C T 1 C T 2 . . . C T D T = the first pD rows of O (9) ∀q ∈ Q : A q = R q R+ ( 10
)
where R+ is the Moore-Penrose pseudoinverse of R.

5: Return Σ N

The intuition behind Algorithm 1 is the following. The state-space of the DTLSS Σ N returned by Algorithm 1 is an isomorphic copy of the space spanned by the columns of H f,N,N . The isomorphism is determined by the matrix R. The columns of B q , q ∈ Q are formed by the columns (q -1)mD + 1, . . . , qmD of the block-matrix

M f (v 1 v 1 ) T . . . M f (v 1 v N(L) ) T T .
The rows of C q , q ∈ Q are formed by the rows (q -1)p + 1, . . . , pq of H f,N,N +1 . Finally, the matrix

A q , q ∈ Q is the matrix of a shift-like operator, which maps a block-column M f (v j v i ) N(L) i=1 of H f,N,N to the block-column M f (v j qv i ) N(L) i=1 of H f,N,N +1 .
The intuition behind Algorithm 1 explains why Theorem 2 requires rankH f,N,N = rankH f , even though Algorithm 1 uses the matrix H f,N,N +1 . In a nutshell, rank H f,N,N = rankH f implies that rankH f,N,N +1 = rankH f,N,N = rankH f . Since A q is the matrix representation of the linear map which maps columns of H f,N,N to columns of H f,N,N +1 , the condition rankH f,N,N +1 = rankH f,N,N ensures that A q is a well-defined square matrix. Moreover, the condition rankH f,N,N +1 = rankH f,N,N = rankH f also ensures that A q is the matrix representation of the linear map which maps a the blockcolumn

M f (v j v i ) ∞ i=1 of the infinite Hankel-matrix H f to the shifted block-column M f (v j qv i ) ∞ i=1
of the same matrix. In turn, the latter is necessary for the result of Algorithm 1 to be a realization of f . Note that requiring only rankH f,N,N +1 = rankH f would not have guaranteed that rankH f,N,N +1 = rankH f,N,N holds, and thus the matrix representation of a linear map shifting columns of H f,N,N would not be a square matrix.

Note that the size of the matrix H f,N,N +1 grows exponentially with N . This renders Algorithm 1 impractical for large N . There is a way to get around it, by using so called selections, introduced in [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF][START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF][START_REF] Petreczky | Spaces of nonlinear and hybrid systems representable by recognizable formal power series[END_REF]. We will call a finite subset α ⊂ Q * × Q × {1, . . . , p} a row selection and a finite subset β ⊆ Q * × Q × {1, . . . , m} a column selection. For the SISO case, row and column selections can be thought of as subsets of Q * × Q. We will refer to row and column selections as selections, if it is clear from the context whether we mean row or column selections.

Selections will be used to define Hankel-like matrices, entries of which are Markov parameters. Assume that α and β are row and column selections respectively and assume that α and β are both finite sets of cardinality n and κ respectively. Fix an enumeration of the elements of α and β as follows:

α = {(v i , q i , l i )} n i=1 , β = {(w j , σ j , h j )} κ j=1 . (11)
Let us now define the matrix H f,α,β ∈ R n×κ as follows:

[H f,α,β ] i,j = (S f (σ j w j v i q i )) li,hj i = 1, . . . , n, j = 1, . . . , κ. (12)
If α and β have the same cardinality, then the matrix H f,α,β is a square one. Intuitively, the rows of H f,α,β are indexed by the elements of α, and the columns by the elements of β.

In order to present the algorithm, we define the matrices

H q,f,α,β ∈ R n×κ , H f,α,q ∈ R n×m and H q,f,β ∈ R p×κ : [H q,f,α,β ] i,j = (S f (σ j w j qv i q i )) li,hj , i = 1, . . . , n, j = 1, . . . , κ, (13)
[H f,α,q ] i,r = (S f (qv i q i )) li,r , i = 1, . . . , n, r = 1, . . . , m, (14)
[H q,f,β ] r,j = (S f (σ j w j q)) r,hj , j = 1, . . . , κ, r = 1, . . . , p

Algorithm 2 Realization algorithm for DTLSSs with selections Inputs: selections α, β and matrices H f,α,β ,H q,f,α,β H f,α,q and H q,f,β , q ∈ Q.

1: Choose a tuple of integers (i 1 , . . . , i nm ) such that the columns of H f,α,β which are indexed by i 1 , . . . , i nm form a basis of ImH f,α,β . Let O nm be n × n m matrix formed by these linearly independent columns, i.e. the rth column of O nm equals the i r th column of H f,α,β . Let

R nm = O + nm H f,α,β , where O + nm is the Moore-Penrose inverse of O nm . It then follows that H f,α,β = O nm R nm and O nm is full column rank, R nm is full row rank. 2: Define Âq = O + nm H q,f,α,β R + nm , Bq = O + nm H f,α,q , Ĉq = H f q,f,β R + nm
where O + nm , R + nm are the Moore-Penrose inverse of O nm and R nm respectively.

3: return Σ = (n m , { Âq , Bq , Ĉq )} q∈Q ).
Theorem 3 (Adapted from [START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF], realization algorithm with selections). If n m is the dimension of a minimal DTLSS realization of f , then the DTLSS Σ defined in Algorithm 2 is a minimal realization of f . Moreover, if n m is the dimension of a minimal DTLSS realization of f , then there exists a pair of selections α ⊆ Q * × Q × {1, . . . , p} and β ⊆ Q * × Q × {1, . . . , m}, such that the cardinality of the sets α, β is n m and rankH f,α,β = n m = rankH f .

In the sequel we will use the following notation.

Notation 7 (Q ≤k ). We denote by Q ≤k the set of all sequences from Q * of length at most k.

Remark 3 (Relationship with Algorithm 1). From Theorem 2 and [START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF] it follows that we can choose α = Q ≤N × Q × {1, . . . , p} and β = Q ≤N × Q × {1, . . . , m}, where N is any integer not smaller than the dimension of a minimal DTLSS realization of f . In this case, Algorithm 2 is equivalent to Algorithm 1, see [START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF][START_REF] Bastug | Model reduction of linear switched systems and lpv state-space models[END_REF].

Remark 4 (Markov parameters indexed by selections determine all Markov-parameters). Theorem 2 and Theorem 3 imply that for any input-output map f which is realizable by a DTLSS, there exist a finite set Γ ⊆ Q * such that the knowledge of the finite number of Markov-parameters {S f (v)} v∈Γ is sufficient to determine the entire input-output map f . This observation will be useful for computing persistently exciting inputs.

Indeed, from Theorem 2 it follows that if f is realizable by a DTLSS of dimension n, then we can choose Γ as

Γ := Γ n = Q ≤2n+3 , (16)
i.e., Γ is the set of all words of length at most 2n + 3. It then follows that {S f (v)} v∈Γ form the entries of the Hankel-matrix H f,n,n+1 and the latter can be used to compute a DTLSS realization of f using Algorithm 1.

The set Γ from (16) has O(|Q| 2n ) elements, and hence its size is exponential in n. As we shall see later, the size of Γ determines the length of persistently exciting inputs. Therefore, this definition of Γ is not always practical for computing persistently exciting inputs.

This motivates us to formulate a refined definition of Γ using selections and Theorem 3. Consider selections α, β such that rankH f,α,β = rankH f . By Theorem 3 such selections always exist. Let us define Γ as a function of α, β as follows

Γ = Γ(α, β) = {rvq | r ∈ Q and ∃q ∈ Q, ∃l = 1, . . . , p : (v, q, l) ∈ α}∪ {q 0 wr | r ∈ Q and ∃q 0 ∈ Q, ∃h ∈ {1, . . . , m} : (w, q 0 , h) ∈ α}∪ {q 0 wrvq | r ∈ Q and ∃q 0 , q ∈ Q, ∃l ∈ {1, . . . , p}, ∃h ∈ {1, . . . , m} : (v, q, l) ∈ α, (w, q 0 , h) ∈ β}∪ {q 0 wvq | ∃q 0 , q ∈ Q, ∃l ∈ {1, . . . , p}, ∃h ∈ {1, . . . , m} : (v, q, l) ∈ α, (w, q 0 , h) ∈ β} (17)
Then the knowledge of {S f (v)} v∈Γ=Γ(α,β) is sufficient to construct the matrices H f,α,β ,H q,f,α,β H f,α,q and H q,f,β , q ∈ Q, and the latter matrices can be used by Algorithm 2 to compute a DTLSS realization of f . In turn, the latter realization is sufficient to determine all the Markov-parameters

{S f (v)} q∈Q * .
Note that α and β can be chosen to have n elements, where n is the dimension of a minimal DTLSS realization of f . That is, at most (|Q| + 1)n 2 + 2n|Q| Markov parameters are sufficient to determine all the Markov-parameters of f .

In general, the choice of α and β depends on the input-output map f , especially if we would like these selections to contain as many elements as the dimension of a minimal DTLSS realization of f . However, if we do not put restrictions on the number of elements of α, β, then it is possible to choose α and β independently of f , namely, by choosing the selections α

= Q ≤N × Q × {1, . . . , p}, β = Q ≤N × Q × {1, . . . , m} such that N ≥ n,
where n is the dimension of a minimal DTLSS realization of f . In this case, Γ(α, β) will be equal to Γ N from [START_REF] Fox | Bayesian nonparametric learning of complex dynamical phenomena[END_REF], and the number of elements of α and β is exponential in N , i.e., it is O(|Q| N ). However, the set of Markov-parameters which is required in order to determine all the Markov-parameters of f does not depend on f .

That is, we can determine all the Markov-parameters of f from a finite set of Markov parameters, and this set either

• depends on f but its cardinality is quadratic in n, or • is independent of f , but then its cardinality is exponential in n,
where n is the dimension of a minimal DTLSS realization of f .

Main results of the paper

The main idea behind our definition of persistence of excitation is as follows. The measured time series is persistently exciting, if from this time-series we can reconstruct the Markov-parameters of the underlying system. Note that by Theorem 2, it is enough to reconstruct finitely many Markovparameters. This also means that our definition of persistence of excitation is also applicable to finite time series.

In order to present our main results, we will need some terminology.

Definition 12 (Output time-series). For any input-output map f and for any finite input sequence w ∈ U + we denote by O(f, w) the output time series induced by f and w, i.e. if w is of the form (2), then O(f, w) = {y t } T t=0 , such that y t = f ((q 0 , u 0 ) • • • (q t , u t )) for all t ≤ T .

Definition 13 (Persistence of excitation). The finite sequence w ∈ U + is persistently exciting for the input-output map f , if it is possible to determine the Markov-parameters of f from the data (w, O(f, w)).

Remark 5 (Interpretation). Remark 4 allows the following interpretation of persistence of excitation defined above. If w is persistently exciting, then the Markov-parameters of f can be computed from the response of f to the prefixes of w. In particular, if f admits a DTLSS realization of dimension at most n, then there exists a finite subset Γ ⊆ Q * of the Markov-parameters such that {S f (v)} v∈Γ determine all the other Markov-parameters, and {S f (v)} v∈Γ can be computed from the data (w, O(f, w)). The knowledge of {S f (v)} v∈Γ is sufficient for computing a DTLSS realization of f . Hence, persistence of excitation of w for f means that Algorithm 1 or Algorithm 2 can serve as an identification algorithm for computing a DTLSS realization of f from the time-series (w, O(f, w)).

Note, however, that our definition does not depend on Algorithm 1 or Algorithm 2. Indeed, if there is any algorithm which can correctly find a DTLSS realization of f from (w, O(f, w)), then according to our definition, w is persistently exciting, as the knowledge of a DTLSS realization allows us to compute all the Markov-parameters. Note that our definition of persistence of excitation involves only the inputs, but not the output response.

So far we have defined the persistence of excitation for finite sequences of inputs. Next, we define the same notion for infinite sequences of inputs. To this end, we need the following notation. Notation 8. We denote by U ω the set of infinite sequences of hybrid inputs. That is, any element w ∈ U ω can be interpreted as a time-series w = {(q t , u t )} ∞ t=0 . For each N ∈ N, denote by w N the sequence formed by the first N elements of w, i.e. w N = (q 0 , u 0 ) • • • (q N , u N ). Definition 14 (Asymptotic persistence of excitation). An infinite sequence of inputs w ∈ U ω is called asymptotically persistently exciting for the input-output map f , if the following holds. For every sufficiently large N , we can compute from (w N , O(f, w N )) asymptotic estimates of the Markov-parameters of f . More precisely, for N ∈ N, we can compute from (w N , O(f, w N )) some matrices

{M f N (v)} v∈Q * such that lim N →∞ M f N (v) = M f (v) for all v ∈ Q * .
When clear from the context, we will use the term persistently exciting instead of asymptotically persistently exciting.

Remark 6 (Interpretation of asymptotic persistence of excitation). The interpretation of asymptotic persistence of excitation is that asymptotically persistently exciting inputs allow us to estimate a DTLSS realization of f with arbitrary accuracy. Indeed, assume that w ∈ U ω is asymptotically persistently exciting. Then for each N we can compute from the time-series (w N , O(f, w N )) an approximation {M f N (v)} v∈Q * of the Markov-parameters of f . Suppose that f is realizable by a DTLSS of dimension n and we know the indices (i 1 , . . . , i n ) of those columns of H f,n-1,n which form a basis of the column space of H f,n-1,n . Let H N f,n-1,n be the matrix which is constructed in the same way as

H f,n-1,n , but with M f N (v) instead of the Markov-parameters M f (v). Since M f N (v) converges to M f (v) for all v ∈ Q * ,
we get that each entry of H N f,n-1,n converges to the corresponding entry of H f,n-1,n . Modify Algorithm 1 by fixing the choice of columns to (i 1 , . . . , i n ) in the first step. It is easy to see that the modified algorithm represents a continuous map from the input data (finite Hankel-matrix) to the output data (matrices of a DTLSS). For sufficiently large N , the columns of H N f,n-1,n indexed by (i 1 , . . . , i n ) also represent a basis of the column space of H N f,n-1,n . If we apply the modified Algorithm 1 to the sequence of matrices H N f,n-1,n , we obtain a sequence of DTLSSs Σ n,N and the parameters of Σ n,N converge to the parameters of the DTLSS Σ which we would obtain from Algorithm 1 if we applied it to H f,n-1,n . In particular, by choosing a sufficiently large N , the parameters of Σ n,N are sufficiently close to those of Σ.

A similar argument can be made by replacing Algorithm 1 by Algorithm 2, and by replacing H f,n-1,n with the matrices H f,α,β , H q,f,α,α , H f,α,q , H q,f,β , q ∈ Q for suitable selections α, β. More precisely, assume that α, β are selections containing n m elements, such that rank H f,α,β = rank H f = n m . In this case, O nm equals H f,α,β , O + nm is the inverse of H f,α,β , and R nm is the identity matrix It then follows that the matrices returned by Algorithm 2 are continuous functions of the entries of the matrices H f,α,β , H q,f,α,α , H f,α,q , H q,f,β , q ∈ Q. Let H N f,α,β , H N q,f,α,α , H N f,α,q , H N q,f,β , q ∈ Q be the matrices constructed by replacing M f (v) by M f N (v) (note that the matrices S f (q 0 vq) used in (12)-( 15) are blocks of M f (v), and hence the matrices defined in (12)-( 15) are functions {M f (v)} v∈Q * ). Consider the DTLSS ΣN returned by a version of Algorithm 2, where H f,α,β , H q,f,α,α , H f,α,q , H q,f,β , q ∈ Q are replaced by H N f,α,β , H N q,f,α,α , H N f,α,q , H N q,f,β , q ∈ Q. Let Σ be the DTLSS returned by Algorithm 2 when applied to the true matrices H f,α,β , H q,f,α,α , H f,α,q , H q,f,β , q ∈ Q. Since for large enough N , the matrices

H N f,α,β , H N q,f,α,α , H N f,α,q , H N q,f,β , q ∈ Q are close to H f,α,β , H q,f,α,α , H f,α,q
, H q,f,β , q ∈ Q, and the steps of Algorithm 2 are continuous in the elements of those matrices, the matrices of ΣN will converges to those of Σ as N → ∞. That is, ΣN can be viewed as an approximate realization of f .

The discussion above highlights the difference between persistently exciting inputs and asymptotically persistently exciting inputs. Namely, by Remark 5 persistently exciting inputs allow us to reconstruct an exact model of the input-output map f from the output response of finite length. In contrast, as Remark 6 indicates, asymptotically persistently excitating inputs allow us to construct an approximate model of f from output responses of finite length, with the additional property that as the length of the output response converges to ∞, the obtained approximate model converges to an exact model of f . That is, the two concepts are different.

Remark 7 (Recovering finitely many Markov-parameters). The definition of (asymptotically) persistenly exciting inputs involve the possibility of recovering all the Markov-parameters from the output response to that input. At a first glance, this may seem ill-posed, as from inputs of finite length one expects to be able to recover at best a finite number of Markov-parameters. However, Remark 5-6 clearly show that it is sufficient to recover only a finite number of Markov-parameters, as for input-output maps realizable by DTLSSs, a finite number of Markov-parameters determine all the Markov-parameters of the input-output map.

We will show that for every reversible DTLSS there exists some input which is persistently exciting. In addition, we present a class of inputs which are persistently exciting of any inputoutput map f realizable by a stable DTLSS.

Persistently exciting input for specific systems

In this section we present results which state that for any input-output map f which is realizable by a reversible DTLSS, there exists a persistently exciting finite input.

Note that from (4) it follows that the Markov-parameters of f can be obtained from finitely many input-output data. However, the application of (4) implies evaluating the response of the system for different inputs, while started from a fixed initial state. In order to simulate this by evaluating the response of the system to one single input (which is then necessarily persistently exciting), one has to provide means to reset the system to its initial state. In order to be able to do so, we restrict attention to reversible DTLSSs. Definition 15. A DTLSS Σ of the form (1) is reversible, if for every discrete mode q ∈ Q, the matrix A q is invertible.

Reversible DTLSSs arise naturally when sampling continuous-time systems. Theorem 4. Consider an input-output map f . Assume that f has a realization by a reversible DTLSS. Then there exists an input w ∈ U + such that w is persistently exciting for f . Proof. The main idea behind the proof of Theorem 4 is as follows. If f admits a DTLSS realization of dimension n, then by Remark 4, there exists a finite selections α, β and there exists a finite set Γ(α, β) ⊆ Q * such that the Markov-parameters {S f (v)} v∈Γ(α,β) determine all the Markovparameters of f uniquely. Hence, in order for a finite input w to be persistently exciting for f , it is sufficient that {S f (v)} v∈Γ(α,β) can be computed from the response (w, O(f, w)).

Note that (4) implies that {S f (v)} v∈Γ(α,β) can be computed from the responses of f from finitely many inputs. More precisely, {S f (v)} v∈Γ(α,β) can be computed from {f (s) | s ∈ S(α, β)}, where

S(α, β) = {(q 0 , e j ) (σ 1 , 0) . . . (σ k , 0) (q, 0) ∈ U + | q 0 , q ∈ Q, σ 1 , . . . , σ k ∈ Q, q 0 σ 1 • • • σ k q ∈ Γ(α, β), k ≥ 0, j = 1, . . . , m, }. (18)
That is, for each v ∈ Γ(α, β), each column of S f (v) equals to f (s) for some s ∈ S(α, β). Hence, if for each s ∈ S(α, β) there exists a prefix p of w such that f (s) = f (p), then this w will be persistently exciting.

One way to construct such a w is to construct for each s ∈ S(α, β) an input s -1 ∈ U + such that

∀v ∈ U + : f (s s -1 v) = f (v).
That is, the input s -1 neutralizes the effect of the input s. We defer the construction of the input s -1 to the end of the proof. Assume for the moment being that such inputs s -1 exist. Let S(α, β) = {s 1 , . . . , s d } be an enumeration of S(Γ). Then it is easy to see that f (s 1 s -1

1 s 2 ) = f (s 2 ), f (s 1 s -1 1 s 2 s -1 2 s 3 ) = f (s 3 ), etc. Hence, if we define w = s 1 s -1 1 • • • s d-1 s -1 d-1 s d , (19)
then each f (s), s ∈ S(α, β) can be obtained as a response of f to a suitable prefix of w. Hence, w is persistently exciting.

It is left to show that s -1 exists. Consider a reversible realization Σ of f . Then the controllable set and reachable set of Σ coincide by [START_REF] Ge | Reachability and controllability of switched linear discrete-time systems[END_REF]. Hence, from any reachable state x of Σ, there exists an input w(x) such that w(x) drives Σ from x to zero, i.e. x Σ (x, w(x)) = 0. For each s ∈ S, let x(s) = x Σ (0, s) and define s -1 = w(x(s)) as the input which drives x(s) back to the initial zero state.

It is easy to see that Theorem 4 can be extended to any input-output map which admits a controllable DTLSS realization. However, it is not clear if every input-output map which is realizable by a DTLSS is also realizable by a controllable DTLSS.

The proof of Theorem 4 can be used to formulate an algorithm for constructing a persistently exciting input. In order to present this algorithm, we will need to adapt from [START_REF] Sun | Switched linear systems : control and design[END_REF] the following procedure for constructing an input to drive a DTLSS from any state to zero.

Assume that Σ is a DTLSS of the form (1), and consider a finite column selection

β ⊆ Q * × Q × {1, . . . , m} β = {(w i , q i , j i )} κ i=1 (20)
such that the matrix

R(β) = A w1 B q1 , A w2 B q2 , . . . , A wκ B qκ (21)
has rank n, i.e., rankR(β) = n. In particular, from [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] it follows that if Σ is span-reachable, then there exists a set β of the form [START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF] such that rankR(β) = n. Moreover, β = Q ≤n-1 ×Q×{1, . . . , m} is a valid choice for any span-reachable DTLSS. In fact, from [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] it follows that if rankH f,α,β = rank H f for some selections α, β, then rank R(β) = n for any minimal DTLSS realization Σ of f such that dim Σ = n.

Let us define the switching sequences π i , i = 1, . . . , n recursively as follows:

π 1 = q 1 w 1 , π i+1 = π i • • • π i (n+1)-times q i+1 w i+1 , i = 1, . . . , κ -1 (22)
From [START_REF] Ji | A constructive approach to reachability realization of discrete-time switched linear systems[END_REF] it then follows that any state of Σ can be driven to 0 using the switching sequence π κ and some continuous input. More precisely, assume that

π κ = q 1 • • • q L , (23)
q 1 , . . . , q L ∈ Q for L > 0. It then follows that for any x ∈ R n there exists

u 1 • • • u L ∈ R m , such that for w(x) = (q 1 , u 1 ) (q 2 , u 2 ) • • • (q L , u L ) (24)
x Σ (x, w(x)) = 0. The input u 1 , . . . , u l can be computed as follows: let us define the matrix

R πκ = A q2•••q L B q1 , A q3•••q L B q2 , . . . , A q L B q L-1 , B q L (25)
From [START_REF] Ge | Reachability and controllability of switched linear discrete-time systems[END_REF] it follows that rankR πκ = n and u 1 , . . . , u L can be computed by solving the following linear least squares problem

     u 1 u 2 . . . u L      = argmin ũ1,ũ2,...,ũL∈R m A q1•••q L x + R πκ      ũ1 ũ2 . . . ũL      2 2 (26)
Then using the proof of Theorem 4 yields the following algorithm for constructing a persistently exciting input and switching sequence. From the proof of Theorem 4 the following results follow.

Algorithm 3 Input a reachable DTLSS realization Σ = (n, {A q , B q , C q | q ∈ Q}) of f , and selections α, β such that rankH f,α,β = rankH f . Output input w ∈ U + .

1: Construct the sequence π κ as defined in [START_REF] Breschi | Learning hybrid models with logical and continuous dynamics via multiclass linear separation[END_REF].

2: Consider Γ(α, β) from ( 17).

3: Fix an enumeration Γ(α, β) = {γ 1 , . . . , γ R }. Then S(α, β) from ( 18) is of the form

S(α, β) = {s 1 , . . . , s d }, d = mR
where for every i = 1, . . . , d, if i = m(k -1) + j for some k = 1, . . . , R, j = 1, . . . , m and

γ k = q 0,k q 1,k • • • q L k ,k , q 0,k , . . . , q L k ,k ∈ Q, L k ≥ 1, s i = (q 0 , e j ) (q 1,k , 0) • • • (q L k , 0) (27)
4: For each i = 1, . . . , d, using (27), define

s -1 i = w(x i ), x i = A q 1,k •••q L k ,k q1 B q 0,k e j (28)
where w(x i ) is as in (26) for x = x i . 5: Construct w according to [START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF], i.e.,

w = s 1 s -1 1 • • • s d-1 s -1 d-1 s d 6: return w
Corollary 1 (Correctness of Algorithm 3). Assume that the selections α, β are such that rankH f,α,β = rankH f . The input w returned by Algorithm 3 is persistently exciting for f .

Note that the Algorithm 3 requires the knowledge of selections α, β such that rankH f,α,β = rankH f . This is not a restriction, as from Remark 3 it follows that we can always take α = Q ≤n × Q × {1, . . . , p} and β = Q ≤n × Q × {1, . . . , m} , where n is the dimension of a DTLSS realization of f . Remark 8 (Complexity of the persistently exciting input). If the selections α, β used in Algorithm 3 are chosen to have n elements and belong to Q ≤n × Q × {1, . . . , p} and Q ≤n × Q × {1, . . . , m} respectively, then the length of the persistently exciting input w returned by the Algorithm 3 is O((n+1) n •(n 2 +3)•mR) = O((n+1) n+4 ), i.e., it is exponential in n. Indeed, the length of π n is at most (n+1) n , and hence so is the length of s -1 i . The length of each s i is at most

n 2 +3 ≤ O((n+1) 2 ). Finally, the number R of elements of Γ(α, β) is at most 2(|Q| • n) + (|Q| + 1)n 2 , i.e, O((n + 1) 2 ).
This means that the length of the necessary input grows rapidly with the state-space dimension of the underlying DTLSS. The memory complexity of Algorithm 3 is then also O((n + 1) n+4 ). The time complexity of Algorithm 3 is determined by the need for solving [START_REF] Ljung | System Identification: Theory for the user[END_REF], which is polynomial in R and n, i.e., the time complexity of Algorithm 3 is polynomial in n Example 1. Consider the DTLSS of the form (1) such that Q = {1, 2} and A 1 =   0.67032 0.22099 0.00000 0.00000 0.44933 0.00000 0.00000 0.00000 0.44933   , A 2 =   0.44933 0.00000 0.00000 0.00000 0.72466 0.27534 0.00000 0.27534 0.72466

  , B 1 =   1 1 1   , B 2 =   1 0 1   , C 1 = C 2 = 1 0 0 (29)
Consider α = {( , 1, 1), (1, 1, 1), (21, 1, 1)} and β = {( , 2, 1), (2, 1, 1), (21, 2, 1)}. Then by applying Algorithm 3 we get a persistenly exciting input of length 864. In particular, the sequence π n from (22) will be 222122122221222221 and its length is 18. The set Γ has 38 elements, the first couple of elements of Γ(α, β) are as follows: Then the first couple of inputs s i from (27) are as follows:

Γ(α, β) = {11,
s 1 = (1, 1) (1, 0), s 2 = (2, 1) (1, 0), . . . , s 9 = (2, 1) (2, 0) • (1, 0) (1, 0) (1, 0). Then for instance s -1 1 from (28) is s -1 1 = (2, 0.00090) (2, -0.00090) (2, -0.00089) (1, -0.00399) (2, -0.00199) (2, -0.00199) (1, -0.00886) (2, -0.00443) (2, -0.00440) (2, -0.00434) (2, -0.00421) (1, -0.01924) (2, -0.00957) (2, -0.00885) (2, -0.00724) (2, -0.00364) (2, 0.00435) (1, 0.00007) s -1 9 = (2, -0.00009) (2, -0.00009) (2, -0.00009) (1, -0.00040) (2, -0.00020) (2, -0.00020) (1, -0.00089) (2, -0.00045) • (2, -0.00044) (2, -0.00044) (2, -0.00042) (1, -0.00194) (2, -0.00097)
(2, -0.00089) (2, -0.00073) (2, -0.00037) (2, 0.00044) (1, 0.00001) Then using [START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF], the persistenly exciting input w is of the form w = (1, 1) (1, 0)(2, 0.00090) (2, -0.00090) (2, -0.00089) (1, -0.00399) (2, -0.00199)

(2, -0.00199) (1, -0.00886) (2, -0.00443) (2, -0.00440) (2, -0.00434) (2, -0.00421) (1, -0.01924) (2, -0.00957) (2, -0.00885) (2, -0.00724) (2, -0.00364) (2, 0.00435) (1, 0.00007) (2, 1) (1, 0) • • • (2, 1) (2, 0) (1, 0) (1, 0) (1, 0) (2, -0.00009) (2, -0.00009) (2, -0.00009) (1, -0.00040) (2, -0.00020) (2, -0.00020) • • • (1, -0.00089) (2, -0.00045) (2, -0.00044) (2, -0.00044) (2, -0.00042) (1, -0.00194) (2, -0.00097) (2, -0.00089) (2, -0.00073) (2, -0.00037) (2, 0.00044) (1, 0.00001)
By performing simulations we can see that (w, O(f, w)) can be used to recover the Markov-parameters. For example, if O(f, w) = {y t } T t=0 where T is the length of w, then

y 1 = C 1 B 1 = 1 = S f (11), y 21 = 1 = C 1 B 2 = 1 = S f (21), etc., for example, y 9 = S f (22111) = C 1 A 1 A 1 A 2 B 2 = 0.27002.
Note that the construction of the persistently exciting w from Theorem 4 requires the knowledge of a DTLSS realization of f . Moreover, the length of persistently exciting signal constructed in Theorem 4 can grow very fast with the number of states necessary to implement f , Below we present a subclass of input-output maps, for which the knowledge of a state-space representation is not required to construct a persistently exciting input.

Definition 16. Fix a map . -1 : U α → α -1 ∈ U + . A input-output map f is said to be reversible with respect to the map . -1 , if for all α ∈ U, s, w ∈ U * , |s w| > 0,

f (s α α -1 w) = f (sw).
Intuitively, f is reversible with respect to . -1 , if the effect of any input α = (q, u) can be neutralized by the input α -1 . Such a property is not that uncommon, think for example of turning a valve on and off.

Remark 9 (Conditions for reversibility). For example, if f has a realization by a DTLSS Σ of the form (1), and Q = {1, . . . , 2K} such that for each q ∈ {1, . . . , K}, A q = A -1 q+K , B q = B q+K , then f is reversible and (q, 0) -1 = (q + K, 0) and for u = 0, (q, u) -1 = (q + K, 0) (q, -u) (q + K, 0), From the proof of Theorem 4, we obtain the following corollary.

Corollary 2. If f is reversible with respect to . -1 , then a persistently exciting input sequence w can be constructed for f . The construction does not require the knowledge of a DTLSS state-space realization of f . If the inputs α -1 from Definition 16 are computable from α, then the construction of w is effective.

Proof of Corollary 2. The proof differs from that of Theorem 4 only in the definition of s -1 for each s ∈ S. More precisely, if f is reversible, then for each s = (q 0 , u 0 )

• • • (q t , u t ) ∈ S define s -1 = (q t , u t ) -1 (q t-1 , u t-1 ) -1 • • • (q 0 , u 0 ) -1 (30)
The proof of Corollary 2 sugggests the following algorithm for computing persistently exciting inputs for reversibel input-output maps.

Algorithm 4 Computing persistently exciting inputs for reversible input-output maps

Input Selections α, β such that rankH f,α,β = rankH f . Output input w ∈ U + 1: Consider Γ(α, β) from ( 17). 2: Repeat Step 3 of Algorithm 3, i.e., fix an enumeration Γ(α, β) = {γ 1 , . . . , γ R } and an enumeration of S(α, β) = {s 1 , . . . , s d } from [START_REF] Paoletti | Input/ouput realization of piecewise affine state space models[END_REF], where d = mR and for every i = 1, . . . , d, if i = m(k -1) + j for some k = 1, . . . , R, j = 1, . . . , m and s i is as in ( 27). 3: For each i = 1, . . . , d, using (27), define s -1 i as in [START_REF] Gécseg | Algebraic theory of automata[END_REF] with s being replaced by s i . 4: Construct w according to [START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF], i.e.,

w = s 1 s -1 1 • • • s d-1 s -1 d-1 s d 5: return w
Remark 10 (Complexity of persistently exciting inputs for reversible input-output maps). For reversible input-output maps the length of persistently exciting inputs and the computational complexity of computing it is much lower. Indeed, Algorithm 4 does not require the computation of the sequence π κ from [START_REF] Breschi | Learning hybrid models with logical and continuous dynamics via multiclass linear separation[END_REF], length of which is O((n + 1) n+4 ). In fact, the length of s -1 i constructed in Step 3 of Algorithm 4 will be the twice that of s i . Therefore, if the selections α, β are chosen to be subsets of Q ≤N × Q × {1, . . . , p} and Q ≤N × Q × {1, . . . , m} respectively, n is the size of α, κ ≥ n is the size of β and N ≥ n, then the length of w returned by the modified Algorithm 3 will be O(N κ 2 ). Indeed, in this case the number of elements of Γ(α, β) is O(κ 2 ) and their length is at most 2N . In particular, for N = κ = n, the length of w is O(n 3 ). This compares favorably with the length of w returned by the original Algorithm 3, which was O((n + 1) n+4 ). In particular, with such a choice of selections α, β, the time and memory complexity of the Algorithm 4 is polynomial and linear respectively in the state dimension.

If the selections α and β are chosen to be α = Q ≤n × Q × {1, . . . , p} and β = Q ≤n × Q × {1, . . . , m}, then κ = O(|Q| n ), and the length of the persistently exciting input returned by Algorithm 4 is O(|Q| 2n ), i.e., it is still exponential in n. Then the storage complexity of Algorithm 4 is also exponential in n. However, this still compares favorably with the complexity of Algorithm 3.

The persistently exciting input constructed in the proof of Theorem 4 and Corollary 2 can be used to formulate a provenly system identification algorithm which finds an exact model based on data. For the sake of completness we present the algorithm.

Algorithm 5 Identification algorithm using persistently exciting input Inputs: Selections α, β such that rankH f,α,β = rankH f = n and the data (w, O(f, w)) for some w of the form [START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF] such that S(α, β) = {s 1 , . . . , s d }, where S(α, β) is as in [START_REF] Paoletti | Input/ouput realization of piecewise affine state space models[END_REF]. Output: DTLSS Σ.

1: Compute Γ(α, β) as in [START_REF] Verdult | Subspace identification of piecewise linear systems[END_REF] and choose an enumeration Γ(α, β) = {γ 1 , . . . , γ R } and an indexing function φ : {1, . . . , R} × {1, . . . m} → {1, . . . , d} such that

S f (γ k ) = f (s φ(k,1) ) f (s φ(k,2) ) • • • f (s φ(k,m) ) .
For m = 1; φ(i, 1) = i could be taken, for m > 1, φ(k, j) = m(k -1) + j could be taken. 2: Assume that O(f, w) = {y t } T t=0 and for all k = 1, . . . , d, recover the Markov-parameters {S f (γ i )} R i=1 from {y t } T t=0 as follows:

S f (γ k ) = y t(φ(k,1)) y t(φ(k,2)) . . . y t(φ(k,m)) t(j) = j-1 i=1 (|s i | + |s -1 i |) + |s j | -1, j = 1, . . . , d (31)
where |s| denotes the length of a sequence of s ∈ U + , and t(j) + 1 equals the length of

s 1 s -1 1 • • • s j-1 s -1 j-1 s j , i.e, y t(j) = f (s 1 s -1 1 • • • s j-1 s -1 j-1 s j ) for all j = 1, . . . , d. 3: Construct the matrices H f,α,β , H q,f,α,β , H f,α,q and H q,f,β , q ∈ Q from O(f, w) = {y t } T
t=0 by using [START_REF] Eilenberg | Automata, Languages and Machines[END_REF]. 4: Let Σ be the DTLSS returned by Algorithm 2 when applied to H f,α,β H q,f,α,β , H f,α,q and H q,f,β . 5: return Σ It is easy to see that the following holds.

Lemma 2 (Consistency of Algorithm 5). The DTLSS returned by Algorithm 5 is a realization of f .

In general, in order to compute the persistently exciting input w, which is necessary for Algorithm 5, the knowledge of the underlying system is required. However, Algorithm 4 for reversible input-output maps does not require the knowledge of the underlying system. Hence, Algorithm 4 in combination with Algorithm 5 is an example of a design of system identification experiment which allows exact identification of the underlying system, assuming that there is no noise. Extensions to the noisy case would require using stochastic realization theory for DTLSSs, see [START_REF] Petreczky | Realization theory for a class of stochastic bilinear systems[END_REF].

Example 2. Consider a DTLSS Σ of the form [START_REF] Sun | Switched linear systems : control and design[END_REF], where Q = {1, 2, 3, 4} and A i , B i , C i , i = 1, 2 are as in [START_REF] Petreczky | On the notion of persistence of excitation for linear switched systems[END_REF], and

A 3 = A -1 1 and A 4 = A -1 2 , B 3 = B 1 , B 4 = B 2 , C 3 = C 1 , C 4 = C 2 . Define the operation . -1 : U α → α -1 ∈ U + as follows: (1, 0) -1 = (3, 0), (2, 0) -1 = (4, 0), (1, u) -1 = (3, 0) (1, -u) (1, 0), (2, u) -1 = (4, 0) (2, -u) (4,
w = (1, 1) (1, 0) (3, 0) (3, 0) (1, -1) (3, 0) (2, 1) (1, 0) (3, 0) (4, 0) (2, -1) (4, 0) • • •
The resulting input is persistently exciting. This can also be seen by simulation: if O(f, w) = {y t } T t=0 then the Markov-parameters which are necessary to identify f can be extracted from {y t } T t=0 : for instance

y 2 = C 1 B 1 = 1, y 6 = C 1 B 2 , y 65 = C 1 A 1 A 1 A 2 B 1 = 0.4493, etc.
The resulting persistently exciting input can be used in combination with Algorithm 5 to obtain a DTLSS Σ = (n, { Âq , Bq , Ĉq } q∈Q ), such that Σ and Σ are related by an isomorphism S, i.e., SA q S -1 = Âq , SB q = Bq , C q S -1 = Ĉq , where In particular, the integers t(j) from (31) are as follows t(1) = 2, t(2) = 8, t(3) = 14, etc., t(10) = 65, etc.. The same result can be obtained if we use Algorithm 5 for the persistently exciting input from Example 1.

S =   1.
Remark 11 (Extension to non-zero initial state). Note that realization theory and the notion of Markov-parameters can be extended to systems with non-zero inital states [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF][START_REF] Petreczky | Realization theory of linear and bilinear switched systems: A formal power series approach: Part i[END_REF][START_REF] Van Den Hof | System theory and system identification of compartmental systems[END_REF]. That is, the basic idea of the paper could in principle be extended to systems with non-zero initial state. More precisely, Theorem 4 can be extended to systems which are controllable to the initial state, i.e., for systems such that any state can be driven to the initial state for some input and switching signal. Corollary 2 can be repeated for systems with non-zero initial states, by using the extended definition of Markov-parameters [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF][START_REF] Petreczky | Realization theory of linear and bilinear switched systems: A formal power series approach: Part i[END_REF].

Universal asymptotically persistently exciting inputs

Next, we discuss classes of inputs which are asymptotically persistently exciting for all inputoutput maps realizable by DTLSSs.

Definition 17 (Persistence of excitation condition). An infinite input w = {(q t , u t )} ∞ t=0 ∈ U ω satisfies PE condition, if for any word v ∈ Q + and any integer j ≥ 1, the limits below exist and satisfy the following conditions,

lim N →∞ 1 N N t=0 u t+j u T t χ(q t q t+1 • • • q t+|v|-1 = v) = 0, lim N →∞ 1 N N t=j u t-j u T t χ(q t-j q t-j+1 • • • q t-j+|v|-1 = v) = 0, R def = lim N →∞ 1 N N t=0 u t u T t > 0, π v def = lim N →∞ 1 N N t=0 χ(q t • • • q t+|v|-1 = v) > 0, lim N →∞ 1 N N t=0 u t u T t χ(q t • • • q t+|v|-1 = v) = π v R.
where χ is the indicator function, i.e. χ(A) = 1 if A holds and χ(A) = 0 otherwise. Note that by R > 0 we mean that R is a strictly positive definite m × m matrix.

Remark 12 (PE condition implies rich switching). Note that if w ∈ U ω satisfies the conditions of Definition 17, then the signal is rich enough, i.e. any sequence of discrete modes occurs in the switching signal infinitely often. Hence, our condition for persistence of excitation implies that the switching signal should be rich enough. This is consistent with many of the existing definitions of persistence of excitation for hybrid systems. The requirement that π v > 0 for all v ∈ Q * is quite a strong one. At the end of this section we will discuss possible relaxations of this requirement.

Remark 13 (Relationship with stochastic processes). Fix a probability space (Ω, F, P ) and consider ergodic discrete-time stochastic processes u t : Ω → R m and q t : Ω → Q with values in R m and Q respectively. In addition, assume the following.

• The processes u t and q t are independent (i.e. the σ-algebras generated by {u t } ∞ t=0 and by {q t } ∞ t=0 are independent.

• The stochastic process u t is a colored noise, i.e. it is zero-mean, u t and u s are uncorrelated for s = t, and E[u t u T t ] = R > 0, with E[•] denoting the expectation operator.

• For each v ∈ Q + , π v = P (q t • • • q t+|v|-1 = v) > 0.
It then follows that almost all sample paths of u t , q t satisfy the PE condition of Definition 17.

That is, there exists a set A ∈ F, such that P (A) = 0 and for all ω ∈ Ω \ A, the sequence w = {(q t , u t ) = (q t (ω), u t (ω)} ∞ t=0 satisfies the PE condition. Remark 14. If u t is a white-noise Gaussian process and if the variables q t are uniformly distributed over Q (i.e. P (q t = q) = 1 |Q| and are independent from each other and from {u s } ∞ s=0 , then u t and q t satisfy the conditions of Remark 13 and hence almost any sample path of u t and q t satisfies the PE condition of Definition 17. This special case also provides a simple practical way to generate inputs which satisfy the PE conditions.

We will show that input sequences which satisfy the conditions of Definition 17 are asymptotically persistently exciting for a large class of input-output maps. The main idea behind the theorem is as follows. Consider a DTLSS Σ which is realization of f , and suppose we feed a stochastic input {q t , u t } into Σ. Then the state x t and the output response y t of Σ will also be stochastic processes. Suppose that {q t , u t } are stochastic processes which satisfy the conditions of Remark 13. It is easy to see that

y t = t k=0 C q t A q t-1 • • • A q k+1 B q k u k .
and hence for all r, q ∈

Q, v ∈ Q * , |rvq| = t + 1, E[y t u T 0 χ(q 0 • • • q t = rvq)] = t k=0 C q A v B r E[u k u T 0 χ(q 0 • • • q t = rvq)] = C q A v B r Rπ rvq = S f (rvq)Rπ rvq . (32)
Hence, if we know the expectations E[y t u T 0 χ(q 0 • • • q t = rvq)] for all r, q ∈ Q, v ∈ Q * , |rvq| = t+1, t > 0, then we can find all the Markov-parameters of f , by the following formula

S f (rvq) = E[y t u T 0 χ(q 0 • • • q t+1 = rvq)]R -1 1 π rvq .
Hence, the problem of estimating the Markov-parameters reduces to estimating the expectations

E[y t u T 0 χ(q 0 • • • q t = rvq)]. (33)
For practical purposes, the expectations in [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF] have to be estimated from a sample-path of y t , u t and q t . The most natural way to accomplish this is to use the formula lim

N →∞ 1 N N t=i y i+t u T i χ(q i • • • q i+t = rvq) (34)
where y t , u t , q t denote the value at time t of a sample-path of y t , u t and q t respectively. Note that y t is in fact the output of Σ at time t, if the input {u i } t i=0 and the switching signal {q i } t i=0 are fed to the system. The problem with estimating (33) by [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] is that the limit (34) may fail to exist or to converge to [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF].

A particular case when [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] converges to [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF] is when the process (y t , u t , q t ) is ergodic, see [START_REF] Bilingsley | Probability and measure[END_REF] for the definition of ergodic processes. Then there exists a sample path (y t , u t , q t ) of (y t , u t , q t ) for which the limit in [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] equals the expectation [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF] ; in fact 'almost all' sample paths will have this property. This means that we can choose a suitable deterministic input sequence {u t } ∞ t=0 and a switching signal {q t } ∞ t=0 , such that for the resulting output {y t } ∞ t=0 , the limit (34) equals the expectation [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF]. That is, in that case the input w = (q 0 , u 0 ) • • • (q t , u t ) • • • is asymptotically persistently exciting. However, proving ergodicity of y t is not easy. In addition, even if y t is ergodic, the particular choice of the deterministic input w for which [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] equals [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF] might depend on the DTLSS itself.

For this reason, instead of using the concepts of ergodicity directly, we just show that for the input sequences w which satisfy the conditions of Definition 17, the corresponding output {y t } ∞ t=0 has the property that the limit [START_REF] Bastug | Model reduction by moment matching for linear switched systems[END_REF] exists and it equals S f (rvq)Rπ rvq , for any input-output map f which is realizable by a l 1 -stable DTLSS. This strategy allows us to use elementary techniques, while not compromising the practical relevance of the result.

In order to present the main result of this section, we have to define the notion of l 1 -stability of DTLSSs.

Definition 18 (Stability of DTLSSs). A DTLSS Σ of the form (1) is called l 1 -stable, if for every x ∈ R n , the series v∈Q * ||A v x|| 2 is convergent.

Remark 15 (Sufficient condition for stability). If for all q ∈ Q, ||A q || 2 < 1 |Q| , where ||A q || 2 is the matrix norm of A q induced by the standard Euclidean norm, then Σ is l 1 -stable.

Remark 16 (Asymptotic stability). If Σ is l 1 -stable, then it is asymptotically stable, in the sense that if s i ∈ Q * , i > 0 is a sequence of words such that lim i→∞ |s i | = +∞, then lim i→∞ A si x = 0 for all x ∈ R n .

Intuitively it is clear why we have to restrict attention to stable systems. Recall that (4) allows us to compute the Markov-parameters of f from the responses of f to finitely many inputs. In order to obtain the response of f to several inputs from the response of f to one input, one has to find means to suppress the contribution of the current state of the system to future inputs. In §4.1 this was done by feeding inputs which drive the system back to the initial state. Unfortunately, the choice of such inputs depended on the system itself. By assuming stability, we can make sure that the effect of the past state will asymptotically diminish in time. Hence, by waiting long enough, we can approximately recover the response of f to any input.

Another intuitive explanation for assuming stability is that it is necessary for the stationarity, and hence ergodicity, of the output and state processes y t , x t .

Equipped with the definitions above, we can finally state the main result of the section.

Theorem 5 (Main result). If w satisfies the PE conditions of Definition 17, then w is asymptotically persistently exciting for any input-output map f which admits a l 1 -stable DTLSS realization.

The theorem above together with Remark 14 imply that white noise input and a binary noise switching signal are asymptotically persistently exciting. The proof of Theorem 5 relies on the following technical result. Lemma 3. Assume that Σ is a l 1 -stable DTLSS of the form (1), and assume that w satisfies the PE conditions. Let {y t } ∞ t=0 and {x t } ∞ t=0 be the output and state response of Σ to w, i.e. y t = f Σ (w t ) and

x t = x Σ (0, w t ). Then for all v, β ∈ Q * , r, q ∈ Q π rvqβ A v B r R = lim N →∞ 1 N N t=0 x t+|v|+1 u T t χ(t, rvqβ) (35)
π rvqβ C q A v B r R = lim N →∞ 1 N N t=0 y t+|v|+1 u T t χ(t, rvqβ) (36)
Here we used the following notation: for all s ∈ Q + ,

χ(t, s) = 1 if s = q t q t+1 • • • q t+|s|-1 0 otherwise
Informally, Lemma 3 implies that if f is realizable by a l 1 -stable DTLSS, then the limit (34) equals [START_REF] Petreczky | Partial-realization of linear switched systems: A formal power series approach[END_REF]. The proof of Lemma 3 can be found in Appendix A.

Proof of Theorem 5. For each t, denote by y t the response of f to the first t elements of w, i.e. y t = f ((q 0 , u 0 ) • • • (q t , u t )). For each integer N ∈ N and for each word v ∈ Q * , define the matrix S N (rvq) as

S N (rvq) = ( 1 N N t=0 y t+|v|+1 u T t χ(t, rvq))R -1 1 π rvq (37)
and define the matrix M N (v) by

   S N (1v1) • • • S N (Dv1) . . . . . . . . . S N (1vD) • • • S N (DvD)   
From Lemma 3 it follows that lim

N →∞ S N (rvq) = S f (rvq) (38)
and hence lim N →∞ M N (v) = M f (v). Hence, w is indeed asymptotically persistently exciting.

Remark 17 (Relaxation of PE condition). Assume that we restrict attention to input-output maps which are realizable by a minimal l 1 -stable DTLSS of dimension at n, and let f be such an input-output map. Furthermore, consider selections α, β such that rankH f,α,β = rankH f = n and α, β have exactly n elements. Recall that such selections always exist. It then follows that it is enough to estimate {S f (v)} v∈Γ(α,β) , where Γ(α, β) is as in [START_REF] Fox | Bayesian nonparametric learning of complex dynamical phenomena[END_REF] in order to estimate all the Markov-parameters of f . . In this case, one can replace the conditions of Definition 17, that π v > 0 by the condition that π v > 0 for all v ∈ Γ(α, β) and still obtain asymptotically persistently exciting inputs for f . Indeed, consider now any w ∈ U ω which satisfies Definition 17 with the exception that π v > 0 is required only for v ∈ Γ(α, β). Then Lemma 3 remains valid for this case (the proof remains literally the same) and from the proof of Theorem 5 we get that for all v ∈ Γ(α, β)

S f (v) = lim N →∞ ( 1 N N t=0 y t+|v|-1 u T t χ(t, v))R -1 1 π v (39)
Hence, {S f (v)} v∈Γ(α,β) can asymptotically be estimated from (w N , O(f, w N )). Since the modified Algorithm 2 from Remark 6 determines a continuous map from {S f (v)} v∈Γ(α,β) to the other Markov-parameters of f , w is asymptotically persistently exciting for f . The proof of Theorem 5 and the discussion of Remark 6 suggests the following system identification algorithm. Note that Algorithm 6 is an adaptation of the CRA method for LPV systems Algorithm 6 Identification algorithm using PE condition Inputs: Selections α, β such that rankH f,α,β = rankH f = n, integer N , and the data (w N , O(f, w N )) for some w ∈ U + which satisfies the PE condition Output: DTLSS Σ N .

1: Construct the matrices H N f,α,β , H N q,f,α,β , H N f,α,q and H N q,f,β q ∈ Q, by replacing in ( 12) -( 15) every occurrence of S f (v) by S N (v) from (37). 2: Let Σ N be the DTLSS returned by Algorithm 2 when applied to H N f,α,β H N q,f,α,β , H N f,α,q and H N q,f,β . 3: return Σ N described in [START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF]. For linear systems, i.e., for |Q| = 1, Algorithm 2 becomes a version of the well known CCA subspace identification algorithms [START_REF] Katayama | Subspace Methods for System Identification[END_REF][START_REF] Van Overschee | Subspace Identification for Linear Systems[END_REF].

Lemma 4 (Consistency of Algorithm 6). Assume that rankH f,α,β = rankH f = n, α, β both contain exactly n elements, and w satisfies the PE condition. Let Σ N returned by Algorithm 2 be of the form Σ N = (n N , { N A q , N B q , N C q } q∈Q ). Then lim N →∞ n N = n and lim N →∞ ( N A q , N B q , N C q ) = (A q , B q , C q ), q ∈ Q and the DTLSS Σ = (n, {A q , B q , C q } q∈Q ) is a realization of f . Proof of Lemma 4. As it was discussed in Remark 6, the matrices of the DTLSS returned by Algorithm 2 are continuous in the entries of H N f,α,β , H N q,f,α,β , H N f,α,q and H N q,f,β q ∈ Q. By (39), the matrices H N f,α,β , H N q,f,α,β , H N f,α,q and H N q,f,β q ∈ Q converge to H f,α,β H q,f,α,β , H f,α,q and H q,f,β as N → ∞. It then follows that for large enogh N , rankH N f,α,β = rankH f,α,β = n, and lim N →∞ ( N A q , N B q , N C q ) = (A q , B q , C q ) holds, where Σ = (n, {A q , B q , C q } q∈Q ) is the DTLSS returned by Algorithm 2. The rest of the statement of the lemma follows from Theorem 3.

Example 3. Consider the input-output map f generated by the DTLSS Σ of the form [START_REF] Sun | Switched linear systems : control and design[END_REF], where Q = {1, 2} and

A 1 =   0.2 0.2 0.2 0.2 0.2 0 0 0 0   , A 2 =   0 0 0 0 0.2 0.2 0 0.2 0.2   B 1 =   1 1 1   , B 2 =   1 0 1   , C 1 = C 2 = 1 0 1 .
Notice that this DTLSS is minimal, it satisfies the rank conditions of [START_REF] Petreczky | Realization theory for discrete-time linear switched systems[END_REF] for observability and span-reachability. However, the second linear subsystems is not minimal. In addition, A 1 and A 2 are not invertable. Hence, the results of Section 4.1 do not apply. However, A 1 2 = 0.427 < 1/2 and A 2 2 = 0.4 < 1/2, and hence by Remark 15 is minimal and l 1 -stable. Consider the selections α = {( , 1, 1), (1, 1, 1), ( 22 By using random number generators, let us generate a time series {u t , q t } N t=0 such that {u t } N t=0 is a sample of a uniformly distributed zero mean white noise process taking values in [-0.5, 0.5] and {q t } N t=0 is a sample path of a binary white noise process q t taking values in {1, 2}, such that the probability of q t = i, i = 1, 2 is 0.5. We choose N = 2 • 10 7 . Let {y t } N t=0 be the corresponding output response (we took the initial state as zero). If we estimate the Markov-parameters S f (v) for all v ∈ Γ(α, β) according to [START_REF] Bastug | Model reduction of linear switched systems and lpv state-space models[END_REF]. The first couple of elements are as follows: In fact, we can use Algorithm 6 to compute a DTLSS from the simulated data. In this case, the matrices H N f,α,β , H N q,f,α,β , H N f,α,q and H N q,f,β q ∈ Q, are as follows

H N f,α,β =   1
  H N 1,f,β = H N 2,f,β = 2.0004 0.4002 0.3996
For comparison, the true matrices H f,α,β , H q,f,α,β , H f,α,q and H q,f,β q ∈ Q as as follows:

H f,α,β =   2
N f,α,β , H N q,f,α,β , H N f,α,q and H N q,f,β q ∈ Q instead of H f,α,β , H q,f
,α,β , H f,α,q and H q,f,β q ∈ Q and they are as follows: | q ∈ Q} is 0.1839. Simulations revealed that the more data points are used, the closer the matrices H N f,α,β , H N q,f,α,β , H N f,α,q and H N q,f,β q ∈ Q are H f,α,β , H q,f,α,β , H f,α,q and H q,f,β , q ∈ Q. Moreover, by increasing N , the output responses of ΣN get closer to those of Σ. In addition, the parameters of ΣN get closer to that of Σ. That is, Algorithm 6 behaves truly as an asymptotically consistent system identification algorithm. Note that for a good performance, we need a lot of data points. Whether this is an inherent feature of the algorithm or it is due to the choice of the example remains a topic of future research.

Remark 18 (Extension of PE condition to non-zero initial state). The results of this section rely on exponential asymptotic stability of the underlying system. For such systems, the effect of the initial state on the output decays exponentially fast. That is, the effect of the initial state is not visible in the long run. For this reason, it is not clear how the derived results could be extended to systems with non-zero initial state.

Remark 19 (Length of PE input required for identifying the system with a desired accuracy). From the definition of asymptotic persistence of excitation it follows that the longer is the input sequence, the more accurate are the estimates of the Markov parameters. In turn, more accurate estimates of the Markov-parameters lead to less error in the identified system. However, in general, for a given N , the accuracy of the system identification algorithm depends on two factors: the rate of convergence of the estimate (37) to the true Markov-parameter and the degree of robustness of Algorithm 2. None of these questions are easy to answer and they are left for future research. As the results of Example 3 indicate, in order to have a satisfactory accuracy, Algorithm 6 may require long input sequences. Whether this is inherent to the problem of identification of switched systems or can be improved by proposing better identification algorithms, remains a topic of future research.

Conclusions

We defined persistence of excitation for input signals of linear switched systems. We showed existence of persistently exciting input sequences and we identified several classes of input signals which are persistently exciting.

Future work includes finding less restrictive conditions for persistence of excitation and extending the obtained results to other classes of hybrid systems. A q x t+L+1 u T t χ(t, rwqβ)+

+ lim N →∞ 1 N N t=0
B q u t+L+1 u T t χ(t, rwqβ) = = A q A w B r π rwqβ + B r 0 = A wq B r Rπ rwqβ .

(A.3) Finally, we prove [START_REF] Petreczky | Spaces of nonlinear and hybrid systems representable by recognizable formal power series[END_REF]. Notice that y t+|v|+2 u T t χ(q, t, rvqβ) = C q x t+|v|+2 u T t χ(t, rvqβ)

and hence by applying [START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF], lim

N →∞ 1 N N t=0 y t+|v|+2 u T t χ(t, rvqβ) = C q lim N →∞ 1 N N t=0
x t+|v|+2 u T t χ(t, rvqβ) =

C q A v B r Rπ rvqβ .
Proof of Lemma 5. Notice that N t=1

x t u T t χ(t, v) =

N t=1 t j=1 A qt-1 • • • A qj B qj-1 u j-1 u T t χ(t, v) = N k=1 ( N t=k A qt-1 • • • A q t-k+1 B q t-k u t-k u T t χ(t, v)) = r∈Q N -1 k=0 |s|=k A s B r N t=k+1 u t-k-1 u T t χ(t -k -1, rsv) = N(N ) i=1 r∈Q A vi B r N t=|vi|+1 u t-|vi|-1 u T t χ(t -|v i | -1, rv i v).
In the last step we used the lexicographic ordering of Q * from Remark 2. It then follows that

K i K j ) 1/2 .
Hence, if we set K = m i,j=1 K i K j , then then ||b r i,N || 2 ≤ K, which is what had to be shown.

  21, 211, 221, 121, 1211, 1221, 2211, 22111, . . .}.

  0). Let us consider the selection α, β as in Example 1. The set Γ contains 68 elements, for instance 11, 21, 211, 231, 241, 221, 121, 1211, 1221, 2211, 22111, etc. Then Algorithm 4 will return the input of length 645 whose first couple of elements are as follows

  , 1, 1)} and β = {( , 2, 1), (2, 1, 1), (1, 2, 1)}. Then the first couple of elements of Γ(α, β) are 21, 211, 2221, 121, 1211, 12221, . . .

S

  N (21) = 1.9995, S N (211) = 0.3999, S N (121) = 0.4033, S N (1211) = 0.1601 For comparison, the corresponding values of S f are as follows S f (21) = 2, S f (21) = 0.4, S f (211) = 0.4, S f (2211) = 0.16

  = 2.0004 0.4002 0.3996 Simulations reveal that the output response of ΣN is very close to Σ, the Best Fit Rate (BFR) is 99.5%. For illustration, let us consider the DTLSS Σ = (3, { Āq , Bq , Cq } q∈Q returned by the realization algorithm Algorithm 2:

From the assumptions on w ituu

  t u T t χ(t, rβ) = Rπ rβ Hence, from the PE conditions and Lemma 5 we get thatlim t u T t χ(t, rβ)) = A r 0 + B r Rπ rβ = π rβ B r R,i.e. (35) holds. Assume that[START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF] holds for all words of length at most L, and assume that v = wq, |w| = L for some w ∈ Q * and q ∈ Q. Then by the induction hypothesis and the assumptions on w lim

|| 2 + / 2 ./ 2 =

 222 |vi|-1 u T t χ(t -|v i | -1, rv i v). |vi|-1 u T t χ(t -|v i | -1, rv i v) a r i,N = A vi B r b r vi,N .Then the statement of the lemma can be shown by showing that for allr ∈ Q, k-1 u T t χ(t -k -1, rv i v) = 0.Moreover, for a fixed N and i, we can get the following estimate||a r i,N || 2 ≤ ||A vi B r || 2 ||b r i,N || 2 .If we can show that ||b r vi,N || 2 is bounded by a number K, then we get that||a r i,N || 2 ≤ ||A vi B r || 2 K.The latter inequality is already sufficient to finish the proof. Indeed, let D r i = ||A vi B r || 2 K and notice from the l 1 -stability assumption on the realization Σ that∞ i=1 D r i = K v∈Q * ||A v B r || 2is convergent. Hence, we get that for every > 0 there exists a I such that Since lim N →∞ a r i,N = 0, there exists N ∈ N such that for all N > N , i = 1, . . . , I , ||a r i,N || 2 < 2I . Define N to be an integer such that N > N and N( N ) > I . Then for every N > N , N(N ) ≥ N( N ) > I and|| /2 + /2 = .In other words, lim N →0 N(N ) i=1 a r i,N = 0. It is left to show that ||b r i,N || 2 ≤ K for some K > 0 and for all i = 1, 2, . . ., r ∈ Q. |vi|-1 u T t χ(t -|v i | -1, rv i v) |vi|-1 u T t χ(t -|v i | -1, rv i v)

  The matrices of the DTLSS Σ N = (3, { Âq , Bq , Ĉq } q∈Q ) returned by Algorithm 6 can be computed by applying Algorithm 2 to H

			.0000 0.4000 0.4000		 0.4000 0.1600 0.1200	
			0.4000 0.1600 0.1200	 , H 1,f,α,β =	 0.1200 0.0480 0.0480	 ,
			0.0800 0.0640 0.0160	0.0160 0.0064 0.0096
			 0.2000 0.1600 0.0400	
	H 2,f,α,β =	 0.0800 0.0640 0.0160	
			0.0320 0.0256 0.0064
		 2.0000 	 2.0000 
	H f,α,1 =	 0.6000  , H f,α,2 =	 0.4000 
			0.1600	0.0800
	H 1,f,β = H 2,f,β = 2.0000 0.4000 0.4000

  It is easy to see that the parameters of Σ and Σ are numerically close, the maximal relative error max{ Âq-Āq 2 Āq 2 , Bq-Bq 2 Bq 2 , Ĉq-Cq 2

	3333 -0.6667 0.6667
	-0.8333 1.6667	0.8333
	1.6667	1.6667 -1.6667
		Cq 2

  an isomorphism from the original system Σ to Σ.

  ) i χ(t -|v i | -1, rv i v)(u t ) jwhere ||.|| F denotes the matrix Frobenius-norm, and ||.|| 2 denotes the matrix norm induced by the Euclidean norm. The application of the Cauchy-Schwartz inequality to (N t=|vi|+1 (u t-|vi|-1 ) i χ(t -|v i | -1, rv i v)(u t ) j ) 2 leads to ) i χ(t -|v i | -1, rv i v)(u T t ) j Notice that (u t-|vi|-1 ) 2 i χ(t -|v i | -1, rv i v) ≤ (u t-|vi|-1 ) 2 i , since χ(t -|v i | -1, rv i v) ∈ [0, 1]. Hence, ) 2 i χ(t -|v i | -1, rv i v) ≤ ) i χ(t -|v i | -1, rv i v)(u T t ) j ) 2 iis bounded from above by some positive number K i . Using this fact and by substituting (A.6) into (A.4), we obtain||b r i,N || 2 ≤ (

				N
				t=|vi|+1 N (u t-|vi|-1 ≤ (u t-|vi|-1 ) 2 i ≤	N	(u t ) 2 i .
				t=|vi|+1	t=0
	Similarly,
				N	N
				(u t ) 2 j ≤	(u t ) 2 j .
				t=|vi|+1	t=0
	Combining these remarks with (A.5), we obtain
			1 N 2 ≤	N t=|vi|+1 1 N N t=0 (u t ) 2 (u t-|vi|-1 2 i t=0 N (u t ) 2 j . 1 N	(A.6)
	Notice that lim N →∞	1 N	N t=0 (u t ) 2 i = R ii and hence 1 N t=0 (u t m N
				i,j=1
				(A.4)
			1 N 2	t=|vi|+1 N (u t-|vi|-1 2 1/2	.
			N	(u t-|vi|-1 2	≤
			t=|vi|+1 N	N	(A.5)
				(u t-|vi|-1 ) 2 i χ(t -|v i | -1, rv i v)	(u t ) 2 j .
			t=|vi|+1	t=|vi|

Appendix A. Technical proofs

The proof of Lemma 3 relies on the following result.

Lemma 5. With the notation and assumptions of Lemma 3, for all

The intuition behind Lemma 5 is as follows. Each x t is a linear combination of inputs u 0 , . . . , u t-1 . Hence, 1 N N t=0 x t u T t can be expressed as linear combination of terms 1 N N t=k u t-k u T t χ(t, s) for some s ∈ Q * , k = 1, . . . , N . Since each such term converges to 0 as N → ∞, intuitively their linear combination should converge to 0 as well. Unfortunately, the number of summands of the above increases with N . In order to deal with this difficulty a technique similar to the M -test for double series has to be used. The assumption that Σ is l 1 -stable is required for this technique to work.

Proof of Lemma 3. We start with the proof of [START_REF] Cox | Towards efficient maximum likelihood estimation of lpv-ss models[END_REF]. The proof goes by induction on the length of v.