\def\al{\alpha}
\def\de{\delta}
\def\ve{\varepsilon}
\def\vp{\varphi}
\def\ga{\gamma}
\def\la{\lambda}
\def\sg{\sigma}
\def\om{\omega}
\def\Om{\Omega}
\def\wt{\widetilde}
\def\pr{\partial}
\def\br{\bold R}
\def\bc{\bold C}
\def\bz{\bold Z}
\def\vk{\kappa}
\def\th{\theta}
\def\tl{\tilde}


\centerline{\bf C\,H\,A\,P\,T\,E\,R\ \ \ II}

\bigskip

\centerline{\bf ESTIMATES OF  LYAPUNOV EXPONENTS}
\centerline{\bf FOR  DISCRETE SYSTEMS}


\bigskip

\bigskip


Consider a system
$$
x(k+1)=A(k)x(k),\qquad x\in\br^n,\ k\in\bz
\eqno(1)
$$
and its fundamental matrix
$$
X(k)=\prod_{j=0}^kA(j).
$$
Here $A(j)$ is a real $n\times n$-matrix. Further, we shall use
the following notations: $\bz$ is a set of integer numbers,
$\br^n$ is an Eucledean $n$-dimensional space, and $\bc^n$
is a unitary  $n$-dimensional space.

Recall also the following definition of the Lyapunov exponent
$\nu_j$:
$$
\nu_j=\ln\varlimsup_{k\to+\infty} \rho_j(k)^{1/k}.
$$


In the present chapter the estimates of the Lyapunov exponents
for continuous linear systems, obtained in pre\-vi\-o\-us
chapter, are extended to discrete systems.

Let $u_1(k),\ldots,u_n(k)$ be an orthonormal system of
eigen\-vec\-tors ot the matrix $X(k)^*X(k)$ such that
$$
X(k)^*X(k)u_j(k){=}\rho_j(k)^2u_j(k).
$$
Recall that a linear operator $X(k)$ transforms the
or\-tho\-go\-nal system $u_1(k),\ldots,u_n(k)$ into the orthonormal one
and\linebreak
$\big|X(k)u_j(k)\big|=\rho_j(k)$.

Let us introduce some $m$-dimensional linear subspace
$L_m\subset\br^n$ and a nonnegative function $\al(k)$.

\medskip

{\bf Lemma 1.}
{\it
Let for any vector $v\in L_m$ an estimate
$\big|X(k)v\big|\geq\al(k)|v|$be satisfied. Then $\rho_m(k)\geq\al(k)$.
}

\medskip

{\bf Proof.}
Fix a number $k$ and choose a vector $v\in L_m$ such that
$v^*u_j(k)=0$, $\ \forall\,j=1,\ldots,m-1$. It is clear that
there exists a nonzero vector $v$ satisfying these conditions.

Having written the following expansion:
$$
v=\sum_{j=m}^n\al_ju_j(k),\quad \al_j\in\br^1,
$$
we obtain
$$
\al(k)^2|v|^2\leq\big|X(k)v\big|^2=\sum_{j=m}^n
\al_j^2\rho_j(k)^2\leq\rho_m(k)^2|v|^2
$$
which proves the Lemma 1.

\medskip

Consider now a symmetric matrix $H$ having no less than $m$
negative eigenvalues, a quadratic form $V(x)=x^*Hx$, and a set
$\Om=\big\{x|\ x^*Hx<0\big\}$.

\medskip

{\bf Lemma 2.}
{\it
Let for some positive number $\la$ and an arbitrary vector
$z\in\Om$ the inequality
$$
\frac1{\la^2}\,z^*A(k)^*HA(k)z\leq z^*Hz
\eqno(2)
$$
be satisfied. Then there exists a number $\beta>0$ such that
$$
\rho_m(k)\geq\beta\la^k,\quad\forall\ k\in\bz,\ k>0.
\eqno(3)
$$
}

\medskip

