UNDEFINABILITY IN O-MINIMAL STRUCTURES OF THE PROBLEM ON EXISTENCE OF BOUNDED INVARIANT SETS FOR A FINITE COLLECTION OF MATRICES

V.S. Kozyakin¹

Institute for Information Transmission Problems
Russian Academy of Sciences

A great variety of problems arising in the theory of dynamical systems may be reduced to the problem whether, for a finite collection of $m\times m$ matrices ${\mathcal{A}}=\{A_{1}, A_{2},\ldots, A_{n}\}$, there exists a bounded invariant set $\Omega$ with nonempty interior:

$$A_{i}\Omega\subseteq\Omega,\qquad \forall A_{i}\in{\mathcal{A}}.$$

This problem is equivalent to the problem on existence of a vector norm $\Vert\cdot\Vert$ in $R^{m}$ in which $\Vert A_{i}\Vert\le1$ for all $A_{i}\in{\mathcal{A}}$. It is also equivalent to the problem whether all finite products of matrices $A_{i}\in{\mathcal{A}}$ be uniformly bounded.

In the case when ${\mathcal{A}}$ consists of a single matrix, ${\mathcal{A}}=\{A\}$, the problem under consideration can be resolved in terms of the spectrum of the matrix $A$. In general case, when $m,n\ge 2$, the problem is turned out to be more complicated, and by now different formal supports to this thesis are known (see, e.g., survey [1]). For example, the problem on boundedness of infinite products of matrices from a finite set, equivalent to the problem under consideration, is NP-hard [1], i.e., algorithmically complex. Alternative characterization of the complexity of the above formulated problem is followed from the fact that this problem is algebraically unsolvable [6] which means, loosely speaking, that it cannot be resolved by finite Boolean combinations of algebraic formulae.

Solutions to finite combinations of algebraic equalities and inequalities form so-called semialgebraic sets with a variety of good (tame) properties which makes them a rather attractive object in mathematical constructions. To isolate the basic properties of semialgebraic sets, in the 80's van den Drie, Knight, Pillay and Steinborn [2,5,7] axiomatically introduce the notion of o-minimal structures and prove that the main bulk of tame properties of semialgebraic sets are inherited by sets definable in o-minimal structures (see., e.g., [3]). Worth to mention that analytical functions (seemingly the most natural candidate to inherit the basic properties of semialgebraic sets) does not form an o-minimal structure nor contained in any o-minimal structure.

Theorem    For $m,n\ge 2$ the problem on existence of a bounded set with nonempty interior, invariant for $n$ pieces of $m\times m$ matrices, is not definable in o-minimal structures containing semialgebraic sets.

One of the most broad and useful in practice examples of the sets, definable in o-minimal structures, is the family ${\mathcal{S}}_{\textrm{an,exp}}$ [4] of all sets which can be described by finite Boolean combinations of formulae composing of finite number of algebraic operations, the operation of exponentiation and application of a finite number of the restricted analytical functions. Here by restricted analytical function is meant the function which is equal to an analytical function on some compact set and to zero outside of it.

So, the formulated Theorem implies, informally, that the problem on existence of nontrivial bounded invariant set for a family of matrices is unsolvable by finite Boolean combinations of formulae composing of finite number of algebraic operations, the operation of exponentiation and application of a finite number of the restricted analytical functions.

The proof of Theorem is essentially based on two facts: that sets definable in o-minimal structures have only finitely many components of connectedness and that polynomial images of such sets are again sets definable in o-minimal structures (Tarski-Seidenberg principle).

Footnotes

... Kozyakin¹

Institute for Information Transmission Problems, Russian Academy of Sciences, Bolshoj Karetny lane, 19, 101447 Moscow, Russia.
Phone: +7 (095) 299-83-54
Fax: +7 (095) 209-05-79