IEEE CONTROL SYSTEMS LETTERS, VOL. 4, NO.

2, APRIL 2020 385

On the Design of Stabilizing Cycles for

Switched Linear Systems
Atreyee Kundu

Abstract—Given a family of systems, identifying preserve stability, are constructed as concatenation of negative
stabilizing switching signals in terms of infinite walks weight cycles [3] (henceforth, also referred to as stabilizing
constructed by concatenating cycles on the underlying cycles).1 This class of results was first introduced in [8] for
directed graph of a switched system that satisfy certain switched linear systems, and was later extended to the setting
conditions, is a well-known technique in the literature. This
letter deals with a new method to design these cycles for
of switched nonlinear systems in [9]. A primary feature of
stability of switched linear systems. We employ properties the stability conditions proposed in [8], [9] is their numerical
of the subsystem matrices and mild assumption on the tractability compared to the prior results that rely on point-
admissible switches between the subsystems for this wise properties of the switching signals [10], [14]. In contrast
purpose. In contrast to prior works, our construction of to verifying certain conditions on the number of switches and
stabilizing cycles does not involve design of Lyapunov-like duration of activation of unstable subsystems on every interval
functions and storage of sets of scalars in memory prior to of time, one needs to detect negative weight cycles on the
the application of a cycle detection algorithm. As a result, underlying weighted directed graph of a switched system.
the techniques proposed in this letter offer improved
numerical tractability. Existence of these cycles depends on two factors: (i) connec-
tivity of the directed graph, and (ii) weights associated to the
Index Terms—Switched systems, stability, stabilizing vertices and edges of this graph. While (i) is determined by the
cycles, algorithms, directed graphs. admissible switches between the subsystems, the elements of
(ii) are scalar quantities calculated from Lyapunov-like func-
tions, the choice of which is not unique. This feature leads to
I. I NTRODUCTION the problem of ‘co’-designing Lyapunov-like functions such
A. Motivation that the underlying weighted directed graph of a switched
SWITCHED system has two ingredients — a family system admits a stabilizing cycle. This design problem, in
A of systems and a switching signal. The switching sig-
nal selects an active subsystem at every instant of time, i.e.,
general, is numerically difficult, see [9, Sec. 3] for a detailed
discussion.
the system from the family that is currently being followed As a natural choice, the existing literature considers the
[12, Sec. 1.1.2]. In this letter we work with switched systems Lyapunov-like functions and the corresponding vertex and
in the setting of linear dynamics in discrete-time. edge weights to be “given”, and detects negative weight cycles
Given a family of systems, identification of classes of on the underlying weighted directed graph of a switched
switching signals that preserve stability of the resulting system. However, non-existence of a negative weight cycle
switched system is a key topic in the literature [12, Ch. 3]. with the given choice of vertex and edge weights does not
In the recent past this problem has been studied widely by conclude that a family of systems does not admit such cycles
employing multiple Lyapunov-like functions [4] and graph- at all. In addition, storing the vertex and edge weights prior to
theoretic tools. A weighted directed graph [3] is associated the application of a negative weight cycle detection algorithm
to a family of systems and the admissible transitions between requires a huge memory when the number of subsystems is
them; the vertices of this graph are weighted by a measure of large. These features motivate the search for a method to con-
the rate of growth or decay of the Lyapunov-like functions cor- struct stabilizing cycles that is independent of the choice of
responding to the subsystems, and the edges are weighted by Lyapunov-like functions and works without complete knowl-
a measure of the jump between these functions. A switching edge of the vertex and edge weights of the underlying directed
signal is expressed as an infinite walk on the above directed graph of a switched system. In this letter we report our result
graph. Infinite walks whose corresponding switching signals that addresses these requirements.

Manuscript received June 1, 2019; revised July 26, 2019; accepted

July 29, 2019. Date of publication August 2, 2019; date of current version B. Our Contributions
August 16, 2019. This work was supported by the Innovation in Science Given a family of systems (containing both stable and unsta-
Pursuit for Inspired Research (INSPIRE) Faculty Award IFA17-ENG225
by the Department of Science and Technology, Government of India.
ble components) and a set of admissible switches between the
Recommended by Senior Editor S. Tarbouriech.
The author is with the Department of Electrical Engineering, 1 By the term ‘stabilizing cycles’ we refer to cycles such that a switch-
Indian Institute of Science, Bengaluru 560012, India (e-mail: ing signal corresponding to an infinite walk constructed by concatenating
atreyeek@iisc.ac.in). these cycles, is stabilizing. We will discuss and employ different methods of
Digital Object Identifier 10.1109/LCSYS.2019.2932836 constructing such cycles throughout this letter.
2475-1456 c 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
386 IEEE CONTROL SYSTEMS LETTERS, VOL. 4, NO. 2, APRIL 2020

