FINITE DYNAMICAL SYSTEMS

REINHARD LAUBENBACHER AND BODO PAREIGIS

Abstract. This paper is motivated by the theory of sequential dynamical systems, developed as a basis for a theory of computer simulation. We study finite dynamical systems on binary strings, that is, iterates of functions from {0, 1}^{n} to itself. We introduce several equivalence relations on systems and study the resulting equivalence classes. The case of two-dimensional systems is studied in detail.

Introduction

The topic of this paper is the study of functions

f : k^{n} ⟶ k^{n},

and their iterates, where k = {0, 1}, and k^{n} is the n-fold Cartesian product of k. We view such functions as finite dynamical systems on the set of binary strings of a given length, and call them systems. Our motivation comes from an interest in their role in computer simulations. During the last several years an effort to establish a rigorous mathematical foundation for computer simulation has been underway, detailed in [2, 3, 4], and the results presented here can be considered a part of this effort. But finite dynamical systems are of considerable interest in their own right, and deserve further study.

In order to motivate the setting of the present paper, we describe the main concept introduced in [3], that of a sequential dynamical system. Computer simulations are typically comprised of entities having state values and local rules governing state transitions, a spatial environment in which the entities act or interact, and some method with which to trigger and update the state of each entity. according to a specified update schedule. The result is what one calls a “simulated system.”

As an example, consider a simulation of road traffic. Here the entities might represent cars, whose state is either stop (0) or go (1). The state space of the simulation then consists of tuples of binary strings, whose length is equal to the number of entities involved in the simulation, and represents the state of each entity at a given time. A state transition of the simulation is the replacement of one state by another. Each entity has an internal function attached to it, which computes its state at any given time, that is, a local rule for state transitions. The entities interact with each other by passing information back and forth, representing the interaction of cars on the road. This interaction takes place in a spatial environment that may correspond to the road network to be modeled or to causal relationships among the cars on it. Dependencies among the entities determine an order in which the states of the individual entities are recomputed in a state transition, the update schedule. For instance, as cars approach a traffic jam, the ones arriving first should come to a stop before cars following them. Finally, the interaction of entities is local, that is, entities interact only with those entities that are adjacent to them, as defined by the underlying spatial environment, just as cars interact only with other cars that are close to them on the road.

Date: May 11, 2001.

This paper was written while the second author was visiting the Department of Mathematical Sciences of NMSU, Las Cruces, in the Fall of 1999. He wishes to thank the Department and all colleagues for their support and hospitality.

A mathematical abstraction of such simulated systems must then be made up of these essential elements: local rules governing state transitions, a framework for interaction represented as an interaction support structure, and an update schedule of the entities. These elements are incorporated into a mathematical structure called a sequential dynamical system (SDS), comprised of a graph, whose vertices correspond to the entities and whose edges represent the causal dependency among the local update maps, a collection of local update functions, and an update schedule. Entities are adjacent if and only if they interact. The update schedule reflects causal or temporal dependencies among entity states. Locality, a property of the update maps, is defined in terms of adjacency, a property of the support and causal structure. The resulting interplay between the topological and algebraic properties of SDS is very rich and interesting and seems to open new areas of purely mathematical investigation.

Following is the precise definition of an SDS.

Definition 0.1. Let Y be a loop-free labeled graph with vertex set {v_{1}, …, v_{n}}, and let k be the field with two elements, denoted 0 and 1. (Consider k^{n} as the state space over {v_{1}, …, v_{n}}.) For each i ∈ {1, …, n} suppose we are given a function

f^{i} : k^{n} ⟶ k^{n},

which changes only the value of the i-th coordinate, and depends only on the values in the i-th coordinate and the values in those coordinates corresponding to the vertices adjacent to v_{i} in the graph Y. Call such a function a 1-local function on k^{n}, with respect to the graph Y. Furthermore, we assume that f^{i} is symmetric in its inputs, that is, it is invariant under permutation of its inputs. To be precise, let v_{i_{1}}, …, v_{i_{r}} be the vertices adjacent to v_{i}. Then the function f^{i} factors through the projection