{\bf Proof.}
Write estimate (2) in the form $V\big(x(k+1)\big)\leq\mh\leq
\la^2V\big(x(k)\big)$. From here it follows that an inequality
$V\big(x(k)\big)\leq V\big(x(0)\big)\la^{2k}$ holds.
Then from the conditions for the spectrum of the matrix
$H$ we can deduce the existence of an  $m$-dimensional hyperplane
$L_m$ and the existence of a number $\beta>0$ such that for any
$x(0)\in L_m$ the following estimates hold:
$$
V\big(x(0)\big)<0,\quad\big|x(k)\big|\geq\beta
\big|x(0)\big|\la^k.
$$
Using this estimate and Lemma 1, we obtain the statement of
Lemma 2.

\medskip

Consider now a symmetric matrix $M$ with no less than $m$
positive eigenvalues.

\medskip

{\bf Lemma 3.}
{\it
Let $\det A(k)\neq0$, $\ \forall\,k\in\bz$, and for some positive
number  $\th$ and an arbitrary vector $z\in\br^n$
the following inequality be satisfied:
$$
\frac1{\th^2}\,z^*A(k)MA(k)^*z\leq z^*Mz. \eqno(4)
$$
Then there exists a number $\ga$ such that
$$
\rho_{n-m+1}(k)\leq\ga\th^k,\quad\forall\ k\in\bz,\ k>0.
\eqno(5)
$$
}

\medskip

{\bf Proof.}
Together with system (1), consider a system
$$
y(k+1)=\big[A(k)^{-1}\big]^*y(k).\eqno(6)
$$
It is obvious that for a fundamental matrix $Y(k)$
of this system an equality
$$
X(k)Y(k)^*=I
$$
is satisfied. From here it follows that
$$
X(k)^*X(k)=\big[Y(k)^*Y(k)\big]^{-1}.
$$
Therefore, for singular numbers $\vk_j(k)$ of a matrix $Y(k)$
such that $\vk_1(k){\geq}{\ldots}{\geq}\vk_n(k)$, an equality
$\vk_j(k){=}\rho_{n-j+1}(k)^{-1}$ is satisfied.

Rewrite now inequality (4) in the following form:
$$
\th^2y^*\big[A(k)^{-1}\big]\,H\,\big[A(k)^{-1}\big]^*y
\leq y^*Hy,\quad\forall\ y\in\br^n.
$$
Here $y=A(k)^*z$, $\ H=-M$, $\ \la=\th^{-1}$. Thus, for system
(6) all conditions of Lemma 2 are satisfied and consequently for
some $\beta>0$ the following inequality holds:
$$
\vk_m(k)\geq\beta\th^{-k},\quad\forall\ k\in\bz,\ k>0.
$$
From here it follows that
$$
\rho_{n-m+1}(k)=\vk_m(k)^{-1}\leq\frac1{\beta}\,\th^k,
\quad\forall\ k\in\bz,\ k>0.
$$

Consider system (1) with
$$
A(k)=A+BU(k)C^*,
$$
where $A$, $B$ and $C$ are constant matrices
$n\times n$, $\,n\times l$, $\,n\times r$ respectively, $U(k)$
is an $l\times r$-matrix.

Let us introduce a transfer matrix
$$
W(p)=C^*(A-pI)^{-1}B,\quad p\in\bc^1
$$
and a Hermitian form $F_m(\sg,\xi)$ of complex vector variables
$\sg\in\bc^r$, $\ \xi\in\bc^l$.

We shall assume that
$$
F_m(\sg,0)\geq0,\quad\forall\ \sg\in\br^r. \eqno(7)
$$
Let also an inequality
$$
F_m\big(\sg,U(k)\sg\big)\geq0,\quad\forall\ \sg\in\br^r,
\ \,\forall\ k\in\bz,\ k>0
\eqno(8)
$$
be satisfied.

\medskip

{\bf Theorem 1.}
{\it
Let for some set of positive numbers\linebreak
$\la_1\geq\ldots\geq\la_n$ the following condition be satisfied:

1) a matrix $\la_m^{-1}A$ has $m$ or more eigenvalues outside of
the circle of radius $1$ with its centre at zero point,