subsystems, we first identify sufficient conditions on cycles where x(t) ∈ Rd is the vector of states at time t,
on the underlying directed graph of the switched system such P = {1, 2, . . . , N} is an index set, Ai ∈ Rd×d , i ∈ P
that they are stabilizing. These conditions are derived in terms are constant matrices, and
of properties of the subsystem matrices, and hence the use of ◦ a switching signal σ : N0 → P that specifies at every time
multiple Lyapunov-like functions is avoided. In particular, we t, the index of the active subsystem, i.e., the dynamics
rely on (matrix) commutators between the subsystem matrices from (2) that is being followed at t.
and mild assumption on the admissible switches between the The solution to (1) is given by
subsystems for this purpose. Our stability condition involves
the rate of decays of the Schur stable matrices, upper bounds x(t) = Aσ (t−1) . . . Aσ (1) Aσ (0) x0 , t ∈ N, (3)
on the Euclidean norms of the commutators of the subsys- where we have suppressed the dependence of x on σ for
tem matrices, certain scalars capturing the properties of these notational simplicity.
matrices individually, and the total number of subsystems. In Definition 1 [1, Sec. 2]: The switched system (1) is globally
contrast to prior works, our directed graphs are unweighted, exponentially stable (GES) under a switching signal σ if there
and the detection of our stabilizing cycles depends only on the exist positive numbers c and γ such that for arbitrary choices
activation of a vertex whose corresponding subsystem satis- of the initial condition x0 , the following inequality holds:
fies certain conditions. We then present an algorithm to detect
cycles on the underlying directed graph of a switched system x(t) ≤ c exp(−γ t)x0  for all t ∈ N. (4)
that satisfy our conditions. We are interested in the following problem.
Matrix commutators (Lie brackets) have been employed to Problem 1: Given a family of systems (2) (containing both
study stability of switched systems with all or some stable stable and unstable components) and a set of admissible
subsystems earlier in the literature [1], [6], [7], [13]. However, switches, find a class of switching signals S such that the
to the best of our knowledge, this is the first instance when switched system (1) is GES under every σ ∈ S .
they are employed to construct stabilizing cycles for switched Prior to presenting our solution to Problem 1, we catalog
systems. some required preliminaries.
In summary, the main contribution of this letter is in extend-
ing the technique of employing stabilizing cycles to construct
stabilizing switching signals, by proposing a new method for B. Family of Systems
designing these cycles. Our class of stabilizing cycles offers Let PS and PU ⊂ P denote the sets of indices of Schur
better numerical tractability in terms of detecting its elements stable and unstable subsystems, respectively, P = PS
PU .2
compared to the existing results. Let E(P ) denote the set of ordered pairs (i, j) such that a
switch from subsystem i to subsystem j is admissible, i, j ∈ P .3
Let
C. Paper Organization
The remainder of this letter is organized as follows: we M = maxAi . (5)
i∈P
formulate the problem under consideration and catalog the
required preliminaries for our result in Section II. Our main The following fact follows from the properties of Schur
result appears in Section III. We also discuss various features stable matrices.
of our result in this section. In Section IV we present numer- Fact 1: There exists m ∈ N and ρ ∈ ]0, 1[ such that the
ical experiments. We provide a comparison of our result with following set of inequalities holds:
 m
the existing methods in Section V, and conclude in Section VI. A  ≤ ρ, i ∈ PS . (6)
i
A proof of our main result appears in Section VII.
We will employ the set of (matrix) commutators defined
below in our stability analysis4 :
D. Notation
N is the set of natural numbers, N0 = N ∪ {0}. · denotes Ep,i = Ap Ai − Ai Ap , p ∈ PS , i ∈ P \{p}. (7)
the Euclidean norm (resp., induced matrix norm) of a vector
(resp., a matrix). For a matrix P, given by a product of matrices C. Switching Signals
Mi ’s, |P| denotes the length of the product, i.e., the number We associate a directed graph G(V, E) with the switched
of matrices that appear in P, counting repetitions. system (1) in the following manner:
◦ The set of vertices V is the set of indices of the
subsystems, P .
II. P RELIMINARIES ◦ The set of edges E contains a directed edge from a vertex
A. The Problem i to a vertex j whenever (i, j) ∈ E(P ).
We consider a discrete-time switched linear Recall that a walk on a directed graph is
system [12, Sec. 1.1.2] an alternating sequence of vertices and edges
2 A matrix A ∈ Rd×d is Schur stable if all its eigenvalues are inside the
x(t + 1) = Aσ (t) x(t), x(0) = x0 , t ∈ N0 (1)
open unit disk. We call A unstable if it is not Schur stable.
3 Clearly, (i, i) implies that it is allowed to dwell on a subsystem for two
generated by or more consecutive time steps.
◦ a family of systems 4 These matrix commutators will be employed in rearranging the matrix
products on the right-hand side of (3). An exchange between Ap with itself
x(t + 1) = Ai x(t), x(0) = x0 , i ∈ P , t ∈ N0 , (2) is undefined, and hence i ∈ P \{p}.
KUNDU: ON DESIGN OF STABILIZING CYCLES FOR SWITCHED LINEAR SYSTEMS 387

W = v0 , e1 , v1 , e2 , v2 , . . . , vn−1 , en , vn , where v ∈ V, and

e = (v−1 , v ) ∈ E, 0 <  ≤ n. The length of a walk is its
m(m + 1) Nm−2 γ Nm
number of edges, counting repetitions, e.g., the length of W ρeγ m + (N − 1) M εp e ≤ 1. (10)
above is n. The initial vertex of W is v0 and the final vertex 2
of W is vn . If v0 = vn , we say that the walk W is closed. A
Then the switched system (1) is GES under every switching
closed walk W is called a cycle if the vertices vi , 0 < i < n
signal σ whose corresponding infinite walk W is constructed
are distinct from each other and v0 . By the term infinite walk
by concatenating elements from Cp .
we mean a walk of infinite length, i.e., it has infinitely many
Theorem 1 is our solution to Problem 1. The elements of
edges.
the class of stabilizing switching signals S correspond to the
Fact 2 [8, Fact 3]: The set of switching signals σ : N0 →
infinite walks that are constructed by concatenating elements
P and the set of infinite walks on G(V, E) are in bijective
from the set of cycles, Cp , where p is a stable subsystem
correspondence.
satisfying certain conditions. Notice that since ρ < 1, there
Clearly, given a family of systems (2) and a set of admissible
always exists a number γ (could be very small) such that
switches, we are interested in a class of infinite walks whose
condition (8) holds. If in addition, there exists a p ∈ PS such
corresponding class of switching signals ensures GES of the
that G(V, E) admits at least one cycle that involves vertex p,
switched system (1).
and the Euclidean norms of (matrix) commutators of Ap and
For a cycle W on G(V, E), let V (W) = {v ∈
Ai , i ∈ P \{p}, are bounded above by a scalar εp small enough
V|v appears in W}, and E (W) = {(u, v) ∈ E|(u, v)
such that condition (10) holds, then (1) is GES under a σ
appears inW}.
whose corresponding infinite walk is constructed by concate-
Definition 2: Fix a vertex v ∈ V. A cycle W =
nating the cycles from Cp . Our stability conditions have the
v0 , (v0 , v1 ), v1 , . . . , vn−1 , (vn−1 , v0 ), v0 on G(V, E) is called a
following important features.
v-cycle if v ∈ V (W).
(1) (1) (1) 1) Theorem 1 accommodates sets of matrices Aj , j ∈ P ,
Definition 3: The distinct cycles W1 = v0 , (v0 , v1 ), for which Ap and Ai , p ∈ PS , i ∈ P \{p}, do not necessarily
(1) (1) (1) (1) (1) (2) (2) (2)
v1 , . . . , vn1 −1 , (vn1 −1 , v0 ), v0 , W2 = v0 , (v0 , v1 ), commute, but are “close” to sets of matrices for which they
(2) (2) (2) (2) (2) (r) (r)
v1 , . . . , vn1 −1 , (vn1 −1 , v0 ), v0 , . . . , Wr = v0 , (v0 , commute. When these matrices commute for all i ∈ P \{p},
(r) (r) (r) (r) (r) (r)
v1 ), v1 , . . . , vn1 −1 , (vn1 −1 , v0 ), v0 , on G(V, E) are called (i.e., εp = 0), condition (10) reduces to condition (8). The
stability conditions of Theorem 1 are inherently robust in the
concatenable on a vertex u ∈ V if v(1) (2)
0 = v0 = · · · = v0 = u.
(r)
above sense. Indeed, if we are relying on approximate models
Let Cv denote the set of all v-cycles on G(V, E), v ∈ V, of Aj , j ∈ P , or the elements of Aj , j ∈ P , are prone to
that are concatenable on vertex u for some u ∈ V. We will evolve over time, then GES of (1) holds under our stabilizing
consider the following structures. switching signals as long as for some p ∈ PS , the commutators
◦ If there is no cycle W on G(V, E) such that v ∈ V (W), of Ap and Ai , i ∈ P \{p}, in their Euclidean norm, are bounded
then Cv = ∅. above by a small scalar εp such that condition (10) holds.
◦ If G(V, E) admits exactly one v-cycle W, then Cv is a 2) The proposed construction of infinite walks involves
singleton. In particular, Cv = {W}. activation of a vertex (subsystem) p ∈ PS for which
We will work with infinite walks on G(V, E) constructed conditions (9)-(10) hold. Clearly, we require PS = ∅.
by concatenating the elements from Cv . At this point, it is However, stabilizing cycles with all unstable vertices except
important to clarify the meaning of such a concatenation. Let for p are perfectly admissible. The activation of at least
W1 , W2 , . . . , Wq be distinct concatenable v-cycles of length one Schur stable subsystem is also a requirement for
n1 , n2 , . . . , nq on G(V, E), respectively. An infinite walk W Lyapunov-like functions based construction of stabilizing
(j )
obtained by concatenating Wj , j = 1, 2, . . . , q is W = v0 1 , cycles.
(j ) (j ) (j ) (j ) (j ) (j ) (j ) (j ) (j )
(v0 1 , v1 1 ), v1 1 , . . . , vn11−1 , (vn11−1 , v0 1 ), v0 2 , (v0 2 , v1 2 ), Remark 1: Commutation relations between the subsystem
(j ) (j ) (j ) (j ) (j ) matrices or certain products of these matrices have been
v1 2 , . . . , vn22−1 , (vn22−1 , v0 2 ), v0 3 , . . . , jk ∈ {1, 2, . . . , q},
employed to study stability of the switched system (1) ear-
k ∈ N.
lier in the literature. The switched system (1) is stable under
We are now in a position to present our result.
arbitrary switching [12, Ch. 2] if all the subsystems Ai ,
i ∈ P , are Schur stable, and commute pairwise [13] or
are “sufficiently close” to a set of matrices whose elements
III. R ESULT
commute pairwise [1]. Recently in [6], [7] stability of (1)
Theorem 1: Consider a switched system (1) and its under- under restricted switching is studied using matrix commu-
lying directed graph G(V, E). Let γ be an arbitrary positive tators. Given an admissible minimum dwell time, in [6] we
number such that identify conditions on the subsystem matrices such that sta-
bility of (1) is preserved under all switching signals satisfying
ρeγ m < 1. (8) the given minimum dwell time. The overarching hypothesis
there is that all subsystems are Schur stable. The problem
Suppose that there exists p ∈ PS that satisfies the following of identifying classes of stabilizing switching signals when
conditions. not all systems in the family (2) are stable and an admissible
◦ Cp = ∅, and switching signal obeys certain minimum and maximum dwell
◦ there exists a scalar εp small enough such that times on all subsystems, is addressed in [7]. In the current
  work we tackle the problem of algorithmically construct-
