Deciding the boundedness and dead-beat stability of
constrained switching systems.

arXiv:1512.04887v1 [math.DS] 15 Dec 2015

Matthew Philippe1 , Gilles Millerioux2 , Raphaël M. Jungers1

Abstract
We study computational questions related with the stability of discrete-time linear switching systems with
switching sequences constrained by an automaton.
We first present a decidable sufficient condition for their boundedness when the maximal exponential growth
rate equals one. The condition generalizes the notion of the irreducibility of a matrix set, which is a well
known sufficient condition for boundedness in the arbitrary switching (i.e. unconstrained) case.
Second, we provide a polynomial time algorithm for deciding the dead-beat stability of a system, i.e. that
all trajectories vanish to the origin in finite time. The algorithm generalizes one proposed by Gurvits for
arbitrary switching systems, and is illustrated with a real-world case study.

1. Introduction
Switching systems are dynamical systems for which the state dynamics themselves vary between different
operating modes according to a switching sequence. The systems under study in this paper are discretetime linear switching systems. Given a set of N matrices M = {A1 , . . . , AN } ⊂ Rn×n , the dynamics of a
discrete-time linear switching system are given by
xt+1 = Aσ(t) xt ,
where x0 ∈ Rn is a given initial condition. The mode of the system at time t is σ(t) ∈ {1, . . . , N }. The
switching sequence driving the system is the sequence of modes σ(0), σ(1), . . . in time. Such systems are
found in many practical and theoretical domains. For example they appear in the study of networked control
systems [2, 15], in congestion control for computer networks [27], in viral mitigation [13], as abstractions of
more complex hybrid systems [19], and other fields (see e.g. [14, 20, 28] and references therein).
A large research effort has been devoted to the study of the stability and stabilization of switching systems
(see e.g. [7, 9, 17, 18, 20, 28]). The question of deciding the stability of a switching system is challenging and
is known to be hard in general (see [14], Section 2.2, for hardness results).
In this paper, we first develop a sufficient condition for the boundedness of switching systems, that is, the
existence of a uniform bound K ≥ 1 such that for all switching sequences and all time t ≥ 0,
kAσ(t) · · · Aσ(0) k ≤ K.

(1)

Second, we provide an algorithm for deciding when a system is dead-beat stable. This corresponds to the fact
that there exists a time T ≥ 1 such that, for all switching sequences, and all t ≥ T , Aσ(t) · · · Aσ(0) = 0. Both
problems have been studied for arbitrary switching systems ([4, 5, 12, 14]), for which the mode σ(t) can take
any value in {1, . . . , N } at any time. To the best of our knowledge, these studies have yet to be extended to
switching systems with more general switching sequences, such as the ones studied in [1, 9, 13, 16–18].
Email addresses: matthew.philippe@uclouvain.be (Matthew Philippe ), gilles.millerioux@univ-lorraine.fr (Gilles
Millerioux ), raphael.jungers@uclouvain.be (Raphaël M. Jungers )
1 M. Philippe (corresponding author) and R. M. Jungers are with the ICTEAM Institute, Université Catholique de Louvain.
M. Philippe is a F.N.R.S./F.R.I.A. fellow; R. Jungers is a F.R.S./F.N.R.S. research associate. They are supported by the Belgian
Interuniversity Attraction Poles, and by the ARC grant 13/18-054 (Communauté française de Belgique).
2 G. Millerioux is with the Research Center for Automatic Control of Nancy (CRAN), Université de Lorraine. This work was
partially supported by Research Grants ANR-13-INSE-0005-01 from the Agence Nationale de la Recherche in France.

Preprint submitted to Elsevier

February 20, 2018

In this work, we allow for the definition of constraints on the switching sequences. These rules on the
switching sequences are expressed through an automaton. Automata are common tools for the representation of admissible sequences of symbols (see [21], Section 1.3 for an introduction). An automaton is here
represented as a strongly connected graph G(V, E), with a set of nodes V and edges E. The edges of this
graph are both directed and labeled. An edge takes the form (v, w, σ) ∈ E, where v and w are respectively
the source and destination nodes of the edge, and σ ∈ {1, . . . , N } is the label, taking its values in the set of
modes of the switching system.
The edges E represent the possible time transitions of a switching system, and the nodes V need not be
inherently associated with modes of the system. A switching sequence σ(1), σ(2), . . . , of the system is then
said to be accepted by G if there exists a path in G such that the sequence of labels along the edges of the
path equals the switching sequence itself. Examples of such automatons, with their corresponding switching
rules, are presented in Figure 1. Note that, in general, there can be several automata that represent a same
set of switching rules. Because it is not relevant to our purpose, we do not specify an initial or final node for
the paths - in this we differ from the classical definition of an automaton ([21], Section 1.3).
2

2
2

1
1
(a)

2

1
(b)

3

1
4

(c)

Figure 1: Both automata on Figure 1a and 1b accept arbitrary switching sequences on two modes. The third
automaton (Figure 1c) is on 4 modes. It does not generate arbitrary switching sequences, mode 1 must be
followed by mode 1 or 2, mode 2 by mode 3 or 4, etc...
Given a graph G(V, E) on N labels and a set of N matrices M, we define the constrained switching system
S(G, M) as the following discrete-time linear switching system:
xt+1 = Aσ(t) xt ,
σ(0), . . . , σ(t) is accepted by G.

(2)

Arbitrary switching systems are special cases of constrained switching systems. Their switching rule can be
represented by the automata alike those of Figures 1a and 1b, or by any path-complete graph (see [1]).
The boundedness and stability properties of a system S(G, M) are tightly linked to its constrained joint
spectral radius. This concept was introduced by X. Dai [8] in 2012 for the stability analysis of constrained
switching systems. The CJSR of the system S(G, M) is defined as follows:
n
1/t
:
ρ̂(S) = lim max
Aσ(t−1) · · · Aσ(0)
t→∞
(3)
o
σ(0), . . . , σ(t − 1) is accepted by G .
When G allows for arbitrary switching, the CJSR is equal to the joint spectral radius (JSR) of the set M,
which was introduced by Rota and Strang in 1960 (see [14] for a monograph on the topic).
The constrained joint spectral radius is the maximal exponential growth rate of a system. Its value reflects the
stability properties of a system S(G, M). If ρ̂(S) < 1, the system is both asymptotically and exponentially
stable (see [8] - Corollary 2.8). If ρ̂(S) > 1, the system possesses an unbounded trajectory whose growth rate
is exponential. The last case ρ̂(S) = 1 is more complicated. The system is not asymptotically stable, but
may be bounded or not depending on its parameters.
If S is an arbitrary switching system with ρ̂(S) = 1, then there exists a condition guaranteeing its boundedness. This condition is the irreducibility of M.
Definition 1. A set M ⊂ Rn×n of matrices is irreducible if for any non-trivial linear subspace X ⊂ Rn , i.e.
with 0 < dim(X ) < n, there is a matrix A ∈ M such that AX 6⊂ X . That is, the matrices in M do not share
a common non-trivial invariant subspace of Rn .
Proposition 1.1 (e.g., [14], Theorem 2.1). If a set of matrices M with joint spectral radius equal to 1 is
irreducible, then there is a uniform bound on the norm of all products of matrices taken from M.
2