2) for all values $p\in\bc^1$ such that $|p|=1$ the following
inequality is true:
$$
F_m\big(-W(\la_mp)\xi,\xi\big)<0,\quad\forall
\ \xi\in\bc^l,\ \xi\neq0.
\eqno(9)
$$

Then for singular values $\rho_m(k)$ of the fundamental matrix
$X(k)$ of system (1) there exists a positive number
$\beta_m$ such that
$$
\rho_m(k)\geq\beta_m\la_m^k,\quad\forall\ k\in\bz,\ k>0.
\eqno(10)
$$
}

\medskip

{\bf Proof.}
From the condition 2) of the theorem, according to the Kalman-Szego
lemma [37], we see that there exists a real matrix $H_m$ such that
$$
\eqalign{
& \frac1{\la_m^2}\,[Az+B\xi]^*H_m[Az+B\xi]-z^*H_mz+
F_m(C^*z,\xi)<0,\cr
& \forall\ z\in\br^n,\ \,\forall
\ \xi\in\br^l,\ \,|z|+|\xi|\neq0.
} \eqno(11)
$$
Putting in (11) $\xi=0$ and taking into account (7), we get an
inequality
$$
\left(\frac1{\la_m}\,Az\right)^*H_m\left(\frac1{\la_m}\,Az\right)
-z^*H_mz<0,\quad\forall\ z\in\br^n,\ z\neq0.
$$
From here and the condition 1) of the theorem by the lemma of
Shepeljavyi [41] it follows that the matrix $H_m$ has no less than
$m$ negative eigenvalues.

From relations (8) and (11) inequality (2) follows. Thus, here
all conditions of Lemma 2 are satisfied. Theorem 1 is proved.

\medskip

Now we shall suppose that instead of conditions (7) and (8) the
following inequalities hold:
$$
F_m(0,\xi)\geq0,\quad\forall\ \xi\in\br^l, \eqno(12)
$$

$$
F_m\big(U(k)^*\xi,\xi\big)\geq0,\quad\forall
\ \xi\in\br^l,\ \,\forall\ k\in\bz,\ k>0. \eqno(13)
$$

\medskip

{\bf Theorem  2.}
{\it
Let $\det A(k)\neq0$, $\ \forall\,k\in\bz$ and for some system
of positive numbers $\th_1\leq\ldots\leq\th_n$ the following
conditions hold:

1) a matrix $A\th_m^{-1}$ has $m$ or more eigenvalues, situated
inside of the circle of radius $1$ with  its centre at zero
point,

2) for all $p\in\bc^1$ such that $|p|=1$ the following inequality
$$
F_m\big(\sg,-W(\th_mp)^*\sg\big)<0,\quad\forall
\ \sg\in\bc^r,\ \sg\neq0 \eqno(14)
$$
is satisfied.

Then for singular values $\rho_{n-m}(k)$ of the fundamental
matrix $X(k)$ of system (1) there exists a number $\ga_m$ such
that
$$
\rho_{n-m+1}(k)\leq\ga_m\th_m^k,\quad\forall\ k\in\bz,\ k>0.
\eqno(15)
$$
}

\medskip

{\bf Proof.}
According to the conditions 2) of the theorem by the Kalman-Szego lemma
[37] there exists a symmetric real matrix $M_m$,
for which
$$
\eqalign{
& \frac1{\th_m^2}[A^*z+C\sg]^*M_m[A^*z{+}C\sg]{-}z^*M_mz{+}
F_m(\sg,B^*z){<}0,\cr
& \forall\ z\in\br^n,\ \ \forall\ \sg\in\br^r,\ |z|+|\sg|\neq0.
} \eqno(16)
$$
Putting in (16) $\sg=0$ and taking into account (12), we obtain
an inequality
$$
\left(\frac1{\th_m}A^*z\right)^*M_m
\left(\frac1{\th_m}A^*z\right){-}z^*M_mz{<}0,\ \,\forall
\,z{\in}\br^n,\,z{\neq}0.
$$
Hence, from the condition 1) of the theorem and from the fact
that spectrums $A$ and $A^*$ are symmetric with respect to
imaginary axis we obtain by the lemma of Shepeljavyi [41] that
the matrix $M_m$ has no less than $m$ positive eigenvalues.