Ep,i  ≤ εp for all i ∈ P \{p}, (9) ing stabilizing cycles by employing commutation relations
388 IEEE CONTROL SYSTEMS LETTERS, VOL. 4, NO. 2, APRIL 2020

Algorithm 1 Detection of p for Which Conditions (9)-(10)

Hold, and Construction of Cp
Input: a family of systems (2) and a set of admissible
switches E(P )
Output: a set of concatenable p-cycles, Cp
1: Construct the underlying directed graph G(V, E) of the
switched system (1).
2: Compute m and ρ such that (6) holds.
3: Compute γ such that (8) holds.
4: for p ∈ PS do  
Fig. 1. Plot of x(t) versus t.
5: Compute εp such that (9) holds.
6: if (10) is satisfied, then
7: Create a set Lp containing all p-cycles on G(V, E).
8: if Lp = ∅, then
9: if Lp contains concatenable elements, then
10: Create a set Cp with all elements of Lp that are
concatenable on a vertex u for some u ∈ V.
11: else
12: Create a set Cp with any one element of Lp .
13: end if
14: else
15: Cp = ∅. Fig. 2. Plot of εp versus N with M = 2 and ρ = 0.9.
16: end if
17: if Cp = ∅ then
18: Store Cp in memory. IV. N UMERICAL E XPERIMENTS
Exit Algorithm 1
 Experiment 1: Consider P = {1, 2,  3} with A1 =