k^{n} ⟶ k^{r+1},

given by

(x_{1}, …, x_{n}) ↦ (x_{i_{1}}, …, x_{i}, …, x_{i_{r}}).

Now let π ∈ S_{n} be a permutation of the subscripts {1, …, n}. We compose the functions f^{i} in the order prescribed by π to obtain a function

f(Y, π) = f^{π(n)} ∘ f^{π(n−1)} ∘ ⋯ ∘ f^{π(1)} : k^{n} ⟶ k^{n}.

We call the function f(Y, π) the sequential dynamical system (SDS) determined by Y, the local functions f^{i} and the permutation π ∈ S_{n}. The graph Y is the dependency graph, and the permutation π is the update schedule.

The assumption that the local update functions f^{i} are symmetric in their inputs is motivated by the desire for a good theory of SDS and facilitates the proof of some key results. From the point of view of applications to simulation it is quite restrictive. For instance, it prevents parallel cellular automata from being modeled as an SDS.

One of the goals of this paper is to clarify the relationship between local functions on k^{n} and the graph Y. For this purpose we disregard the added structure provided by the update schedule, and study n-tuples of functions

(f^{1}, …, f^{n}),

where f^{i} : k^{n} ⟶ k^{n} changes only the value of the i-th coordinate. We also do not require the local functions to be symmetric. More generally, we will study sets of such functions. The main result we obtain is a Galois correspondence between sets of such n-tuples of functions and subgraphs of the complete graph on n vertices. One consequence is that, given a set of functions, there is a graph G, so that the functions are 1-local with respect to G.

This result suggests a possible approach to the study of local functions without explicit reference to a graph. Given that in applications the graph defining the interaction of variables often changes, this might be significant both theoretically and practically.

Then we consider the stable behavior of systems. The set of limit cycles L_{f} in the state space S_{f} is a subdigraph of the state space, with each connected component a single directed cycle, and f restricts to a bijection on the vertices of L_{f}.

Two systems are called isomorphic if there exists a digraph isomorphism between their state spaces. They are stably isomorphic if there exists a digraph isomorphism between their limit cycle graphs. In other words, they are stably isomorphic if they exhibit the same long-term behavior. In this paper we give algebraic conditions for systems to be stably isomorphic.

Finally, we study a very special class of systems, namely the linear ones, given by (n × n)-matrices with coefficients in k. More generally, we study affine systems and their stable isomorphism classes. In particular, we classify explicitly two-dimensional systems.

1. The state space of a finite dynamical system

As for continuous dynamical systems, an important object related to a finite dynamical system is its state space. Definition 1.1. The state space S_{f} of the finite dynamical system f : k^{n} ⟶ k^{n} is the finite directed graph (digraph) with vertex set k^{n}, and with a directed edge from a vertex x to a vertex y if and only if f(x) = y.

It is easy to see that the state space of a system f has a very specific structure. Directed paths in S_{f} correspond to iterations of f on the element, or state, at the beginning of the path. Since the set k^{n} is finite, any directed path must eventually enter a directed cycle, called a limit cycle. Thus, each connected component of S_{f} consist of one limit cycle, together with transients, that is, directed paths having no repeated vertices, and ending in a vertex that is part of a limit cycle. Note that a fixed point of f is a degenerate case of a limit cycle. Example 1.2. Consider the system f : k^{2} ⟶ k^{2} given by the matrix

( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) .

Then the state space of f has three connected components, two of which consist of a single vertex, corresponding to the two fixed points of f, and the third component is a limit cycle of length two.

2. Local Functions and Graphs

Definition 2.1. Let n be a positive integer, d a non-negative integer, and Y a graph with vertex set {1, 2, …, n}.

(1) A function

