# Stability of linear systems
with bounded switching intervals

Vladimir Yu. Protasov , Rinat Kamalov DISIM, University of L’Aquila, Italy;
e-mail<EMAIL_ADDRESS>Instutute of Control Sciences, Russia
e-mail<EMAIL_ADDRESS>
###### Abstract

We address the stability problem for linear switching systems with mode-
dependent restrictions on the switching intervals. Their lengths can be
bounded as from below (the guaranteed dwell-time) as from above. The upper
bounds make this problem quite different from the classical case: a stable
system can consist of unstable matrices, it may not possess Lyapunov
functions, etc. We introduce the concept of Lyapunov multifunction with
discrete monotonicity, which gives upper bounds for the Lyapunov exponent. Its
existence as well as the existence of invariant norms are proved. Tight lower
bounds are obtained in terms of a modified Berger-Wang formula over
periodizable switching laws. Based on those results we develop a method of
computation of the Lyapunov exponent with an arbitrary precision and analyse
its efficiency in numerical results. The case when some of upper bounds can be
cancelled is analysed.

Key words: linear switching system, dynamical system, stability, restricted
switches, dwell time, Lyapunov exponent, invariant norm, multinorms, norm,
trajectories

AMS 2010 subject classification 37B25, 37M25, 15A60, 15-04

1\. Introduction

Stability of continuous linear switching systems with guaranteed mode-
dependent dwell time, i.e., when the time interval between consecutive
switches is bounded below, has been studied in great detail due to
applications in industry such as robotics [23], multilevel power converters
[3], etc. Theoretical study of such systems draw much attention in recent
years [10, 20, 24, 26, 28], see also [7, 8, 9, 15] and references therein for
the numerical issues. In this work we address the stability problem when the
time interval between switches can be bounded not only below but also above.
Those are the systems that cannot stay in some modes too long and must be
switched when the time interval reaches some fixed mode-dependent bound. This
issue is natural both from theoretical and practical viewpoints, when a system
can stagnate, overheat, etc., after being in one regime for a long time.
Surprisingly enough, the approaches elaborated in the aforementioned works can
hardly be applied to this problem, in spite of an apparent similarity. We
begin with explanations of this phenomenon in Section 2. In fact, some
properties of systems with upper bounds for the switching intervals are
fundamentally different from both the classical systems (without the switching
time restrictions) and the systems with guaranteed dwell time. First of all,
those systems being stable may not have Lyapunov functions. They may not have
Lyapunov multifunctions either, which are often associated to the guaranteed
dwell time stability [10]. Second, the stability of the system may not imply
the stability of each matrix separately. Several unstable regimes can form a
stable system, although it may seem strange from the first site. More
generally, a finite time switching law not always provides a lower bound for
the Lyapunov exponent, as it is the case for usual systems. Thus, with the
upper time restrictions we do not have the main source of bounds for Lyapunov
exponents. That is why systems with bounded switching time require new
concepts of the very basic notions and actually developing a special theory.

We deal with the linear switching systems of the form

$\left\\{\begin{array}[]{l}\dot{\boldsymbol{x}}(t)\ =\
A(t){\boldsymbol{x}}(t),\qquad t\geq 0;\\\
{\boldsymbol{x}}(0)={\boldsymbol{x}}_{0},\quad
A(t)\,\in\,{\mathcal{A}}\,.\end{array}\right.$ (1)

Here ${\boldsymbol{x}}(\cdot):\,{\mathbb{R}}_{+}\to{\mathbb{R}}^{d}$ is the
trajectory; the switching law $A(\cdot)$ is a measurable function with valuer
on a compact control set of real $d\times d$ matrices. We deal with the case
of finite control set ${\mathcal{A}}\,=\,\\{A_{1},\ldots,A_{n}\\}$. Each
matrix $A_{j}$ corresponds to its mode or regime of ODE (1). The time between
two consecutive switches is a switching interval. Each mode $A_{j}$ has
restrictions on the length of its switching interval between $m_{i}$ (the
lower bound) and $M_{j}$ (the upper bound). Thus, we obtain the system with
restrictions on the switching intervals, or in short, the restricted system
$S=\\{{\mathcal{A}},{\boldsymbol{m}},{\mathcal{M}}\\}$, where
${\boldsymbol{m}}=\\{m_{1},\ldots,m_{n}\\},\,{\mathcal{M}}=\\{M_{1},\ldots,M_{n}\\}$.
The system can stay in the regime $A_{j}$ without switches for the time
interval of length on $[m_{j},M_{j}]$.

Note that if we impose the upper bounds, then we have to restrict the dwell
time as well. Otherwise one could split every switching interval by an
arbitrary small interval of another regime, which would make the upper
restrictions useless. Thus, $m_{i}>0$ and $M_{i}\in(m_{i},+\infty]$ for all
$i$. In the case $M_{i}=+\infty$ there is no upper restriction for $A_{j}$. In
particular, if all $M_{j}$ are infinite, then we obtain a system with
guaranteed mode-dependent dwell time. If the converse is not stated we always
assume that $M_{j}$ are finite. In Section 8 we show that this assumption is
actually made without loss of generality.

The restricted system is called asymptotically stable if all its trajectories
tend to zero as $t\to+\infty$. We do not consider other kinds of stability and
usually drop the word “asymptotically”. For the classical (unrestricted)
systems, the necessary condition of stability is that each matrix $A_{j}$ is
Hurwitz or, more generally, every finite switching law (i.e., switching law on
the finite segment) generates a Hurwitz matrix. Neither of this conditions
work for the restricted systems. Finally, the usual stability condition
provided by Lyapunov functions is not applicable either. A stable restricted
system does not necessarily possess Lyapunov function, i.e., a positively
homogeneous function that decreases along every trajectory.

To analyse the stability of restricted systems we begin with Lyapunov
functions. The modification of this concept is done in several stages. First,
we replace one function $f$ but a family of functions $\\{f_{j}\\}_{j=1}^{n}$
associated to the matrices $A_{j}$. Each function $f_{j}$ measures the
trajectory ${\boldsymbol{x}}(t)$ on the interval of the regime $A_{j}$. So,
the Lyapunov function $f$ possesses a piecewise structure, switching between
the components $f_{j}$ simultaneously with the modes $A_{j}$. Second, we
replace the decrease condition of $f(t)$ along any trajectory by the decrease
along the sequence of the switching points. This discrete monotonicity ensures
the stability of a restricted system. Moreover, we show that the existence of
such a Lyapunov multifunction is necessary and sufficient for the stability.
Every stable restricted system does possess a Lyapunov multifunction with
convex components $f_{j}$ (a multinorm) and, moreover, every irreducible
system has an invariant multinorm, which is analogous to the Barabanov norm.
To obtain lower bounds for the Lyapunov exponents, we prove a version of the
Berger-Wang formula for restricted systems. While in the classical case, the
Lyapunov exponent is estimated from below by finite switching laws, for
restricted systems we use only admissible finite laws, which begin and end
with different matrices.

Applying the modified concepts of Lyapunov functions and of the Berger-Wang
formula we derive an algorithm for computation of the Lyapunov exponent with
an arbitrary precision and for deciding the stability of restricted systems.
This algorithm originates with the invariant polytope algorithm for
unrestricted systems [18, 19, 27] but it constructs simultaneously several
polytopes as unit balls of the norms $f_{j}$. The numerical results are
demonstrated in Section 7.

For the sake of simplicity we mostly deal with the case when all regimes
$A_{j}$ have the same lover and upper bounds $m$ and $M$ respectively and
denote such systems as $S=\\{{\mathcal{A}},m,M\\}$. All the results are
extended to the mode-dependent restrictions $m_{j},M_{j}$ in a straightforward
manner. In Section 2 we establish some basic properties of restricted systems
and give examples. Section 3 introduces the modified concept of Lyapunov
function as a multifunction with discrete monotonicity. In Section 4 we
establish the fundamental theorems on the existence of the Lyapunov
multifunction and of the invariant (Barabanov) multinorms. The latter concept
is also modified for restricted systems. Section 6 presents the algorithm for
computing the Lyapunov exponent and for deciding stability; the numerical
results are provided in Section 7. Section 8 deals with the case when the
upper bound $M_{j}$ is big. Under which condition it can be reduced or,
conversely, increased to $+\infty$, i.e. be omitted? We solve this problem by
introducing a concept of “cut tail point” of a matrix. Finally in Section 9 we
provide proofs of the main result.

2\. Basic properties of restricted systems

We consider a linear switching system $S=\\{{\mathcal{A}},m,M\\}$ defined by a
family of matrices $\\{A_{1},\ldots,A_{n}\\}$ and by the time segment $[m,M]$
for the length of allowed length of switching intervals. Every switching law
$A(\cdot)$ is supposed to be admissible, i.e., having the lengths of all
switching intervals on the segment $[m,M]$. We assume formally that all the
switching intervals are open from the right, so all the switching points
$t_{k}$ are associated to the left ends, i.e.,
$A(t_{k})\,=\,A(t_{k}-\varepsilon)$. The point $t_{0}=0$ is formally
associated to some “zero mode” $A_{k}\in{\mathcal{A}}$, so it is considered as
a “zero switching point” from $A_{k}\in{\mathcal{A}}$ to the first mode
$A_{i}$.

Let us remember that we are restricted to the case of equal time segments for
all the modes for the sake of simplicity; all our results are easily extended
to arbitrary mode-dependent segments $[m_{i},M_{i}]$.

For an arbitrary switching law $A(\cdot)$, we consider the solution $\Pi(t)$
of the matrix ODE $\Pi^{\prime}(t)\,=A(t)\Pi(t),\,\Pi(0)=I$, where $I$ is the
$d\times d$ identity matrix. For every $t\geq 0$ we call the $P(t)$ a product
generated by the switching law $A(\cdot)$, in analogy with the case of equal
switching intervals of length $\tau$, when $\Pi(k\tau)$ is a product of
matrices from the set $e^{\tau A_{j}},\,j=1,\ldots,n$. Every trajectory has
the form ${\boldsymbol{x}}(t)\,=\,\Pi(t){\boldsymbol{x}}_{0}$. A restriction
of a switching low to a finite segment $[0,T]$ will be called a finite
switching law.

Since the family ${\mathcal{A}}$ is compact, it follows easily that the family
of functions $\Pi(\cdot)$ is equicontinuous in each finite segment $[0,T]$,
and hence, by the Arzela-Ascoli theorem, it is compact on this segment.
Therefore, the set of all trajectories ${\boldsymbol{x}}(t)$ starting in a
given compact set $K\subset{\mathbb{R}}^{d}$ is compact in $C[0,T]$. This is
true for all switching systems. For the restricted systems we can say more:
the set of admissible switching laws is also compact. To formulate the
corresponding property we need some further notation. The set of all switching
laws $A(\cdot)$ of a restricted system on $[0,T]$ will be referred to as
${\mathcal{E}}(T)$. This is a subset of the $L_{1}$ space of martix-valued
functions on $[0,T]$. Similarly we define the set
${\mathcal{E}}={\mathcal{E}}(+\infty)$ with the topology of convergence in
each segment in ${\mathbb{R}}_{+}$.

###### Proposition 1

For arbitrary restricted system, the set of admissible switching laws
${\mathcal{E}}$ is compact and the sets ${\mathcal{E}}(T)$ are compact for all
$T>0$.

Proof. Every switching law on $[0,T]$ can have at most $T/m$ switching points,
from which it depends continuously. Hence, the set ${\mathcal{E}}(T)$ is
compact as an image of a compact set under a continuous map. Thus,
${\mathcal{E}}(T)$ is compact for all $T$, hence, the set ${\mathcal{E}}$ is
compact as well.

$\Box$

Similarly to the usual (unrestricted) switching systems, the maximal rate of
growth of trajectories is measured by the Lyapunov exponent:

$\sigma(S)\quad=\quad\inf\
\Bigl{\\{}\quad\alpha\quad\Bigl{|}\quad\|{\boldsymbol{x}}(t)\|\ \leq\
C\,e^{\,\alpha t}\quad\mbox{for every trajectory}\
{\boldsymbol{x}}(t)\,\Bigr{\\}}\,.$

For a system generated by one matrix $A$, we have
$\sigma(A)\,=\,\max_{k=1}^{d}{\rm Re}\,\lambda_{k}$ is the spectral abscissa,
where ${\rm Re}$ denotes the real part of a complex number and
$\lambda_{1},\ldots,\lambda_{d}$ are the eigenvalues of $A$ counting
multiplicities. In particular, the one-regime system is stable if the matrix
$A$ is stable or Hurwitz, i.e., ${\rm Re}\,\lambda_{k}<0$ for all
$k=1,\ldots,d$.

The following fact is well known for unrestricted systems, however, in the
restricted case it needs a different proof, which is given in Appendix.

###### Proposition 2

The system is stable precisely when $\sigma(S)<0$.

The Lyapunov exponent is usually estimated from above by a finite switching
law. In particular, $\sigma({\mathcal{A}})\geq\sigma(A_{j})$ for all
$j=1,\ldots,n$. This is true for unrestricted systems or for systems with
guaranteed dwell time [10]. However, if the system is restricted, then this
inequality may fail, as the following simple example demonstrates.

###### Example 1

(Stable system of unstable matrices). Consider the system in
${\mathbb{R}}^{2}$ with two diagonal matrices $A_{1}\,=\,{\rm
diag}\,(1,-3),A_{2}\,=\,{\rm diag}\,(-3,1)$ and with the interval
$[m,M]=[1,2]$. Clearly, both of them are unstable with $\sigma=1$.
Nevertheless, the system is stable and $\sigma\\{A_{1},A_{2}\\}=-\frac{1}{3}$.
To see this we take an arbitrary switching law and denote by $s_{j}\in[1,2]$
the length of $j$th time interval. After the first $2k$ intervals ($2k-1$
switches), we obtain a diagonal matrix $\Pi_{2k}$ with the diagonal elements
$e^{\ \sum_{j=1}^{k}\,(s_{2j-1}-3s_{2j})}\,\leq\,e^{\,k(2-3)}\,=\,e^{\,-k}$
and $e^{\ \sum_{j=1}^{k}\,(-3s_{2j-1}+s_{2j})}\,\leq\,e^{\,-k}$. Since the
total time is at most $3k$, we get $\sigma(S)\leq\frac{1}{3}$. On the other
hand, the switching law with $s_{2j-1}=1,s_{2j}=2,\,j\,\in\,{\mathbb{N}}$,
gives the exponent of growth precisely $\,\frac{1}{3}$.

Actually, this phenomenon is not surprising: the stationary switching laws
$A(t)\equiv A_{1}$ and $A(t)\equiv A_{2}$ are unstable (the trajectory is
unbounded) but they both are not admissible.

The standard way to prove the stability is to present a Lyapunov function,
i.e., a positively homogeneous function decreasing along every trajectory of
the system. It is well-known that every stable linear switching system does
possess a Lyapunov function, which, moreover, can be chosen convex (the
Lyapunov norm) [29]. However, this is not true for restricted systems.

###### Example 2

(A stable restricted system which does not possess Lyapunov function).
Consider the system on ${\mathbb{R}}^{1}$ with two matrices (numbers)
$A_{1}=a,\,A_{2}=b,\ a>b$, and with the switching interval $[m,M]=[1,2]$. The
maximal growth is given by the periodic switching law with the period $3$:
$A(t)=a,\,t\in[0,2);\ A(t)\,=\,b,\ t\in[2,3)$. The Lyapunov exponent is
$\sigma\,=\,\frac{1}{3}\,(2a+b)$. Hence, if $2a+b<0$, then the system is
stable. For example, it is stable for $a=1,b=-3$. However, there is no
Lyapunov function in this case. Indeed, every Lyapunov function on
${\mathbb{R}}$ has the form $f({\boldsymbol{x}})\,=\,c\,|{\boldsymbol{x}}|$
with some $c>0$. Hence, if $0=t_{0}<t_{1}<\cdots$ are the switching points,
then in all the intervals $(t_{2k},t_{2k+1}),\,k\in{\mathbb{N}}$, we have
$A(t)=a$, and hence
$f\bigl{(}{\boldsymbol{x}}(t)\bigr{)}\,=\,c\,|{\boldsymbol{x}}(t)|\,=\,c\,|\,e^{\,a(t-t_{2k})}{\boldsymbol{x}}(t_{2k})|$
increases on those intervals.

Thus, the system is stable but $f$ somewhere increases, hence, this is not a
Lyapunov function. Let us remark that in this case even the sequence
$f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)}$ at the switching points $t_{k}$ is
not monotone.

3\. The concept of Lyapunov functions for restricted systems

Example 2 above shows that a stable restricted system may not possess Lyapunov
functions. In this case, how to prove stability? One needs to modify the the
concept of Lyapunov function for restricted systems. We do this in three
steps. First, we pass to multifunctions, which is a collection of functions:
each matrix $A_{j}$ is equipped with its function $f_{j}$. Second, the
monotonicity requirement for Lyapunov functions is relaxed to monotonicity
over the set of switching points. Third, the Lyapunov multifunction is not
defined in the minimal time intervals $(t_{k},t_{k}+m]$

3.1 Three steps of modification