19:
20: end if 0.86 0.05 0.81 −0.07
and A2 = . Clearly, PS = {1}
21: end if −0.07 0.89 −0.74 0.73
22: end for and PU = {2}. Let E(P ) = {(1, 2), (2, 1)}.
It follows that L1 = {(1, (1, 2), 2, (2, 1), 1), (2, (2, 1), 1,
(1, 2), 2)}. Fix C1 = {1, (1, 2), 2, (2, 1), 1}. It is worth noting
between the subsystem matrices. We deal with families con- that both A1 A2  and A2 A1  > 1, and hence stability of (1)
taining both stable and unstable subsystems, and obeying under the switching signal σ (0) = 1, σ (1) = 2, σ (2) = 1,
pre-specified restrictions on admissible switches between the σ (3) = 2, . . . is non-trivial. We will apply the conditions of
subsystems. See Remark 2 for a discussion on our analysis Theorem 1 to determine of GES of (1) under the above σ .
technique. We have A1  = 0.89 and M = 1.25. Let ρ = 0.90 and
We next provide an algorithm (Algorithm 1) that detects γ = 0.0001. It follows that m = 1 and ρeγ m = 0.90 < 1. We
a vertex (subsystem) p such that conditions (9)-(10) hold, compute ε1 = A1 A2 − A2 A1  = 0.06. Consequently,
and constructs the set of cycles, Cp . Once a suitable Cp is m(m + 1) Nm−2 γ Nm
obtained, an infinite walk W = v0 , (v0 , v1 ), v1 , (v1 , v2 ), v2 , . . . ρeγ m + (N − 1) M εp e = 0.96 < 1.
2
can be constructed by concatenating the elements of Cp
as described in Section II, and the corresponding switch- We demonstrate (x(t))t∈N0 under σ corresponding to 1000
ing signal σ can be designed as σ (0) = v0 , σ (1) = different initial conditions x0 chosen uniformly at random from
v1 , σ (2) = v2 , . . .. Clearly, if Cp is a singleton, e.g., the interval [−10, 10]2 in Figure 1.
Cp = {W}, then a stabilizing σ described in Theorem 1 is Experiment 2: We now check scalability of the stability
periodic. It corresponds to the infinite walk constructed by conditions in Theorem 1 with respect to N, M, m and ρ. In
repeating W. the simplest case when there is a p ∈ PS such that the matrix
An important aspect of our stability conditions is the Ap commutes with every matrix Ai , i ∈ P \{p} (i.e., εp = 0),
existence and detection of a set of cycles, Cp , correspond- it follows that condition (10) holds even when the numbers
ing to a vertex (subsystem) p for which conditions (9)- M, N and m are very large. A more interesting case is, of
(10) hold. The existence of a non-empty Cp depends solely course, when the above matrices do not commute but are suf-
on the connectivity of G(V, E) which is governed by ficiently “close”. We fix γ = 0.0001, and vary the parameters
the given set of admissible switches E(P ). We address N, m, M, ρ to plot upper bounds on εp for the satisfaction of
the detection issue in two steps: first, we list out all condition (10), see Figures 2, 3 and 4. Not surprisingly, it is
p-cycles on G(V, E), and second, we pick elements from observed that the size of the class of non-commuting matrices
the above list that are concatenable on a vertex u for some catered by Theorem 1 shrinks with increasing N, m, M, and ρ.
u ∈ V. Off-the-shelf algorithms from graph theory can be
employed to enumerate all cycles on G(V, E) that involve V. D ISCUSSION
a pre-specified vertex p, see, e.g., [5] and the references The method of characterizing stabilizing switching signals
therein. in terms of their corresponding infinite walks constructed by
KUNDU: ON DESIGN OF STABILIZING CYCLES FOR SWITCHED LINEAR SYSTEMS 389

