Linear dynamical systems over finite rings II

Last week, we studied some properties of the following finite linear dynamical system

$\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 $x := (x_1, x_2)$ lives in $\mathbb{Z}_4^2$ , where $\mathbb{Z}_4 := \{0, 1, 2, 3\}$ . 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 rewrite the state update equation as $x^+ = A x$ .

In the 1st installment, we obtained qualitative information about the dynamical system from visual inspection of its state transition diagram, which is clearly impossible for finite dynamical systems with state sets of sufficiently large cardinality. Thus, in this post, we will study the same dynamical system using only algebra. The goal is to see how far we can go without knowing what the state transition diagram looks like.

Before we embark on this journey, please take a good look at the addition and multiplication tables of the finite ring $(\mathbb{Z}_4, +, \times)$

__________

Time reversibility

Suppose there exists a matrix $B \in \mathbb{Z}_4^{2 \times 2}$ such that $B A = I$ , where $I \in \mathbb{Z}_4^{2 \times 2}$ is the identity matrix. Then, left-multiplying both sides of the state update equation by $B$ , we obtain $B x^+ = B A x = I x$ , which is equivalent to $x = B x^+$ . Hence, if matrix $B$ exists, we can propagate the state backwards in time, and the dynamical system is time reversible.

Matrix equation $B A = I$ can be written as

$\left[\begin{array}{cc} b_{11} & b_{12}\\ b_{21} & b_{22}\\\end{array}\right] \left[\begin{array}{cc} 2 & 3\\ 1 & 0\\\end{array}\right] = \left[\begin{array}{cc} 1 & 0\\ 0 & 1\\\end{array}\right]$

and, vectorizing both sides, we obtain a linear system of equations $(A^T \otimes I)\, \mbox{vec}(B) = \mbox{vec}(I)$ , i.e., we have

$\left[\begin{array}{cccc} 2 & 0 & 1 & 0\\ 0 & 2 & 0 & 1\\ 3 & 0 & 0 & 0\\ 0 & 3 & 0 & 0\\\end{array}\right] \left[\begin{array}{c} b_{11}\\ b_{21}\\ b_{12}\\ b_{22}\\\end{array}\right] = \left[\begin{array}{c} 1\\ 0\\ 0\\ 1\\\end{array}\right]$

From the 4th and last equation, $3 b_{21} = 1$ , we get $b_{21} = 3$ , as $3 \times 3 = 1$ in modulo 4 arithmetic. From the 3rd equation, $3 b_{11} = 0$ , we get $b_{11} = 0$ . The 2nd equation, $2 b_{21} + b_{22} = 0$ , becomes then $2 + b_{22} = 0$ , which yields $b_{22} = 2$ . Finally, the 1st equation, $2 b_{11} + b_{12} = 1$ , becomes $b_{12} = 1$ . Let us define $A^{-1} := B$ . Hence, we have

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

which is the (left and right) inverse of matrix $A$ . We then have the (backwards in time) state update equation $x = A^{-1} x^+$ . If we draw the state transition diagram for this linear dynamical system, we obtain the diagram we obtained last week, but with the direction of the arrows reversed. If you do not believe me, then define $g (x) := A^{-1} x$ and run the following Python script:

# define function g
def g (x):
    g1 = x[1] % 4
    g2 = (3 * x[0] + 2 * x[1]) % 4
    return (g1, g2)

print "State transitions:\n"
for x1 in [0,1,2,3]:
    for x2 in [0,1,2,3]:
        print "g(%d,%d) = (%d,%d)" % (x1, x2, g((x1,x2))[0], g((x1,x2))[1])

__________

Fixed points

As mentioned last week, we can find fixed points of the dynamical system $x^+ = A x$ by solving the equation $A x = x$ . Since $-1 = 3$ in modulo 4 arithmetic, let us add $3 x$ to both sides of the equation, which yields $(A + 3 I) x = 0_2$ , 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]$

and, since one of the equations is redundant, we are left with $x_1 + 3 x_2 = 0$ , which is equivalent to $x_1 = x_2$ . The set of fixed points is, thus,

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

Fixed points are periodic points of period equal to 1. Let us now find periodic points of period greater than 1.

__________

Periodic points of period equal to 2

To find periodic points of period equal to 2, we must solve the equation $A^2 x = x$ , where

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

Once again, let us add $3 x$ to both sides of the equation, which yields $(A^2 + 3 I) x = 0_2$ , i.e.,

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

and, eliminating the redundant equation, we are left with $2 x_1 + 2 x_2 = 0$ . Since $-2 = 2$ in modulo 4 arithmetic, we finally obtain the equation $2 x_1 = 2 x_2$ . If we were solving equations over $\mathbb{R}$ , we could just multiply both sides of $2 x_1 = 2 x_2$ by $1 / 2$ and obtain $x_1 = x_2$ . However, we are working with the finite ring $(\mathbb{Z}_4, +, \times)$ , for which the element 2 does not have a multiplicative inverse! Let us write the equation for various values of $x_2$ :

if $x_2 = 0$ , then we obtain the equation $2 x_1 = 0$ , which yields $x_1 \in \{0, 2\}$ . We thus have points $(0, 0)$ and $(2,0)$ .

if $x_2 = 1$ , then we obtain the equation $2 x_1 = 2$ , which yields $x_1 \in \{1, 3\}$ . We thus have points $(1, 1)$ and $(3,1)$ .

if $x_2 = 2$ , then we obtain the equation $2 x_1 = 0$ , which yields $x_1 \in \{0, 2\}$ . We thus have points $(0, 2)$ and $(2,2)$ .