The irreducibility property is known to be decidable (see [3] and references therein). Moreover, irreducibility implies the existence of Barabanov norms for arbitrary switching systems. The existence of such
norms is very useful for the stability analysis of arbitrary switching systems [11, 14, 32].
The first part of this paper is focused around providing a proper generalization of both irreducibility and
Proposition 1.1 for constrained switching systems3 . As shown in Example 1, Proposition 1.1 does not generalize directly to constrained switching systems.
Example 1. We construct an unbounded constrained switching system S(G, M), which has both ρ̂(S) = 1
and an irreducible set of matrices. The set M = {A1 , A2 } is defined as




1 1
0 1
A1 =
, A2 =
.
(4)
0 1
1 0
The automaton G is given in Figure 2. It refuses any switching sequence containing . . . 121 . . . as a subsequence. Since A1 and A2 do not share common eigenvectors, the set M is irreducible.
2
1
2

Figure 2: No paths in this graph can carry a sequence containing . . . 121 . . ..
Moreover, we can verify that ρ̂(S) = 1. Indeed, for all k ≥ 1, the sequence σ(1), . . . , σ(k) maximizing the
norm kAσ(k) · · · Aσ(1) k in (3) is simply σ(t) = 1 for all t = 1, . . . , k. Equation (3) thus boils down to the
classical Gel’fand formula for computing the spectral radius of A1 , which is equal to 1.
However, for the same switching sequence, we have that kAt1 k → ∞ as t → ∞, and so S is unbounded.
We conclude that proposition 1.1 does not generalize as it is to constrained switching systems.
In the second part of the paper, we put ourselves in the case ρ̂(S) = 0. From the results of Dai, we known
that this implies the asymptotic stability of any constrained switching system. However, in the arbitrary
switching case, this is also equivalent to dead-beat stability (Theorem 1.2) and we can decide ρ̂(S) = 0 in
polynomial time.
Theorem 1.2 (e.g. [14], Section 2.3.1). The joint spectral radius of a set of N matrices M is zero if and
only if all products of size n of matrices in M are equal to zero.
To the best of our knowledge, no extensions of these results to constrained switching systems have been
proposed yet. And again, it appears that Theorem 1.2 does not hold for constrained switching systems.
Example 2. The scalar (n = 1) system on the two matrices A1 = 1 and A2 = 0 with the cyclic automaton of
Figure 3 sees all of its trajectories vanish to the origin after 2 steps, and so ρ̂(S) = 0 from (3). We conclude
1
2

Figure 3: A simple cyclic system on two modes.
that Theorem 1.2 does not hold when constraints are added on switching sequences.
The plan of the paper is as follows.
Section 2 presents a decidable sufficient condition for the boundedness of systems S(G, M) with ρ̂(S) = 1.
Our main result provides a condition generalizing the concept of irreducibility to constrained switching
systems. Its decidability is proven in Subsection 2.2. In Subsection 2.3, we then compare the condition
3 Preliminary

results on this question were presented in the conference paper [26].

3

with a second one which, after a one-shot transformation of a constrained switching system into a higherdimensional arbitrary switching system, relies on the classical definition of irreducibility .
In Section 3 we generalize Theorem 1.2 to constrained switching systems. We provide an algorithm that, given
a system S(G, M), outputs whether ρ̂(S) = 0 or ρ̂(S) > 0. The complexity of the algorithm is polynomial
in the dimensions of M and G. An example of application of this algorithm for designing the left-inverter of
a dynamical system is presented in Subsection 3.2.
Notations
Given an automaton G(V, E) with nodes V and edges E, |V | and |E| denote respectively the amount of
nodes and edges of G. A path in the graph G is a sequence of consecutive edges. The length of a path p is
denoted |p| and is the amount of edges it contains. An edge e = (v1 , v2 , σ) is a path of length 1. We refer to
sets of paths by borrowing notations of language theory. The set of all the paths of length k is written E k ,
k
k
and we let E ∗ = ∪∞
k=1 E . Given two nodes v and w, we use Ev,w to denote the set of all the paths of length
∗
∞
k
k from the node v to the node w, and we let Ev,w = ∪k=1 Ev,w . When the second node is unspecified, Evk and
Ev∗ relate to paths whose source is v, and whose destination can be any node in V . We use p = [p1 , p2 , . . .]
to denote a partition of the path p in smaller consecutive paths p1 , p2 , . . .. A cycle on a node v is a path
∗
∗
c ∈ Ev,v
. The cycle c is simple on the node v if there are no partitions c = [c1 , c2 ] where both c1 ∈ Ev,v
and
∗
c2 ∈ Ev,v .
To each path p with length |p| = T is associated a matrix product Ap = Aσ(T ) · · · Aσ(1) , where σ(i), 1 ≤ i ≤ t
is the label of the i’th edge in p.
For x ∈ Rn and A ∈ Rn×n , kxk is the euclidean norm of x and kAk the matrix norm of A induced by the
euclidean norm.
2. Generalizing irreducibility to constrained switching systems
In this section, we provide a sufficient condition for the boundedness of systems with ρ̂(S) = 1, generalizing
the concept of irreducibility and Proposition 1.1 to constrained switching systems. The first part of this
section is focused on the presentation our main result Theorem 2.2. Its proof is detailed in Subsection 2.1.
In Subsection 2.2 we prove the decidability of the condition. Subsection 2.3 then presents an alternative
boundedness condition, appealing since it allows to ignore combinatorial details about the graph G after a
one-shot transformation of a system, but definitely weaker than Theorem 2.2.
Our generalization of irreducibility relies on the following definition.
Definition 2 (Nodal irreducibility). Given a system S(G(V, E), M), a node v ∈ V is irreducible if for any
∗
non-trivial linear subspace X ⊂ Rn there is a cycle c ∈ Ev,v
such that Ac X 6⊂ X .
For a system with ρ̂(S) = 1, it must be the case that there exists a sequence of paths in G, {pk ∈
Evk }k=1,2,... , starting at some node v ∈ V such that, for all k = 1, 2, . . ., Apk 6= 0. The existence of arbitrary
long paths is guaranteed by the strong connectivity of the directed graph G. But this is not enough. The
system S(G, M) must possess a connectivity beyond the one brought in a graph theoretical sense by G.
Definition 3 (Linear Connectivity). Given a system S(G(V, E), M) and two nodes v, w ∈ V , v is linearly
∗
connected to w if there exists p ∈ Ev,w
such that Ap 6= 0.
The system S is linearly connected if all pairs of nodes are linearly connected.
Our main result in this section can be roughly stated as follows. If we can guarantee that all the trajectories
of a system with CJSR = 1 encounter irreducible nodes regularly, then the system is bounded. To formalize
the result, we borrow the concept of unavoidability from automata theory (see e.g. [21], Proposition 1.6.7.).
Definition 4. Given a graph G(V, E), a subset V ∗ of V is said to be unavoidable if any cycle in G encounters
at least one node in V ∗ .
Lemma 2.1. Given a graph G(V, E), let V ∗ be an unavoidable set of nodes. Any path p of length |V |
encounters at least 1 node in V ∗ .
Proof. Such a path p must visit |V | + 1 nodes. At least one node in V appears twice in p, implying that p
contains a cycle. Therefore, p visits an unavoidable node in V ∗ .
4