and edge weights prior to the application of a negative weight

cycle detection algorithm, has a large memory requirement.
Recently in [2] the authors proposed a randomized algorithm
that detects a cycle on G(V, E) without prior knowledge of
vertex and edge weights of the graph, and identified sufficient
conditions on the connectivity and vertex and edge weights of
G(V, E) under which such a cycle is stabilizing (in the sense
that it is a negative weight cycle). The conditions on favourable
vertex and edge weights are provided in terms of their statis-
tical properties. However, given a family of systems (2), the
Fig. 3. Plot of εp versus N with m = 5 and ρ = 0.9. problem of designing Lyapunov-like functions Vi , i ∈ P such
that the corresponding scalars λi , i ∈ P and μij , (i, j) ∈ E(P )
satisfy the proposed conditions is not addressed.
In the current work we employ properties of the subsys-
tem matrices and avoid the use of Lyapunov-like functions.
In contrast to G(V, E), we do not associate weights to the
vertices and edges of G(V, E), and our detection mechanism
for a set cycles, Cp , solely depends on the connectivity of
G(V, E). However, the stability conditions presented in this
letter are restricted to the setting of switched linear systems
unlike the case of Lyapunov-like functions based construction
of stabilizing cycles that extends to the nonlinear setting, as
Fig. 4. Plot of εp versus N with M = 2 and m = 5. demonstrated in [9].

