矩阵环的迭代图

Contents

Chinese Abstract i

English Abstract ii

1Introduction 1

1.1Motivation and Background (1)

1.2 Preliminaries (3)

1.3 Summary of Results (4)

2 The k-th Iteration Graph of M atrix Ring M2(Zp) 5

2.1 The subgraphs induced by D(M2(Zp)) (5)

2.2 The subgraphs induced by U(M2(Zp)) (8)

3 The k-th Iteration Graph of Formal M atrix Ring M2(Zp;0)18

3.1 Introduction (18)

3.2 The subgraphs induced by D(M2(Zp; 0)) (19)

3.3 The subgraphs induced by U(M2(Zp; 0)) (21)

4 The Isomorphism Problem of k-th Iteration Graph 27

4.1 Introduction (27)

4.2 The Isomorphism Problem (27)

Bibliography 31 Publications 36 Acknowledgement 37

iv

万方数据

万方数据

Chapter 1

Introduction

1.1M o t i v a t i o n a n d B a c k g r o u n d

Iteration is a natural phenomenon; it can be seen everywhere, and the study of iterations has an extremely important significance. Dynamical system is a subject to study state changes over time. Some famous examples of finite dynamical systems include Boolean networks and cellular automata, which have found broad applica-tions in computer science, engineering, and more recently, computational biology.

In recent decades, scholars also have interest in dynamical systems over rings.

In 1975, E.D. Sontag studied some problems appearing in the extension of the theory of linear dynamical systems to the case in which parameters are taken from noncommutative rings in [29]. Fixed Points in dynamical systems are studied in [3,4,6]. In particular, for finite field F2, E. Delgado-Eckert introduced cycle numbers in [9]. Monomial dynamical systems over finite fields have been studied in [38] from the viewpoint of graph theory, they gave formulas for the number of periodic points with period r and for that of cycles with length r respectively.

Let f = (fi, f'2, ? ? ?,fn)：F^, n >1be a finite dynamical system, where Fq is a finite field, |F g|= q,F? is the vector space of dimension n over Fq,and fi are its coordinate functions. In the case that all fi are linear polynomials without constant term, the finite dynamical system f can be represented as a matrix. Let S be a group or ring, the k-th iteration graph of S is a digraph r(S, k) defined on the elements of S and with an edge from a vertex a to a vertex b iff ak =b,where k is

1

万方数据