From relations (13) and (16) the inequality
$$
\eqalign{
& \frac1{\th_m^2}\big[A^*z+CU(k)^*B^*z\big]^*M_m
\big[A^*z+CU(k)^*B^*z\big]-\cr
& -z^*Mz\leq-F_m\big(U(k)^*B^*z,B^*z\big)\leq0,\quad
\forall\ z\in\br^n
}
$$
follows.
The last  inequality means that inequality (4) is satisfied.
Thus, all conditions of Lemma 3 are satisfied and, consequently,
estimate (5), which coincides with (15), can be found.

\medskip

Now we shall suppose that $l=r=1$ and for some numbers
$\mu_1$, $\,\mu_2$ such that $\mu_1\mu_2\leq0$ the inequality
$$
\mu_1\leq U(k)\leq\mu_2
$$
is satisfied.

\medskip

{\bf Theorem  3 (an analog of the circle criterion).}
{\it
Let for some set of positive numbers $\la_1\geq\ldots\geq\la_n$
condition 1) of Theorem 1 be satisfied and for all
$p\in\bc^1$  such that $|p|=1$ the inequality
$$
\hbox{Re}\,\left[\big(1+\mu_1{\overline{W(\la_mp)}}\big)\big(
1+\mu_2W(\la_mp)\big)\right]>0
\eqno(17)
$$
be satisfied. Then the statement of Theorem 1 is true.
}

\medskip

For proving Theorem 3 it is sufficient to use Theorem 1 with the
Hermitian form
$$
F_m(\sg,\xi)=(\mu_2\bar\sg-\bar\xi)(\xi-\mu_1\sg)+
(\mu_2\sg-\xi)(\bar\xi-\mu_1\bar\sg).
\eqno(18)
$$

\medskip

{\bf Theorem  4 (an analog of the circle criterion).}
{\it
Let the following inequalities be satisfied:
$$
\det A\neq0,\quad 1+W(0)\al\neq0,\quad
\forall\ \al\in[\mu_1,\mu_2].
\eqno(19)
$$
Suppose that for some set of positive numbers $\th_1\leq\ldots
\leq\th_n$ the condition 1) of Theorem 2 is satisfied and for all
$p\in\bc^1$ such that $|p|=1$ an inequality
$$
\hbox{Re}\,\left[\big(1+\mu_1{\overline{W(\th_mp)}}\big)\big(
1+\mu_2W(\th_mp)\big)\right]>0
\eqno(20)
$$
holds. Then the statement of Theorem 2 is true.
}

\medskip

{\bf Proof.}
It is easy to see that conditions (19) imply the nondegeneracy of
a matrix $A(k)=A+BU(k)C^*$. For a Hermitian form
$$
F_m(\sg,\xi)=(\mu_2\bar\xi-\bar\sg)(\sg-\mu_1\xi)+
(\mu_2\xi-\sg)(\bar\sg-\mu_1\bar\xi)
$$
all conditions of Theorem 2 are satisfied. Really,
we get
$$
F_m(0,\xi)=-2\mu_1\mu_2\xi^2\geq0,\quad\forall\ \xi\in\br^1,
$$
$$
F_m\big(U(k)^*\xi,\xi\big){=}2\big(\mu_2{-}U(k)\big)
\big(U(k){-}\mu_1\big)\xi^2{\geq}0,\quad\forall\,\xi{\in}\br^1,
$$

$$
\eqalign{
& F_m(\sg,{-}W(\th_mp)^*\sg)=\cr
& =-2\hbox{Re}\left[\big(1+\mu_2{\overline{W(\th_mp)}}\big)\big(
1+\mu_1W(\th_mp)\big)\right]|\sg|^2<0,\cr
& \forall\ \sg\in\bc^1,\qquad \sg\neq0.
}
$$
Therefore inequality (15) can be found.

\medskip

{\bf Remark.}
It is evident that from Theorems 1-4 there follow the following
estimates for the Lyapunov exponents $\nu_m$:
$$
\ln\th_{n-m+1}\geq\nu_m\geq\ln\la_m.
$$

\medskip