VI. C ONCLUDING R EMARKS

concatenating cycles that satisfy certain conditions, is not new In this letter we proposed a new method to construct stabi-
in the literature. Consider a directed graph G(V, E), which is lizing cycles for switched linear systems. The proposed result
the graph G(V, E) with vertex weights w(i) = −|ln λi |, if i ∈ involves properties of commutators of the subsystem matrices
PS and w(i) = |ln λi |, if i ∈ PU , and edge weights w(i, j) = and mild assumption on the admissible switches between the
ln μij , (i, j) ∈ E(P ). Here the scalars 0 < λi < 1 for p ∈ PS , subsystems. Algorithmic construction of stabilizing cycles for
λi ≥ 1 for p ∈ PU and μij > 0 for (i, j) ∈ E(P ), are computed switched nonlinear systems without involving the design of
from Lyapunov-like functions Vi : Rd → R corresponding to Lyapunov-like functions remains an open question.
the subsystems i ∈ P .
In [8], [9] a stabilizing cycle was characterized as a neg- VII. P ROOF OF O UR R ESULT
ative weight cycle on G(V, E). Notice that the existence of Proof of Theorem 1: Let (2) admit a p ∈ PS for which con-
a negative weight cycle W on G(V, E) depends on: (a) the ditions (9) and (10) hold. Let σ be a switching signal whose
connectivity of G(V, E), and (b) the weights associated to the corresponding infinite walk is constructed by concatenating
vertices and edges of G(V, E). While connectivity of G(V, E) elements from the set Cp . Let M be the corresponding word
is governed by the given set of admissible switches E(P ), (matrix product) defined as M = · · · Aσ (2) Aσ (1) Aσ (0) . The
there is an element of ‘choice’ associated to the Lyapunov- condition (4) for GES of (1) under σ can be written equiva-
like functions Vi , i ∈ P and hence the corresponding scalars lently as [1, Sec. 2]: there exist positive numbers c and γ such
λi , i ∈ P and μij , (i, j) ∈ E(P ). A natural question is, there- that
fore, the following: given a family of systems and a set of
admissible switches, can we design Lyapunov-like functions M ≤ ce−γ |M| for all |M|. (11)
Vi , i ∈ P (and hence, the corresponding scalars λi , i ∈ P and It, therefore, suffices to show that condition (11) holds for
μij , (i, j) ∈ E(P )) such that G(V, E) admits a negative weight the above σ . We will employ mathematical induction on |M|
cycle? To the best of our knowledge, this question is numer- for this purpose.
ically difficult, and only a partial solution can be obtained
as a special case of [11, Algorithm 2]. This partial solution A. Induction Basis
searches for suitable scalars over a finite number of choices Pick c large enough so that (11) holds for M satisfying
from the set of quadratic Lyapunov-like functions, see also [11, |M| ≤ Nm.
Remarks 9 and 12] for discussions.
In the absence of a complete solution to the above question, B. Induction Hypothesis
the existing literature considers the Lyapunov-like functions
Vi , i ∈ P and the corresponding scalars λi , i ∈ P and μij , Let |M| ≥ Nm + 1 and assume that (11) is proved for all
(i, j) ∈ E(P ) to be “given”, and searches for negative weight products of length less than |M|.
cycles on G(V, E). However, non-existence of such a cycle
with the given sets of vertex and edge weights, does not con- C. Induction Step
clude that (2) does not admit such a cycle at all, and hence adds Let M = LR, where |L| = Nm. We observe that L contains
to the conservatism of the class of results under consideration. at least m-many Ap . Indeed, each cycle in Cp contains vertex
Moreover, for large-scale switched systems, storing the vertex p, and the length of any cycle on G(V, E) is at most N.
390 IEEE CONTROL SYSTEMS LETTERS, VOL. 4, NO. 2, APRIL 2020