if $x_2 = 3$ , then we obtain the equation $2 x_1 = 2$ , which yields $x_1 \in \{1, 3\}$ . We thus have points $(1, 3)$ and $(3,3)$ .

To summarize, we have eight periodic points of period equal to 2

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

of which, 4 points are fixed points. Removing these fixed points, we are left with 4 periodic points of fundamental period equal to 2

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

We finally conclude that the finite dynamical system under study has two cycles of length equal to 2, namely

$(2,0) \mapsto (0,2) \mapsto (2,0)$

$(3,1) \mapsto (1,3) \mapsto (3,1)$

__________

Periodic points of period equal to 3

To find periodic points of period equal to 3, we must solve the equation $A^3 x = x$ , where

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

Note that $A^3 = A^{-1}$ . Hence, $A^4 = A^{-1} A = I$ , and $A^5 = A$ . In order to solve equation $A^3 x = x$ , let us (yet once again) add $3 x$ to both sides of the equation, which yields $(A^3 + 3 I) x = 0_2$ , i.e.,

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

and, eliminating the redundant equation, we are left with $3 x_1 + x_2 = 0$ . Since $-1 = 3$ in modulo 4 arithmetic, we finally obtain the equation $3 x_1 = 3 x_2$ . Fortunately, element 3 has a multiplicative inverse, which is itself (as $3 \times 3 = 1$ ). Multiplying both sides by 3, we obtain $x_1 = x_2$ , an equation we solved already when looking for the fixed points. Since the only solutions of this equation are the four fixed points, we conclude that there are no periodic points of fundamental period equal to 3, i.e., there are no cycles of length 3.

__________

Periodic points of period equal to 4

To find periodic points of period equal to 4, we must solve the equation $A^4 x = x$ . Nevertheless, we know that $A^4 = I$ and, hence, $A^4 x = x$ reduces to $x = x$ , which is satisfied by every $x \in \mathbb{Z}_4^2$ , of course. In other words, every single point in the state set is a periodic point of period equal to 4. Some of them have fundamental period equal to 1, some others have fundamental period equal to 2. Removing from the state set these two sets, we are left with the periodic points of fundamental period equal to 4

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

We finally conclude that the finite dynamical system under study has two cycles of length equal to 4, namely

$(1,0) \mapsto (2,1) \mapsto (3,2) \mapsto (0,3) \mapsto (1,0)$

$(3,0) \mapsto (2,3) \mapsto (1,2) \mapsto (0,1) \mapsto (3,0)$

The hunt for periodic points is over. Since $A^5 = A$ , equation $A^5 x = x$ reduces to equation $A x = x$ , which we already solved. Likewise, $A^6 x = x$ boils down to $A^2 x = x$ , which we already solved too. We have found all the cycles.

__________

Concluding remarks

All the qualitative information about the finite dynamical system that we were able to obtain by taking a look at the state transition diagram can instead be obtained algebraically.

Last week, we found the solutions of the equations $A^k x = x$ using sheer brute force, i.e., via exhaustive search over the entire state set. By contrast, in this post we actually did solve the equations using algebra. Intuitively, the latter should be computationally cheaper. If this is correct, then the question is: how much cheaper?

About these ads

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

This entry was posted on July 28, 2011 at 01:02 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 II”

Michael Knap Says:
July 28, 2011 at 07:10 | Reply
Great work!

It is coincidental that just a few weeks ago I was presenting my thesis about linear dynamical systems with uncertainty. The work I was showing was over the reals, and the algebraist in the group asked about the possibility of such things over finite fields.

It is perfect timing that your posts surfaced in my blog reading!

I do have a question. In the last part of algebraically finding periodic points with period=2, you say “We finally conclude that the finite dynamical system under study has two cycles of length equal to 2, namely …” My question is how did you come to this conclusion from the known set of points {(2,0),(0,2),(3,1),(1,3)}?

Well, I seem to have answered my own question in writing out this reply; but, just to be sure, you simply examined the iteration of the system using the found points as input?

I can’t wait to read your next post. A big interest of mine is computation, and you seem to be heading in that direction.
- Rod Carvalho Says:
  July 28, 2011 at 17:39 | Reply
  The work I was showing was over the reals, and the algebraist in the group asked about the possibility of such things over finite fields.
  
  Take a look at this thesis: Monomial Dynamical Systems over Finite Fields (2005).
  
  I do have a question. In the last part of algebraically finding periodic points with period=2, you say “We finally conclude that the finite dynamical system under study has two cycles of length equal to 2, namely …” My question is how did you come to this conclusion from the known set of points {(2,0),(0,2),(3,1),(1,3)}?
  
  Solving $A^2 x = x$ , I got the eight periodic points of period equal to 2. Removing the four fixed points, I was left with the four periodic points of fundamental period equal to 2, which are
  
  $\{ (2,0), (3,1), (0,2), (1,3)\}$ .
  
  Let us pick point $(2,0)$ and propagate it two steps forwards in time using $x^+ = A x$ . Then, we obtain a cycle of length equal to 2
  
  $(2,0) \mapsto (0,2) \mapsto (2,0)$
  
  and, removing $(2,0)$ and $(0,2)$ from the set of periodic points of fundamental period equal to 2, we are left with points $(3,1)$ and $(1,3)$ which must form a cycle of length 2 as well, namely
  
  $(3,1) \mapsto (1,3) \mapsto (3,1)$ .
  
  Now, I need to find some software that solves linear systems of equations modulo $m$ . The cycle-finding algorithm should be easy to implement.

Rod Carvalho

Linear dynamical systems over finite rings II

Like this:

2 Responses to “Linear dynamical systems over finite rings II”

Leave a Reply Cancel reply

Follow “Rod Carvalho”