Topological entropy of switched linear systems: general matrices and matrices with commutation relations

This paper studies a notion of topological entropy for switched systems, formulated in terms of the minimal number of trajectories needed to approximate all trajectories with a finite precision. For general switched linear systems, we prove that the topological entropy is independent of the set of initial states. We construct an upper bound for the topological entropy in terms of an average of the measures of system matrices of individual modes, weighted by their corresponding active times, and a lower bound in terms of an active-time-weighted average of their traces. For switched linear systems with scalar-valued state and those with pairwise commuting matrices, we establish formulae for the topological entropy in terms of active-time-weighted averages of the eigenvalues of system matrices of individual modes. For the more general case with simultaneously triangularizable matrices, we construct upper bounds for the topological entropy that only depend on the eigenvalues, their order in a simultaneous triangularization, and the active times. In each case above, we also establish upper bounds that are more conservative but require less information on the system matrices or on the switching, with their relations illustrated by numerical examples. Stability conditions inspired by the upper bounds for the topological entropy are presented as well.

1. In information theory, entropy notions are often formulated using binary logarithms due to their connection with binary signals. In this paper, we use natural logarithms to avoid generating additional multiplicative constants \( \ln 2 \) when computing the topological entropy.

2. In all examples, we denote by \( t_1< t_2 < \cdots \) the sequence of switches and let \( t_0 := 0 \), with \( \sigma = 1 \) on \( [t_{2k}, t_{2k+1}) \) and \( \sigma = 2 \) on \( [t_{2k+1}, t_{2k+2}) \).

3. We can apply [11, Th. 27, p. 34] to the switched linear system (14) as the switching signal \( \sigma \) is piecewise constant.

4. Following (23), the upper bound (24) is tighter than the one in the previous result [43, eq. (19)].

5. In particular, for each \( p \in \mathcal P\), the diagonal entries \( a_p^i \) are also the eigenvalues of the original system matrix \( A_p \) [17, Th. 2.4.8.1, p. 117].

6. For example, when the switching signal \( \sigma \) is periodic; see [36, Sec. 3.2.1] for more conditions.

7. A sufficient condition for simultaneous triangularizability is that the matrices \( A_p \) are pairwise commuting (see, e.g., [17, Th. 2.3.3, p. 103]). More sufficient conditions can be found in [25]. A necessary and sufficient condition is that the Lie algebra \( \{A_p: p \in \mathcal P\}_{LA} \) is solvable (see, e.g., [18, pp. 10, 16]). More necessary and sufficient conditions can be found in [13, 31].

The work of G. Yang and J. P. Hespanha was supported by the Office of Naval Research under the MURI Grant N00014-16-1-2710, and by the National Science Foundation under the Grants CNS-1329650 and EPCN-1608880. The work of D. Liberzon was supported by the National Science Foundation under the Grant CMMI-1662708, and by the Air Force Office of Scientific Research under the Grant FA9550-17-1-0236. The authors thank Raphaël M. Jungers for his comments on a preliminary version of the paper.

Authors and Affiliations

1. Center for Control, Dynamical Systems, and Computation, University of California, Santa Barbara, CA, 93106, USA

   Guosong Yang & João P. Hespanha

2. Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA

   A. James Schmidt & Daniel Liberzon

Corresponding author

Correspondence to Guosong Yang.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A Proof of Lemma 1

As a direct consequence of the definition (12), the maximal weighted average \( \bar{a} \) satisfies

and thus \( \limsup _{T \rightarrow \infty }\, \bar{a}(T) \ge \max \{\hat{a},\, 0\} \).