We rewrite L as L = Am p L1 + L2 , where |L1 | = (N − 1)m, − E2,1 A4 A3 A4 A3 A2 A1 − A2 E4,1 A3 A4 A3 A2 A1

and L2 contains at most (N −1) m(m+1)
2 terms of length Nm−1 − A2 A4 E3,1 A4 A3 A2 A1
with Nm − 2 Ai , i ∈ P and 1 Ep,i , i ∈ P \{p}. = A1 A2 A4 A1 A3 A4 A3 A2 − A1 A2 A4 E3,1 A4 A3 A2
Now, from the sub-multiplicativity and sub-additivity prop-
− A1 A2 A4 A3 E4,1 A3 A2 − A1 A2 A4 A3 A4 E3,1 A2
erties of the induced norm, we have
  − A1 A2 A4 A3 A4 A3 E2,1 − E2,1 A4 A3 A4 A3 A2 A1
 
M = LR ≤ Am
p L1 R + L2 R − A2 E4,1 A3 A4 A3 A2 A1 − A2 A4 E3,1 A4 A3 A2 A1
m(m + 1) Nm−2 = A1 A2 A1 A4 A3 A4 A3 A2 − A1 A2 E4,1 A3 A4 A3 A2
≤ ρce−γ (|M|−m) + (N − 1) M εp ce−γ (|M|−Nm)
 2  − A1 A2 A4 E3,1 A4 A3 A2 − A1 A2 A4 A3 E4,1 A3 A2
= ce−γ |M| ρeλm + (N − 1)(m(m + 1)/2)M Nm−2 εp eγ Nm . (12) − A1 A2 A4 A3 A4 E3,1 A2 − A1 A2 A4 A3 A4 A3 E2,1
− E2,1 A4 A3 A4 A3 A2 A1 − A2 E4,1 A3 A4 A3 A2 A1
In the above inequality the upper bounds  on L1 R and R are
  − A2 A4 E3,1 A4 A3 A2 A1