f : k^{n} ⟶ k^{n}

is d-local on Y if, for any 1 ≤ j ≤ n, the j-th coordinate of the value of f on x ∈ k^{n} depends only on the value of those coordinates of x that have distance less than or equal to d from j in Y. In other words, if f(x) = ((f_{1}(x), …, f_{n}(x)), then

f_{j} : k^{n} ⟶ k

depends only on those coordinates that have distance less than or equal to d from j.

(2) Let L_{d}^{j}(Y) be the set of all functions

f : k^{n} ⟶ k^{n}

such that

f(x_{1}, …, x_{n}) = (x_{1}, …, x_{j−1}, f_{j}(x), x_{j+1}, …, x_{n}),

and f_{j} : k^{n} ⟶ k depends only on the values of those coordinates of x which have distance at most d from j in Y. Hence L_{d}^{j}(Y) consists of d-local functions on k^{n}, which are the identity on all but possibly the j-th coordinate.

Observe that neither L_{0}^{j} nor L_{n}^{j} depend on the graph Y. Furthermore, L_{0}^{j} ≅ Map(k, k) contains all four possible functions, namely the identity on k, the two projections to one element in k, and the inversion.

For the remainder of this section we study the set

L_{n}^{1} × ⋯ × L_{n}^{n} = {(f^{1}, …, f^{n}) | f^{j} ∈ L_{n}^{j}},

i.e. f^{i} = (pr_{1}, …, pr_{i−1}, f_{i}^{i}, pr_{i+1}, …, pr_{n}) or

f^{i}(x) = (x_{1}, …, x_{i−1}, f_{i}^{i}(x), x_{i+1}, …, x_{n}),

with arbitrary functions f_{i}^{i} : k^{n} ⟶ k. We denote by F the power set of this set without the empty set, that is, its elements are non-empty sets of n-tuples of functions from k^{n} to itself, where the j-th function applied to x ∈ k^{n} changes only the j-th coordinate of x. Theorem 2.2. There is a Galois correspondence between F and the set G of subgraphs of the complete graph K_{n} on the vertex set {1, …, n}.

Proof. We first define functions

Φ : F ⟶ G, Ψ : G ⟶ F,

and then verify that they satisfy the conditions for a Galois correspondence, that is, that Φ and Ψ are inclusion reversing, F ⊆ ΨΦ(F), and G ⊆ ΦΨ(G).

Let F ∈ F. Define a subgraph Φ(F) of K_{n} as follows. First construct the set F̃ of all n-tuples f̃ = (f̃^{1}, f̃^{2}, …, f̃^{n}), which either are in F, or arise from an element in F by replacing one of the coordinates by a 0-local function, that is, by a function from L_{0}^{i} for some i. Now define the graph Φ(F) as follows. An edge i–j of K_{n} is in Φ(F) if and only if f̃^{i} ∘ f̃^{j} = f̃^{j} ∘ f̃^{i} for all f̃ = (f^{1}, …, f^{n}) ∈ F̃.

Now let G ⊂ K_{n} be a graph. We define a set Ψ(G) of n-tuples of functions on k^{n} by

Ψ(G) = L_{1}^{1}(\overline{G}) × L_{1}^{2}(\overline{G}) × ⋯ × L_{1}^{n}(\overline{G}),

where \overline{G} is the complement of G in K_{n}.

We need to show that Φ and Ψ are inclusion reversing, that F ⊂ ΨΦ(F), and that G ⊂ ΦΨ(G). To show the first property, let F ⊂ F′ in F. Then F̃ ⊂ F̃′. An edge i–j of K_{n} is in Φ(F′) if and only f^{i} and f^{j} commute for every element f = (f^{l}) ∈ F̃′. Since F̃ ⊂ F̃′, i–j is also contained in Φ(F). If G ⊂ G′ are subgraphs of K_{n}, then \overline{G′} ⊂ \overline{G}. A 1-local function on the smaller graph is certainly also 1-local on the larger graph. This shows that the correspondence is inclusion reversing.

To show that F ⊂ ΨΦ(F), let (f^{1}, …, f^{n}) ∈ F. We have to show that f^{i} ∈ L_{1}^{i}(\overline{Φ(F)}), i.e. that f^{i}(x) does not depend on the j-th coordinate x_{j} of x if j is not connected to i in the graph \overline{Φ(F)}. Let j(≠ i) be a vertex in \overline{Φ(F)} such that i–j is not in \overline{Φ(F)}. Let f̃^{j} be a function in L_{0}^{j}. Then (f^{1}, …, f̃^{j}, …, f^{n}) ∈ F̃. Since i–j is not in \overline{Φ(F)}, it is in Φ(F) hence f^{i} ∘ f̃^{j} = f̃^{j} ∘ f^{i} for all four functions f̃^{j} ∈ L_{0}^{j}. Now

f̃^{j} ∘ f^{i}(x) = (x_{1}, …, f_{i}^{i}(x), …, f̃_{j}^{j}(x), …, x_{n})

and

f^{i} ∘ f̃^{j}(x) = (x_{1}, …, f_{i}^{i}(x_{1}, …, x̃_{j}, …, x_{n}), …, f̃_{j}^{j}(x), …, x_{n}),

where x̃_{j} = f̃_{j}^{j}(x), hence f_{i}^{i}(x) and f^{i}(x) do not depend on x_{j}.

Now we show that G ⊂ ΦΨ(G). First observe that

{ \atop Ψ(G)} = Ψ(G) = L_{1}^{1}(\overline{G}) × L_{1}^{2}(\overline{G}) × ⋯ × L_{1}^{n}(\overline{G}),

since L_{0}^{i} ⊂ L_{1}^{i}(\overline{G}). Let i–j be in G and let f ∈ Ψ(G). We have to show that f^{i} ∘ f^{j} = f^{j} ∘ f^{i} holds, since then i–j is an edge in ΦΨ(G). Now f ∈ Ψ(G) = L_{1}^{1}(\overline{G}) × L_{1}^{2}(\overline{G}) × ⋯ × L_{1}^{n}(\overline{G}) implies that f_{i}^{i}(x) does not depend on x_{j} since the edge i–j is not in \overline{G} and, similarly, f_{j}^{j}(x) does not depend on x_{i}. Hence we get

f^{i} ∘ f^{j}(x) = f^{i}(x_{1}, …, f_{j}^{j}(x), …, x_{n}) = (x_{1}, …, f_{i}^{i}(x), …, f_{j}^{j}(x), …, x_{n})

and, similarly,

f^{j} ∘ f^{i}(x) = f^{j}(x_{1}, …, f_{i}^{i}(x), …, x_{n}) = (x_{1}, …, f_{i}^{i}(x), …, f_{j}^{j}(x), …, x_{n}).

Thus, we have f^{i} ∘ f^{j} = f^{j} ∘ f^{i}. □

We illustrate this correspondence with an example. Let n = 3, and let F consist of the single triple of functions f = (f^{1}, f^{2}, f^{3}) with

\begin{aligned}f^{1}(x_{1}, x_{2}, x_{3}) & = (x_{2}, x_{2}, x_{3}), \\ f^{2}(x_{1}, x_{2}, x_{3}) & = (x_{1}, x_{1}, x_{3}), \\ f^{3}(x_{1}, x_{2}, x_{3}) & = (x_{1}, x_{2}, x_{1} + x_{3}). \end{aligned}

Inspection shows that the only edge of K_{3} contained in Φ(F) is 2-3. Hence Φ(F) consists of a graph with three vertices and one edge. Hence its complement is the graph with three vertices and two edges emanating from vertex 1. Therefore, ΨΦ(F) consists of the set of all functions (g^{1}, g^{2}, g^{3}) such that g^{1} is arbitrary, g^{2} does not depend on the third variable, and g^{3} does not depend on the second variable.

Corollary 2.3. With notation as in the above theorem, we have

(1)

ΦΨ(G) = G,

for all graphs G. (2)

ΦΨΦ(F) = Φ(F),

and, in particular,

ΨΦ(ΨΦ(F)) = ΨΦ(F),

for all sets F ∈ F. That is, ΨΦ is a closure operator on the set of n-tuples of local functions on k^{n}.

Proof. The second claim is a standard consequence of the properties of a Galois correspondence. To show the first claim, let i–j be an edge in ΦΨ(G), and suppose that it is not in G. Then i–j ∈ \overline{G}. Recall that

Ψ(G) = L_{1}^{1}(\overline{G}) × ⋯ × L_{1}^{n}(\overline{G}).

Then Ψ(G) contains the function f = (f^{1}, …, f^{n}), such that f^{p} = id for all p ≠ i, j, and

f^{i}(x_{1}, …, x_{n}) = (x_{1}, …, x_{i−1}, x_{i} + x_{j}, x_{i+1}, …, x_{n}),
f^{j}(x_{1}, …, x_{n}) = (x_{1}, …, x_{j−1}, 0, x_{j+1}, …, x_{n}),

that is, f^{i}, resp. f^{j}, changes only the ith, resp. the jth, coordinate. Observe now that f^{i} ∘ f^{j} ≠ f^{j} ∘ f^{i}. This implies that i–j is not in ΦΨ(G), which is a contradiction. □

3. Equivalence Relations On Systems

In this section we consider several equivalence relations on systems. The first one corresponds to the notion of topologically conjugate discrete dynamical systems. Definition 3.1. Two systems f, g : k^{n} ⟶ k^{n} are called isomorphic or dynamically equivalent if there exists a bijective function ϕ : k^{n} ⟶ k^{n} such that g ∘ ϕ = ϕ ∘ f.

It is easy to see that two systems are isomorphic if and only if they have isomorphic state spaces, that is, the function ϕ induces an isomorphism of directed graphs. This definition of dynamic equivalence has the property that powers of f and of g are also isomorphic, since g^{s}∘ϕ = g^{s−1}∘ϕ∘f = ⋯ = ϕ∘f^{s}. So the dynamic behavior (under iteration) of f and g is the same. Lemma 3.2. If f : k^{n} ⟶ k^{n} is a system, and ϕ : k^{n} ⟶ k^{n} is an invertible function, then the systems f and ϕ^{−1} ∘ f ∘ ϕ are dynamically equivalent.

We now define a weaker equivalence relation on the whole collection of systems {f : k^{n} ⟶ k^{n} | n ∈ ℕ}, which we call stable equivalence. Then we show that stable equivalence of systems corresponds to the existence of a digraph isomorphism between the limit cycles in the respective state spaces. Definition 3.3. Let f : k^{n} ⟶ k^{n} be a system with state space S_{f} and with the sub-digraph L_{f} of limit cycles. Then x ∈ k^{n} is a vertex in L_{f} if and only if there exists a positive integer m such that f^{m}(x) = x. Let m be the smallest integer such that f^{m}(x) = x for all x ∈ L_{f}. We call m the order of the system f, denoted Order(f). Lemma 3.4. The integer Order(f) exists.

Proof. For each x ∈ L_{f} there is an integer m_{x} such that f^{m_{x}}(x) = x. Hence the least common multiple of all m_{x} is an integer m such that f^{m}(x) = x for all x. □

Definition 3.5. Let f : k^{r} ⟶ k^{r} and g : k^{m} ⟶ k^{m} be two systems. Then f and g are called stably equivalent if there exist maps p : k^{r} ⟶ k^{m} and q : k^{m} ⟶ k^{r}, a positive integer s prime to lcm(Order(f), Order(g)), and a nonnegative integer n, such that the diagram

[figure: k^{r}; k^{m}; p; k^{r}; k^{m}; p; k^{r}; q; k^{r}; q; f^{s}; g^{s}; f^{s}]

commutes, and q ∘ p = f^{n}, p ∘ q = g^{n}.

We postpone the proof that stable equivalence is an equivalence relation until after the following theorem. Definition 3.6. Let f_{1}, f_{2} be systems with state spaces S_{f_{i}} and sub-digraphs of limit cycles L_{f_{i}}. We call f_{1} and f_{2} stably isomorphic if there exists a digraph isomorphism between L_{f_{1}} and L_{f_{2}}.

It is clear that stable isomorphism is an equivalence relation. Theorem 3.7. Two systems f and g are stably equivalent if and only if they are stably isomorphic.

Proof. First assume that f and g are stably equivalent, that is, there are maps p, q, and a positive integer s prime to lcm(Order(f), Order(g)) and a non-negative integer n, such that g^{s}p = pf^{s}, qg^{s} = f^{s}q, and qp = f^{n}, pq = g^{n}.

Let a := Order(f), b := Order(g), lcm(a, b) = a′b = ab′ for some integers a′, b′. Let rs + t · lcm(a, b) = 1 for some positive integer r. We have x ∈ L_{f} if and only if f^{a}(x) = x. Similarly, x ∈ L_{g} if and only if g^{b}(x) = x.

Given x ∈ L_{f}, we have

g^{sa′b}p(x) = (g^{s})^{a′b}p(x) = p(f^{s})^{ab′}(x) = p(f^{a})^{sb′}(x) = p(x).

Hence p(x) ∈ L_{g}, so that p induces a set map

P : L_{f} ⟶ L_{g}.

This map is also a morphism of digraphs. To show this, let x ∈ L_{f} so that f^{a}(x) = x. Then

P f(x) = pf^{rs+tab′}(x) = pf^{rs}(x) = g^{rs}p(x) = g^{rs+ta′b}p(x) = gP (x),

since p(x) ∈ L_{g} and g^{b}(p(x)) = p(x). But P f = gP on L_{f} implies that P : L_{f} ⟶ L_{g} is a morphism of digraphs.

Note that f^{n} is a bijection on L_{f} for all n. From the definition of stable equivalence we obtain an n such that qp = f^{n}. Hence P : L_{f} ⟶ L_{g} is injective and Q : L_{g} ⟶ L_{f} is surjective. Similarly P is surjective so that P is an isomorphism of digraphs. This shows that f and g are stably isomorphic.

Conversely, assume that f and g are stably isomorphic, with a digraph isomorphism

P : L_{f} ⟶ L_{g}.

From each limit cycle in L_{f} choose a vertex as representative, with {x_{1}, x_{2}, …} the full set of representatives. Similarly, choose representatives {y_{1}, y_{2}, …} for the limit cycles of L_{g}, such that P (x_{i}) = y_{i}. The restriction of P to each limit cycle gives an isomorphism of digraphs

p_{i} : {x_{i}, f(x_{i}), f^{2}(x_{i}), …} ⟶ {P (x_{i}) = y_{i}, g(y_{i}), g^{2}(y_{i}), …},

with

p_{i}f^{t}(x_{i}) = g^{t}p_{i}(x_{i})

for all t.

We now construct a function p : k^{n} ⟶ k^{m} as follows. Let x ∈ S_{f}. There exists a unique minimal s ∈ ℕ_{0} such that f^{s}(x) ∈ L_{f}. Let r be minimal such that f^{s}(x) = f^{r}(x_{i}) for a unique representative x_{i}. Then define

p(x) = p_{i}f^{r−s}(x_{i}),

where f^{r−s}(x_{i}) is to be taken in L_{f} if r − s is negative. Note that f is bijective on L_{f}, so that negative exponents r − s make sense. We have s = 0 if and only if x ∈ L_{f}. Observe that

pf(x) = p_{i}f^{r−s+1}(x_{i}).

Let a = Order(f). By adding a suitable multiple ta of a to r − s we can force the exponent of f in the definition of p(x) to be positive. Observe that p(x) is an element of L_{f}.

We define q : k^{m} ⟶ k^{n} similarly, using the inverse of P. We need to verify that p and q satisfy the conditions of Definition 3.5, making f and g stably equivalent.

First of all, for x ∈ k^{n}, we have that p(x) = p_{i}f^{j}(x_{i}) for some i, j. Then

gp(x) = gp_{i}f^{j}(x_{i}) = p_{i}f^{j}f(x_{i}) = pf(x).

A similar argument shows that fq = qg. This proves that p and q satisfy the first condition of a stable equivalence, with s = 1.

In order to verify the second condition, we need to find a nonnegative integer n such that qp = f^{n} and pq = g^{n}. We have

p(x) = p_{i}f^{r−s}(x_{i}) = g^{r−s}p_{i}(x_{i}) = g^{r−s}(y_{i}).

Then, for each x,

qp(x) = q_{i}g^{r−s}(y_{i}) = f^{r−s}q_{i}(y_{i}) = f^{r−s}(x_{i}).

Hence

f^{s}qp(x) = f^{r}(x_{i}) = f^{s}(x)

and

qp(x) = f^{ta−s+s}qp(x) = f^{ta}(x)

for all sufficiently large t (such that ta ≥ s). Take the largest t occuring for all x ∈ S_{f} (and all y ∈ S_{g}) and define n = ta. Then n satisfies the second condition for stable equivalence. □

The proof of this theorem implies the following corollary. Corollary 3.8.

(1) Stable equivalence is an equivalence relation.

(2) Using s = 1 in the definition of stable equivalence leads to the same

equivalence relation. Remark 3.9. Note that stable equivalence is an equivalence relation on the collection of ALL systems, without restrictions on the dimension. Furthermore, observe that stable equivalence with n = 0 (and s = 1) is the same as dynamic equivalence.

4. Affine Systems

In this section we give some results on linear and affine systems, with explicit calculations in dimension two. First we consider linear systems, that is, systems f : k^{n} ⟶ k^{n}, which are linear transformations.

For linear systems we can therefore immediately answer the question about a possible canonical form. By Lemma 3.2 systems represented by similar matrices have isomorphic state spaces. Hence we can use the rational canonical form of the representing matrix as the normal form of a linear system.

We derive a necessary condition for a finite dynamical system to be linear. Proposition 4.1. Let f : k^{n} ⟶ k^{n} be an affine finite dynamical system. Then the underlying set of the digraph of limit cycles L_{f} is isomorphic to k^{t}, for some t ≤ n. In particular, it has 2^{t} elements.

Proof. Let a := Order(f) be the order of f. Then x ∈ L_{f} if and only if f^{a}(x) = x. Assume first that f is linear. Then L_{f} is the eigenspace for the eigenvalue 1 of f^{a}, a subspace of dimension t.

If f is affine then f^{a} is also affine. Let f^{a}(x) = g(x) + b with g linear and b ∈ k^{n}. We have x ∈ L_{f} iff g(x) + b = x iff (g − 1)(x) = −b. But the preimage of −b under the linear map (g − 1) is an affine subspace and has 2^{t} elements. □

The following result is based on an observation by C. Greither [5]. Proposition 4.2. Let n ≥ 1 be an integer, and t a divisor of 2^{n} − 1. Then there exists a linear system f : k^{n} ⟶ k^{n} whose state space S_{f} consists of the fixed point 0 = (0, 0, …, 0), together with (2^{n} − 1)/t cycles of length t. In particular, for every n there exists a linear system k^{n} ⟶ k^{n} with a limit cycle of length 2^{n} − 1.

Proof. The Galois field F_{2^{n}} is an n-dimensional vector space over k = F_{2}, hence is isomorphic to k^{n} as a k-vector space. The multiplicative group F_{2^{n}}^{∗} is cyclic of order 2^{n} − 1. For each divisor t of 2^{n} − 1 there exists a (unique) subgroup of F_{2^{n}}^{∗} of order t. Let a be a generator of this subgroup. Then the system

f : k^{n} ⟶ k^{n},

given by multiplication by a is linear and invertible. Furthermore, Order(f) = t.

For any linear system 0 is a fixed point, and for an invertible system it is a one element component. The proposition now follows by observing that the other components of S_{f} correspond to the distinct cosets of ⟨a⟩ in F_{2^{n}}^{∗}, whose element are cyclically permuted under multiplication by a. □

This proposition shows that, for a given dimension n, there exist linear systems with limit cycles of maximal length. This makes it problematic to use limit cycle length for defining chaotic systems in the finite case.

For the rest of this section we investigate linear and affine systems of dimension 2, that is, functions

f : k^{2} ⟶ k^{2},

which are of the form Ax + b, for a (2 × 2)-matrix A and b ∈ k^{2}. We treat the two-dimensional case enumeratively, and intend it to be mostly illustrative. It shows a rich interplay between the linear algebra and the combinatorics, which merits a more thorough investigation.

First we consider the case b = 0. There are 16 (2 × 2)-matrices over k, which have the following 6 rational canonical forms:

(A) ( \begin{matrix}0 & 0 \\ 0 & 0 \end{matrix} ) (B) ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) (C) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) (D) ( \begin{matrix}0 & 1 \\ 0 & 1 \end{matrix} )