Consider a system
$$
x(k+1)=Ax(k)+Bf\big(C^*x(k)\big), \eqno(21)
$$
where $A$, $B$, $C$ are respectively $n\times
n$, $\ n\times l$ and $n\times r$
constant matrices and $f(\tau)$ is a continuously
differentiable vector function.

Suppose that some compact set $K$ is invariant with respect to
the shift operator along the trajectories of system (21), i.e.
$$
x(k,x_0)\in K,\quad\forall\ k\in\bz,\ \,\forall\ x_0\in K.
$$
Here $x(0,x_0)=x_0$.

Theorems 1-4 make it possible to obtain the upper estimates of the
Hausdorff dimension $\hbox{dim}\,K$ of the invariant compact set $K$.
For this purpose we introduce the following notations:
$$
\wt K=\big\{\tau|\ \tau=C^*x,\ x\in K\big\},
$$
$$
\Cal D(\tau)=\left|\det\left(A+B\frac{\pr f(\tau)}{\pr\tau}
\,C^*\right)\,\right|,\quad\Cal D=\max_{\tau\in\tl K}\Cal D(\tau).
$$
Here $\frac{\pr f(\tau)}{\pr\tau}$ is Jacobi matrix  for the
vector function $f(\tau)$ at a point $\tau$.

Suppose, at first, that for Hermitian forms $F_m(\sg,\xi)$
condition (7) is satisfied and condition (8) is replaced by the
inequality
$$
F_m\left(\sg,\frac{\pr f(\tau)}{\pr\tau}\,\sg\right)\geq0,\quad
\forall\ \sg\in\br^r,\ \,\forall\ \tau\in\wt K. \eqno(22)
$$

\medskip

{\bf Theorem  5.}
{\it
Let for some set of positive numbers $\la_1\geq\ldots\geq\la_n$
the conditions of Theorem 1 be satisfied. Suppose also that for
some natural number  $d$ and for $s\in[0,1]$ an inequality
$$
\Cal D<\la_{d+1}^{1-s}\la_{d+2}\cdots\la_n
\eqno(23)
$$
holds. Then $\hbox{dim}\,K<d+s$.
}

\medskip

The estimate $$
\rho_1(k)\cdots\rho_{d+1}^s(k)\leq\beta\,\Cal D^k\la_{d+1}^{k(s-1)}
\la_{d+2}^{-k}\cdots\la_n^{-k},
\eqno(24)
$$
which follows from Theorem 1, is basis for the proof of this
theorem. Here $\beta$ is a number,
$\rho_j(k)$ are singular numbers of fundamental matrices of
systems obtained as a result of linearization of system (21)
along trajectories $x(k,x_0)$, $\ x_0\in K$. Further, the proof of
Theorem 5 repeats the scheme given in [23--25].

\medskip

Let $l=r=1$ and for some numbers  $\mu_1$ and $\mu_2$ such that
$\mu_1\mu_2\leq0$, an inequality
$$
\mu_1\leq\frac{df(\tau)}{d\tau}\leq\mu_2,\quad\forall
\ \tau\in\wt K
\eqno(25)
$$
be satisfied.

\medskip

{\bf Theorem  6.}
{\it
Let all conditions of Theorem 3 and inequalities {\rm(23), (25)} be
satisfied; then $\hbox{dim}\,K<d+s$.
}

\medskip

This theorem is a corollary of Theorems 3 and 5.

Analogously, using Theorem 2 and 4, it is possible to formulate
the following results.

\medskip

{\bf Theorem  7.}
{\it
Let $\Cal D(\tau)\neq0$, $\ \forall$~$\tau\in\wt K$,
inequality {\rm(12)} be satisfied, and let
$$
F_m\left(\left(\frac{\pr f(\tau)}{\pr\tau}\right)^*\xi,\,\xi\right)
\geq0,\quad\forall\ \xi\in\br^l,\ \,\forall\ \tau\in\wt K.
\eqno(26)
$$
Suppose also that for some set of positive numbers
$\th_1\leq\ldots\leq\th_n$ all conditions of Theorem 2  are
satisfied and for a natural number  $d$ and $s\in[0,1]$ the following
inequality
$$
\th_n\cdots\th_{n-d+1}\th_{n-d}^s<1.
\eqno(27)
$$
can be found.
Then $\hbox{dim}\,K<d+s$.
}