Step 1. Lyapunov multifunctions. The main idea is to consider the action of
each operator $A_{j}$ separately of others. We use $n$ functions $f_{j}$, a
priory different, each of them corresponds to its operator $A_{j}$ and
measures the trajectory ${\boldsymbol{x}}(t)$ only on intervals of the regime
$A_{j}$. Thus, the functions $f_{j}$ are switched together with the operators
$A_{j}$. Now we compose the multifuntion
$f({\boldsymbol{x}})=\bigl{(}f_{1}({\boldsymbol{x}}),\ldots,f_{n}({\boldsymbol{x}})\bigr{)}$
with the following property:
$f({\boldsymbol{x}}(t))=f_{j}({\boldsymbol{x}}(t))$ when $A(t)=A_{j},\
j=1,\ldots,n$. At the switching points the function $f$ is supposed to be
continuous from the left, i.e., if at the point $t_{k}$ the mode switches from
$A_{i}$ to $A_{j}$, then $f({\boldsymbol{x}}(t))=f_{i}({\boldsymbol{x}}(t))$.
The point $t=0$ can be associated to an arbitrary “ zero mode” from
${\mathcal{A}}$.

Step 2. Asymptotic behaviour over a discrete set. Multifunctions do not solve
the problem either: for a stable restricted system, there may not exist
functions $f_{j}({\boldsymbol{x}})$ that decrease on the intervals of the
corresponding regimes $A_{j}$. In Example 2, whatever positively homogeneous
function $f_{j}$ to take, it increases on each interval of the regime
$A_{1}=a$.

Thus, for restricted systems, one cannot provide the main property of Lyapunov
functions to decrease along all trajectories. A way out of this situation is
to narrow down the base of convergence. Namely, we relax the requirement for
the Lyapunov function to decrease over the set of switching points only.

For the restricted systems, when the lengths of switching intervals are
bounded above, the asymptotics of an arbitrary trajectory
${\boldsymbol{x}}(t)$ as $t\to\infty$ is equivalent to its asymptotics over
the sequence of switching points. Hence, if a positive homogeneous function
$f$ decreases over switching points of every trajectory, then the system is
stable, see Proposition 3.

Step 3. The trajectory on the dwell time intervals. We will pay no attention
to the behaviour of the trajectory on the obligatory dwell time intervals
$(t_{k},t_{k}+m]$, where we anyway cannot change the control. Due to the fixed
lengths of those intervals, the asymptitic behaviour of the trajectory on them
is the same as along the switching points.

Let us now summarise the three main steps of the modification:

1) replace the concept of Lyapunov function
$f:{\mathbb{R}}^{d}\to{\mathbb{R}}_{+}$ by the Lyapunov
multifunction$f=(f_{1},\ldots,f_{n}):\,{\mathbb{R}}^{d}\to{\mathbb{R}}_{+}^{n}$
and switch the functions $f_{j}$ accordingly to the control regime
simultaneously with the operators $A_{j}$;

2) relax the condition for decreasing $f({\boldsymbol{x}}(t))$ along the axis
${\mathbb{R}}_{+}$ to the decreasing on the set of switching points, i.e.,
$f({\boldsymbol{x}}(t_{k+1}))\,<\,f({\boldsymbol{x}}(t_{k})),\
k\in{\mathbb{N}}$;

3) do not consider the values of $f$ on the dwell-time intervals
$(t_{k},t_{k}+m]$.

We are going to see that it is sufficient to consider only multinorms, when
all $f_{j}$ are convex functions.

###### Definition 1

The multinorm $f$ is called Lyapunov for a system $\\{{\mathcal{A}},m,M\\}$ if
the sequence $f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)},\,k\geq 0,$ decreases
on every trajectory ${\boldsymbol{x}}(t)$.

This means that if $t_{k}$ is a switching point from the mode $A_{i}$ to
$A_{j}$, then $f_{i}(t_{k})\,>\,f_{j}(t_{k+1})$. The point $t_{0}=0$ is
considered as a “zero switching point” from an arbitrary “zero mode”
$A_{k}\in{\mathcal{A}}$ to the mode starting mode $A_{i}$.

###### Proposition 3

If a restricted system $S=\\{{\mathcal{A}},m,M\\}$ possesses the Lyapunov
multinorm, then $S$ is stable.

Proof. Let $f$ be a Lyapunov multinorm; then for each indices $i\neq j$, for
every ${\boldsymbol{x}}\in{\mathbb{R}}^{d}$ such that
$f_{i}({\boldsymbol{x}})=1$ and for every $\tau\in[m,M]$, we have
$f_{j}(e^{\,\tau A_{j}}{\boldsymbol{x}})<1$. Indeed, consider the trajectory
${\boldsymbol{x}}(\cdot)$ starting at
${\boldsymbol{x}}(0)\,=\,{\boldsymbol{x}}$, with the formal zero mode $A_{i}$
followed by the first mode $A_{j}$ and $t_{1}=\tau$ is the first switching
point. We have $f_{j}\bigl{(}e^{\,\tau
A_{j}}{\boldsymbol{x}}\bigr{)}\,=\,f_{j}\bigl{(}{\boldsymbol{x}}(t_{1})\bigr{)}\,<\,f_{i}\bigl{(}{\boldsymbol{x}}(t_{0})\bigr{)}\,=\,1$.
Now by the compactness argument it follows that the maximum of
$f_{j}\bigl{(}e^{\,\tau A_{j}}{\boldsymbol{x}}\bigr{)}$ over all
$\tau\in[m,M],\,i,j\in\\{1,\ldots,n\\},\,i\neq j$ and over ${\boldsymbol{x}}$
such that $f_{i}({\boldsymbol{x}})=1$ is less than one. Denote this maximum by
$q<1$. Then for every trajectory ${\boldsymbol{x}}(\cdot)$ with
$f({\boldsymbol{x}}(0))=1$, we have $f({\boldsymbol{x}}(t_{k}))\,\leq\,q^{k}$
and therefore, for every $t\in[t_{k},t_{k+1}]$, we have
$f({\boldsymbol{x}}(t))\,\leq\,C\,q^{k}$, where $C$ is some constant.
Therefore, $f({\boldsymbol{x}}(t))\to 0$ as $t\to+\infty$.

$\Box$

###### Remark 1

Thus, if a positive homogeneous multifunction $f$ decreases over switching
points of every trajectory, then the system is stable. For unrestricted
systems this may not be true, and therefore, our modification of the Lyapunov
function property is impossible.

For the Lyapunov exponent of a restricted system, we have

$\sigma(S)\ =\ \inf\,\Bigl{\\{}\alpha\in{\mathbb{R}}\ \Bigl{|}\
\|{\boldsymbol{x}}(t_{k})\|\,\leq\,C\,e^{\,\alpha t}\,,\
k\in{\mathbb{N}}\Bigr{\\}},$

where $\\{t_{k}\\}_{k\in{\mathbb{N}}}$ are the switching points, and the
infimum is computed over all trajectories of the system. Thus, for the
restricted systems, the asymptotics of any trajectory along the time axis is
equivalent to that along the sequence of switching points.

One may wonder if the multinorm concept is really needed to have the Lyapunov
property from Definition 1? Can the components $f_{j}$ be always chosen equal
or at least proportional to each other? The answer is negative as the
following example demonstrates.

###### Example 3

(The stable system which does not have a Lyapunov function with proportional
components). Consider the system on ${\mathbb{R}}^{2}$ with two matrices
$A_{1},A_{2}$ defined as follows. Take a diagonal matrix $B\,=\,{\rm
diag}\,\bigl{(}\frac{1}{2},\frac{1}{3}\bigr{)}$ and a rotation $R$ on an
irrational ${\rm mod}\,\pi$ angle. Then $A_{1},A_{2}$ are defined from the
equalities $e^{A_{1}}\,=\,B,e^{A_{1}}\,=\,RB^{-1}$. For $m=M=1$ (which is
formally not allowed but we make an exception for a while), each trajectory
${\boldsymbol{x}}(t)$ is bounded. Furthermore,
${\boldsymbol{x}}(t_{2k})\,=\,{\boldsymbol{x}}(2k)\,$ is an image of
${\boldsymbol{x}}(t_{0})$ under the rotation by the angle $k\alpha$.
Therefore, the points ${\boldsymbol{x}}(t_{2k})$ are everywhere dense on the
circle. Hence, the Euclidean norm is the only norm which is non-decreasing on
the sequence $\\{t_{2k}\\}_{k\in{\mathbb{N}}}$. Assume
$\|{\boldsymbol{x}}(t_{0})\|=1$ and so, $\|{\boldsymbol{x}}(t_{2k})\|=1$ for
all $k$. However, for the points
${\boldsymbol{x}}(t_{2k+1})\,=\,B^{-1}R^{k}{\boldsymbol{x}}(t_{0})$, we have
$\|{\boldsymbol{x}}(t_{2k+1})\|>1$. Now take a close system which is stable
and $m,M$ are close but not equal. Thus, if this system has a Lyapunov
multifunction $f=(f_{1},f_{2})$ with proportional $f_{1},f_{2}$, then they
both close to be proportional to the Euclidean norm, and hence
$\|{\boldsymbol{x}}(t_{2k+1})\|\,>\,\|{\boldsymbol{x}}(t_{2k})\|$ for not very
large $k$. Hence $f$ cannot be a Lyapunov multinorm. We see that in this
example there are no Lyapunov multinorms with proportional components.

Thus, to characterize stable systems one needs multinorms with a priori
different (even non proportional) components.

To deal with Lyapunov multinorms it is convenient to to use the graph
interpretation. In the next subsection we recall the concept of dynamical
systems on graphs and show how to put an arbitrary restricted switching system
to the graph.

3.2. The graph structure

Lyapunov multinorms for restricted systems can naturally be formulated in
terms of graphs. The switching systems of graphs have been actively studied in
the recent literature [12, 22, 31, 32, 34] and such models are special
occurrences of hybrid automata [35]. Some generalizations to discrete-
continuous hybrid systems were presented in [10], where they provided tools
for the study systems with the lower restrictions on switching time. To the
upper restrictions, that approach is hardly applicable, however, as we shall
see below, the graph idea can also be put to good use.

The graph multinorm. We consider a directed graph $G$ with vertices
$g_{1},\ldots,g_{n}$, each vertex $g_{j}$ is associated to a linear space
$L_{j}$ isomorphic to ${\mathbb{R}}^{d}$. Let
${\mathcal{B}}=\\{B_{1},\ldots,B_{n}\\}$ be a family of linear operators on
${\mathbb{R}}^{d}$. All edges of $G$ are coloured in $n$ colours corresponding
to these operators. Each pair of vertices $g_{i},g_{j},\,i\neq j$, are
connected by two edges: the edge of colour $B_{j}$ is directed from $g_{i}$ to
$g_{j}$ and the opposite edge is of colour $B_{i}$. Thus, each vertex $g_{j}$
has precisely $n$ incoming edges, all of the colour $B_{j}$. The operator
$B_{j}$ associated to the edge $g_{i}g_{j}$ acts from $L_{i}$ to $L_{j}$ (so
$B_{j}:{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}$ is considered as an operator from
$L_{i}$ to $L_{j}$). Now we introduce a multinorm on this graph.

###### Definition 2

If every space $L_{i}$ on the graph $G$ is equipped with a norm
$\|\cdot\|_{i}$, then the collection of norms $\,\bigl{\\{}\,\|\cdot\|_{i},\
\bigl{|}\ i=1,\ldots,n\,\bigr{\\}}$, is called a multinorm. The norm of an
operator $B:L_{i}\to L_{j}$ is defined as
$\,\|B\|\,=\sup\limits_{{\boldsymbol{x}}\in
L_{i},\|{\boldsymbol{x}}\|_{i}=1}\|B{\boldsymbol{x}}\|_{j}$.

We denote that multinorm by $\|\cdot\|$. Thus, for every ${\boldsymbol{x}}\in
L_{i}$, we have $\|{\boldsymbol{x}}\|=\|{\boldsymbol{x}}\|_{i}$ and we drop
the index of the norm if it is clear to which space $L_{i}$ the point
${\boldsymbol{x}}$ belongs to.

From restricted systems to dynamical systems on graph. We consider an
arbitrary restricted system $\\{{\mathcal{A}},m,M\\}$ in ${\mathbb{R}}^{d}$
and turn it to a system on a graph $G=\\{g_{i}\\}_{i=1}^{n}$ with
$L_{j}={\mathbb{R}}^{d},j=1,\ldots,n$. We assume that $A_{j}$ acts in the
space $L_{j}$ and denote $B_{j}=e^{\,mA_{j}},\,j=1,\ldots,n$.

Define the following linear switching system on the graph $G$. We start with a
point ${\boldsymbol{x}}(t_{0})\in L_{i}$ (for some $i$), then jump to some
$L_{j}$ to the point
${\boldsymbol{x}}(t_{0}+m)\,=\,B_{j}{\boldsymbol{x}}(t_{0})$, then go in
$L_{j}$ along the curve
${\boldsymbol{x}}(t)\,=\,e^{(t-t_{0})A_{j}}{\boldsymbol{x}}(t_{0}),\
t\in[t_{0}+m,t_{1}]$ with some $t_{1}\leq t_{0}+M$. In other words, we go
along the solution of the ODE $\
\dot{\boldsymbol{x}}(t)\,=\,A_{j}{\boldsymbol{x}}(t),\,t\in[t_{0}+m,t_{1}]$
from the point ${\boldsymbol{x}}(t_{0}+m)\,=\,B_{j}{\boldsymbol{x}}(t_{0})$
during the time at most $M-m$ until the switching point
${\boldsymbol{x}}_{1}$. Then we apply some $B_{s}$ and jump to the space
$L_{s}$ landing at the point
${\boldsymbol{x}}(t_{1}+m)\,=\,B_{k}\,{\boldsymbol{x}}(t_{1})$, etc. We obtain
a trajectory ${\boldsymbol{x}}(t)$ with switching points $\\{t_{k}\\}_{k\geq
0}$.

In our notation, for each $k\geq 0$, the point ${\boldsymbol{x}}(t_{k})$ is in
the space $L_{j_{k}}$. From this point the trajectory goes to the space
$L_{j_{k+1}}$ by means of the operator $B_{j_{k+1}}$. Thus, the trajectory
switches from ${\boldsymbol{x}}(t_{k})$ to the point
${\boldsymbol{x}}(t_{k}+m)\,=\,B_{j_{k+1}}{\boldsymbol{x}}(t_{k})$ in the
space $L_{j_{k+1}}$. Then the trajectory stays inside this space for the time
$t_{k+1}-t_{k}-m$ and goes along the solution of the ODE
$\,\dot{\boldsymbol{x}}(t)=A_{j_{k+1}}{\boldsymbol{x}}(t),\,t\in[t_{k}+m,t_{k+1}]$.

We see that each jump (switch) between the spaces takes time precisely $m$ and
each ODE takes time $t_{k+1}-t_{k}-m$, which does not exceed $M-m$. We control
the switching points $t_{k}$ under the restrictions $m\leq t_{k+1}-t_{k}\leq
M$ for all $k\geq 0$, and the choice of the indices $j_{k}$. Each choice
produces a control law and a trajectory ${\boldsymbol{x}}(t)$. For
$t\in(t_{k},t_{k}+m)$ the point ${\boldsymbol{x}}(t)$ is not considered,
although at can be defined as
$e^{(t-t_{k})A_{j_{k+1}}}{\boldsymbol{x}}(t_{k})$.

4\. Lyapunov and invariant multinorms

The Lyapunov multinorm of a restricted switching system (Definition 1) has an
obvious geometrical interpretation on the graph. Let ${\mathcal{B}}_{i}$ be
the unit ball of the norm $f_{i}$ and ${\mathcal{S}}_{i}$ be the corresponding
unit sphere.

###### Proposition 4

A multinorm $f$ is Lyapunov if for each $i=1,\ldots,n$, and $j\neq i$, and for
every ${\boldsymbol{x}}\in{\mathcal{S}}_{i}$, the curve
$e^{tA_{j}}\,B_{j}\,{\boldsymbol{x}}\,,\ t\in[0,M-m]$, lies strictly inside
${\mathcal{S}}_{j}$.

Proof. If $f$ is a Lyapunov norm, then choosing arbitrary
${\boldsymbol{x}}(t_{1})\in{\mathcal{S}}_{i}$ and $t_{2}\in[m,M]$ and denoting
$t=t_{2}-m$, we get
${\boldsymbol{x}}(t_{2})\,=\,e^{\,tA_{j}}\,B_{j}\,{\boldsymbol{x}}(t_{1})$,
and therefore,
${f\bigl{(}{\boldsymbol{x}}(t_{2})\bigr{)}\,<\,f\bigl{(}{\boldsymbol{x}}(t_{1})\bigr{)}\,=\,1}$.
Hence, the point ${\boldsymbol{x}}(t_{2})$ is strictly inside
${\mathcal{S}}_{j}$. Conversely, if the condition of the proposition is
satisfied, then, for an arbitrary trajectory ${\boldsymbol{x}}(\cdot)$ and for
an arbitrary its switching point $t_{k}$ from a mode $A_{i}$ to $A_{j}$, we
have
${\boldsymbol{x}}(t_{k+1})\,=\,e^{tA_{j}}\,B_{j}\,{\boldsymbol{x}}(t_{k})$
with $t=t_{k+1}-t_{k}-m$. Normalising ${\boldsymbol{x}}(t_{k})$ to have norm
one, we obtain the point ${\boldsymbol{x}}(t_{k+1})$ inside
${\mathcal{S}}_{j}$, hence $\|{\boldsymbol{x}}(t_{k+1})\|<1$. Thus,
$\|{\boldsymbol{x}}(t_{k+1})\|<\|{\boldsymbol{x}}(t_{k})\|$, which completes
the proof.