obtained from the relations |M| = Am p  + |L1 R| and |M| =
|L| + |R|, respectively. Applying (10) to (12) leads to (11). = A21 A2 A4 A3 A4 A3 A2 − A1 E2,1 A4 A3 A4 A3 A2
Consequently, (1) is GES under the σ in consideration. − A1 A2 E4,1 A3 A4 A3 A2 − A1 A2 A4 E3,1 A4 A3 A2
This completes our proof of Theorem 1. − A1 A2 A4 A3 E4,1 A3 A2 − A1 A2 A4 A3 A4 E3,1 A2
Remark 2: Our proof of Theorem 1 relies on combinatorial
− A1 A2 A4 A3 A4 A3 E2,1 − E2,1 A4 A3 A4 A3 A2 A1
arguments applied to the matrix product M split into sums
Amp L1 R + L2 R. Combinatorial analysis technique for stability
− A2 E4,1 A3 A4 A3 A2 A1 − A2 A4 E3,1 A4 A3 A2 A1 .
of switched system was first introduced in [1] for stability In the worst case the k-th instance of Ap in L (reading from the
under arbitrary switching, and was recently extended to right) is to be exchanged with k(N −1) terms, k = 1, 2, . . . , m,
stability under pre-specified dwell times in [6], [7]. The to obtain the desired structure of L.
following properties of stabilizing cycles are used in our
analysis: (i) each of them contains a vertex p for which
conditions (9)-(10) hold, and (ii) each of them is of length R EFERENCES
at most N. The choice of matrix commutators involves [1] A. A. Agrachev, Y. Baryshnikov, and D. Liberzon, “On robust Lie-
the subsystem matrix Ap and the subsystem matrices Ai , algebraic stability conditions for switched linear systems,” Syst. Control
Lett., vol. 61, no. 2, pp. 347–353, 2012.
i ∈ P \{p}, and they are utilized to rearrange any possible [2] N. Balachandran, A. Kundu, and D. Chatterjee, “A randomized algo-
product corresponding to an infinite walk constructed by rithms for stabilizing switching signals,” Math. Control Related Fields,
concatenating elements from Cp . Notice that the upper bound vol. 9, no. 1, pp. 159–174, 2019.
on the number of terms in L2 and their structure are obtained [3] B. Bollobás, Modern Graph Theory (Graduate Texts in Mathematics),
vol. 184. New York, NY, USA: Springer-Verlag, 1998.
by exchanging Ap with Ai , i ∈ P \{p} towards achieving [4] M. S. Branicky, “Multiple Lyapunov functions and other analysis tools
the form L = Am p L1 + L2 . Consider, for example, G(V, E) for switched and hybrid systems,” IEEE Trans. Autom. Control, vol. 43,
with V = {1, 2, 3, 4}, PS = {1, 2}, PU = {3, 4} and E(P ) = no. 4, pp. 475–482, Apr. 1998.
[5] D. B. Johnson, “Finding all the elementary circuits of a directed graph,”
{(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (3, 4), (4, 1), (4, 2), (4, 3)}. SIAM J. Comput., vol. 4, no. 1, pp. 77–84, 1975.
Let m = 2, and conditions (9)-(10) hold for p = 1. Suppose [6] A. Kundu, “Robust stability conditions for switched linear systems
that L = A2 A4 A3 A1 A4 A3 A2 A1 . It can be rewritten as under restricted switching,” arxiv: 1903.09440. [Online]. Available:
https://arxiv.org/abs/1903.09440
A2 A4 A3 A1 A4 A3 A2 A1 [7] A. Kundu and D. Chatterjee, “Robust matrix commutator conditions for
stability of switched linear systems under restricted switching,” arxiv:
= A2 A4 A1 A3 A4 A3 A2 A1 − A2 A4 E3,1 A4 A3 A2 A1 1903.10249. [Online]. Available: https://arxiv.org/abs/1903.10249
= A2 A1 A4 A3 A4 A3 A2 A1 − A2 E4,1 A3 A4 A3 A2 A1 [8] A. Kundu and D. Chatterjee, “Stabilizing discrete-time switched lin-
ear systems,” in Proc. 17th ACM Conf. Hybrid Syst. Comput. Control,
− A2 A4 E3,1 A4 A3 A2 A1 Apr. 2014, pp. 11–20.
[9] A. Kundu and D. Chatterjee, “On stability of discrete-time switched
= A1 A2 A4 A3 A4 A3 A2 A1 − E2,1 A4 A3 A4 A3 A2 A1 systems,” Nonlin. Anal. Hybrid Syst., vol. 23, pp. 191–210, Feb. 2017.
− A2 E4,1 A3 A4 A3 A2 A1 − A2 A4 E3,1 A4 A3 A2 A1 [10] A. Kundu, P. K. Mishra, and D. Chatterjee, “Stabilizing discrete-time
switched systems with inputs,” in Proc. 54th Conf. Decis. Control,
= A1 A2 A4 A3 A4 A3 A1 A2 − A1 A2 A4 A3 A4 A3 E2,1 Dec. 2015, pp. 4897–4902.
− E2,1 A4 A3 A4 A3 A2 A1 − A2 E4,1 A3 A4 A3 A2 A1 [11] A. Kundu and D. E. Quevedo, “Stabilizing scheduling policies for
networked control systems,” IEEE Trans. Control Netw. Syst., to be
− A2 A4 E3,1 A4 A3 A2 A1 published.
[12] D. Liberzon, Switching in Systems and Control (Systems & Control:
= A1 A2 A4 A3 A4 A1 A3 A2 − A1 A2 A4 A3 A4 E3,1 A2 Foundations & Applications). Boston, MA, USA: Birkhäuser, 2003.
− A1 A2 A4 A3 A4 A3 E2,1 − E2,1 A4 A3 A4 A3 A2 A1 [13] K. S. Narendra and J. Balakrishnan, “A common Lyapunov function for
stable LTI systems with commuting A-matrices,” IEEE Trans. Autom.
− A2 E4,1 A3 A4 A3 A2 A1 − A2 A4 E3,1 A4 A3 A2 A1 Control, vol. 39, no. 12, pp. 2469–2471, Dec. 1994.
= A1 A2 A4 A3 A1 A4 A3 A2 − A1 A2 A4 A3 E4,1 A3 A2 [14] G. Zhai, B. Hu, K. Yasuda, and A. N. Michel, “Qualitative analysis of
discrete-time switched systems,” in Proc. Amer. Control Conf., 2002,
− A1 A2 A4 A3 A4 E3,1 A2 − A1 A2 A4 A3 A4 A3 E2,1 pp. 1880–1885.