Linear dynamical systems over finite rings

Consider the following linear dynamical system (example 3.4 in [1])

$\left[\begin{array}{cc} x_1^+\\ x_2^+\end{array}\right] = \left[\begin{array}{cc} 2 & 3\\ 1 & 0\\\end{array}\right] \left[\begin{array}{c} x_1 \\ x_2\\\end{array}\right]$

where the state vector $x := (x_1, x_2)$ travels in the finite state space $\mathbb{Z}_4^2$ , where $\mathbb{Z}_4 := \{0, 1, 2, 3\}$ . Since the state space is finite, let us henceforth call it state set. Let $A \in \mathbb{Z}_4^{2 \times 2}$ be defined by

$A := \left[\begin{array}{cc} 2 & 3\\ 1 & 0\\\end{array}\right]$

so that we can write the state update equation in the more compressed form $x^+ = A x$ . For simplicity, let us introduce function $f : \mathbb{Z}_4^2 \to \mathbb{Z}_4^2$ defined by $f (x) := A x$ . Hence, we have $x^+ = f (x)$ .

Do note that we are working with the finite ring $(\mathbb{Z}_4, +, \times)$ , whose addition and multiplication tables are as follows

and, therefore, when we update each state via $x_i^+ = a_{i1} x_1 + a_{i2} x_2$ , we use addition and multiplication modulo 4.

When we study discrete-time dynamical systems over $\mathbb{R}$ , we are usually interested in finding equilibrium points, fixed points and limit cycles. For dynamical systems over a finite ring, what are the properties of interest? And how can one study them?

__________

State transition graph

The state set, $\mathbb{Z}_4^2$ , which has $4^2 = 16$ elements, is a subset of the 2-dimensional integer lattice $\mathbb{Z}^2$ , as depicted below

Computing $x^+ = f(x)$ for each $x$ in the state set and forming ordered pairs $(x, f(x))$ , we can build the state transition graph, whose vertex set is the state set $\mathbb{Z}_4^2$ , and whose edge set is the set $\{(x, f(x))\}_{x \in \mathbb{Z}_4^2}$ . A pictorial representation of this graph is shown below

Note that the out-degree of each vertex is 1. This is due to the fact that function $f$ maps states to states, not states to sets of states. In other words, we do not allow non-determinism.

Visual inspection of the state transition diagram allows us to conclude that, interestingly, the in-degree of each vertex is also 1, i.e., function $f$ is injective and surjective. Thus, $f$ is invertible, which means that the dynamical system we are studying is time reversible! Switch the direction of each arrow in the diagram, and we obtain a new state transition diagram. Hence, if are given the state at a certain time step, we can determine the entire history of the system, both past and future!

A state $x$ is a fixed point if $f(x) = x$ , i.e., if $x^+ = x$ . Taking a look at the state transition diagram, we see that there are four vertices with self-loops, which means that the system has four fixed points

$\{ (0,0), (1,1), (2,2), (3,3)\}$ .

If the system starts at a fixed point $x$ , it will remain there forever

$x \mapsto f(x) = x \mapsto f(x) = x \mapsto \dots$

and, thus, the set of all fixed points is an invariant set. Note that a fixed point is a periodic point of period equal to 1.

Observing the state transition diagram again, we notice the existence of loops of various lengths. We have two loops of length equal to 2 and two loops of length equal to 4, depicted below in blue and magenta, respectively

Do note, however, that we also have four loops of length equal to 1, which are the self-loops corresponding to the fixed points, but we already mentioned those.

For the dynamical system under study, we could obtain qualitative information about its behavior by visual inspection of its state transition diagram. Suppose, for example, that we want to study a dynamical system whose state set is $\mathbb{Z}_4^{16}$ , which has over four billion states. It is evident that drawing diagrams and counting loops is an approach that does not scale! Can one use Algebra to obtain qualitative information about the dynamical system being studied?

__________

Finding periodic points

If state $x$ is a fixed point, then $f (x) = x$ or, equivalently, $A x = x$ , as we defined $f (x) := A x$ . Hence, we can find fixed points by solving the equation $A x = x$ .

A state $x$ is a periodic point of period equal to $k$ if $f^{(k)} (x) = x$ , where $f^{(k)} = f \circ f^{(k-1)}$ and $f^{(1)} = f$ . Since $f (x) := A x$ , we have that $f^{(k)} (x) = A^k x$ . Thus, we can find periodic points of period equal to $k$ by solving the equation $A^k x = x$ .

However, do note that fixed points, i.e., periodic points of period equal to 1, are also periodic points of period equal to 2, equal to 3, equal to 4, etc. Therefore, let the fundamental period be the smallest natural number $k$ for which $A^k x = x$ . For example, the set of all periodic points of fundamental period equal to 2 is

$\{x \in \mathbb{Z}_4^2 \mid A^2 x = x \land A x \neq x\}$

and the set of all periodic points of fundamental period equal to 3 is

$\{x \in \mathbb{Z}_4^2 \mid A^3 x = x \land A x \neq x\}$ .