$\Box$

###### Corollary 1

If $f$ is a Lyapunov multinorm, then for every trajectory ${\boldsymbol{x}}$
and for every its switching point $t_{k}$, we have
$f\bigl{(}{\boldsymbol{x}}(t)\bigr{)}\,<\,f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)}$
for all $t>t_{k}$.

Thus, along every trajectory ${\boldsymbol{x}}(\cdot)$, the Lyapunov function
“decreases by intervals”: at each point of the interval $(t_{k},t_{k+1})$ it
is less than at each point of the previous interval $(t_{k-1},t_{k})$.

The following theorem shows that the existence of a Lyapunov multinorm with
discrete monotonicity completely characterizes stable systems.

###### Theorem 1

Every stable restricted system possesses a Lyapunov multinorm.

The proof is in Section 9. The next stage is the extension of the concept of
invariant or Barabanov norms to restricted systems. Such norms are usually
applied to obtain a very refined analysis of the fastest growth of
trajectories. Now it is quite expected that such an extension should require
significant modifications for restricted systems.

###### Definition 3

An invariant multinorm for a system $S=\\{{\mathcal{A}},m,M\\}$ is a multinorm
$f$ with two properties:

a) for every trajectory ${\boldsymbol{x}}(\cdot)$ with switching points
$\\{t_{k}\\}$, the sequence
$e^{-\sigma\,t_{k}}\,f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)}$ is non-
increasing;

b) for every ${\boldsymbol{x}}_{0}\in{\mathbb{R}}^{d}$, there exists a
trajectory $\bar{\boldsymbol{x}}(\cdot)$ starting at ${\boldsymbol{x}}_{0}$
such that
$e^{-\sigma\,t_{k}}f\bigl{(}\bar{\boldsymbol{x}}(t_{k})\bigr{)}\,\equiv\,{\rm
const}$.

###### Remark 2

If $\sigma(S)=0$, then the definition of the invariant multinorm gets a
simpler form:

for every trajectory, the sequence $f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)}$
is non-increasing and for every ${\boldsymbol{x}}_{0}\in{\mathbb{R}}^{d}$,
there exists a trajectory $\bar{\boldsymbol{x}}(\cdot)$ starting at
${\boldsymbol{x}}_{0}$ such that
$f\bigl{(}\bar{\boldsymbol{x}}(t_{k})\bigr{)}\,\equiv\,{\rm const}$.

Note that every system can be reduced to the case $\sigma=0$ by replacing each
matrix $A_{i}$ with $A_{i}\,-\,\sigma I$. Hence, it is sufficient to formulate
the notion of invariant multinorm only for the case $\sigma=0$.

###### Proposition 5

Let $\\{{\mathcal{A}},m,M\\}$ be a system with $\sigma=0$. A multinorm $f$ is
invariant if for each $i=1,\ldots,n$ and for every
${\boldsymbol{x}}\in{\mathcal{S}}_{i}$, the curve
$e^{tA_{i+1}}\,B_{i+1}\,{\boldsymbol{x}}\,,\ t\in[0,M-m]$, lies in the ball
${\mathcal{B}}_{i+1}$ and at least one point of this curve is on its surface
${\mathcal{S}}_{i+1}$.

Proof. If $f$ is invariant, then choosing arbitrary
${\boldsymbol{x}}(t_{1})\in{\mathcal{S}}_{1}$ and $t_{2}\in[m,M]$ and denoting
$t=t_{2}-m$, we obtain
$f\bigl{(}{\boldsymbol{x}}(t_{2})\bigr{)}\,\leq\,f\bigl{(}{\boldsymbol{x}}(t_{1})\bigr{)}\,=\,1$.
Moreover, this inequality must become an equality for some $t_{2}\in[m,M]$, in
which case ${\boldsymbol{x}}(t_{2})$ is on the surface of
${\mathcal{S}}_{i+1}$.

Conversely, arguing as above we conclude that for each choice of switching
points $\\{t_{k}\\}_{k\in{\mathbb{N}}}$, it holds that
$f\bigl{(}{\boldsymbol{x}}(t_{k+1})\bigr{)}\leq
f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)},\ k\in{\mathbb{N}}$. The trajectory
$\bar{\boldsymbol{x}}$ is constructed by induction. The point
$\bar{\boldsymbol{x}}(t_{1})\in{\mathcal{S}}_{1}$ is arbitrary. Let the
trajectory $\bar{\boldsymbol{x}}$ be constructed on the segment $[0,t_{k}]$.
Applying our assumption to the point
${\boldsymbol{x}}=\bar{\boldsymbol{x}}(t_{k})$ we get a point
$e^{tA_{i+1}}\,B_{i+1}\,\bar{\boldsymbol{x}}(t_{k})$ on the unit sphere for
some $t\in[0,M-n]$. We set $\,t_{k+1}=t_{k}+t$ and obtain
$f\bigl{(}{\boldsymbol{x}}(t_{k+1})\bigr{)}=1$. This way we extend the
trajectory $\bar{\boldsymbol{x}}(t)$ to the segment $[t_{k},t_{k+1}]$, which
proves the inductive assumption.

$\Box$

Every trajectory of the maximal growth takes values
$f({\boldsymbol{x}}(t_{k}))\,=\,e^{\,\sigma t_{k}}f({\boldsymbol{x}}(0))$ at
all its switching points $t_{k},\,k\geq 0$, while for all other trajectories
this sequence in non-increasing and for some $k$ we have
$f({\boldsymbol{x}}(t_{k}))\,<\,e^{\,\sigma t_{k}}f({\boldsymbol{x}}(0))$ (for
each trajectory, the values of $f$ are computed over its own switching
points). Thus, the invariant multinorm allows us to characterize all
trajectories of maximal growth and to evaluate the multinorm at all its
switching points. A question arises if such a norm always exists? The answer
is affirmative provided the family of matrices ${\mathcal{A}}$ is irreducible,
i.e., those matrices do not share a common nontrivial invariant subspace.

###### Theorem 2

Every irreducible restricted system possesses an invariant Lyapunov multinorm.

The proof is in Section 9. It is interesting that Theorem 2 has the same
formulation as for the usual (unrestricted) systems, proved by Barabanov in
[2] with one exception: for the usual system it holds provided the control set
${\mathcal{A}}$ is convex (and hence, infinite, unless one-point). This
distinction is explained by the different definitions: the invariant norm
according to Definition 3 exists for all finite ${\mathcal{A}}$. Another
modification of invariant norm was done for hybrid systems in [10]. Also note
that for systems with at least two matrices, the irreducibility is a generic
property. Moreover, it suffices to analyse the maximal growth of trajectories
and find the Lyapunov exponents for irreducible systems only (see Section 6).

5\. Periodic solutions. The Berger-Wang formula

One more difference of the restricted systems from the classical ones is the
role of periodic trajectories. In the classical case, for the unrestricted
systems, each finite switching law $A(\cdot)\in{\mathcal{E}}(T)$ gives a lower
bound for the Lyapunov exponent:
$\sigma(T)\,=\,T^{-1}\sigma\bigl{(}\Pi(T)\bigr{)}$, where, recall, $\Pi(t)$ is
the solution of matrix ODE $\Pi^{\prime}(t)=A(t)\Pi(t),\,\Pi(0)=I$. Indeed,
the maximal growth over all trajectories does not exceed the growth of the
periodic switching law with the period $\Pi(T)$. For restricted systems this
is not true. For instance, the univariate system from Example 2 has the
Lyapunov exponent $\sigma=\frac{2\ln a\,+\,\ln b}{3}$, while the stationary
switching law $A(t)\equiv a$, which is, of course, also periodic, has the
Lyapunov exponent $\ln a\,>\,\sigma$. The reason is that not all finite
switching laws can be periodized for a restricted switching system. The
obtained periodic law must belong to ${\mathcal{E}}$, i.e., have the time
intervals for each regime $A_{i}$ are all between $m$ and $M$.

5.1. Admissible periods

Which finite switching laws are periodisable? These are the admissible laws
according to the following definition:

###### Definition 4

A finite switching law is called admissible if it begins and ends with
different matrices. The set of admissible switching laws is denoted as
${\mathcal{E}}_{0}$.

###### Proposition 6

A finite switching law belongs to ${\mathcal{E}}_{0}$ precisely when there
exists $i\in\\{1,\ldots,n\\}$ such that this law on the graph starts and
finishes in $L_{i}$.

Proof. If $A(\cdot)\in{\mathcal{E}}_{0}$ starts with a matrix $A_{j}$ and ends
with $A_{i}$, then $i\neq j$. Moreover, the time interval for $A_{i}$ is at
least $m$, hence any product $\Pi(t)$ starts with $e^{mA_{j}}=B_{j}$. Taking
arbitrary ${\boldsymbol{x}}\in L_{i}$ we can apply $B_{j}$ and obtain a point
$B_{j}{\boldsymbol{x}}\in L_{j}$, then we continue along the switching law
$A(\cdot)$ and finally return to $L_{i}$ since the law finishes with $A_{i}$.
Conversely, if a finite trajectory starts and finishes in $L_{i}$, then the
corresponding switching law $A(\cdot)$ starts with some matrix different from
$A_{i}$ and finishes with $A_{i}$. Hence, $A(\cdot)\in{\mathcal{E}}_{0}$.

$\Box$

Proposition 6 yields that ${\mathcal{E}}_{0}$ is the set of all periodizable
finite switching laws:

###### Corollary 2

A periodic switching law belongs to ${\mathcal{E}}$ if and only if its period
is from ${\mathcal{E}}_{0}$.

Now we can show that every $A(\cdot)\in{\mathcal{E}}_{0}$ provides a lower
bound for the Lyapunov exponent. Recall that for matrix $\Pi$ we denote by
$\sigma(\Pi)$ its spectral abscissa, i.e., the biggest real part of its
eigenvalues.

###### Proposition 7

Fro a restricted system $S$, every product $\Pi(T)$ generated by a switching
law from ${\mathcal{E}}_{0}$ possesses the property $\
T^{-1}\sigma(\Pi(T))\,\leq\,\sigma(S)$.

Proof. Since $A(\cdot)\in{\mathcal{E}}_{0}$, there exists an admissible
periodic switching law with period $\Pi(T)$. The rate of growth of this
switching law is $T^{-1}\bigl{(}\sigma(\Pi(T)\bigr{)}$ and this does not
exceed the maximal rate of growth, which is $\sigma(S)$.

$\Box$

Thus, finite switching laws from ${\mathcal{E}}_{0}$ provide lower bounds for
$\sigma(S)$. The question arises if they can be arbitrarily sharp? In other
words, can the values $\,T^{-1}\sigma(\Pi(T))$ for
$\,A(\cdot)\in{\mathcal{E}}_{0}$ approach arbitrarily close to $\sigma(S)$?
For the classical (unrestricted) systems the answer is affirmative because all
finite switching laws can be periodized. This implies the classical Berger-
Wang formula for the classical case:

$\sigma(S)\quad=\quad\limsup_{T\to\infty}\
\frac{1}{T}\,\max\limits_{A(\cdot)\in{\mathcal{E}}(T)}\,\sigma\bigl{(}\Pi(T)\bigr{)}\,.$
(2)

An extension of this formula to restricted systems is not direct since in this
case we have a narrower class of admissible finite laws $E$ and, respectively,
the less set of lower bounds. That is why there is no evidence that those
bounds reach $\sigma(S)$. Nevertheless, this is true. The following corollary
of Theorem 2 not only generalizes the Berger-Wang formula to restricted
switching systems but even slightly improve it.

###### Theorem 3

For every restricted switching system, we have

$T\,\sigma\,({\mathcal{A}})\ -\
\max\limits_{A(\cdot)\in{\mathcal{E}}_{0}(t),\,t\leq
T}\,\sigma(\Pi(t))\quad\to\quad 0\ ,\qquad\mbox{as}\quad T\to\infty\,.$ (3)

The proof is in Section 9. Dividing equality (3) by $T$, we obtain (2).

###### Corollary 3

The equality (2) holds for restricted systems after replacing ${\mathcal{E}}$
by ${\mathcal{E}}_{0}$ .

For unrestricted systems, the assertion (3) implies the Berger-Wang formula
but not vice versa. Hence, even in the classical case Theorem 3 strengthens
the Berger-Wang formula.

###### Definition 5

For given $T>0$, the maximal $T$-period of the restricted system is a
switching law $A(\cdot)\in{\mathcal{E}}_{0}(t),\ t\in[m,T]$ for which the
value $\,t^{-1}\,\sigma(\Pi(t))$ is maximal among all admissible switching
laws in the the time interval no longer than $T$.

The maximal $T$-period is well-defined because the set of products $\Pi(t)$
generated by all switching laws $A(\cdot)\in{\mathcal{E}}_{0}(t),\,\
t\in[m,T]$, is compact.

The maximum in Theorem 3 can be computed over the maximal $T$-periods. It
would be natural to expect some regular behaviour of the maximal $T$-period
with respect to $T$, for example, its continuity. Suppose that the matrix
$A_{j}$ is dominant in ${\mathcal{A}}$, i.e., it has the maximal spectral
abscissa $\sigma(A)$ among all $A\in{\mathcal{A}}$. Is it true that the
maximal $(m+M)$-period is provided by a law with the maximal contribution of
$A_{j}$, i.e., when the mode $A_{j}$ has the time interval of length $M$?

The answer is negative. Moreover, the maximal $T$-period can be discontinuous
in $T$. Even its length can be discontinuous.

5.2. A restricted system with discontinuous $T$-period

Consider the system ${\mathcal{A}}$ of two $2\times 2$ matrices with $m=\pi$
and with arbitrary $M>\pi$:

$A_{1}\ =\ \left(\begin{array}[]{rr}-1&0\\\ 0&-a\end{array}\right)\ ;\qquad
A_{2}\ =\ \left(\begin{array}[]{rr}0&-1\\\ 1&0\end{array}\right)\ ,$

where $a>1$. We have $e^{tA_{1}}\,=\,{\rm diag}\,(e^{-t},e^{-2t})$ and
$e^{tA_{2}}$ is a rotation by the angle $t$. Therefore, for the unrestricted
system with the matrices $A_{1},A_{2}$, the matrix $A_{2}$ is dominant and the
law $A(t)\equiv A_{2}$ provides the maximal growth. Does $A_{2}$ preserve its
dominancy for the constraint system? This means that the longer the time
interval for $A_{2}$ the faster growth we have. For a given $T$, denote by
$\Pi_{m}(T)$ the product of the following switching law:
$A(t)=A_{1},\,t\in[0,m)$ and $A(t)=A_{2},\,[t,T]$. The question is whether
$\Pi_{m}(M)$ is the $M$-period whatever upper time restriction $M$ to take?

Before giving the answer let us make some observations. First, the only law
$A(\cdot)\in{\mathcal{E}}_{0}$, for which the (Euclidean) norm $\|Pi(T)\|$
reaches the value $e^{-\pi}$ is $\Pi_{m}$. Indeed, the rotation $e^{tA_{2}}$
does not change the norm while the contraction $e^{tA_{2}}$ reduce it. For
$t=\pi k$ the matrix $\Pi_{m}(t)$ has the spectral radius $e^{-\pi}$ (the
corresponding eigenvector is ${\boldsymbol{v}}=(1,0)$). Hence, the spectral
radius of $\Pi_{m}(t)$ reaches its maximal value $e^{-\pi}$ precisely at the
points $t=\pi k$. For all other laws, the spectral radius of $\Pi(t)$ is
smaller than $e^{-\pi}$ for all $t$.

###### Proposition 8

For every large $a>1$, there is a number $n\in{\mathbb{N}}$ and positive
numbers $\tau_{1}<\cdots<\tau_{2n}$ such that for each $k=1,\ldots,n$, the
following hold:

1) $\ \pi k<t_{2k-1}<\pi(k+1)$;

2) for the restricted system ${\mathcal{A}}$ with $M=\tau_{2k}$, a the
solution $E_{m}(M)$ is a unique $M$-period;

3) for the restricted system ${\mathcal{A}}$ with $M=\tau_{2k-1}$.

Moreover, $n\to\infty$ as $p\to\infty$.

Proof. By the compactness, for each $t$, the maximum of $\rho(\Pi(t))$ over
all laws $A(\cdot)\in{\mathcal{E}}_{0}$ is achieved and is smaller than
$e^{-\pi}$ for all points $t\neq\pi k,\,k\in{\mathbb{N}}$. Denote by
$\varphi(t)$ this maximum to the power $1/t$ and by $\varphi_{m}(t)$ the
spectral radius of $\Pi_{m}(t)$ to the power $1/t$. We have $\varphi(\pi
k)=\varphi_{m}(\pi k)\,=\,e^{-1/k}$ and $\varphi(t)\geq\varphi_{m}(t)$ for all
other $t$. Observe that for the spectral radius of
$\Pi_{m}\bigl{(}\frac{\pi}{2}+\pi k\bigr{)}$ is equal to
$e^{-\frac{(a+1)\pi}{2}}$, therefore

