CHAPTER 1
Introduction
Suppose that / : Rn Rn is a linear mapping such that f(Kn) C Kn and
\\f(x) f(y)\\i \\x 2/||x f°r a u xiV £ ^ n - Equivalently, / is given by an n x n
matrix A = (a^) with a^ 0 for all i and j and X^
= 1
d%j 1 for 1 j n. The
Perron-Frobenius theory of nonnegative matrices implies that for every x G Kn
there exists a minimal positive integer p and a point £x = £ G K
n
such that
lim /'*(*) = £, and /*(£) = £, /(£) ^ f o r l i p .
Furthermore, Perron-Frobenius theory implies that p is the least common multiple
of some set of positive integers whose sum is less than or equal to n, so p is the order
of some element of the symmetric group on n letters. (For completeness we shall
sketch a proof of a more general result in Chapter 9.) Conversely, every element
a of the symmetric group on n letters generates a linear map as above and has a
periodic point of period equal to its order. Thus, in the linear case, it is possible
to describe exactly the set of possible periods p. However, one should note that
even in the linear case the explicit computation of the set of possible periods is not
entirely trivial for large n; and finding asymptotics and explicit upper bounds for
the largest order of an element of the symmetric groups on n letters involves the
prime number theorem [6, 7].
Our goal in this paper and in [13] and [14] is to give a precise extension of the
above aspects of linear Perron-Frobenius theory to a class of nonlinear maps. We
begin by recalling some relevant background.
Let D be a subset of
W1.
A map / : D
Rn
is called nonexpansive with
respect to the li-norm or 11-nonexpansive if, for all x,y G Z), one has
!l/(*)-/G/)Hil|z-y||1,
where
n
\\x\\i := ^2,\xi\ and x = (xi,... ,x
n
).
2 = 1
If D C Rn is closed, / : D D is l\-nonexpansive and there exists n G D such that
sup{||/J(ry)||i | j 1} oo, then results of Akcoglu and Krengel [1] imply that for
every x G D, there exists a positive integer px p and a point £x = £ G D with
lim f"(x) = £, and fp(0 = £, /'(£) ? £ for 1 i p. (1.1)
Here
fk
denotes the composition of / with itself k times. Related results for "poly-
hedral norms" have been obtained by Weller [20], Nussbaum [9], Sine [19], Lyons
and Nussbaum [4], Martus [5], and Lo [3]. Among other results, it has been proved
that if V is a finite dimensional vector space with polyhedral norm || ||, D is a
subset of V and f : D D is nonexpansive with respect to || ||, then there exists
l
Previous Page Next Page