However, the periodic points of period equal to 2 are also periodic points of period equal to 4. Hence, the set of periodic points of fundamental period equal to 4 is

$\{x \in \mathbb{Z}_4^2 \mid A^4 x = x \land A^2 x \neq x \land A x \neq x\}$ .

But, how do we solve equations of the form $A^k x = x$ over the ring $(\mathbb{Z}_4, +, \times)$ ? A possibility is to search the whole state set and find the states for which the equations hold. That is precisely what the following Python script does:

# define function f
def f (x):
    f1 = (2 * x[0] + 3 * x[1]) % 4
    f2 = x[0] % 4
    return (f1, f2)

# create state set
X = []
for x1 in [0,1,2,3]:
    for x2 in [0,1,2,3]:
        X.append((x1,x2))

print "State transitions:\n"
for x in X:
    x1, x2, f1, f2 = x[0], x[1], f(x)[0], f(x)[1]
    print "f(%d,%d) = (%d,%d)" % (x1, x2, f1, f2)

# find periodic points of fundamental periods 1, 2, 3, 4
PP1, PP2, PP3, PP4 = [], [], [], []
for x in X:
    if f(x) == x:
        PP1.append(x)
    elif f(f(x)) == x:
        PP2.append(x)
    elif f(f(f(x))) == x:
        PP3.append(x)
    elif f(f(f(f(x)))) == x:
        PP4.append(x)

print "\nLists of periodic points:\n"
print "\nFundamental period equal to 1:\n %s" % PP1
print "\nFundamental period equal to 2:\n %s" % PP2
print "\nFundamental period equal to 3:\n %s" % PP3
print "\nFundamental period equal to 4:\n %s" % PP4

The output of this script is the following:

State transitions:

f(0,0) = (0,0)
f(0,1) = (3,0)
f(0,2) = (2,0)
f(0,3) = (1,0)
f(1,0) = (2,1)
f(1,1) = (1,1)
f(1,2) = (0,1)
f(1,3) = (3,1)
f(2,0) = (0,2)
f(2,1) = (3,2)
f(2,2) = (2,2)
f(2,3) = (1,2)
f(3,0) = (2,3)
f(3,1) = (1,3)
f(3,2) = (0,3)
f(3,3) = (3,3)

Lists of periodic points:

Fundamental period equal to 1:
[(0, 0), (1, 1), (2, 2), (3, 3)]

Fundamental period equal to 2:
[(0, 2), (1, 3), (2, 0), (3, 1)]

Fundamental period equal to 3:
[]

Fundamental period equal to 4:
[(0, 1), (0, 3), (1, 0), (1, 2), (2, 1), (2, 3), (3, 0), (3, 2)]

Note that there are no periodic points of fundamental period equal to 3, as a quick glance at the state transition diagram will tell.

__________

References

[1] O. Colón-Reyes, A. Jarrah, R. Laubenbacher, B. Sturmfels, Monomial Dynamical Systems over Finite Fields, May 2006.

About these ads

Tags: Discrete Dynamical Systems, Finite Dynamical Systems, Finite Rings, Fixed Points, Periodic Points

This entry was posted on July 18, 2011 at 20:15 and is filed under Algebra, Dynamical Systems. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Linear dynamical systems over finite rings”

SteveBrooklineMA Says:
July 24, 2011 at 12:56 | Reply
Nice! and I think you could do more math here. We know $f$ is bijective because $A$ has an inverse:

$A^{-1}= \left[\begin{array}{cc} 0 & 1\\ 3 & 2\end{array}\right]$ .

Also, we can simply solve $A x = x$ , i.e.

$\left[\begin{array}{cc} 2 & 3\\ 1 & 0\end{array}\right] \left[\begin{array}{c} x_1\\ x_2 \end{array}\right] = \left[\begin{array}{c} x_1\\ x_2 \end{array}\right]$ , i.e.

$\left[\begin{array}{cc} 1 & 3\\ 1 & 3\end{array}\right] \left[\begin{array}{c} x_1\\ x_2 \end{array}\right] = \left[\begin{array}{c} 0\\ 0 \end{array}\right]$

The solution is just $x_1 = x_2$ , giving $(0,0)$ , $(1,1)$ , $(2,2)$ and $(3,3)$ . Similarly, $A^2x = x$ gives $2 x_1 = 2 x_2$ , so we get $(0,2)$ , $(2,0)$ , $(1,3)$ and $(3,1)$ , and also of course the 4 previous ordered pairs. I think an orbit of size 3 is impossible since 3 and 4 are relatively prime. Finally, since $A^4 = I$ , all 16 ordered pairs satisfy $A^4 x = x$ .
- Rod Carvalho Says:
  July 24, 2011 at 17:53 | Reply
  Nice! and I think you could do more math here.
  
  Indeed! That will be part II.
  
  Thanks for your comment. I edited it slightly. I will take the liberty of sending you an email when the 2nd installment is posted.

Rod Carvalho

Linear dynamical systems over finite rings

Like this:

2 Responses to “Linear dynamical systems over finite rings”

Leave a Reply Cancel reply

Follow “Rod Carvalho”