$\varphi_{m}\,\left(\frac{\pi}{2}+\pi k\right)\ =\ e^{-\frac{(a+1)}{2k+1}}\ <\
e^{-\frac{1}{k}}\ =\ \varphi_{m}\,\left(\pi k\right)\,.$

Thus, for each segment $\bigl{[}\pi k\,,\,\pi(k+1)\bigr{]}$, the value of
$\varphi_{m}$ at the midpoint is less than at the ends. Denote by $h_{2k-1}$
the minimum of $\varphi_{m}$ on this segment and by $h_{2k}$ its maximum on
the segment
$\bigl{[}\,\pi\bigr{(}k+\frac{1}{2}\bigr{)}\,,\,\pi\,\bigl{(}k+\frac{3}{2}\bigr{)}\bigr{]}$.
Then $h_{2k}$ is the point of maximum of $\varphi_{m}$ on the segment
$[\pi,h_{2k+1})$. If $a$ is large enough, then the function $\varphi$
possesses the same property for a finite sequence
$\pi=h_{0}^{\prime}\,<\,h_{1}^{\prime}\,<\ldots<h_{2n}^{\prime}$. Moreover,
$n$ can be arbitrarily large, provided $a$ is big enough. Now it remains to
set $\tau_{j}=h_{j}^{\prime}$.

$\Box$

6\. Deciding stability and computing the Lyapunov exponent

We present an algorithm which for every system $S=\\{{\mathcal{A}},m,M\\}$
with a finite set ${\mathcal{A}}$ decides the stability with some
approximation rate. The algorithm decides between two cases: either
$\sigma(S)>-\delta$ or $\sigma(S)<\varepsilon$, where $\delta>0$ is a chosen
precision and $\varepsilon>0$ is an upper bound that depends on the parameters
of the algorithm and that can also be made arbitrarily small. Thus, the
algorithm solves the stability problem approximately with an arbitrary
precision. Then we can compute the Lyapunov exponent $\sigma(S)$ by the double
division.

To avoid technical difficulties, we assume that our system is irreducible
i.e., its matrices do not share a common nontrivial invariant subspace. This
assumption is made without loss of generality since the stability problem can
always be reduced to this case. Namely, every reducible system is split into
several systems of smaller dimension and its Lyapunov exponent is equal to the
maximal Lyapunov exponents of those systems, see [2, 12] for details.

6.1. The main idea and the structure of the algorithm

We exploit the idea of the invariant polytope algorithm from [18], when a
polyhedral Lyapunov norm is constructed iteratively. The theoretical base of
the algorithm is provided by three our results:

Theorem 1 – the existence of the Lyapunov norm for stable systems;

Theorem 3 – the improved Berger-Wang formula.

Proposition 12 – the estimate of the precision of discretization.

The algorithm finds the Lyapunov multinorm for the discretized system, when
the switches on the interval $[m,M]$ are allowed only at the points of the
uniform partition: $m+k\tau,k=0,\ldots,N$, where $\tau=\frac{M-m}{N}$. Thus,
after the operator $B_{j}$ we apply some power of the operator $e^{\,\tau
A_{j}}$ in the space $L_{j}$. Since the discretized system has a smaller set
of trajectories, it follows that its Lyapunov exponent gives a lowed bound for
$\sigma(S)$. On the other hand, Proposition 12 proved below in Section 9 gives
an inverse estimate: the distance between the Lyapunov exponents of these two
systems does not exceed $\frac{C}{N^{2}}$, where $C$ is an effective constant.

The stability of the discretized system is verified by its Lyapunov multinorm.
We construct a polyhedral multinorm which is defined in each space $L_{j}$ as
the Minkowski functional of a polytope $P_{j}$. The set of polytopes
$\\{P_{j}\\}_{j=1}^{n}$ is computed iteratively. At the first iteration we
take some index $i$ and a nonzero point ${\boldsymbol{x}}_{0}\in L_{i}$. The
further construction is by induction. If after the $k$th iteration we have
polytopes $P_{j}^{(k)}\in L_{j},\,j=1,\ldots,n$, then for each vertex
${\boldsymbol{v}}$ of $P_{j}^{(k)}$ and for each $s=1,\ldots,n$, we consider
$N$ points in the space $L_{s}$: $e^{r\tau
A_{s}}B_{s}\,{\boldsymbol{v}},\,r=0,\ldots,N$. Those points split the
trajectory of the ODE
$\dot{\boldsymbol{x}}(t)\,=\,A_{j}{\boldsymbol{x}}(t),\,t\in[m,M],\,{\boldsymbol{x}}(m)\,=\,B_{s}\,{\boldsymbol{v}}$
into $N$ arcs. If some of those points are inside the polytope $P_{j}^{(k)}$,
we call them dead and remove those points. All other points are alive and are
added to the set of vertices of $P_{j}^{(k)}$. Thus, the polytopes
$P_{j}^{(k)}$ grow with each iteration. Simultaneously we compute the spectral
radii of the matrix products $\Pi({\boldsymbol{v}})$ corresponding to each
alive vertex and get a lower bound for $\sigma(S)$. We consider only allowed
products, which belong to ${\mathcal{E}}_{0}$.

The algorithm halts when either the lower bound becomes positive (in which
case the system is unstable) or no alive vertices appear in a current
iteration. After this we get the bounds for $\sigma(S)$ which are provided by
Theorem 3 (the lower bound) and by Proposition 12 (the upper bound). The
distance between bounds can be made arbitrarily small. The algorithm always
halts, for every restricted system (Theorem 4).

6.2. The algorithm

Preliminary notation and remarks. For a given $N$, we set

$\tau\ =\ \frac{M-m}{N},\qquad{\mathcal{A}}_{\tau}\ =\ \Bigl{\\{}e^{s\tau
A_{j}}B_{j},\,s=0,\ldots,N;\ j=1,\ldots,n\Bigr{\\}}.$

If ${\mathcal{A}}_{\tau}$ is reducible for all $N$, then the family
$\bigl{\\{}e^{tA_{j}}B_{j},\ t\in[0,M-m]\bigr{\\}}$ is reducible, which is
impossible by Lemma 1. Hence, there exists $N$ such ${\mathcal{A}}_{\tau}$ is
irreducible. In the algorithm we use the notation for the symmetrized convex
hull ${\rm co}_{s}\,X\,=\,{\rm co}\,\bigl{\\{}X,-X\bigr{\\}}$; by $\Pi(a,b)$
we denote the solution of the matrix equation $\Pi^{\prime}=A(t)\Pi,\
\Pi(a)=I$ and call it product. Thus, $\Pi(0,T)\,=\,\Pi(T)$.

Algorithm 1.

We have an irreducible system $S=\\{{\mathcal{A}},m,M\\}$ with
${\mathcal{A}}=\\{A_{1},\ldots,A_{n}\\}$. For each $j$, we use notation
$L_{j}$ for the space ${\mathbb{R}}^{d}$ as the domain of the operator
$A_{j}$. Choose the precision $\delta>0$.

Initialization. We fix natural $N\geq 1$ and denote $\tau=\frac{M-m}{N}$.
Verify that ${\mathcal{A}}_{\tau}$ is irreducible. Choose arbitrary
$i\in\\{1,\ldots,n\\}$ and a starting point ${\boldsymbol{x}}(0)\in
L_{i}\setminus\\{0\\}$. Define two sets
${\mathcal{V}}_{i}^{(1)}={\mathcal{R}}_{i}^{(1)}\,=\,\\{{\boldsymbol{x}}(0)\\}$;
for all $j\neq i$, we set
${\mathcal{V}}_{j}^{(1)}={\mathcal{R}}_{j}^{(1)}\,=\,\emptyset$.

The main loop. $k$th iteration.

In each space $\,L_{j},\ 1,\ldots,n$, we have a finite set
${\mathcal{V}}_{j}^{(k)}\subset L_{j}$ and its subset
${\mathcal{R}}_{j}^{(k)}$. Define
${\mathcal{V}}_{j}^{(k+1)}\,=\,{\mathcal{V}}_{j}^{(k)},\
{\mathcal{R}}_{j}^{(k+1)}\,=\,\emptyset$.

For every $j=1,\ldots,n$, we take consequently all
$q\in\\{1,\ldots,n\\}\setminus\\{j\\}$.

For each $q$, we take consequently all points of the set
${\mathcal{R}}_{q}^{(k)}$.

For each point ${\boldsymbol{x}}\in{\mathcal{R}}_{q}^{(k)}$, we construct
$N+1$ points in the space $L_{j}$: ${\boldsymbol{x}}_{s}\,=\,e^{\,s\tau
A_{j}}B_{j}{\boldsymbol{x}},\ s=0,\ldots,N$. For each of them, we check
whether ${\boldsymbol{x}}_{s}$ belongs to the interior of the symmetrized
convex hull ${\rm co}_{s}\,{\mathcal{V}}_{j}^{(k+1)}$. This is done by the
auxiliary Problem 1 (problem (5)). If so, then ${\boldsymbol{x}}_{s}$ is dead
and we leave ${\mathcal{R}}_{j}^{(k+1)}$ and ${\mathcal{V}}_{j}^{(k+1)}$ as
they are. If not, then the point ${\boldsymbol{x}}_{s}$ survived and we add it
to both those sets ${\mathcal{R}}_{j}^{(k+1)}$ and
${\mathcal{V}}_{j}^{(k+1)}$. Then we consider the trajectory of the system
leading from the starting point ${\boldsymbol{x}}(0)$ to
${\boldsymbol{x}}_{s}$. Denote by $t$ the time of the point
${\boldsymbol{x}}_{s}$, i.e., ${\boldsymbol{x}}(t)\,=\,{\boldsymbol{x}}_{s}$.
Denote by $t_{1},\ldots,t_{\ell}$ the time moments of switches form the space
$L_{j}$ to other spaces (or, the same, from the matrix $A_{j}$ to other
matrices). Then we set $\mu$ to be equal to
$\max\,\bigl{\\{}\mu\,,\,\frac{1}{t-t_{i}}\sigma\bigl{(}\Pi(t_{i},t)\bigr{)},\
i=1,\ldots,\ell\bigr{\\}}$ (if there are no such switches, then we leave $\mu$
as it is).

If $s<N$, then we pass to the next point
${\boldsymbol{x}}\in{\mathcal{R}}_{q}^{(k)}$.

If all points of ${\mathcal{R}}_{q}^{(k)}$ are exhausted, then we pass from
$q$ to $q+1$, provided $q+1\neq j$ (otherwise we pass to $q+2$).

If all $q\in\\{1,\ldots,n\\}\setminus\\{j\\}$ are exhausted, then we pass from
$j$ to $j+1$.

If $j=n$, then the $k$th iteration is completed.

Termination. There are two possible cases:

Case 1. If $\mu>-\delta$ at some moment of the algorithm, then the algorithm
halts. We have $\sigma(S)\geq-\delta$.

Case 2. If ${\mathcal{R}}_{j}^{(k+1)}\,=\,\emptyset$ for all $j$, i.e., the
$k$th iteration does not produce any new point, then the algorithm halts.
Denote $P_{j}\,=\,{\rm co}_{s}\,{\mathcal{V}}_{j}^{(k)}$ and find the value

$\bigl{\|}A_{j}^{2}\bigr{\|}_{P_{j}}\quad=\quad\min\
\Bigl{\\{}\,\lambda>0\quad\Bigl{|}\quad A_{j}^{2}P_{j}\subset\lambda P_{j}\
\Bigr{\\}}\,,$

which is the operator norm of $A_{j}^{2}$ induced by the Minkowski norm of the
polytope $P_{j}$. Let
$\|{\mathcal{A}}^{2}\|_{P}\,=\,\max\limits_{j=1,\ldots,n}\bigl{\|}A_{j}^{2}\bigr{\|}_{P_{j}}$.
This value is computed by the auxiliary Problem 3 given below. Then
$\sigma(S)<\nu$, where

$\nu\ =\
-\,\frac{1}{m}\,\ln\,\left(1\,-\,\frac{(M-m)^{2}\|{\mathcal{A}}^{2}\|_{P}}{8N^{2}}\right)\,.$
(4)

End of the Algorithm 1

The auxiliary problems. Given a finite set
${\mathcal{V}}=\\{{\boldsymbol{x}}_{i}\\}_{i=1}^{\ell}$ and a point
${\boldsymbol{x}}_{0}$. Consider the polytope $P={\rm co}_{s}\,{\mathcal{V}}$.

1) Decide whether ${\boldsymbol{x}}_{0}\in{\rm int}\,P$;

Solution. Solve the linear programming (LP) problem:

$\left\\{\begin{array}[]{l}t_{0}\ \to\ \max\\\ t_{0}{\boldsymbol{x}}_{0}\ =\
\sum_{j=1}^{\ell}(t_{i}-s_{i}){\boldsymbol{x}}_{i}\\\ \sum_{j=1}^{\ell}t_{i}\
=\ \sum_{j=1}^{\ell}s_{i}\ =\ 1\\\ t_{i}\geq 0,\ s_{i}\geq 0,\qquad
i=1,\ldots,\ell\,.\end{array}\right.$ (5)

Then ${\boldsymbol{x}}_{0}\in{\rm int}\,P\ $ iff $\ t_{0}>1$.

2). Find $\|{\boldsymbol{x}}_{0}\|_{P}$.

Solution. ${\|{\boldsymbol{x}}_{0}\|_{P}\,=\,1/t_{0}}$, where $t_{0}$ is the
solution of the LP problem (5).

3). For a given $d\times d$ matrix $A$, find $\|A\|_{P}$.

Solution. For every $j=1,\ldots,\ell$, set
${\boldsymbol{x}}_{0}=A{\boldsymbol{x}}_{j}$, solve the LP problem (5) and
denote ${t_{0}=t_{0}^{(j)}}$. Then
$\|A\|_{P}\,=\,\max_{j=1}^{\ell}\|A{\boldsymbol{x}}_{j}\|_{P}\,=\,\max_{j=1}^{\ell}1/t_{0}^{(j)}$.

The main result of this section states that Algorithm 1 always terminates
within finite time.

###### Theorem 4

For every initial data, Algorithm 1 halts within finite time. If it halts in
Case 1, then $\sigma(S)>-\delta$. Otherwise, it halts in Case 2 and
$\sigma(S)<\nu$, where $\nu$ is defined in (4), and the multinorm
$\|\cdot\|_{P}$ is Lyapunov for the system ${\mathcal{A}}-\nu I$.

The proof is in Section 9.

###### Remark 3

The parameter $\delta$ can be chosen arbitrarily small, which could allow
Algorithm 1 to compute the Lyapunov exponent with an arbitrary precision.
However, there is also parameter $\nu$ which increases the distance between
upper and lower bounds. This is unavoidable in the framework of Algorithm 1
since it constructs the polyhedral Lyapunov norm for the discretized system.
The parameter $\nu$ is the precision of approximation by the discretization.
It is asymptotically equivalent to
$\frac{1}{8N^{2}}\,\frac{(M-m)^{2}\|{\mathcal{A}}\|_{P}}{m}$ as $N\to\infty$.
Increasing $N$ we improve the precision, but increase the number of vertices,
which slows down the algorithm.

Computing the Lyapunov exponent $\sigma(S)$. By Theorem 4, Algorithm 1 decides
within finite time between two cases: either $\sigma(S)>-\delta$ or
$\sigma(S)<\nu$. Therefore, introducing a parameter $\alpha$ and applying
Algorithm 1 to the system ${\mathcal{A}}-\alpha I$, one can realize the double
division in $\alpha$. The initial interval for $\alpha$ can be chosen, for
example, as $\,\bigl{[}\,\max_{j=1}^{n}\sigma(A_{j})\ ,\
\hat{\sigma}(S)\bigr{]}$, where $\hat{\sigma}({\mathcal{A}})$ is an arbitrary
upper bound for the unrestricted system with matrices ${\mathcal{A}}$, for
example, it can be the CQLF estimate [25] or polyhedral estimates [6, 17]. Let
$L$ be the length of the initial interval. Then after $k\geq 1$ iterations
Algorithm 1 localizes the value of $\sigma({\mathcal{A}})$ on an interval of
length $2^{-k}L+\delta+\nu$. The parameter $\delta$ is under our control and
can be chosen arbitrarily small. For the value $\nu$ defined in (4), we have
$\nu=O\bigl{(}\frac{1}{N^{2}}\bigr{)}$, so it can be made small by increasing
$N$. Thus, Algorithm 1 along with the double division and with the proper
choice of the parameters $\delta$ and $N$ computes the Lyapunov exponent with
a given precision.

Algorithm 1 for positive systems. If the restricted system
$S=\\{{\mathcal{A}},m,M\\}$ is positive, then Algorithm 1 can be modified,
which in practice gives much more efficiency. Let us recall that the system is
called positive if all the matrices from ${\mathcal{A}}$ are Metzler, i.e.,
all their off-diagonal elements are nonnegative. In this case all trajectories
of the system starting on the positive orthant ${\mathbb{R}}^{d}_{+}$ stays
inside it for all $t\in[0,+\infty)$. See, [14, 17] for more on positive
systems.

