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