Our main result is the following.
Theorem 2.2. Consider a system S(G(V, E), M) that is linearly connected and has an unavoidable set of
irreducible nodes. If ρ̂(S) = 1, then the system is bounded.
The conditions guaranteeing boundedness in Theorem 2.2 are split in two sets of conditions.
The first set of conditions (irreducibility and connectivity) is on the structure of the system S. As we will
prove in Subsection 2.2, these conditions are decidable.
The second condition is ρ̂(S) = 1. Given any system S, the question of knowing whether ρ̂(S) = 1 or not is
known to undecidable (see [5] for the special case of arbitrary switching). However if we relax this condition,
we may still extract some interesting properties about the stability of S. This is discussed in Section 3,
Proposition 3.4.
In the previous conference version of this work [26], the concept of unavoidability was left aside. The
main result of [26] is in fact a special case of Theorem 2.2, where all the nodes of G are irreducible. This
trivially implies the unavoidability of the set of irreducible nodes.
Theorem 2.3 ( From [26], Theorem 2.1). Consider a system S(G(V, E), M) that is linearly connected and
has all of its nodes being irreducible. If ρ̂(S) = 1, then the system is bounded.
There are scenarios where the irreducibility of all nodes (Theorem 2.3) is definitely too strong of a
requirement, but where systems do possess an unavoidable set of irreducible nodes (Theorem 2.2).
Example 3. Consider a system on two matrices M = {A1 , A2 }



0 1
0
A1 =
, A2 =
1 0
0

with

0
,
1

and constrained by the automaton of Figure 4. The node on the left is irreducible since the matrices A1
2
1

2

1
1

Figure 4: We cannot activate mode 2 more than twice in a row.
and A1 A2 do not share common eigenvectors. The node is also unavoidable since contained in every cycle
in the graph. However, the middle and right nodes are reducible, with the invariant subspace Im(A2 ). In
conclusion, the system satisfies to the conditions of Theorem 2.2 and has only one irreducible node.
We now move to the proof of Theorem 2.2.
2.1. The proof of Theorem 2.2
We start with two lemmas.
Lemma 2.4. Consider a system S(G, M), linearly connected and has an unavoidable set of irreducible nodes
V ∗ ⊂ V . At any irreducible node v ∈ V ∗ , the subspace defined as
Kv = {x ∈ Rn : ∃K < ∞ : ∀p ∈ Ev∗ , kAp xk < K}

(5)