The modification is the following. For an arbitrary subset $K$ of the positive
orthant ${\mathbb{R}}^{d}_{+}$, we consider its positive convex hull ${\rm
co}_{p}\,K\,=\,\bigl{\\{}{\boldsymbol{x}}\geq
0,\,\exists\,{\boldsymbol{y}}\in{\rm co}\,K\ \mbox{s.t.}\
{\boldsymbol{y}}\geq{\boldsymbol{x}}\bigr{\\}}$, where the vector inequality
${\boldsymbol{y}}\geq{\boldsymbol{x}}$ is coordinatewise. If $K$ is a finite
set, then ${\rm co}_{p}\,K\,$ is a positive polytope. In Algorithm 1 we
replace the polytopes $P_{j}={\rm co}_{s}\,{\mathcal{V}}$ by the positive
polytopes $P_{j}={\rm co}_{p}\,{\mathcal{V}}$. In Algorithm 1 we everywhere
replace the symmetrized convex hill by the positive convex hull, respectively,
the LP problem 5 is replaced by

$\left\\{\begin{array}[]{l}t_{0}\ \to\ \max\\\ t_{0}{\boldsymbol{x}}_{0}\ =\
\,{\boldsymbol{y}}\,+\,\sum_{j=1}^{\ell}t_{i}{\boldsymbol{x}}_{i},\\\
\sum_{j=1}^{\ell}t_{i}\ =\ 1,\\\ {\boldsymbol{y}}\ \leq\ 0,\\\ t_{i}\geq 0,\
\qquad i=1,\ldots,\ell\,.\end{array}\right.$ (6)

As a rule, this version of Algorithm 1 leaves much less alive vertices of
polytopes $P_{j}^{(k)}$ (in this case, positive polytopes) and converges much
faster, even in high dimensions.

If Algorithm 1 does not terminate within reasonable time, it can be
interrupted, in which case we have the following output:

Complement to Algorithm 1. Choose $K$ as the maximal number of iterations. If
Algorithm 1 does not halt by the $K$th iteration, then we interrupt it and
make one more iteration. For every survived point ${\boldsymbol{x}}_{s}$
generated in this iteration (i.e., ${\boldsymbol{x}}_{s}\in
L_{i},\,{\boldsymbol{x}}_{s}\notin{\rm int}\,P^{(K)}_{i}$). Then we denote by
$\gamma$ the biggest one of those numbers and obtain

$\mu\ \leq\ \sigma(S)\ \leq\
-\,\frac{1}{m}\,\ln\,\left(1\,-\,\frac{(M-m)^{2}\gamma\|{\mathcal{A}}^{2}\|_{P}}{8N^{2}}\right)\,.$
(7)

7\. Numerical results

We consider two low-dimensional examples of computing the Lyapunov exponent by
Algorithm 1. Then we present statistics of numerical experiments for higher
dimensions for general restricted systems and for positive systems.

7.1. Examples

###### Example 4

For the system with ${\mathcal{A}}=\\{A_{1},A_{2}\\},\ m=1,M=2$, where

$A_{1}=\left(\begin{array}[]{cc}-0.3&0.5\\\
0.2&-0.4\end{array}\right),\,A_{2}=\left(\begin{array}[]{cc}-0.6&0\\\
0&1\end{array}\right),\qquad m=1,M=2.$

Algorithm 1 gives the following results:

Table 1: $2\times 2$ matrices , $m=1,M=2$. $\text{len}P_{1}$ | $\text{len}P_{2}$ | $N$ | # iterations | $\sigma$ | time
---|---|---|---|---|---
$28$ | $34$ | $10$ | $16$ | $(0.15560,0.15685)$ | $11.9$

Here $\text{len}P_{i}$ denotes the half of the number of verices of the
polytope $P_{i}$ that generates the Lyapunov norm $f_{i},\,i=1,2$; $N$ is the
number of points of discretization (so, the discretization step is
$\tau=\frac{M-m}{N}=0.1$); the column “$\sigma$” shows the interval for
$\sigma(S)$; “time” shows the time (sec) of running Algorithm 1 in a standard
laptop.

We see that in this example Algorithm 1 gives the estimates
$0.15560<\sigma(S)<0.15685$, the relative error is less than $1.3\cdot
10^{-3}$.

###### Example 5

For the system with ${\mathcal{A}}=\\{A_{1},A_{2}\\},\ m=1,M=2.5$, where

$A_{1}=\left(\begin{array}[]{cc}-0.3&0.5\\\
0.2&-0.4\end{array}\right),\,A_{2}=\left(\begin{array}[]{cc}-0.6&0\\\
0&1\end{array}\right),\qquad m=1,M=2.5.$

Algorithm 1 gives the following results:

Table 2: matrices $2\times 2$, $m=1,M=2.5$. $\text{len}P_{1}$ | $\text{len}P_{2}$ | $N$ | # iterations | $\sigma$ | time
---|---|---|---|---|---
$10$ | $8$ | $10$ | $10$ | $(0.61507,0.62433)$ | $5.4$

The interval for $\sigma$ is $(0.61507,0.62433)$, the relative error is less
than $0.01$.

7.2. Results of numerical experiments

Table 3 shows the results of Algorithm 1 applied to systems with two $d\times
d$ matrices with $[m,M]=[1,2]$. The notation are the same as in Example 4, $d$
is the dimension.

Table 3: $d\times d$ matrices $m=1,M=2$. dim | $\text{len}P_{1}$ | $\text{len}P_{2}$ | $N$ | # iterations | $\sigma$ | time
---|---|---|---|---|---|---
$3$ | $16$ | $10$ | $10$ | $18$ | $(1.15482,1.16474)$ | $26.5$
$4$ | $44$ | $46$ | $10$ | $22$ | $(2.52396,2.98327)$ | $128.1$
$5$ | $138$ | $106$ | $10$ | $12$ | $(3.00530,4.03136)$ | $96.9$

Table 4 shows the results of Algorithm 1 applied to systems with two $d\times
d$ matrices with $[m,M]=[1,2.5]$.

Table 4: $d\times d$ matrices, $m=1,M=2.5$. dim | $\text{len}P_{1}$ | $\text{len}X_{P}$ | $N$ | # iterations | $\sigma$ | time
---|---|---|---|---|---|---
$3$ | $10$ | $12$ | $10$ | $12$ | $(1.23099,1.25315)$ | $11.2$
$4$ | $60$ | $62$ | $15$ | $16$ | $(2.57561,3.06883)$ | $126.1$
$5$ | $144$ | $140$ | $15$ | $8$ | $(3.15519,4.10713)$ | $188.9$

Tables 5 and 6 show the results for positive systems. We see that in this case
we have quite sharp computations even for relatively hight dimensions, up to
$35$.

Table 5: nonnegative matrices, $m=1,M=2$. dim | $\text{len}P_{1}$ | $\text{len}P_{2}$ | $N$ | # iterations | $\sigma$ | time
---|---|---|---|---|---|---
$3$ | $1$ | $2$ | $10$ | $6$ | $9.02606$ | $46.5$
$5$ | $1$ | $2$ | $10$ | $6$ | $13.62821$ | $35.3$
$10$ | $1$ | $1$ | $10$ | $4$ | $(24.70551,24.70731)$ | $5.3$
$20$ | $1$ | $1$ | $10$ | $4$ | $(50.07293,50.07355)$ | $4.5$
$35$ | $1$ | $1$ | $10$ | $4$ | $(87.07711,87.0775)$ | $7.8$
Table 6: nonnegative matrices, $m=1,M=2.5$. dim | $\text{len}P_{1}$ | $\text{len}P_{2}$ | $N$ | # iterations | $\sigma$ | time
---|---|---|---|---|---|---
$3$ | $1$ | $2$ | $10$ | $6$ | $9.17010$ | $29.1$
$5$ | $1$ | $2$ | $10$ | $6$ | $13.66565$ | $8.8$
$10$ | $1$ | $1$ | $10$ | $4$ | $(24.87671,24.87968)$ | $5.3$
$20$ | $1$ | $1$ | $10$ | $4$ | $(50.12228,50.12387$ | $4.0$
$35$ | $1$ | $1$ | $10$ | $4$ | $(87.11728,87.11831)$ | $5.3$

8\. When can the upper bound be cancelled?

In this section we deal with the general case of mode-dependent segments
$[m_{j},M_{j}]$. Algorithm 1 may suffer when the maximal switching time
$M_{j}$ is big. Indeed, by Theorem 4, the upper bound for the Lyapunov
exponent given by (4) requires a large number $N$ of discretization segments
to get a satisfactory precision. This significantly increases the number of
vertices of the polytopes and, therefore, the running time. The question
arises whether the upper bound $M_{j}$ can be reduced without changing the
stability/instability of the system? Reducing some of those bounds simplifies
the implementation of Algorithm 1.

On the other hand, in case $M_{j}=+\infty$, when there is no upper bound for
the switching time of $A_{j}$, the stability can be decided by many methods
known from the literature [10]. So, the opposite problem is when the upper
bound can be cancelled without influencing the stability?

Problem 1. For a given $j$, under what conditions the upper time limit $M_{j}$
can be reduced (and to which point) without changing the stability/instability
of the system?

Problem 2. For which $M_{j}$ the stability of the system does not change after
replacing $M_{j}\,$ by $\,+\infty$ ?

We attack these problem by considering first a system
$\dot{\boldsymbol{x}}\,=\,A{\boldsymbol{x}},{\boldsymbol{x}}(0)={\boldsymbol{x}}_{0}$
with a constant matrix $A$, without switches. This system is stable when $A$
is stable, or a Hurwitz matrix, i.e., when $\sigma(A)<0$.

In what follows we assume that ${\boldsymbol{x}}_{0}$ is a generic point,
i.e., it does not belong to any proper invariant subspace of $A$. For an
arbitrary segment $[t_{1},t_{2}]\subset{\mathbb{R}}_{+}$, we denote
$\Gamma(t_{1},t_{2})\,=\,\bigl{\\{}{\boldsymbol{x}}(t)\ |\
t\in[t_{1},t_{2}]\bigr{\\}}$ and $G(t_{1},t_{2})\,=\,{\rm
co}_{s}\,\Gamma(t_{1},t_{2})$. We also denote by $\Gamma=\Gamma(0,+\infty)$
the entire trajectory and, respectively, $G=G(0,+\infty)$. It is seen easily
that $G(t_{1}+h,t_{2}+h)\,=\,e^{hA}\,G(t_{1},t_{2})$.

###### Definition 6

A point $T>0$ is called a cut tail point for the stable system
$\dot{\boldsymbol{x}}\,=\,A{\boldsymbol{x}},\
{\boldsymbol{x}}(0)={\boldsymbol{x}}_{0}$, if for every $t>T$, the point
${\boldsymbol{x}}(t)$ belongs to the interior of the set $G(0,T)$.

###### Proposition 9

For every stable system $\dot{\boldsymbol{x}}\,=\,A{\boldsymbol{x}},\
{\boldsymbol{x}}(0)={\boldsymbol{x}}_{0}$, the set of cut tail points is
nonempty.

Proof. Since the point ${\boldsymbol{x}}_{0}$ is generic, it follows that
every arc of the trajectory is not contained in a hyperplane, therefore, for
each segment $[t_{1},t_{2}]$, the set $G(t_{1},t_{2})$ is full-dimensional and
hence, it contains a ball centered at the origin. On the other hand, the
trajectory converges to zero as $t\to\infty$, hence, say, $G(0,1)$ contains
${\boldsymbol{x}}(t)$ for all $t$ bigger than some $T>1$. Since $G(0,1)\subset
G(0,T)$, we see that $T$ is a cut tail point. $\Box$

The set of cut tail points is obviously closed, hence, there exists the
minimal point, which will be denoted by $T_{cut}$. Clearly,
${\boldsymbol{x}}(T_{cut})$ is on the boundary of $G$. If two trajectories
start at generic points ${\boldsymbol{x}}_{0},{\boldsymbol{x}}_{0}^{\prime}$,
then they are affinely similar. Hence cut tail points do not depend on
${\boldsymbol{x}}_{0}$ and are functions of the matrix $A$. Thus, speaking
about the cut tail points we may not specify ${\boldsymbol{x}}_{0}$.

###### Proposition 10

Suppose $A$ is a stable matrix; then the arc $\Gamma(0,T_{cut})$ lies on the
boundary of $G$.

Proof. If, on the contrary, there exists $t<T_{cut}$ such that
${\boldsymbol{x}}(t)\in{\rm int}\,G$, then, since the “tail”
$\\{{\boldsymbol{x}}(s)\ |\ s>T_{cut}\\}$ of the trajectory $\Gamma$ lies in
the interior of $G$, it follows that ${\boldsymbol{x}}(t)\in{\rm
int}\,G(0,T_{cut})$. Hence,

${\boldsymbol{x}}(T_{cut})\ =\,e^{(T_{cut}-t)A}\,{\boldsymbol{x}}(t)\ \in\
{\rm int}\,e^{(T_{cut}-t)A}\,G(0,T_{cut})\ =\ {\rm
int}\,G\,(T_{cut}-t\,,\,2T_{cut}-t)\ \subset\ {\rm int}\,G.$

Thus, ${\boldsymbol{x}}(T_{cut})\in{\rm int}\,G$, which is a contradiction.

$\Box$

We see that the point ${\boldsymbol{x}}(T_{cut})$ separates the part of
trajectory that lies on the boundary form that in the interior:
${\boldsymbol{x}}(t)\in\partial G$, for all $t\leq T_{cut}$, and
${\boldsymbol{x}}(t)\in{\rm int}\,G$, for all $t>T_{cut}$.

###### Corollary 4

The set of cut tail points is precisely the half-line $[T_{cut},+\infty)$.

Now turn back to the switching systems. Consider a stable system
$S=\\{{\mathcal{A}},{\boldsymbol{m}},{\mathcal{M}}\\}$. Let us omit the upper
limit $M_{j}$ for some of the matrices $A_{j}$, i.e., we allow the switching
time for those matrices to run over $[m_{j},+\infty)$. The new system has a
bigger set of of trajectories, so its Lypunov exponent is at least not
smaller. In particular, the Lypunov exponent can become positive, in which
case the system loses stability. We are going to show that if $T=M_{j}-m_{j}$
is a cut tail point for the matrix $A_{j}$, then the system stays stable and,
moreover, have the same Lyapunov multifunction.

###### Theorem 5

Let $S=\\{{\mathcal{A}},{\boldsymbol{m}},{\mathcal{M}}\\}$ be a restricted
system with all the matrices $A_{j}$ being stable. Let $J$ be an arbitrary
subset of the index set of ${\mathcal{A}}$. If for each $j\in J$, we have
$T_{cut}(A_{j})\leq M_{j}-m_{j}$, then replacing each $M_{j}$ either by
$+\infty$ or by $m_{j}+T_{cut}(A_{j})$ changes neither the stability of $S$
nor the Lyapunov multinorms.

Thus, if the number $M_{j}-m_{j}$ is a cut tail point for some of the matrices
$A_{j}$, then one either omit this upper bound or reduce it to
$m_{j}+T_{cut}(A_{j})$ without changing the stability/instability.

###### Corollary 5

If for a stable system $S=\\{{\mathcal{A}},m,M\\}$ with stable matrices, we
have $M-m\,\geq\,\max_{j=1,\ldots,n}T_{cut}(A_{j})$, then the system
$\\{{\mathcal{A}},m,+\infty\\}$ is also stable and have the same Lyapunov
multinorms.

Proof of Theorem 5. If $S$ is stable, then it possesses a Lyapunov multinorm
$f$. Then for each $i\in J$ and for every $k\neq j$ and for every
${\boldsymbol{x}}\in{\mathcal{S}}_{k}$, the curve
$\gamma\,=\,\bigl{\\{}e^{tA_{i}}\,B_{i}\,{\boldsymbol{x}}\,,\
t\in[0,M_{i}-m_{i}]\,\bigr{\\}}$, is strictly inside the ball
${\mathcal{B}}_{i}$ (Proposition 4). If $M_{j}-m_{j}\,\geq\,T_{cut}(A_{i})$,
then $M_{i}-m_{i}$ is a cut tail point for $A_{i}$. Therefore, the entire
curve $e^{tA_{i}}\,B_{i}\,{\boldsymbol{x}}\,,\ t\in[0,+\infty)$ is contained
in ${\rm co}_{s}\,\Gamma$ and hence, it lies inside ${\mathcal{B}}_{i}$. Thus,
if $i\in J$, then $f$ is a Lyapunov multinorm for the system with the omitted
upper restriction for $A_{i}$. Similarly we show that if after the reduction
of $M_{i}$ to $T_{cut}(A_{i})$, the system is stable, then the original system
is stable as well.

$\Box$

Now the problem becomes how to decide if a given $T$ is a cut tail point for a
given stable matrix $A$ and how to find $T_{cut}(A)$? Let us denote by
${\mathcal{P}}_{A}$ the linear span of the functions
$f_{{\boldsymbol{x}}}(t)=e^{tA}{\boldsymbol{x}},\
{\boldsymbol{x}}\in{\mathbb{R}}^{d}$. This is the space of quasipolynomials
which are linear combinations of functions $t^{k}e^{\,\alpha t}\sin\beta t$
and $t^{k}e^{\,\alpha t}\,\cos\beta t\,$, where $\alpha+i\beta$ is an
eigenvalue of $A$ and $k=1,\ldots,r-1$, where $r$ is the size of the largest
Jordan bock of $A$ corresponding to that eigenvalue. The dimension of
${\mathcal{P}}_{A}$ is equal to the degree of the minimal annihilating
polynomial of the matrix $A$.

###### Theorem 6

Let $A$ be a stable matrix; then a number $T>0$ is a cut tail point if and
only if the value of the convex extremal problem

$\left\\{\begin{array}[]{l}p(T)\to\max\\\
\|{\boldsymbol{p}}\|_{C({\mathbb{R}}_{+})}\ \leq\ 1\\\
p\in{\mathcal{P}}_{A}\end{array}\right.$ (8)

is smaller than $1$.

Proof. By Proposition 10, the inequality $T>T_{cut}$ is equivalent to that
${\boldsymbol{x}}(T)\in{\rm int}\,G$. This means that the point
${\boldsymbol{x}}(T)$ cannot be separated from $G$ by a linear functional,
i.e., for every nonzero vector ${\boldsymbol{p}}\in{\mathbb{R}}^{d}$, we have
$\bigl{(}{\boldsymbol{p}},{\boldsymbol{x}}(T)\bigr{)}\,<\,\sup\limits_{{\boldsymbol{y}}\in
G}\,({\boldsymbol{p}},{\boldsymbol{y}})$. Since $G$ is a convex hull of points
$\,\pm\,{\boldsymbol{x}}(t)\,,\,t\geq 0$, it follows that
$\sup\limits_{{\boldsymbol{y}}\in
G}\,({\boldsymbol{p}},{\boldsymbol{y}})\,=\,\sup\limits_{t\geq
0}\,\bigl{|}({\boldsymbol{p}},{\boldsymbol{x}}(t))\bigr{|}$. Thus,

$\bigl{(}{\boldsymbol{p}},{\boldsymbol{x}}(T)\bigr{)}\ <\
\sup\limits_{t\in{\mathbb{R}}_{+}}\bigl{|}({\boldsymbol{p}},{\boldsymbol{x}}(t))\bigr{|}.$

On the other hand, $({\boldsymbol{p}},{\boldsymbol{x}}(t))=p(t)$, where
$p\in{\mathcal{P}}_{A}$ is the quasipolynomial with the vector of coefficients
${\boldsymbol{p}}$. We obtain $p(T)<\|p\|_{C({\mathbb{R}}_{+})}$.
Consequently, $p(T)<1$ for every quasipolynomial from the unit ball
$\|p\|_{C({\mathbb{R}}^{+})}\leq 1$. Now by the compactness argument we
conclude that the value of the problem (8) is smaller than one.

$\Box$

The problem (8) is a convex problem on ${\mathbb{R}}^{d}$ and can be solved by
the convex optimisation methods. For $2\times 2$ matrices, the parameter
$T_{cut}$ can be evaluated in the explicit form.

The two-dimensional systems.

Case 1. The eigenvalues of $A$ are real. For the sake of simplicity we assume
they are different, denote them by $\alpha_{1},\alpha_{2}$. The trajectory
$\Gamma=\\{{\boldsymbol{x}}(t)\,|\,t\geq 0\\}$ in the basis of eigenvectors of
$A$ has the equation
$(x_{1}(t),x_{2}(t))\,=\,\bigl{(}e^{\alpha_{1}t}\,,\,e^{\alpha_{2}t}\bigr{)}\,,\
t\in{\mathbb{R}}_{+}$. Since $A$ is stable, both $\alpha_{1},\alpha_{2}$ are
negative and ${\boldsymbol{x}}(0)=(1,1),\,{\boldsymbol{x}}(+\infty)=(0,0)$.
Let ${\boldsymbol{a}}\in\Gamma$ be the point where the tangent line drawn from
the point $(-1,-1)$ touches $\Gamma$. Then $G\,=\,{\rm co}_{s}\,\Gamma$ is
bounded by the line segment from $(-1,-1)$ to ${\boldsymbol{a}}$ and by the
arc of $\Gamma$ from ${\boldsymbol{a}}$ to $(1,1)$, then reflected about the
origin. Hence, if ${\boldsymbol{a}}={\boldsymbol{x}}(T)$, then
${\boldsymbol{x}}(t)\in{\rm int}\,G$ for all $t>T$, and so $T=T_{cut}$. We
have $\,{\boldsymbol{a}}\,+\,s\,\dot{\boldsymbol{x}}(T_{cut})\,=\,(-1,-1)$,
where $s>0$ is some number. Writing this equality coordinatewise, we obtain
the equation for $t=T_{cut}$:

$\left\\{\begin{array}[]{lcl}e^{\alpha_{1}t}\ +\
s\,\alpha_{1}\,e^{\alpha_{1}t}&=&-1\\\ e^{\alpha_{2}t}\ +\
s\,\alpha_{2}\,e^{\alpha_{2}t}&=&-1\end{array}\right.$

which becomes after simplification
$\frac{1+e^{-\alpha_{1}t}}{\alpha_{1}}\,=\,\frac{1+e^{-\alpha_{2}t}}{\alpha_{2}}$.
The unique solution is $T_{cut}$.

If the eigenvalues of $A$ are non-real, they are complex conjugate $\alpha\pm
i\beta$ with $\alpha<0$. The trajectory $\Gamma$ in a suitable basis has the
equation $(x_{1}(t),x_{2}(t))\,=\,e^{\alpha t}\,(\cos\beta t\,,\,\sin\beta
t)\,,\ t\in{\mathbb{R}}_{+}$. The trajectory $\Gamma$ goes from the point
${\boldsymbol{x}}(0)=(1,0)$ to zero making infinitely many rotations. Taking
the point of tangency ${\boldsymbol{a}}$ of $\Gamma$ with the line going from
the point $(-1,0)$ and arguing as above we obtain

$\left\\{\begin{array}[]{lcr}e^{\alpha t}\cos\beta t\ +\ s\,e^{\alpha
t}\bigl{(}\alpha\cos\beta t\,-\,\beta\sin\beta t\bigr{)}&=&-1\\\ e^{\alpha
t}\sin\beta t\ +\ s\,e^{\alpha t}\bigl{(}\alpha\sin\beta t\,+\,\beta\cos\beta
t\bigr{)}&=&0\end{array}\right.$

from which it follows $\alpha\sin\beta t\,+\,\beta\cos\beta
t\,+\,\beta\,e^{\alpha t}\,=\,0$. The unique solution of this equation is
$t=T_{cut}$.

9\. Proofs of the fundamental theorems

In this section we give proofs of Theorems 1, 2, 3, and 4.

9.1 Preliminary results. Discrete systems on graphs

We begin with proof of Theorem 2 on the existence of invariant multinorm for
irreducible systems. Then we prove Theorems 1 and 1. The proof of Theorem 4 is
the most difficult, we give it is a separate subsection 9.3.

The proof of Theorem 2 uses some results from the discrete dynamical systems
on graphs. The theory of such systems was developed recently in [12, 22, 31].
We begin with basic definitions.

We have a directed multigraph $G$ with $m$ vertices $g_{1},\ldots,g_{n}$.
Sometimes, the vertices will be denoted by their numbers. To each vertex $i$
we associate a linear space $L_{i}$ of dimension $d_{i}\geq 1$. If the
converse is not stated, we assume $d_{i}\geq 1$. The set of spaces
$L_{1},\ldots,L_{n}$ is denoted by ${\mathcal{L}}$. For each vertices $i,j\in
G$ (possibly coinciding), there is a set $\ell_{ji}$ of edges from $i$ to $j$.
Each edge from $\ell_{ji}$ is identified with a linear operator
$A_{ji}:\,L_{i}\to L_{j}$. The family of those operators (or edges) is denoted
by ${\mathcal{A}}_{ji}$. If $\ell_{ji}=\emptyset$, then
${\mathcal{A}}_{ji}=\emptyset$. Thus, we have a family of spaces
${\mathcal{L}}$ and a family of operators/edges
${\mathcal{A}}=\cup_{i,j}{\mathcal{A}}_{ji}$ that act between these spaces
according to the multigraph $G$. This triplet
$\,\xi=(G,{\mathcal{L}},{\mathcal{A}})$ of the multigraph, spaces, and
operators will be referred to as a system on graph. A path $\alpha$ on the
multigraph $G$ is a sequence of connected subsequent edges, its length (number
of edges) is denoted by $|\alpha|$. The length of the empty path is zero. To
every path $\alpha$ along vertices $i_{1}\rightarrow
i_{2}\rightarrow\cdots\rightarrow i_{k+1}$ that consists of edges (operators)
$A_{i_{s+1}i_{s}}\in{\mathcal{A}}_{i_{s+1}i_{s}},\,s=1,\ldots,k$, we associate
the corresponding product (composition) of operators
$\Pi_{\alpha}=A_{i_{k+1}i_{k}}\cdots A_{i_{2}i_{1}}$. Note that $|\alpha|=k$.
Let us emphasize that a path is not a sequence of vertices but edges. If $G$
is a graph, then any path is uniquely defined by the sequence of its vertices,
if $G$ is a multigraph, then there may be many paths corresponding to the same
sequence of vertices. If the path is closed ($i_{1}=i_{k+1}$), then
$\Pi_{\alpha}$ maps the space $L_{i_{1}}$ to itself. In this case
$\Pi_{\alpha}$ is given by a square matrix, and possess eigenvalues,
eigenvectors and the spectral radius $\rho(\Pi_{\alpha})$, which is the
maximal modulus of its eigenvalues. The set of all closed paths will be
denoted by ${\mathcal{C}}(G)$. For an arbitrary $\alpha\in{\mathcal{C}}(G)$ we
denote by $\alpha^{k}=\alpha\ldots\alpha$ the $k$th power of $\alpha$. A
closed path is called simple if it is not a power of a shorter path.

A multinorm on a multigraph is introduced in the same way as in Definition 2.

For a given ${\boldsymbol{x}}_{0}\in L_{i}$ and for an infinite path $\alpha$
starting at the vertex $i$, we consider the trajectory
$\\{{\boldsymbol{x}}_{k}\\}_{k\geq 0}$ of the system along this path. Here
$x_{k}=\Pi_{\,\alpha_{k}}\,{\boldsymbol{x}}_{0}$, where $\alpha_{k}$ is a
prefix of $\alpha$ of length $k$. The concepts of stability and of Lyapunov
exponent are defined in a standard way. The invariant norm is also defined
similarly. For the sake of simplicity we will reduce the definition to the
case $\sigma(\xi)=0$.

###### Definition 7

Let us have a discrete system on graph $\xi$ with $\sigma=0$. A multinorm
$\|\cdots\|$ is invariant for $\xi$ if for every $i$ and ${\boldsymbol{x}}\in
L_{i}$, we have

$\max_{A_{ji}\in{\mathcal{A}}_{ji},\,j=1,\ldots,n}\,\|A_{ji}{\boldsymbol{x}}\|_{j}\
=\,\|x\|_{i}\,.$ (9)

Similarly to Theorem 2, the existence of the invariant norm holds under the
irreducibility assumption. However, the definition of irreducible systems on
graphs is more complicated, it requires not one invariant subspace but a
collection of subspaces. A triplet
$\xi^{\prime}=(G,{\mathcal{L}}^{\prime},{\mathcal{A}}^{\prime})$ is embedded
in $\xi$, if $L_{i}^{\prime}\subset L_{i}$ for each $i$ and every operator
$A_{ji}^{\prime}=A_{ji}|_{L_{i}^{\prime}}$ maps $L_{i}^{\prime}$ to
$L_{j}^{\prime}$, whenever $l_{ji}\in G$. The embedding is strict if
$L_{i}^{\prime}$ is a proper subspace of $L_{i}$ for at least one $i$. Thus,
an embedded triplet has the same multigraph and smaller spaces at the
vertices. A triplet $\xi=(G,{\mathcal{L}},{\mathcal{A}})$ is reducible if it
has a strictly embedded triplet. Otherwise, it is called irreducible.

Theorem A [12]. An irreducible discrete system on graph with $\sigma=0$
possesses an invariant multinorm.

9.2 Proofs of Theorems 1, 2, and 3

We begin with the following auxiliary fact, whose proof is placed in Appendix:

###### Lemma 1

Let $A_{j},B_{j}$ be linear operators in ${\mathbb{R}}^{d}$ and all $B_{j}$ be
invertible, $j=1,\ldots,n$. Suppose, for some segment $[\alpha,\beta]$, all
operators from the set $\bigl{\\{}\,e^{tA_{j}}B_{j},\ t\in[\alpha,\beta],\
j=1,\ldots,n\bigr{\\}}$ share a proper common invariant subspace; then all
$A_{j}$ and $B_{j}$ share the same subspace.

Proof of Theorem 2. We consider the multigraph with vertices $g_{i}$
associated to spaces $L_{i}$. The set of edges/operators from $L_{i}$ to
$L_{j}$ is ${\mathcal{A}}_{ji}\,=\,\bigl{\\{}e^{tA_{j}}B_{j},\
t\in[0,M-m]\bigr{\\}}$. Clearly this is a compact set. If ${\mathcal{A}}$ is
irreducible, then by Lemma 1, the set $\bigl{\\{}\,e^{tA_{j}}B_{j},\
t\in[0,M-m],\ j=1,\ldots,n\bigr{\\}}$ is also irreducible. This means that the
discrete system on graph $\xi$ is irreducible. Hence, we can invoke Theorem A
and obtain an invariant multinorm $f$ for $\xi$. By the definition of
invariant multinorm, for every point ${\boldsymbol{x}}$ from the unit sphere
${\mathcal{S}}_{i}$, all the points
$A_{ji}{\boldsymbol{x}},\,A_{ji}\in{\mathcal{A}}_{ji}$ are inside the unit
ball ${\mathcal{B}}_{j}$ and at least one of them is on the sphere
${\mathcal{S}}_{i}$. Therefore, for every point
${\boldsymbol{x}}\in{\mathcal{S}}_{i}$, all the points
$B_{j}e^{tA_{j}}{\boldsymbol{x}}$ are inside ${\mathcal{B}}_{j}$ and at least
one of them is on ${\mathcal{S}}_{i}$. Thus, $f$ is an invariant multinorm for
the system ${\mathcal{A}}$, which completes the proof.

$\Box$

Proof of Theorem 1. If the system is stable, then $\sigma<0$. Take arbitrary
$\alpha\in(\sigma,0)$ and an arbitrary multinorm
$\|\cdot\|\,=\,\bigl{(}\|\cdot\|_{1}\,,\cdots,\,\|\cdot\|_{n}\bigr{)}$ on
$(L_{1},\ldots,L_{n})$. For every ${\boldsymbol{x}}\in L_{i}$, we set
$f({\boldsymbol{x}})\,=\,\sup\limits_{{\boldsymbol{y}}(\cdot),t\geq
0}e^{-\alpha t}\|{\boldsymbol{y}}(t)\|$, where the supremum is computed over
all trajectories ${\boldsymbol{y}}$ such that
${\boldsymbol{y}}(0)={\boldsymbol{x}}$. Since $\alpha>\sigma$, it follows that
the supremum is finite and so $f({\boldsymbol{x}})<\infty$. Obviously
$f({\boldsymbol{x}})>0$ and $f$ is positively homogeneous. Finally,
${\boldsymbol{y}}(t)\,=\,\Pi(t){\boldsymbol{x}}$, where
$\Pi(t)\in{\mathcal{E}}$ is the matrix product corresponding to the switching
law of the trajectory ${\boldsymbol{y}}(\cdot)$. Hence, $f({\boldsymbol{x}})$
is the supremum of functions $e^{-\alpha t}\|\Pi(t){\boldsymbol{x}}\|$ over
all proper matrices $\Pi(t)$ and over all positive $t$. Consequently, $f$ is
convex as a supremum of convex functions. Thus, $f$ is a norm which possesses
the property: for every trajectory ${\boldsymbol{y}}(t)$ starting at
${\boldsymbol{x}}$, we have $f\bigl{(}{\boldsymbol{y}}(t)\bigr{)}\leq
e^{\alpha t}f\bigl{(}{\boldsymbol{x}}\bigr{)}$. Now consider an arbitrary
trajectory ${\boldsymbol{y}}(t)$ with switching points
$\\{t_{k}\\}_{k\in{\mathbb{N}}}$. Taking
${\boldsymbol{x}}={\boldsymbol{y}}(t_{k})$ and $t=t_{k+1}$ we get
$f\bigl{(}{\boldsymbol{y}}(t_{k+1})\bigr{)}\leq e^{\alpha
t_{k+1}}f\bigl{(}{\boldsymbol{y}}(t_{k})\bigr{)}\,<\,f\bigl{(}{\boldsymbol{y}}(t_{k})\bigr{)}$,
which proves that $f$ is a Luapunov norm.

$\Box$

Proof of Theorem 3. After a suitable shift it can be assumed that
$\sigma(S)=0$. If ${\mathcal{A}}$ is irreducible, then Theorem 2 provides an
invariant norm $f$. Hence, there are infinite trajectories for which
$f\bigl{(}{\boldsymbol{x}}(t_{k})\bigr{)}=1$ for all switching points
$t_{k}\,,k\in{\mathbb{N}}$. Infinitely many points ${\boldsymbol{x}}(t_{k})$
belong to one space $L_{i}$ and, due to compactness of the unit sphere, there
is a convergent subsequence ${\boldsymbol{x}}(t_{k_{s}})$ as $s\to\infty$.
Take arbitrary positive $\varepsilon<1$. For every $\delta>0$, there exists
$N=N(\delta)$ such that
$f\,\bigl{(}{\boldsymbol{x}}(t_{k_{s+1}})-{\boldsymbol{x}}(t_{k_{s}})\bigr{)}<\delta$,
whenever $s>N$. On the other hand, those points belong to one trajectory,
hence ${\boldsymbol{x}}(t_{k_{s+1}})=\Pi\,{\boldsymbol{x}}(t_{k_{s}})$ for
some product $\Pi=\Pi(t_{k_{s+1}}-t_{k_{s}})\,\in\,{\mathcal{E}}_{0}$. Thus,
$f\bigl{(}\,(\Pi-I){\boldsymbol{x}}(t_{k_{s}})\bigr{)}<\delta$ and therefore
$\,\bigl{|}\rho(\Pi)-1\bigr{|}\,\leq\,\frac{\varepsilon}{2}$ whenever $\delta$
is small enough. Since
$\,\ln\alpha\,\geq\,(\alpha-1)\,-\,\frac{1}{2}|\alpha-1|^{2}$ for all positive
$\alpha$, we have
$\sigma(\Pi)\,=\,\ln\rho(\Pi)\,\geq\,-\frac{\varepsilon}{2}\,-\,\frac{\varepsilon^{2}}{8}\,>\,-\varepsilon$,
which completes the proof in the irreducible case.

If the system is reducible, then all its matrices admit a simultaneous block
upper-triangular factorisation with irreducible blocks
${\mathcal{A}}_{1},\ldots,{\mathcal{A}}_{r}$. Since the spectrum of a block
upper-triangular matrix is a union of spectra of the blocks, it follows that
$\sigma({\mathcal{A}})\,=\,\max\,\bigl{\\{}\sigma({\mathcal{A}}_{1}),\ldots,\sigma({\mathcal{A}}_{r})\bigr{\\}}$,
where ${\mathcal{A}}_{k}$ is the Lyapunov exponent of the restricted system
(with the same switching interval $[m,M]$) corresponding to the $k$th block.
Hence, if Theorem 3 holds in each irreducible block, it holds for the whole
system.

$\Box$

Extra parts 1): Thus, for the time restricted systems, the asymptotics of any
trajectory along the real time axis is equivalent to that along the sequence
of switching points. Therefore, for the Lyapunov exponent, we have
$\sigma(S)\,=\ \inf\,\bigl{\\{}\alpha\in{\mathbb{R}}\ \bigl{|}\
\|{\boldsymbol{x}}(t_{k})\|\,\leq\,Ce^{\,\alpha t_{k}}\,,\
k\in{\mathbb{N}}\bigr{\\}}$, where $\\{t_{k}\\}_{k\in{\mathbb{N}}}$ are the
switching points of the trajectory ${\boldsymbol{x}}(t)$ and the infimum is
computed over all trajectories of the system.

9.3. Proof of Theorem 4

Let us denote by $\|\cdot\|_{P}$ the multinorm
$\bigl{\\{}\|\cdot\|_{P_{j}}\bigr{\\}}_{j=1}^{n}$, where the norm
$\|\cdot\|_{P_{j}}$ in $L_{j}$ is generated by the polytope $P_{j}$. The same
for the multinorm $\|\cdot\|_{P^{(k)}_{j}}$ generated by the polytope
$P_{j}^{(k)}$ after the $k$th iteration.

###### Proposition 11

There exists $k_{0}\in{\mathbb{N}}$ such that for all $k\geq k_{0}$, all the
polytopes $P_{j}^{(k)}\,=\,{\rm co}_{s}\,{\mathcal{V}}_{j}^{(k)}$ possess
nonempty interiors.

Proof. For a given $j$, we have $P_{j}^{(k)}\subset P_{j}^{(k+1)}$ for all
$k$, therefore, either $P_{j}^{(k)}$ possesses a nonempty interior for all
sufficiently big $k$, or they are all contained in some proper subspace
$L_{j}^{\prime}\in L_{j}$. If this happens for some $j$, then the family
${\mathcal{A}}_{j}$ is reducible, which is a contradiction.

$\Box$

###### Lemma 2

Let $\|\cdot\|$ be an arbitrary norm in ${\mathbb{R}}^{d}$ and
${\boldsymbol{x}}:\,[0,\tau]\to{\mathbb{R}}^{d}$ be a $C^{2}$-curve. Then, for
every $t\in[0,\tau]$, the distance from the point ${\boldsymbol{x}}(t)$ to the
segment $[{\boldsymbol{x}}(0),{\boldsymbol{x}}(\tau)]$ does not exceed
$\frac{\tau^{2}}{8}\,\|\ddot{\boldsymbol{x}}\|_{C[0,\tau]}$.

Proof. It can be assumed that ${\boldsymbol{x}}(0)=0$, denote also
${\boldsymbol{x}}(\tau)={\boldsymbol{a}}$. Let the distance from
${\boldsymbol{x}}(t)$ to the segment $[0,{\boldsymbol{a}}]$ be equal to $r$
and be attained at the point ${\boldsymbol{x}}(\xi)$. Let ${\boldsymbol{y}}$
be the closest to ${\boldsymbol{x}}(\xi)$ point of that segment. Denote
${\boldsymbol{h}}={\boldsymbol{x}}(\xi)\,-\,{\boldsymbol{y}}$. Thus,
$\|{\boldsymbol{h}}\|=r$. The segment $[0,{\boldsymbol{a}}]$ does not
intersect the interior of the ball of radius $r$ centered at
${\boldsymbol{x}}(\xi)$. Therefore, by the convex separation theorem, there
exists a linear functional
${\boldsymbol{p}}\in{\mathbb{R}}^{d},\,\|{\boldsymbol{p}}\|^{*}=1$, that
vanishes on the segment $[0,{\boldsymbol{a}}]$ and
$({\boldsymbol{p}},{\boldsymbol{h}})\,=\,\|{\boldsymbol{h}}\|$. Since
$({\boldsymbol{p}},{\boldsymbol{h}})\,=\,({\boldsymbol{p}},{\boldsymbol{x}}(\xi))\,-\,({\boldsymbol{p}},{\boldsymbol{y}})\,=\,({\boldsymbol{p}},{\boldsymbol{x}}(\xi))$,
we have $({\boldsymbol{p}},{\boldsymbol{x}}(\xi))\,=\,r$. Define the function
$f(t)\,=\,\bigl{(}{\boldsymbol{p}},{\boldsymbol{x}}(t)\bigr{)}$. The maximum
of $f(t)$ on the segment $[0,\tau]$ is attained at $t=\xi$, hence
$f^{\prime}(\xi)=0$. Without loss of generality we assume that
$\xi\leq\frac{1}{2}\,\tau$, otherwise interchange the ends of the segment
$[0,\tau]$. The Tailor expansion of $f$ at the point $\xi$ gives
$f(t)\,=\,f(\xi)\,+\,f^{\prime}(\xi)(t-\xi)\,+\,+\frac{1}{2}\,f^{\prime}(\eta)(t-\xi)^{2}$,
where $\eta\in[t,\xi]$. Since $f^{\prime}(\xi)=0$, we obtain for $t=0$:
$f(0)\,=\,f(\xi)\,+\,\frac{1}{2}\,f^{\prime\prime}(\eta)\xi^{2}$. Thus,

$f(\xi)\ -\ f(0)\ =\
\bigl{(}{\boldsymbol{p}}\,,\,{\boldsymbol{x}}(\xi)-{\boldsymbol{x}}(0)\bigr{)}\
=\ \bigl{(}{\boldsymbol{p}},{\boldsymbol{x}}(\xi)\bigr{)}\,=\,r.$

Therefore,

$r\ \leq\
\frac{1}{2}\,\bigl{|}f^{\prime\prime}(\eta)\bigr{|}\xi^{2}\,\leq\,\frac{\tau^{2}}{8}\,\bigl{|}\bigl{(}{\boldsymbol{p}}\,,\,\ddot{\boldsymbol{x}}(\eta)\bigr{)}\bigr{|}\
\leq\ \frac{\tau^{2}}{8}\,\bigl{\|}\ddot{\boldsymbol{x}}\bigr{\|}\,,$

which completes the proof.

$\Box$

###### Corollary 6

Under the assumptions of Lemma 2, if ${\boldsymbol{x}}$ is a solution of the
differential equation $\dot{\boldsymbol{x}}\,=\,A{\boldsymbol{x}}$, then, for
every $t\in[0,\tau]$, the distance from the point ${\boldsymbol{x}}(t)$ to the
segment $[{\boldsymbol{x}}(0),{\boldsymbol{x}}(\tau)]$ does not exceed

$\frac{\frac{\tau^{2}}{8}\,\|A^{2}\|}{1\,-\,\frac{\tau^{2}}{8}\,\|A^{2}\|}\,\max\,\bigl{\\{}\|{\boldsymbol{x}}(0)\|\,,\|{\boldsymbol{x}}(\tau)\|\,\bigr{\\}}$
(10)

Proof. Since
$\ddot{\boldsymbol{x}}=A\dot{\boldsymbol{x}}\,=\,A^{2}{\boldsymbol{x}}$, it
follows that
$|f^{\prime\prime}(\eta)|\,=\,\bigl{|}\bigl{(}{\boldsymbol{p}},A^{2}{\boldsymbol{x}}(\eta)\bigr{)}\bigr{|}\,\leq\,\bigl{\|}A^{2}{\boldsymbol{x}}(\eta)\bigr{\|}\,\leq\,\bigl{\|}A^{2}\bigr{\|}\,\bigl{\|}{\boldsymbol{x}}(\eta)\bigr{\|}$.
Thus,

$r\ \leq\ \frac{\tau^{2}}{8}\,\|A^{2}\|\,\|{\boldsymbol{x}}(\eta)\|\,.$ (11)

Let ${\boldsymbol{y}}$ be the closest to ${\boldsymbol{x}}(\eta)$ point of the
segment $[{\boldsymbol{x}}(0),{\boldsymbol{x}}(\tau)]$. We have

$\bigl{\|}{\boldsymbol{x}}(\eta)\bigr{\|}\ \leq\ \|{\boldsymbol{y}}\|\,+\,r\
\leq\ \|{\boldsymbol{y}}\|\ +\
\frac{\tau^{2}}{8}\,\|A^{2}\|\,\|{\boldsymbol{x}}(\eta)\|,$

therefore,

$\bigl{\|}{\boldsymbol{x}}(\eta)\bigr{\|}\ \leq\
\frac{\|{\boldsymbol{y}}\|}{1\,-\,\frac{\tau^{2}}{8}\,\|A^{2}\|}\ =\
\frac{\max\,\bigl{\\{}\|{\boldsymbol{x}}(0)\|\,,\|{\boldsymbol{x}}(\tau)\|\,\bigr{\\}}}{1\,-\,\frac{\tau^{2}}{8}\,\|A^{2}\|}$

The latter inequality follows from the convexity of the norm. Combining with
(11), we complete the proof.

$\Box$

###### Proposition 12

If $\|\cdot\|$ is an arbitrary norm in ${\mathbb{R}}^{d}$ and
${\boldsymbol{x}}(t)$ and is a solution of the differential equation
$\dot{\boldsymbol{x}}\,=\,A{\boldsymbol{x}}$, then, for every $t\in[0,\tau]$,
we have

$\bigl{\|}{\boldsymbol{x}}(t)\bigr{\|}\quad\leq\quad\frac{1}{1\,-\,\frac{\tau^{2}}{8}\,\|A^{2}\|}\,\max\,\Bigl{\\{}\,\|{\boldsymbol{x}}(0)\|\,,\,\|{\boldsymbol{x}}(\tau)\|\,\Bigr{\\}}$
(12)

Proof. If ${\boldsymbol{y}}$ is the closest to ${\boldsymbol{x}}(t)$ point of
the segment $[{\boldsymbol{x}}(0),{\boldsymbol{x}}(\tau)]$, then
$\|{\boldsymbol{x}}(t)\|\leq\|{\boldsymbol{y}}\|\,+\,\|{\boldsymbol{y}}-{\boldsymbol{x}}(t)\|$.
The convexity of the norm implies that
$\|{\boldsymbol{y}}\|\,\leq\,\max\,\\{\|{\boldsymbol{x}}(0)\|,\|{\boldsymbol{x}}(\tau)\|\\}$.
Estimating $\|{\boldsymbol{y}}-{\boldsymbol{x}}(t)\|$ from above by (10) we
arrive at (12).

$\Box$

###### Lemma 3

[33] There is a continuous function $\psi(\delta,z)$ on ${\mathbb{R}}_{+}^{2}$
such that $\psi(0,z)=0$ for all $z$ and for every $d\times d$ matrix $A$, the
following is true: if there is a vector ${\boldsymbol{x}}$ such that
$\|A\,{\boldsymbol{x}}-{\boldsymbol{x}}\|\,\leq\,\delta\,\|{\boldsymbol{x}}\|$,
then $A$ has an eigenvalue $\lambda\in{\mathbb{C}}$ such that
$|\lambda-1|\,\leq\,\psi(\delta,\|A\|)$.

Proof of Theorem 4. Algorithm terminates in Case 1. We have $\mu>\delta$.
Since the set of products $\Pi(t_{i},t)$ is contained in ${\mathcal{E}}_{0}$
and $\mu$ is the maximum of the values
$\frac{1}{t-t_{i}}\sigma\bigl{(}\Pi(t_{i},t)\bigr{)}$ along this set, is
follows from Proposition 7 that $\sigma(S)\geq\mu>-\delta$.

Algorithm does not terminates in Case 1. Let us show that the algorithm
terminates in Case 2, $\sigma(S)<\nu$, and $\|\cdot\|_{P}$ is the
corresponding Lyapunov norm.

Termination. If, to the contrary, Algorithm 1 does not halt in Case 2, then
there is an infinite trajectory on the graph, for which all the switching
points are not absorbed by the corresponding polytopes. This means that the
switching point ${\boldsymbol{x}}(t_{k})$, which appears in the $k$th
iteration on some $L_{j}$, does not belong to the polytope $P_{j}^{(k)}$. By
Proposition 11, there exists $k_{0}\in{\mathbb{N}}$ such that all
$P_{j}^{(k_{0})}$ possess nonempty interiors. Let they all contain a ball of
radius $r$ centered at zero. Since all those polytopes can only enlarge as $k$
grows, it follows that for all $k\geq k_{0}$, the polytopes $P_{j}^{(k)}$
contain this ball. Hence, $\|{\boldsymbol{x}}(t_{k})\|\geq r$ for all $k\geq
k_{0}$. Note that this trajectory is generated by the discrete system
${\mathcal{A}}_{\tau}$ on the graph. Hence, this system possesses a trajectory
that does not converge to zero. Therefore, its joint spectral radius does not
exceed one [12]. By continuity, there exists $\alpha\geq 0$ such that the
joint spectral radius of the discrete system $({\mathcal{A}}-\alpha I)_{\tau}$
is equal to one (the system $({\mathcal{A}}-\alpha I)_{\tau}$ obtained from
the system ${\mathcal{A}}-\alpha I$ by the same discretization as
${\mathcal{A}}_{\tau}$ is obtained from ${\mathcal{A}}$). Clearly, this system
is also irreducible. Hence, all its products are uniformly bounded by some
constant $C$ [12]. Consider the discrete invariant polytope algorithm applied
for the system $({\mathcal{A}}-\alpha I)_{\tau}$ with the same starting point
${\boldsymbol{x}}(0)$ as in Algorithm 1. Since the joint spectral radius is
equal to one, it follows that the discrete invariant polytope algorithm does
not converge within finite time. Hence, there exists a discrete trajectory
$\tilde{\boldsymbol{x}}(t)$ with
$\tilde{\boldsymbol{x}}(0)={\boldsymbol{x}}(0)$ and with some switching points
$\tilde{\boldsymbol{x}}(\tilde{t}_{k})$ such that every switching point does
not belong to the corresponding polytope $\tilde{P}^{(k)}_{j}$. Now we use the
main argument. Consider the trajectory of the original (continuous) system
${\mathcal{A}}$ with the same switching points $\tilde{t}_{k}$. Denote it by
${\boldsymbol{y}}(t)$ and by $Q_{j}^{(k)}$ the corresponding polytopes
generated by Algorithm 1. We have ${\boldsymbol{y}}(t)=e^{\alpha
t}\tilde{x}(t)$ for all $t\geq 0$, every vertex of $Q^{(k)}_{j}$ is obtained
from the corresponding vertex of $\tilde{P}^{(k)}_{j}$ by $e^{\alpha t}$,
where $t$ is the time when that vertex is generated. Since
$\tilde{x}(\tilde{t}_{k})$ does not belong to the interior of
$\tilde{P}^{(k)}_{j}$ and the point ${\boldsymbol{y}}(\tilde{t}_{k})$ appears
later than all vertices of the polytope $Q^{(k)}_{j}$ (later at least by the
discretization step $\tau$), it follows that ${\boldsymbol{y}}(\tilde{t}_{k})$
does not belong to the interior of $e^{\tau\alpha}Q^{(k)}_{j}$ and hence does
not belong to $Q^{(k)}_{j}$. Thus, Algorithm 1 produces an infinite trajectory
${\boldsymbol{y}}(t)$. Hence, at every iteration $k$, the value $\mu_{k}$ is
bigger than or equal to the maximum of the values
$\frac{1}{t-\tilde{t}_{i}}\sigma\bigl{(}\Pi(\tilde{t}_{i},t)\bigr{)}$ over all
products $\Pi(\tilde{t}_{i},t)\in{\mathcal{E}}_{0}$. This is bigger than or
equal to the maximum of the corresponding values
$\frac{1}{t-\tilde{t}_{i}}\sigma\bigl{(}\tilde{\Pi}(\tilde{t}_{i},t)\bigr{)}$
for the discrete system. Let as recall that for the discrete system, the norms
of all products $\tilde{\Pi}(\tilde{t}_{i},t)$ are bounded above by some
constant $C$. Hence $\|\tilde{x}(t)\|\leq C\|x(0)\|$ for all $t$, and
therefore, the trajectory $\tilde{x}(t)$ possesses some limit point
${\boldsymbol{z}}\in L_{i}$. For this limit point, there are products
$\tilde{\Pi}_{r}$ such that
$\|\tilde{\Pi}_{r}{\boldsymbol{z}}\,-\,{\boldsymbol{z}}\|\to 0$ as
$r\to\infty$. Since all those products are uniformly bounded, it follows from
Lemma 3, that the distance from the point $\lambda=1$ to the closest
eigenvalue of $\tilde{\Pi}_{r}$ tends to zero, and hence
$\limsup_{r\to\infty}\sigma(\tilde{\Pi}_{r})\,\geq\,0$. On the other hand, the
corresponding product of $\Pi_{r}$ of the system ${\mathcal{A}}$ is equal to
$e^{\alpha\tau_{t}\tilde{\Pi}_{r}}$, where $\tau_{r}$ is the time interval of
the product $\Pi_{r}$. Consequently,
$\limsup_{r\to\infty}\sigma(\Pi_{r})\,\geq\,0$ and hence $\mu\geq 0$. So
Algorithm 1 must stop in Case 1, which is a contradiction.

The upper bound $\sigma(S)<\nu$ and the Lyapunov norm property.

By the construction of the polytopes $P_{j}$, for every $j=1,\ldots,n$ and
$q\neq j$, we have $e^{\,s\tau A_{j}}B_{j}P_{q}\,\subset\,{\rm\int}\,P_{j},\
s=0,\ldots,N$. Since the set of all admissible triples $(j,q,s)$ is finite, if
follows that there is $\varepsilon>0$ such that

$e^{\,s\tau A_{j}}B_{j}P_{q}\,\subset\,(1-\varepsilon)\,P_{j},\qquad
j=1,\ldots,n;\ q\neq j\,,\ s=0,\ldots,N.$

Hence $\|e^{\,s\tau A_{j}}B_{j}\|_{P}\leq 1-\varepsilon$. To simplify the
notation we denote $\|\cdot\|_{P_{j}}\,=\,\|\cdot\|_{j}$. Thus, for an
arbitrary point ${\boldsymbol{x}}\in P_{q}$, we have

$\bigl{\|}e^{\,s\tau A_{j}}B_{j}{\boldsymbol{x}}\bigr{\|}_{j}\ \leq\
(1-\varepsilon)\,\bigl{\|}{\boldsymbol{x}}\bigr{\|}_{q}\quad\mbox{ for all}\
s=0,\ldots,N.$

Now take and arbitrary $t\in[0,M-m]$, say, $t\in[s\tau,(s+1)\tau]$ for some
$s\leq N-1$. Invoking Proposition 12 for
$A=A_{j},{\boldsymbol{x}}(0)=e^{\,s\tau A_{j}}B_{j}{\boldsymbol{x}}$ and
${\boldsymbol{x}}(\tau)=e^{\,(s+1)\tau A_{j}}B_{j}{\boldsymbol{x}}$ and taking
into account that both $\|{\boldsymbol{x}}(0)\|_{j}$ and
$\|{\boldsymbol{x}}(\tau)\|_{j}$ do not exceed
$(1-\varepsilon)\,\|{\boldsymbol{x}}\|_{q}$, we obtain
$\max\,\bigl{\\{}\|{\boldsymbol{x}}(0)\|_{j},\|{\boldsymbol{x}}(\tau)\|_{j}\bigr{\\}}\,\leq\,\,(1-\varepsilon)\|{\boldsymbol{x}}\|_{q}$.
Therefore

$\bigl{\|}e^{\,t\tau
A_{j}}B_{j}{\boldsymbol{x}}\bigr{\|}_{j}\quad\leq\quad\frac{1-\varepsilon}{1\,-\,\frac{\tau^{2}}{8}\,\|A_{j}^{2}\|_{j}}\,\|{\boldsymbol{x}}\|_{q}\,.$
(13)

Replacing $\|A_{j}^{2}\|_{j}$ by
$\|{\mathcal{A}}^{2}\|\,=\,\max_{j}\|A_{j}^{2}\|_{j}$, we increase the right
hand side of (13). This yields

$\bigl{\|}e^{\,t\tau
A_{j}}B_{j}{\boldsymbol{x}}\bigr{\|}_{j}\quad\leq\quad\frac{1-\varepsilon}{1\,-\,\frac{\tau^{2}}{8}\,\|{\mathcal{A}}^{2}\|}\,\|{\boldsymbol{x}}\|_{q}\,,\qquad
t\in[0,M-m]\,$

Consequently, for an arbitrary trajectory starting at some point
${\boldsymbol{x}}_{0}$ for its $k$th switching point $t_{k}$, we have

$\|{\boldsymbol{x}}(t_{k})\|\quad\leq\quad(1-\varepsilon)^{k-1}\,\left(1\,-\,\frac{\tau^{2}}{8}\,\|{\mathcal{A}}^{2}\|\,\right)^{-(k-1)}\,\|{\boldsymbol{x}}_{0}\|\,.$

On the other hand, $t_{k}\geq(k-1)m$. Computing the logarithm of the both
parts and taking the limit as $k\to\infty$ gives

$\sigma(S)\ \leq\
-\,(1-\varepsilon)\frac{1}{m}\,\ln\,\left(1\,-\,\frac{\tau^{2}\,\|{\mathcal{A}}^{2}\|}{8}\right)\,.$

Substituting $\tau=\frac{M-m}{N}$ we arrive at the upper bound of (4).

$\Box$

Appendix

Proof of Proposition 2. The inequality $\sigma<0$ implies that every
trajectory tends to zero, and hence, the system is stable. We need to
establish the converse: the stability implies that $\sigma<0$. By the
compactness argument, for every $T>0$, the set $\|\Pi(t)\|,\,t\in[0,T]$, is
uniformly bounded above by some constant $H(T)$ over all switching laws from
${\mathcal{E}}(T)$. Denote by $U(T)$ the subset of the unit sphere in
${\mathbb{R}}^{d}$ such that there is a trajectory starting on that set for
which $\|{\boldsymbol{x}}(T)\|\geq 1$. Consider two possible cases:

1) for some $T$, the set $U(T)$ is empty. In this case there is $q<1$ such
that $\|{\boldsymbol{x}}(T)\|<q$ for all trajectories
${\boldsymbol{x}}(\cdot)$ starting on the unit sphere. Then splitting every
infinite trajectory ${\boldsymbol{x}}(t)$ to the time intervals of length $T$,
we obtain $\|{\boldsymbol{x}}(Tk)\|<q^{\,k},\,k\in{\mathbb{N}}$. Consequently,
$\|{\boldsymbol{x}}(t)\|\,<\,H(T)q^{\,k}$ for all $t\in[kT,(k+1)T]$ and so
$\sigma\,\leq\,T^{-1}\ln q\,<\,0$.

2) the sets $U(T)$ are non-empty for all $T$. Since they are all compact and
form an embedded system, they have a non-empty intersection. For every point
${\boldsymbol{x}}_{0}$ from this intersection and for every $T$, there exists
a trajectory ${\boldsymbol{x}}(t)$ such that
${\boldsymbol{x}}(0)={\boldsymbol{x}}_{0}$ and ${\boldsymbol{x}}(T)\,\geq\,1$.
Invoking the compactness of the set of all trajectories on a segment, we
obtain a trajectory, for which ${\boldsymbol{x}}(T)\,\geq\,1$ for all $T>0$,
hence the system is unstable.

$\Box$

Proof of Lemma 1. Let $L$ by the common invariant subspace of all
$e^{tA_{j}}B_{j},\ t\in[\alpha,\beta],\ j=1,\ldots,n$, and let
$C_{j}=e^{\alpha A_{j}}B_{i}$. We first show that the operators $A_{j},C_{j},\
i=1,\ldots,n$ share the subspace $L$. This is obvious for $C_{j}$ since they
belong to our set of operators (for $t=0$). If some $A_{k}$ does not respect
$L$, then there exists ${\boldsymbol{x}}\in L$ such that
$A_{k}{\boldsymbol{x}}\notin L$. Let $h>0$ be the distance from
$A_{k}{\boldsymbol{x}}$ to $L$ and set ${\boldsymbol{y}}\in
C_{k}^{-1}{\boldsymbol{x}}$. Since $L$ is an invariant subspace for $C_{k}$,
it follows that ${\boldsymbol{y}}\in L$. Furthermore, since
$e^{tA_{k}}C_{k}{\boldsymbol{y}}\in L$ for all $t\in[0,\beta-\alpha]$, and
$e^{tA_{k}}\,=\,I+tA_{k}+O(t^{2})$ as $t\to 0$, the distance from the point
$(I+tA_{k})C_{k}{\boldsymbol{y}}$ to $L$ is also $O(t^{2})$. On the other
hand,
$(I+tA_{k})C_{k}{\boldsymbol{y}}\,=\,(I+tA_{k}){\boldsymbol{x}}\,=\,{\boldsymbol{x}}+tA_{k}{\boldsymbol{x}}$,
hence, this distance is equal to $th$. Thus, $th\,=\,O(t^{2})$ as $t\to 0$,
which is a contradiction. Consequently, $L$ is invariant with respect to
$A_{k}$ and $C_{k}$. Therefore, it is invariant for $e^{-\alpha A_{k}}$ and
hence, for $e^{-\alpha A_{k}}C_{k}=B_{k}$, which concludes the proof.

$\Box$

## References

  * [1] N. Athanasopoulos and R. M. Jungers,  Combinatorial methods for invariance and safety of hybrid systems,  Automatica J. IFAC, 98 (2018), 130–140.
  * [2] N. E. Barabanov,  Lyapunov indicator for discrete inclusions, I–III,  Autom. Remote Control, 49 (1988), No 2, 152–157.
  * [3] C. Basso.  Switch-mode power supplies spice simulations and practical designs.  McGraw-Hill, Inc., New York, NY, USA, 1 edition, 2008.
  * [4] M. A. Berger and Y. Wang,  Bounded semigroups of matrices,  Linear Alg. Appl., 166 (1992) 21-27.
  * [5] F. Blanchini, D, Casagrande and S. Miani,  Modal and transition dwell time computation in switching systems: a set-theoretic approach,  Automatica J. IFAC, 46(9):1477–1482, 2010.
  * [6] F. Blanchini, S. Miani,  A new class of universal Lyapunov functions for the control of uncertain linear systems,  IEEE Trans. Automat. Control, 44 (1999), no 3, 641–647.
  * [7] C. Briat and A. Seuret.  Affine characterizations of minimal and mode-dependent dwell-times for uncertain linear switched systems.  IEEE Trans. Automat. Control, 58(5):1304–1310, 2013.
  * [8] G. Chesi and P. Colaneri.  Homogeneous rational Lyapunov functions for performance analysis of switched systems with arbitrary switching and dwell time constraints.  IEEE Trans. Automat. Control, 62(10):5124–5137, 2017.
  * [9] G. Chesi, P. Colaneri, J. C. Geromel, R. Middleton, and R. Shorten.  A nonconservative LMI condition for stability of switched systems with guaranteed dwell time.  IEEE Trans. Automat. Control, 57(5):1297–1302, 2012.
  * [10] Y. Chitour, N. Guglielmi, V.Yu. Protasov, M. Sigalotti,  Switching systems with dwell time: computing the maximal Lyapunov exponent,  Nonlinear Anal. Hybrid Syst. 40 (2021), Paper No. 101021, 21 pp
  * [11] Y. Chitour, P. Mason, and M. Sigalotti.  A characterization of switched linear control systems with finite $L_{2}$-gain.  IEEE Trans. Automat. Control, 62(4):1825–1837, 2017.
  * [12] A. Cicone, N. Guglielmi, and V. Y. Protasov.  Linear switched dynamical systems on graphs.  Nonlinear Anal. Hybrid Syst., 29:165–186, 2018.
  * [13] M. Dehghan and C-J. Ong,  Characterization and computation of disturbance invariant sets for constrained switched linear systems with dwell time restriction,  Automatica J. IFAC, 48(9):2175–2181, 2012.
  * [14] L. Fainshil and M. Margaliot,  A maximum principle for the stability analysis of positive bilinear control systems with applications to positive linear switched systems,  SIAM J. Control Optim. 50 (2012), no. 4, 2193–2215.
  * [15] J. C. Geromel and P. Colaneri.  Stability and stabilization of continuous-time switched linear systems.  SIAM J. Control Optim., 45(5):1915–1930, 2006.
  * [16] R. Goebel, R. G. Sanfelice, and A. R. Teel.  Hybrid dynamical systems.  Modeling, stability, and robustness.  Princeton University Press, Princeton, NJ, 2012.
  * [17] N. Guglielmi, L. Laglia, and V. Protasov.  Polytope Lyapunov functions for stable and for stabilizable LSS.  Found. Comput. Math., 17(2):567–623, 2017.
  * [18] N. Guglielmi and V. Protasov.  Exact computation of joint spectral characteristics of linear operators.  Found. Comput. Math., 13(1):37–97, 2013.
  * [19] N. Guglielmi and V. Protasov.  Invariant polytopes of linear operators with applications to regularity of wavelets and of subdivisions.  SIAM J. Matrix Anal. Appl., 37(1):18–52, 2016.
  * [20] J. Hespanha and S. Morse.  Stability of switched systems with average dwell-time.  In Proceedings of the 38th IEEE Conference on Decision and Control, 1999.
  * [21] B. Ingalls, E. Sontag, and Y. Wang.  An infinite-time relaxation theorem for differential inclusions.  Proceedings of the American Mathematical Society, 131(2):487–499, 2003.
  * [22] V. Kozyakin.  The Berger-Wang formula for the Markovian joint spectral radius.  Linear Algebra Appl., 448:315–328, 2014.
  * [23] T. Kröger.  On-Line Trajectory Generation in Robotic Systems: Basic Concepts for Instantaneous Reactions to Unforeseen (Sensor) Events.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
  * [24] D. Liberzon.  Switching in systems and control.  Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA, 2003.
  * [25] D. Liberzon, J.P. Hespanha, A.S. Morse  Stability of switched systems: a Lie-algebraic condition,  Syst.& Contr. Letters, 37 (1999), no 3, 117–122.
  * [26] D. Liberzon and A. S. Morse.  Basic problems in stability and design of switched systems.  IIEEE Control Systems Magazine, 19:59–70, 1999.
  * [27] T. Mejstrik.  Improved invariant polytope algorithm and applications, ACM Trans. Math. Softw., ACM Transactions on Mathematical Software 46 (2020), no 3, p. 1–26, https://doi.org/10.1145/3408891.
  * [28] A. S. Morse.  Supervisory control of families of linear set-point controllers. I. Exact matching.  IEEE Trans. Automat. Control, 41(10):1413–1431, 1996.
  * [29] A. P. Molchanov and E. S. Pyatnitskiĭ.  Lyapunov functions that define necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems. III.  Avtomat. i Telemekh., (5):38–49, 1986.
  * [30] A. P. Molchanov and Y. S. Pyatnitskiy.  Criteria of asymptotic stability of differential and difference inclusions encountered in control theory.  Systems Control Lett., 13(1):59–64, 1989.
  * [31] M. Philippe, R. Essick, G. E. Dullerud, and R. M. Jungers.  Stability of discrete-time switching systems with constrained switching sequences.  Automatica J. IFAC, 72:242–250, 2016.
  * [32] M. Philippe, G. Millerioux, and R. M. Jungers.  Deciding the boundedness and dead-beat stability of constrained switching systems.  Nonlinear Anal. Hybrid Syst., 23:287–299, 2017.
  * [33] V.Yu. Protasov,  The Barabanov norm is generically unique, simple, and easily computed.  SIAM J. Contr. Optim., to appear in SIAM J. Cont. Opt. (2022), arXiv:2109.12159.
  * [34] M. Souza, A. Fioravanti, and R. Shorten.  Dwell-time control of continuous-time switched linear systems.  In Proceedings of the 54th IEEE Conference on Decision and Control, pages 4661–4666, 2015.
  * [35] A. van der Schaft and H. Schumacher.  An introduction to hybrid dynamical systems, volume 251 of Lecture Notes in Control and Information Sciences.  Springer-Verlag London, Ltd., London, 2000.
  * [36] Y. Wang, N. Roohi, G. Dullerud, and M. Viswanathan.  Stability of linear autonomous systems under regular switching sequences,  In Proceedings of the 54th IEEE Conference on Decision and Control, pages 5445–5450, 2015.
  * [37] W. Xiang.  On equivalence of two stability criteria for continuous-time switched systems with dwell time constraint,  Automatica J. IFAC, 54:36–40, 2015.
  * [38] W. Xiang.  Necessary and sufficient condition for stability of switched uncertain linear systems under dwell-time constraint,  IEEE Trans. Automat. Control, 61(11):3619–3624, 2016.