(E) ( \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ) (F) ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) .

An inspection of the state spaces shows that these six systems are pairwise not dynamically equivalent. Inspection also shows that only the systems (A) and (E) are stably isomorphic, both having a graph of limit cycles consisting of a single vertex. Thus, there are five stable equivalence classes of linear systems.

In dimension 2 it is feasible to simply enumerate all possible state spaces for general systems, of which there are 18, listed in Figure 1.

These 18 isomorphism classes fall into 11 stable equivalence classes, depicted in Figure 2.

We now consider affine systems. A straightforward verification shows that the linear systems B, C, and D give rise to new isomorphism classes of systems by choosing b = (0, 1)^{t} in all three cases. In the labeling above, Bx + b is a system of type (17), Cx + b gives type (13), and Dx + b results in (15).

FINITE DYNAMICAL SYSTEMS 13

Figure 1. Possible State Spaces for Two-dimensional Systems. Figure 2. Representatives of Stable Equivalence Classes.

Of the 11 stable equivalence classes, we see that all but two are realized by affine systems.

References

[1] C. L. Barrett, R. Thord, and C. M. Reidys, Knowledge and Networks in a Dynamical Economy, in Simulations in Decision Making for Socio-technical Systems, M. Beckman and B. Johansson and F. Snickars and R. Thord (eds.), Springer Verlag, New York, 1998.

[2] C. L. Barrett, and C. M. Reidys, Elements of a Theory of Simulation, I: Sequential CA Over Random Graphs, Appl. Math. and Comput. 98, pp. 241–259, 1999.

[3] C. L. Barrett, H. S. Mortveit, and C. M. Reidys, Elements of a Theory of Simulation II: Sequential Dynamical Systems, Appl. Math. and Comp. 107 (2–3), pp. 121–136, 1999.

[4] C. L. Barrett, H. S. Mortveit, and C. M. Reidys, Elements of a Theory of Simulation III, preprint, 1999.

[5] C. Greither, private communication.

Department of Mathematical Sciences, New Mexico State University, Las Cruces, NM 88003, USA

E-mail address: reinhard@nmsu.edu

Mathematisches Institut, Universität München, Theresienstr. 39, D-80333 München, Germany

E-mail address: pareigis@rz.mathematik.uni-muenchen.de