is either Rn or {0}. Moreover, if S is unbounded, then for any irreducible node v ∈ V ∗ , Kv = {0}.
Proof. It is clear that Kv is a linear subspace. We prove the first part by contradiction. Take an irreducible
node v ∈ V ∗ , and assume first that Kv 6= Rn , and second that there is a non-zero vector x ∈ Kv . Since v is
∗
irreducible, there must be c ∈ Ev,v
such that y = Ac x 6∈ Kv . Indeed, if there was no such cycle, the subspace
defined as
∗ Ac x} ⊆ Kv
span{x, ∪c∈Ev,v
would be invariant at v, contradicting the irreducibility of the node. This implies the existence of unbounded
trajectories from the point y, which in turn implies the contradiction x 6∈ Kv .
5

We now move to the second part of the Lemma and assume that S is unbounded. In that case, there exists a
node v (not necessarily irreducible) and a sequence of paths {pk ∈ Evk }k=1,2,... such that limk→∞ kApk k = ∞.
For k ≥ |V |, pk must have visited an irreducible node w ∈ V ∗ (Lemma 2.1). Therefore, we have Kw = {0}
from the first part of the Lemma.
If w was the only irreducible node, then the proof is done. So assume there are other irreducible nodes, and
∗
take such a node w′ ∈ V ∗ . From the linear connectivity of S, there must be a path p ∈ Ew
′ ,w and a vector
n
x ∈ R such that Ap x 6= 0, and since Kw = {0}, Ap x 6∈ Kw . Therefore it must be the case that x 6∈ Kw′ and
so Kw′ 6= Rn . From the first part of the Lemma, we must conclude Kw′ = {0}. Repeating the above for all
irreducible nodes, we then conclude that Kv = {0} for all v ∈ V ∗ .
Lemma 2.5. Consider a system S(G, M), linearly connected and with an unavoidable set of irreducible
nodes V ∗ ⊂ V . If S is unbounded then for any scalar ℓ > 1, there must exist an integer Tℓ ≥ 1 such that for
any irreducible node v ∈ V ∗ and any x ∈ Rn ,
∃ p ∈ Ev∗T , |p| ≤ Tℓ : kAp xk ≥ ℓkxk.

(6)

Proof. Assume by contradiction that the opposite of the Lemma’s claim is true. There exists a scalar ℓ > 1
such that for all T ≥ 1, there is an irreducible node vT ∈ V ∗ and a vector xT 6= 0 satisfying
∀ p ∈ Ev∗T , |p| ≤ T : kAp xT k < ℓkxT k.
We can further assume, without loss of generality, that for all T , kxT k = 1. Since there are a finite amount of
nodes in V ∗ , there must be a sequence {Tk }k=1,2,... and a node w ∈ V ∗ , such that vTk = w for all k = 1, 2, . . ..
The vectors {xTk }k=1,2,... form a sequence of vectors on the unit ball {x ∈ Rn : kxk = 1}. Since the unit ball
is a compact set, there exists a subsequence of {xTk }k=1,2,... converging, as k goes to infinity, to a limit point
x∗ on the unit ball. This limit point is such that
∗
: kAp x∗ k ≤ ℓkx∗ k,
∀p ∈ Ew

which implies by definition that x∗ ∈ Kw . By Lemma 2.4, this contradicts the fact that, since w is irreducible,
it should have Kv = {0}.
Proof of Theorem 2.2. We consider a system S(G(V, E), M) which is linearly connected and with an unavoidable set of irreducible nodes V ∗ ⊂ V . We will show that if S is unbounded, then ρ̂(S) > 1. Theorem 2.2
will then be proven by contraposition.
To do so, assume that S is unbounded. We begin by proving a result similar to Lemma 2.5, but which
only involves irreducible nodes.
Claim: There exists an integer T ∗ ≥ 1 such that, for any irreducible node v ∈ V ∗ , and any non-zero
vector x ∈ Rn ,
∗
∃w ∈ V ∗ , ∃ p ∈ Ev,w
, |p| ≤ T ∗ : kAp xk ≥ 2kxk.
(7)
For proving the Claim, we first define K = maxA∈M kAk. Since induced matrix norms are sub multiplicative, we have that for all p ∈ E ∗ , kAp k ≤ K |p| . Also K > 1 since we assumed S to be unbounded.
Observe that Lemma 2.5 holds under our current set of assumptions. Moreover, for any choice of the constant
ℓ, paths p satisfying (6) must be such that
ℓ ≤ kAp k ≤ K |p| .
Therefore, for the choice ℓ = 2K |V | , we can guarantee that the paths in (6) have a minimum length of |V | + 1.
We now invoke the concept of unavoidability. Lemma 2.1 guarantees that an irreducible node is encountered
within the last |V | edges of the paths considered above. Take any irreducible node v and any x ∈ Rn . Let
p be a path satisfying (6) for ℓ = 2K |V | . Let w ∈ V ∗ be the last irreducible node encountered along the
path, and let v ′ ∈ V be the destination of the path. Assume for the moment that v ′ 6= w. We can write

6

p = [p1 , p2 ], with p1 ∈ Ev,w and p2 ∈ Ew,v′ , and with |p2 | ≤ |V |. By definition of p, from our choice of ℓ, and
by sub multiplicativity of the norm, we have
2K |V | kxk ≤ kAp2 Ap1 xk ≤ K |p2 | kAp1 xk ≤ K |V | kAp1 xk.
If w = v ′ , the discussion is even simpler and we let p1 = p, kAp1 xk ≥ 2K |V | kxk. We have shown the existence
of a path p1 whose origin is v and destination is an irreducible node w such that kAp1 xk ≥ 2kxk. This being
done from an arbitrary irreducible node v and arbitrary x ∈ Rn , we conclude that our Claim holds true.
We now prove that ρ̂(S) > 1. Take any irreducible node v0 ∈ V ∗ and any non-zero x ∈ Rn . From (7),
there exists a sequence {vk }k=1,2,... of nodes in V ∗ and a corresponding sequence of paths {pk }k=1,2,... , each
k
with a length Tk ≤ T ∗ and with pk ∈ EvTk−1
,vk , that satisfy for all k = 1, 2, . . .,
kApk · · · Ap1 xk ≥ 2k kxk.
We then obtain a lower bound on ρ̂(S) from (3):




P
∗
∗
ρ̂(S) ≥ lim kApk · · · Ap1 k1/ Tk ≥ lim kApk · · · Ap1 k1/(kT ) ≥ 21/T > 1.
k→∞

k→∞

We conclude that a system S(G, M), linearly connected and with an unavoidable set of nodes is unbounded
if ρ̂(S) > 1. If ρ̂(S) ≤ 1, the system must be bounded.
2.2. Decidability of nodal irreducibility and linear connectivity
Knowing whether a finite set of matrices M is irreducible is decidable (see e.g. [3] and references therein).
That is, given a finite set of matrices M, there exists an algorithm, running in finite time, returning whether
the set is irreducible or not.
In this subsection, we show that knowing whether a system S(G, M) is linearly connected and has an
unavoidable set of irreducible nodes is decidable as well. To do so, we show that the irreducibility of a single
node in the system is equivalent to the irreducibility of a finite set of matrices, and that a similar result holds
for linear connectivity.
We begin by a technical lemma. The authors believe the result to be folklore in linear algebra, but
its proof, while perhaps not presented in its most compact form, reveals to be insightful for the proof of
Theorem 2.7.
Lemma 2.6. Let M = {A1 , A2 , . . .} be a (possibly infinite) set of matrices in Rn×n . Given a non-trivial
subspace X ⊂ Rn of dimension 1 ≤ d < n and x ∈ X , x 6= 0, if for all products of matrices of length t ≤ d,
Aσ(t) · · · Aσ(1) x ∈ X ,
with Aσ(i) ∈ M, 1 ≤ i ≤ t then for any product A∗ from matrices in M,
A∗ x ∈ X .
Proof. We show by contradiction that the shortest product under which the image of x no longer lies in X
must be of length at most d. Assume that T > d is the length of a shortest product such that
A∗ Aσ(d) · · · Aσ(1) x 6∈ X ,

(8)

where A∗ is itself a product of length T − d of matrices in M.
Since the vectors x, Aσ(1) x, . . . , Aσ(d) · · · Aσ(1) x are d + 1 vectors that belong to X which is of dimension d,
we can state the following:

∃ 1 ≤ k ≤ d : Aσ(k) · · · Aσ(1) x ∈ span x, Aσ(1) x, . . . , Aσ(k−1) · · · Aσ(1) x .
(9)
Assume for the moment that k = d. From (8) and (9), we can write

A∗ Aσ(d) · · · Aσ(1) x ∈ span A∗ x, A∗ Aσ(1) x, . . . , A∗ Aσ(d−1) · · · Aσ(1) x 6⊆ X .

After observing that all products of matrices involved in the span on the right are of length at most T − 1,
and that at least one vector in this span does not lie in X , we conclude that T is not the shortest
length.
Qd
In the case k < d, we can repeat the above process by first multiplying (9) on the left by i=k+1 Aσ(i) and
then by A∗ . The conclusion remains unchanged, and we have proved the Lemma by contradiction.
7

Theorem 2.7. Consider a system S(G(V, E), M), M ⊂ Rn×n . Given an irreducible node v and a non-trivial
∗
linear subspace X ⊂ Rn , the shortest cycle c ∈ Ev,v
such that Ac X * X is of length
|c| ≤ 1 + n(|V | − 1).
∗
If a pair of nodes v, w is linearly connected, then the shortest path p ∈ Ev,w
with Ap 6= 0 is of length

|p| ≤ 1 + n(|V | − 2).

Proof. We start with the first part of the theorem. Consider an irreducible node v, a non-trivial subspace X
∗
and a cycle cv ∈ Ev,v
with the smallest length satisfying
Acv X 6⊆ X .

(10)

We are now going to establish two properties of cv , allowing us to show that |cv | ≤ 1 + n(|V | − 1).
Claim 1 : The cycle cv is simple on the node v.
∗
The simplicity of cv means that there are no partitions cv = [c1v , c2v ] where c1v , c2v ∈ Ev,v
. If there was such a
partition, then either Ac1v X 6⊂ X , or Ac2v X 6⊂ X . Thus, cv would not be a shortest cycle satisfying (10).
Claim 2 : The cycle cv never visits a node w 6= v more than n times.
This part of the proof relies on Lemma 2.6 and its proof.
Assume by contradiction that cv visits a node w 6= v for T > n times. We can write
cv = [pv,w , cw , pw,v ],
∗
∗
where pv,w ∈ Ev,w
and pw,v ∈ Ew,v
are paths that visit v and w at most once as source or destination; and
cw is a cycle on the node w. In turn, we can write

cw = [c1w , . . . , cTw−1 ],
where the ckw , k = 1, . . . , T − 1 are simple cycles on w. Note that the above does imply that w is visited T
times overall in cv .
We now define the subspaces Xw = Apv,w X and Y = {x ∈ Rn : Apw,v x ∈ X }. Since cv satisfies (10) and is of
shortest length, these subspaces must satisfy to the following two relations:
Xw ⊆ Y,
Acw Xw 6⊆ Y,
and consequently 1 ≤ dim(Y) ≤ n − 1. The second relation above is equivalent to


AcTw−1 · · · Acnw Acn−1
· · · Ac1w Xw 6⊆ Y,
w
and from the proof of Lemma 2.6, there must exist 1 ≤ k ≤ n − 2 such that


AcTw−1 · · · Acnw Ackw · · · Ac1w Xw 6⊆ Y.
This contradicts the fact that cv is of shortest length. Indeed, defining c′w = [c1w , . . . , ckw , cnw , . . . cTw−1 ], we have
that c′v = [pv,w , c′w , pw,v ] satisfies (10) and is such that |c′v | < |cv |. This concludes the proof of the second
claim.
Having established these properties, we can easily compute an upper bound on the length of cv : there
are at most n(|V | − 1) visits to nodes other than v, requiring a path of length at most n(|V | − 1) − 1. To
form a simple cycle on v from this path, we add two edges from and to v, respectively at the beginning and
the end of the path, giving us a cycle of length 1 + n(|V | − 1) at most.
The second part of the theorem relates to linear connectivity. The proof is similar in its ideas, so we
will only highlight the main differences. Consider two linearly connected nodes v and v ′ and let the path
∗
pv,v′ ∈ Ev,v
6= 0. Similarly to Claim 1, we can show that pv,v′ cannot
′ be a shortest path satisfying Ap
v,v′
8

visit neither v or v ′ more than once (as origin and destination, resp.). Claim 2 still holds, any node w visited
by pv,v′ cannot bevisitedmore than n times. The proof proceeds by writing pv,v′ = [pv,w , cw , pw,v′ ] as before,
defining Y = Ker Apw,v′ , and applying Lemma 2.6 to escape Y from Im(Apv,w ). Finally, pv,v′ visits |V | − 2
nodes n times at maximum, to which we need to add two edges for connecting v and v ′ , giving us a bound
of |pv,v′ | ≤ 1 + n(|V | − 2).

Based on the above result and on the fact that irreducibility (Definition 1) is decidable, we are able to
formulate a decision algorithm for verifying that a system is linearly connected and has an unavoidable set of
irreducible nodes. We present this algorithm in three distinct parts. First (Algorithm 1) checks for the linear
connectivity of the system, second (Algorithm 2) marks all the irreducible nodes, and third (Algorithm 3)
checks the unavoidability of the set of irreducible nodes.
Algorithm 1 Checking linear connectivity of S(G(V, E), M)
for all pairs of nodes v, w ∈ V do
∗
if ∀p ∈ Ev,w
, |p| ≤ 1 + n(|V | − 2) : Ap = 0 then
Return False
end if
end for
Return True

⊲ the pair v,w is disconnected.

⊲ all pairs are Linearly Connected.

Algorithm 2 Marking the irreducible nodes of S(G(V, E), M)
Initialize set of irreducible nodes: V ∗ = {}.
for all nodes v ∈ V do
Initialize set of matrices Cv = {}.
∗
for all cycles c ∈ Ev,v
, with |c| ≤ 1 + n(|V | − 1) do
Update the matrix set: Cv ← Cv ∪ Ac .
end for
if the set Cv is irreducible then
Mark the node v as irreducible: V ∗ ← V ∗ ∪ v.
end if
end for
Return V ∗
Algorithm 3 Checking unavoidability of a subset V ∗ ⊂ V in the graph G(V, E)
Construct the graph G′ (V \V ∗ , E ′ ) by removing all nodes in V ∗ from G.
if G′ has no cycle then
Return True
end if
Return False

⊲ the set V ∗ is unavoidable

Remark 1. The decidability of nodal irreducibility is guaranteed from the fact that the irreducibility of matrix
sets is decidable. However, to the best of our knowledge, it is not known whether deciding the irreducibility
of a set M is NP-hard or not. Moreover, even if we assumed the existence of an algorithm deciding the
irreducibility of a set M in a number of steps polynomial in the size of M, Algorithm 2 would still require an
exponential amount of steps. Indeed, the algorithm proceeds by computing all cycles of length 1 + n(|V | − 1).
Even for two nodes, the amount of cycles involved is O(|E|(1+n(|V |+1)) ).
Before ending this subsection, we show that the bounds of Theorem 2.7 are tight.
Proposition 2.8. For all integers n, m ≥ 1, one can build a system S(G(V, E), M), M ⊂ Rn×n , |V | = m,
for which a cycle of length 1 + n(m − 1) is needed to exit a particular non-trivial subspace X ⊂ Rn from a
particular node v ∈ V . This holds even when M contains two matrices.
9

Proof. We take any automaton G on m nodes from the Černỳ automata family (see Figure 5). These
automata are related to the well-known Černỳ’s conjecture, which is still the subject of active research (a
state-of-the-art survey is presented in [30]). Černỳ’ automata possess N = 2 transition labels, and we define
1
1

2

1

2

2

2

2

1

1

Figure 5: A Černỳ automaton on 5 nodes. In this example, the particular node v is taken as the node on the
left without self-loop.
following the set of matrices M = {A1 , A2 } ∈ {0, 1}n×n:
A1 (i, i + 1) = 1, i = 1 · · · n − 1,
A2 (n, 1) = 1,
with the rest of the entries equals 0 for both matrices.
The particular node v ∈ V is taken to be the only node without self loop. The non-trivial subspace X is
defined as the span of the basis vector e1 = [1, 0, 0, . . .]⊤ ∈ Rn . Notice that e1 ∈ Ker(A1 ), A2 e1 ∈ Ker(A2 ),
A2 e1 6⊂ X , and finally A1n−1 A2 e1 = e1 .
For this system, the shortest cycle c ⊂ E on v ∗ such that y = Ac x 6∈ X has the associated product
Ac = A2 (A1n−1 A2 )m−1 ,
which is indeed a product of length 1 + n(m − 1).
Regarding linear connectivity property, the bound 1 + n(m − 2) of Theorem 2.7 is attained through the
same family of automaton, with the same matrices, by taking the source node as the node without self loop,
and the destination node as the one just before it (bottom of Figure 5).
2.3. A sufficient condition based on an algebraic lifting
In this last subsection, we show how a recently developed lifting technique can be put to good use in
order to derive an alternative sufficient condition for the boundedness of a system. We will also make use of
the technique for the proofs presented in Section 3.
Definition 5. Consider a system S(G(V, E), M) with nodes V = {vk }k=1,...,|V | . The set MG ⊂ R(|V |n)×(|V |n)
is defined as follows :
MG = {A(vi ,vj ,σ) , (vi , vj , σ) ∈ E},
with

A(vi ,vj ,σ) = ej e⊤
i ⊗ Aσ ,

where ei is the ith element of the canonical basis of R|V | , and the operator ”⊗” is the Kroenecker product
between matrices.

4

4 Given two matrices A ∈ Rm×n and B ∈ Rp×q , the Kroenecker product of A and B is a matrix of dimension (mp) × (nq)
defined as follows:


[A]1,1 B, · · · , [A]1,n B


..
..
..
A⊗B =
,
.,
.,
.
[A]m,1 B, · · · , [A]m,n B

where [A]i,j is the element on the ith row and jth column of A.

10

The lifting procedure allows to study the stability and boundedness properties of constrained switching
systems through an equivalent, but higher dimensional, arbitrary switching system. In [16], Kozyakin introduced this lift to study constrained switching systems where the switching sequence is a realization of a
Markov Chain. The results of [16] show the equality between the CJSR of these Markovian systems and the
JSR of the arbitrary switching system on the lifted set of matrices. A similar lifting procedure was introduced
in parallel by Wang et al. [31] for the general class of systems described by an automaton G. Wang et al.
proved that the stability of a constrained switching system is equivalent to that of the lifted set of matrices
presented above. From these results and those of Dai’s [8], it is easy to conclude the following: the CJSR of
a constrained switching system S(G, M) equals the JSR of the lifted matrix set MG , and the boundedness
of both the constrained and lifted arbitrary switching systems are equivalent.
This leads us to a very natural idea. Instead of devising complex boundedness conditions for constrained
switching systems S(G, M) with ρ̂(S) = 1, we may just consider the irreducibility of the matrix set MG ,
which would directly imply the boundedness of S(G, M).
However, when analysing the system through its lift MG , one loses all the combinatorial aspect of the
dynamics encapsulated in the automaton. As illustrated in the next example, this leads to the fact that the
irreducibility of a set MG is weaker than the condition of Theorem 2.2.
Example 4 (Example 3, cont.). Consider the constrained switching system S(G(V, E), M) of Example 3. For
this system, there are 6 matrices in the set MG , one per edge of the graph G of Figure 4. For constructing the
set MG , we let the nodes v1 , v2 and v3 be respectively the left, middle and right nodes in Figure 4. Then, we
apply Definition 5 to build the matrices. For example, considering the edge (v1 , v2 , 2) ∈ E, the corresponding
matrix is given by
    


⊤
0
1
0 0 0


A(v1 ,v2 ,2) = 1 · 0  ⊗ A2 = A2 0 0 .
0
0
0 0 0
After constructing the set MG , is is easy to verify that the subspace of R3·2 defined as
X = {(x, y, z)⊤ ∈ R3·2 , x =∈ R2 , y ∈ Im(A2 ), z ∈ Im(A2 )},
is invariant under all matrices in MG . Its is non-trivial with dimension 4 (recall that A2 has rank 1 here).
We conclude that for the system S(G, M) of Example 3, the lifted set MG is reducible. However, the system
satisfies to the conditions of Theorem 2.2.
The following further qualifies the relation between Theorem 2.2 and the irreducibility of MG .
Theorem 2.9. Consider a system S(G, M). If the lifted set of matrices MG is irreducible, then for all
v ∈ V , v is irreducible.
Proof. Assume that there exists one node v ′ ∈ V which is reducible, with a non-trivial invariant subspace Y.
At each node v ∈ V , v 6= v ′ , we define the following subspace,
∗
Xv = {x ∈ Rn : ∀p ∈ Ev,v
′ , Ap x ∈ Y}.

and we let Xv′ = Y. The fact that v ′ is reducible means that each one of these subspaces is invariant at its
corresponding node. They may however be non-trivial.
From these subspaces we then construct a non-trivial invariant subspace X ⊂ Rn|V | of the set MG by taking
the cartesian product of the {Xv }v∈V .
This shows that if at least one node in V is reducible, then the set MG is reducible as well.
3. A polynomial time algorithm for deciding dead-beat stability and CJSR = 0
We now turn our focus towards our second goal, that is to provide a polynomial time algorithm for
deciding, given a system S(G, M), whether ρ̂(S) = 0 or ρ̂(S) > 0. We prove that, as it is the case for
arbitrary switching systems, ρ̂(S) = 0 is equivalent to dead-beat stability. The interest lies in that it can
provide conditions, checked in polynomial time, of dead-beat stabilizability for switched autonomous systems,
11

an issue that has not been extensively addressed in the literature and no clear results have been provided so
far. The paper [6] gives a good introduction for that problem but the systems under consideration are non
autonomous. The work [10] deals with dead-beat stability in the context of state reconstruction for LPV
systems.
Our theoretical results are presented in Subsection 3.1. Then, they are illustrated in Subsection 3.2. The
issue of left inverter design is discussed for a real-world application.
3.1. General results
Our main theoretical result in this section is the generalization of Theorem 1.2.
Theorem 3.1. Given a system S(G, M), ρ̂(S) = 0 if and only if for all paths p of length n|V |, Ap = 0.
Proof. The proof is direct from the relation between the CJSR of a system S(G, M) and the JSR of the lift
MG (Definition 5). From Theorem 1.2, we know that the JSR of the lifted system equals zero if and only
if all products of length n|V | of matrices in MG are equal to zero. This is equivalent to asking that for all
paths p of length n|V |, Ap = 0.
The result above naturally indicates that ρ̂(S) = 0 is decidable. This was of course known for the case of
arbitrary switching systems, and L. Gurvits [12] proposed (without proof) a polynomial time algorithm for
checking whether the joint spectral radius of a set of matrices is zero or not. A proof is presented in [14],
Section 2.3.1.
Proposition 3.2 (Gurvits’ iteration [12] ). Let M ⊂ Rn×n be a finite set of matrices, and let U0 = I be the
identity matrix in Rn×n . For k = 1, 2, . . ., let
X
Uk =
A⊤ Uk−1 A.
A∈M

The joint spectral radius of M is zero if and only if Un = 0.
The result above can be extended to constrained switching systems with the (expected) cost of taking
the automaton G into account. A first approach would be to apply Proposition 3.2 to the lifted arbitrary
switching system on the set MG obtained from Definition 5. However, this requires the computation of MG ,
and this first approach does not benefit of the combinatorial structure of the system S(G, M). Instead of
doing this, we propose a second, more efficient, approach.
Proposition 3.3 (Generalized Gurvits’ iteration). Consider a system S(G(V, E), M). Define, for all nodes
v ∈ V , U0v = I, the identity matrix in Rn×n . For k = 1, 2, . . ., for all nodes v, let
X
w
A⊤
Ukv =
σ Uk−1 Aσ .
(v,w,σ)∈Ev1

v
The system has ρ̂(G, M) = 0 if and only if Un|V
| = 0 for all v ∈ V .

Proof. By construction, we obtain
Ukv =

X

A⊤
p Ap .

p∈Evk

These matrices are sum of positive semi-definite matrices. They equal zero if and only if all the matrices in
n|V |
v
the sum are zero. Therefore, we have Un|V
, Ap = 0. The conclusion
| = 0 if an only if for all paths p ∈ Ev
follows immediately.
Ending this subsection, we relate the case ρ̂(S) = 0 with our main result in Section 2, Theorem 2.2.
Proposition 3.4. Consider a system S(G(V, E), M) linearly connected and with an unavoidable set of
irreducible nodes. For this system, ρ̂(S) > 0 and there exists a constant K > 0 such that for any t ≥ 0 and
any switching sequence σ(0), . . . , σ(t − 1) accepted by G,
kAσ (t − 1) · · · Aσ (0)k ≤ K ρ̂(S)t .

12

(11)

Proof. The proof that ρ̂(S) > 0 is extracted from Theorem 2.7 and from [14] - Lemma 2.2. This second
Lemma states that the joint spectral radius of an irreducible set of matrices is greater than 0.
Now, take any irreducible node v of the system. From Theorem 2.7, the set of matrices
∗
Mv = {Ac : c ∈ Ev,v
, |c| ≤ 1 + n(|V | − 1)},

is irreducible. From Lemma 2.2 in [14] the joint spectral radius ρ of this set is greater than zero. From this
point, it is easy to conclude that ρ̂(S) ≥ ρ1/(1+n(|V |−1)) > 0.
For the second part of the proposition, remark that the CJSR (3) is homogeneous in the set of matrices M.
That is, if one scales all the matrices in M by a same constant τ ≥ 0, the CJSR of the scaled system is then
equal to τ ρ̂(S). Therefore, by scaling the set M of the system S by the positive constant 1/ρ̂(S), the scaled
system has a CJSR of 1. This scaled system then satisfies to the hypothesis of Theorem 2.2, and by the
definition of boundedness (1) and homogeneity of the norm, we obtain
ρ̂(S)−t kAσ(t−1) · · · Aσ(0) k ≤ K,
for some constant K, for all t ≥ 0 and all switching sequences σ(0), . . . , σ(t − 1) of the original system S.
We now move onto an example to show the applicability and efficiency of the framework. The example
proposed below corresponds to a real-world case study.
3.2. Example: designing a left inverter for an electrical vehicle
The vehicle under consideration has been deeply studied in [22]. Actually, it is the prototype developed
by the Research Center for Automatic Control of Nancy which is annually involved in the European Shell
Eco-Marathon race in the Plug-in (battery) category. The nonlinear discrete-time model with state variables
(1)
(2)
xt and xt denoting respectively the position and the velocity at time t admits the state space form




1
a(Tt )
0
xt +
u
(12)
xt+1 =
(2)
c(Tt ) t
0 b(Tt , xt )
(2)

(2)

with time-varying entries a(Tt ), b(Tt , xt ) and c(Tt ) as a function of Tt and/or xt and of physical parameters
(mass, dimensions, aerodynamics, . . . ) of the vehicle. The quantity Tt is the sampling period that may be

(2)
either constant or time-varying. We denote with ρt the vector ρt = a(Tt ), b(Tt , xt ), c(Tt ) .

(1)
Let us consider the position xt as the measured output yt , that is yt = 1 0 xt . Hence, the system (12)
can be expressed as
xt+1 = A(ρt )xt + B(ρt )ut ,
(13)
yt = Cxt .
We aim at designing a left inverter for (12). A left inverter is a dynamical system able to give, for every time
t, the input ut from a sequence of measures yt , yt−1 , . . .. This left inverter has a practical interest insofar as
it will allow to estimate the control ut from the measures yt , yt−1 , . . . delivered by the sensors. When placed
on-board, it will be involved in an actuator default detection module that plays a central role for the sake of
safety.
Left inversion for discrete-time linear switched (and by extension Parameter Varying) systems has been
addressed in several papers for different purposes [23–25, 29]. From those papers, it is recalled that the
stability of the left inverter, that is the convergence in finite time of the input estimate ût delivered by the
left inverter to the actual input ut is guaranteed whenever the auxiliary system defined below is dead-beat
stable.
ǫt+1 = Q(ρt , . . . , ρt+r )ǫt ,
(14)
where the integer r corresponds to the relative degree of the system. The relative degree is the minimum
number of iterations r such that the output yt+r depends explicitely on the input ut [25].
The matrix Q(ρt , . . . , ρt+r ) describes the dynamics of the reconstruction error ǫt = ut − ût . For the system
(13), the relative degree is r = 2 since the product CA(ρt+1 )B(ρt ) 6= 0, and Q(ρt , ρt+1 , ρt+2 ) is given by
−1
Q(ρt , ρt+1 , ρt+2 ) = A(ρt ) − B(ρt ) CA(ρt+1 )B(ρt )
CA(ρt+1 )A(ρt ).
13

It turns out that in our case, Q(ρt , ρt+1 , ρt+2 ) depends only on the sampling periods at times t and t + 1,
that is


1
a(Tt )
Q(ρt , ρt+1 , ρt+2 ) =
= Q(Tt , Tt+1 ).
−a(Tt+1 )−1 −a(Tt+1 )−1 a(Tt )
In this case study, the sampling period Tt takes 2 possible values T 1 or T 2 according to the range of variation
of the velocity of the vehicle. The faster the vehicle, the lower the sampling period. Then, we can rewrite
the auxiliary system (14) as
ǫt+1 = Qσ(t) ǫt ,
(15)
which takes the form of a switched linear system that assigns to each sequence (Tt , Tt+1 ) starting at time t
a mode σ(t) ∈ {1, 2, 3, 4}. This explicitly induces constraints on the the switching sequences. Indeed, let us
consider that at a given time t, the mode σ(t) corresponds to (Tt , Tt+1 ) = (Tt , T 2 ). At time t + 1, we need
a mode σ(t + 1) corresponding to a sequence of the form (Tt+1 , Tt+2 ) = (T 2 , Tt+2 ). Therefore, the auxiliary
system can be expressed as a system S(G, M) on N = 4 modes. A valid automaton for the system is given
in Figure 6.

Figure 6: Every mode σ(t) of the inverse system corresponds to a sequence (Tt , Tt+1 ) ∈ {T 1 , T 2 }2 of the
original system. There are 4 of such pairs, and 4 possible transitions between these pairs.
For our system, Theorem 3.1 is verified and the algorithm of Proposition 3.3 confirms that ρ̂(S) = 0.
This can be verified by hand, noticing that the product Q(Tt+1 , Tt+2 )Q(Tt , Tt+1 ) = 0, for all t ≥ 0 when
following the switching rules. The auxiliary system is here dead-beat stable. It is worth noticing that, since
the product Q(Tt , Tt+1 )Q(Tt+1 , Tt+2 ) 6= 0, the arbitrary switching system on the set of matrices defining the
auxiliary system is not deadbeat stable. This highlights again that the result is not trivial, and that a tool
adapted for constrained switching systems was required.
4. Conclusion
Discrete-time linear switching systems with constrained switching sequences are a rich class of dynamical
systems. They present many challenging problems regarding their stability and boundedness properties.
In this work, we focused on two aspects. First, we provided decidable sufficient boundedness conditions for
the case when the constrained joint spectral radius (3) of a system is equal to one. Second, we provided a
polynomial time algorithm for deciding when all trajectories of a system vanish to the origin in finite time.
For future research direction, we first point out that while we proved the decidability of our boundedness
conditions, we currently have no polynomial time algorithm for their verification (see Remark 1). To the best
of our knowledge, this problem is open even in the special case of arbitrary switching systems, for which the
conditions boil down to the irreducibility of a set of matrices (Definition 1). Second, it has been shown in
[25] that deciding dead-beat stability can be used for flatness analysis of switching linear systems. Hence, we
expect that the algorithm presented here will lead to interesting alternatives for characterizing the flatness
of switching systems. The study of the stability properties of constrained switching systems arising as left
inverters (see Subsection 3.2), or by extension, Unknown Input Observers, also deserves further inspection.
5. Bibliography
References
[1] A. A. Ahmadi, R. M. Jungers, P. A. Parrilo, and M. Roozbehani. Joint spectral radius and path-complete
graph lyapunov functions. SIAM Journal on Control and Optimization, 52(1):687–717, 2014.

14

[2] R. Alur, A. D’Innocenzo, K. H. Johansson, G. J. Pappas, and G. Weiss. Compositional modeling and
analysis of multi-hop control networks. IEEE Transactions on Automatic control, 56(10):2345–2357,
2011.
[3] D. Arapura and C. Peterson. The common invariant subspace problem: an approach via gröbner bases.
Linear Algebra and its Applications, 384:1–7, 2004.
[4] M. A. Berger and Y. Wang. Bounded semigroups of matrices. Linear Algebra and its Applications,
166:21–27, 1992.
[5] V. D. Blondel and J. N. Tsitsiklis. The boundedness of all products of a pair of matrices is undecidable.
Systems & Control Letters, 41(2):135–140, 2000.
[6] L. T. Conner, Jr and D. P. Stanford. State deadbeat response and observability in multi-modal systems.
SIAM Journal of Control and Optimization, 22(4):630–644, 1984.
[7] J. Daafouz and J. Bernussou. Parameter dependent lyapunov functions for discrete time systems with
time varying parametric uncertainties. Systems & Control Letters, 43(5):355–359, 2001.
[8] X. Dai. A Gel’fand-type spectral radius formula and stability of linear constrained switching systems.
Linear Algebra and its Applications, 436(5):1099–1113, 2012.
[9] R. Essick, J.-W. Lee, and G. E. Dullerud. Control of linear switched systems with receding horizon
modal information. IEEE Transactions on Automatic Control, 59(9):2340–2352, 2014.
[10] M. Fiacchini and G. Millerioux. Dead-beat functional observers for discrete-time lpv systems with
unknown inputs. IEEE Transactions on Automatic Control, 58(12):3230–3235, 2013.
[11] N. Guglielmi and V. Protasov. Exact computation of joint spectral characteristics of linear operators.
Foundations of Computational Mathematics, 13(1):37–97, 2013.
[12] L. Gurvits. Stability of linear inclusions - part 2. NECI technical report TR, pages 96–173, 1996.
[13] E. A. Hernandez-Vargas, R. H. Middleton, and P. Colaneri. Optimal and mpc switching strategies for
mitigating viral mutation and escape. In Proc. of the 18th IFAC World Congress Milano (Italy) August,
2011.
[14] R. Jungers. The joint spectral radius. Lecture Notes in Control and Information Sciences, 385, 2009.
[15] R. M. Jungers, A. D’Innocenzo, and M. D. Di Benedetto. Feedback stabilization of dynamical systems
with switched delays. In Proc. of the 51st IEEE Conference on Decision and Control, pages 1325–1330,
2012.
[16] V. Kozyakin. The Berger–Wang formula for the markovian joint spectral radius. Linear Algebra and its
Applications, 448:315–328, 2014.
[17] A. Kundu and D. Chatterjee. Stabilizing switching signals for switched systems. IEEE Transactions on
Automatic Control,, 60(3):882–888, 2015.
[18] J.-W. Lee and G. E. Dullerud. Uniform stabilization of discrete-time switched and markovian jump
linear systems. Automatica, 42(2), 205-218, 2006.
[19] D. Liberzon and A. S. Morse. Basic problems in stability and design of switched systems. IEEE Control
Systems Magazine, 19(5):59–70, 1999.
[20] H. Lin and P. J. Antsaklis. Stability and stabilizability of switched linear systems: a survey of recent
results. IEEE Transactions on Automatic control, 54(2):308–322, 2009.
[21] M. Lothaire. Algebraic combinatorics on words, volume 90. Cambridge University Press, 2002.
[22] T. Manrique. Optimal control of a low consumption electric vehicle under real-time constraints. PhD
thesis, Université de Lorraine, 2015.
15

[23] G. Millerioux and J. Daafouz. Invertibility and flatness of switched linear discrete-time systems. In
Hybrid Systems: Computation and Control, pages 714–717. Springer, 2007.
[24] G. Millerioux and J. Daafouz. Flatness of switched linear discrete-time systems. IEEE Transactions on
Automatic Control, 54(3):615–619, 2009.
[25] J. Parriaux and G. Millerioux. Nilpotent semigroups for the characterization of flat outputs of discretetime switched linear and lpv systems. In Proc. of the 51st IEEE Conference on Decision and Control,
2012.
[26] M. Philippe and R. M. Jungers. A sufficient condition for the boundedness of matrix products accepted
by an automaton. In Proceedings of the 18th International Conference on Hybrid Systems: Computation
and Control, pages 51–57. ACM, 2015.
[27] R. Shorten, F. Wirth, and D. Leith. A positive systems model of tcp-like congestion control: asymptotic
results. IEEE/ACM Transactions on Networking, 14(3):616–629, 2006.
[28] R. Shorten, F. Wirth, O. Mason, K. Wulff, and C. King. Stability criteria for switched and hybrid
systems. SIAM review, 49(4):545–592, 2007.
[29] S. Sundaram and C. N. Hadjicostis. Designing stable inverters and state observers for switched linear
systems with unknown inputs. In Proc. of the 45th IEEE Conference on Decision and Control, pages
4105–4110, 2006.
[30] M. V. Volkov. Synchronizing automata and the černỳ conjecture. In Language and Automata Theory
and Applications, pages 11–27. Springer, 2008.
[31] Y. Wang, N. Roohi, G. E. Dullerud, and M. Viswanathan. Stability of linear autonomous systems under
regular switching sequences. In Proc. of the 53rd IEEE Conference on Decision and Control, pages
5445–5450, 2014.
[32] F. Wirth. On the structure of the set of extremal norms of a linear inclusion. In Proc. of the 44th IEEE
Conference on Decision and Control, pages 3019–3024, 2005.

16