\medskip

Suppose $l=r=1$ and condition (25) hold.

\medskip

{\bf Theorem  8.}
{\it
Let all conditions of Theorem 4 and inequality  {\rm(27)} be
satisfied. Then $\hbox{dim}\,K<d+s$.
}

\medskip

Let us consider the system of Henon [19,44]
$$
\eqalign{
& z(k+1)=1-az(k)^2+y(k),\cr
& y(k+1)=bz(k),
} \eqno(28)
$$
where $a$ and $b$ are positive numbers, $b<1$.

In our notation,
$$
A=\left(\matrix 0&1\\ b&0\endmatrix\right),\quad
B=\left(\matrix1\\0\endmatrix\right),\quad
C=\left(\matrix1\\0\endmatrix\right),\quad
$$

$$
f(\tau)=1-a\tau^2.
$$
We shall suppose that for some invariant compact set $K$ the
following estimate is satisfied
$$
K\subset\left\{\left(\matrix z\\y\endmatrix\right)\bigg|\ -\al
\leq z\leq\al\right\}. \eqno(29)
$$
Here $\al$ is a positive number. In this case we may take
$$
\mu_2=-\mu_1=2a\al.
$$
It is clear that here
$$
W(p)=\frac{-p}{p^2-b},\quad \la_m^{-1}A=
\left(\matrix 0&\la_m^{-1}\\ b\la_m^{-1}&0\endmatrix\right).
$$
It is easy to see that both eigenvalues of this matrix are
situated outside of the unit circle if $\la_m<\sqrt b\,$.

In this case condition (17) takes the form
$$
\big|W(\la_mp)\big|^2<\mu_2^{-2},\quad |p|=1.
$$
This inequality holds if
$$
\frac1{\la_m\left|p^2-\frac{b}{\la_m^2}\right|}<\mu_2^{-1},
\quad|p|=1.
$$
The last inequality is true if
$$
\la_m^{-1}b-\la_m>\mu_2.
$$
Thus,  if
$$
0<\la_2<-\frac{\mu_2}2+\sqrt{b+\frac{\mu_2^2}4},
$$
all conditions of Theorem 3 are satisfied for $m=2$.

In our case $\Cal D=b$, $\ d=1$, $\ m=2$. Then a number\linebreak
$s\in[0,1]$, for which (23) holds, can be found from an
inequality
$$
s>1-\frac{\ln b}{\ln\la_2}.
$$
From this estimate we obtain by Theorem 6 that
$$
\hbox{dim}\,K\leq\max\left(1,\ 2-\frac{\ln b}
{\ds\ln\left[\frac{-\mu_2}2+\sqrt{b+\frac{\mu_2^2}4}\,\right]}
\right). \eqno(30)
$$

Note that by a circle criterion
$$
\big|W(p)\big|^2<\mu_2^{-2},\quad|p|=1,
$$
we obtain for system (28) the following result. If $\mu_2<1-b$,
then any solution  $z(k)$, $\,y(k)$, which is situated completely
for all $k\geq0$ in a band $\{-\al\leq z\leq\al\}$, tends to the
state of equilibrium. Hence and from (30) we get finally the
following estimate;
$$
\hbox{dim}\,K\leq\cases
2-\frac{\ds \ln b}{\ds\ln\left[\ds \frac{-\mu_2}2+
\sqrt{b+\frac{\mu_2^2}4}\,\right]}&\hbox{if}\ \mu_2>1-b,\\
\\
0&\hbox{if}\ \mu_2<1-b.
\endcases
$$

Consider a case when $a=1.4$, $\ b=0.3$. It is shown in [19]
that one can take $\al=1.33$. Then from estimate (31) we obtain that
$\hbox{dim}\,K<1.523$. This estimate have been obtain also for the
Henon system in [20]. In [44] as a result of numerical experiment
it was obtained that  $\hbox{dim}\,K=1.24$.