It remains to prove that the reverse inequality holds as well. The definition (11) of the asymptotic weighted average \( \hat{a} \) implies that for each \( \delta > 0 \), there is a large enough \( T_\delta ' \ge 0 \) such that \( \sum _{p \in \mathcal P} a_p \rho _p(t) < \hat{a} + \delta \) for all \( t > T_\delta ' \). For a \( T > T_\delta ' \), let

Then, \( \sum _{p \in \mathcal P} a_p \tau _p(t^*(T)) \ge 0 \). If \( t^*(T) \in (T_\delta ', T] \), then

Otherwise \( t^*(T) \in [0, T_\delta '] \), and thus

with the constant \( a_m := \max _{p \in \mathcal P} a_p \). Combining the two cases above yields

Hence

As \( \delta > 0 \) is arbitrary, we have \( \limsup _{T \rightarrow \infty }\, \bar{a}(T) \le \max \{\hat{a},\, 0\} \).

B Proof of Lemma 2

1. 1.

   As \( R(\hat{x}) \subset B_{A_\sigma }(\hat{x}, \varepsilon , T) \) for all \( \hat{x} \in G(\theta ) \), we have

   $$\begin{aligned} K = \bigcup _{\hat{x} \in G(\theta )} R(\hat{x}) \subset \bigcup _{\hat{x} \in G(\theta )} B_{A_\sigma }(\hat{x}, \varepsilon , T). \end{aligned}$$

   Then, (4) implies that the grid \( G(\theta ) \) is \( (T, \varepsilon ) \)-spanning, and thus

   $$\begin{aligned} \log S(A_\sigma , \varepsilon , T, K) \le \log |G(\theta )| = \sum _{i=1}^{n} \log (2 \lfloor 1/\theta _i \rfloor + 1) \le \sum _{i=1}^{n} \log (2/\theta _i + 1). \end{aligned}$$

   Consequently, the definition of entropy (5) implies

   $$\begin{aligned} h(A_\sigma )\le & {} \lim _{\varepsilon \searrow 0} \limsup _{T \rightarrow \infty } \sum _{i=1}^{n} \dfrac{\log (2/\theta _i + 1)}{T} \\= & {} \lim _{\varepsilon \searrow 0} \limsup _{T \rightarrow \infty } \sum _{i=1}^{n} \dfrac{\log (1/\theta _i)}{T}+ \lim _{\varepsilon \searrow 0} \limsup _{T \rightarrow \infty } \sum _{i=1}^{n} \dfrac{\log (2 + \theta _i)}{T}, \end{aligned}$$

   where the last term equals 0 if (17) holds.

2. 2.

   For all distinct points \( \hat{x}, \hat{x}' \in G(\theta ) \), as \( \hat{x}' \notin R(\hat{x}) \) and \( B_{A_\sigma }(\hat{x}, \varepsilon , T) \subset R(\hat{x}) \), we have \( \hat{x}' \notin B_{A_\sigma }(\hat{x}, \varepsilon , T) \). Then, (6) implies that the grid \( G(\theta ) \) is \( (T, \varepsilon ) \)-separated, and thus

   $$\begin{aligned}&\log N(A_\sigma , \varepsilon , T, K) \ge \log |G(\theta )| \\&= \sum _{i=1}^{n} \log (2 \lfloor 1/\theta _i \rfloor + 1) > \sum _{i=1}^{n} \log (\max \{2/\theta _i - 1,\, 1\}). \end{aligned}$$

   Consequently, the definition of entropy (5) implies

   $$\begin{aligned} \begin{aligned} h(A_\sigma )&\ge \lim _{\varepsilon \searrow 0} \limsup _{T \rightarrow \infty } \sum _{i=1}^{n} \dfrac{\log (\max \{2/\theta _i - 1,\, 1\})}{T} \\&= \lim _{\varepsilon \searrow 0} \limsup _{T \rightarrow \infty } \sum _{i=1}^{n} \dfrac{\log (1/\theta _i)}{T} + \lim _{\varepsilon \searrow 0} \limsup _{T \rightarrow \infty } \sum _{i=1}^{n} \dfrac{\log (\max \{2 - \theta _i,\, \theta _i\})}{T}, \end{aligned} \end{aligned}$$

   where the last term equals 0 if (17) holds.

C Proof of Corollary 2

First, the definition (11) of \( \hat{a} \) and the subadditivity of limit suprema imply

which, combined with (28), implies the upper bound (29). For the case where the limits \( \lim _{t \rightarrow \infty } \rho _p(t) \) exist and \( a_p \ge 0 \) for all \( p \in \mathcal P\), the inequalities in the derivation above becomes equalities due to the additivity of limits and \( \max \{a_p,\, 0\} = a_p \). Second, the definition (11) of \( \hat{a} \) implies

which, combined with (28), implies the upper bound (30).

D Proof of Lemma 6

First, we establish the upper bound in (36). For each \( p \in \mathcal P\), as \( N_p \) is nilpotent, there is a positive integer \( k_p \) such that \( N_p^{k_p} = 0 \). Let \( k_s := \sum _{p \in \mathcal P} k_p \), which is finite as the index set \( \mathcal P\) is finite. Define the weighted average matrix over [0, t] by

For all \( t \ge 0 \), as \( \{N_p: p \in \mathcal P\} \) is a commuting family, we have \( (N(t))^{k_s} = 0 \). Also, \( \Vert N(t)\Vert \le \eta _M := \max _{p \in \mathcal P} \Vert N_p\Vert \). Hence for all \( v \in \mathbb C^n \), we have

with \( c_\delta := \max \{(\eta _M/\delta )^{k_s - 1},\, 1\} > 0 \).

Second, we establish the lower bound in (36). As \( \Vert {-N(t)}\Vert = \Vert N(t)\Vert \le \eta _M \) for all \( t \ge 0 \), the proof above also implies that for all \( v \in \mathbb C^n \), we have

that is, \( \Vert e^{N(t)\, t} v\Vert \ge c_\delta ^{-1} e^{-\delta t} \Vert v\Vert \) for all \( t \ge 0 \).

E Computation of \( h(D_{\sigma _2}) \) using (34) in Example 3

Recall from footnote 2 that \( \sigma = 1 \) on \( [t_{2k}, t_{2k+1}) \) and \( \sigma = 2 \) on \( [t_{2k+1}, t_{2k+2}) \), where \( t_0 = 0 \), \( t_1 = 1 \), and \( t_k = 9^{k-1} + 9^{k-2} \) for all \( k \ge 2 \). Hence

(68)

and thus

Then, \( \bar{a}_1 \) and \( \bar{a}_2 \) in (34) satisfy

Hence

Therefore,

F Proof of Lemma 7

We regard (43) as a family of scalar differential equations (recall that here \( \xi _\sigma ^k \) denotes the k-th scalar component of \( \xi _\sigma \)):

and prove Lemma 7 by mathematical induction. For brevity, let

Then, \( \varPsi \) in (50) can be written as

1.1 F.1 The basis of induction

For the n-th scalar differential equation \( \dot{\xi }_\sigma ^n = a_\sigma ^n \xi _\sigma ^n \), the state-transition function is defined by

Hence the n-th scalar component of \( \xi _\sigma (x, t) \) satisfies \( \xi _\sigma ^n(x, t) = e^{\eta _n(t)} x_n \), that is, (50) holds for \( k = n \).

1.2 F.2 The inductive step

For an arbitrary \( m \in \{1, \ldots , n-1\} \), suppose that \( \xi _\sigma ^k(x, t) \) satisfy (50) for all \( k \in \{m+1, \ldots , n\} \). For the m-th differential equation

the state-transition function is defined by

By variation of constants, the m-th scalar component of \( \xi _\sigma (x, t) \) satisfies

Based on the definition (52) of \( \mathcal C_{k,l,i} \) and the formula (69) of \( \varPsi \), we have

and

Changing the order of summation, we obtain

where in the last step we also let \( i' = i + 1 \). Next, we prove that the family of sets \( \{\{m\} \times \mathcal C_{k,l,i'-1}: k = m+1, \ldots , l-i'+1\} \) forms a partition of \( \mathcal C_{m,l,i'} \).

• For all \( (c_1, \ldots , c_{i'}) \in \mathcal C_{k_1,l,i'-1} \) and \( (c'_1, \ldots , c'_{i'}) \in \mathcal C_{k_2,l,i-1} \) with \( k_1 \ne k_2 \), as \( c_1 = k_1 \ne k_2 = c'_1 \), we have \( (c_1, \ldots , c_{i'}) \ne (c'_1, \ldots , c'_{i'}) \). Hence the sets in \( \{\{m\} \times \mathcal C_{k,l,i'-1}: k = m+1, \ldots , l-i'+1\} \) are pairwise disjoint.

• For all \( (c_1, \ldots , c_{i'}) \in \mathcal C_{k,l,i'-1} \), as \( c_1 = k \ge m+1 \) and \( c_{i'} = l \), we have \( (m, c_1, \ldots , c_{i'}) \in \mathcal C_{m,l,i'} \). Hence \( \bigcup _{k=m+1}^{l-i'-1} \{m\} \times \mathcal C_{k,l,i'-1} \subset \mathcal C_{m,l,i'} \).

• For all \( (c_0, \ldots , c_i') \in \mathcal C_{m,l,i'} \), as \( c_1 \ge c_0 + 1 = m + 1 \) and \( c_1 \le c_{i'} - (i' - 1) = l - i' + 1 \), we have \( k := c_1 \) satisfies \( m + 1 \le k \le l - i' + 1 \) and \( (c_0, \ldots , c_{i'}) \in \{m\} \times \mathcal C_{k,l,i'-1} \). Hence \( \mathcal C_{m,l,i'} \subset \bigcup _{k=m+1}^{l-i'-1} \{m\} \times \mathcal C_{k,l,i'-1} \).

Therefore,

Combining the results above, we obtain

that is, (50) holds for \( k = m \). Therefore, mathematical induction implies that (50) holds for all \( k \in \{1, \ldots , n\} \).

G Proof of Lemma 8

For every \( k \in \{1, \ldots , n\} \), following the formula (50) and the triangle inequality, the k-th scalar component of \( \xi _\sigma (x, t) \) satisfies

First, following the definitions (46) of \( \bar{d}_i \) and (51) of \( \eta _i \), we have

Hence

where the last inequality follows partially from the definition (52) of the sets \( \mathcal C_{k,l,i} \). As \( b_M^i t^i \) and \( \sum _{j=k+1}^{l} \bar{d}_j(t)\, t \) are independent of the choice of \( (c_0, \ldots , c_i) \in \mathcal C_{k,l,i} \) and the latter is also independent of the choice of \( i \in \{1, \ldots , l-k\} \), and the set \( \mathcal C_{k,l,i} \) can be characterized by the combinations of \( i-1 \) increasing integers from \( k+1 \) to \( l-1 \), we have

where the last inequality follows partially from the binomial formula. Hence

Note that the upper bound for \( |\xi _\sigma ^k(x, t)| \) above is decreasing in k. Indeed, the upper bound for \( |\xi _\sigma ^{k-1}(x, t)| \) satisfies

Hence we obtain (53) by taking the upper bound for \( |\xi _\sigma ^1(x, t)| \) (recall that we take \( \Vert \cdot \Vert \) to be the \( \infty \)-norm; see Remark 1).

Second, recall \( c_0 = k \) and \( c_i = l \), and let \( s_0 := t \) and

Following the definition (51) of \( \eta _i \), we have

Hence

where the last inequality follows partially from the definition (52) of the sets \( \mathcal C_{k,l,i} \). As \( b_M^i t^i \) and \( \max _{k \le j \le l} a_m^j t \) are independent of the choice of \( (c_0, \ldots , c_i) \in \mathcal C_{k,l,i} \) and the latter is also independent of the choice of \( i \in \{1, \ldots , l-k\} \), and the set \( \mathcal C_{k,l,i} \) can be characterized by the combinations of \( i-1 \) increasing integers from \( k+1 \) to \( l-1 \), we have

where the last inequality follows partially from the binomial formula. Hence

Note that the upper bound for \( |\xi _\sigma ^k(x, t)| \) above is decreasing in k. Indeed, the upper bound for \( |\xi _\sigma ^{k-1}(x, t)| \) satisfies

Hence we obtain (54) by taking the upper bound for \( |\xi _\sigma ^1(x, t)| \) (recall that we take \( \Vert \cdot \Vert \) to be the \( \infty \)-norm; see Remark 1).

H Computation of an upper bound for \( h(U_{\sigma _2}) \) using (44) in Example 4

Following (68) in “Appendix E”, we have

Then, \( \bar{a}_1 \) and \( \bar{d}_2 \) in (44) satisfy

Hence

Therefore,

Reprints and permissions