# Dynamics of Endomorphism of Finite Abelian Groups

Authors: Zhao Jinxing; Nan Jizhu
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

We study the dynamics of endomorphisms on a finite abelian group. We obtain the automorphism group for these dynamical systems. We also give criteria and algorithms to determine whether it is a fixed point system.


---

## Body

## 1. Introduction

A discrete dynamical system is consisting of a pairX,f, where X is a nonempty set and f:X→X is a function. The functional graph of X,f is a directed graph with vertex set X and an arrow from x to y if and only if fx=y. We denote the functional graph of X,f by GX,f.Finite discrete dynamical systems appeared in engineering, control systems computer science, and genetic networks; see [1, 2]. One of the most important examples of discrete dynamical systems is given by Fqn,f, where Fqn is the vector space over a finite field Fq and f is a linear transformation. The structure these dynamical systems can be described by the elementary divisors of the corresponding matrix; see [3, 4]. By using the same method, Brown and Vaughan [5] studied the cycle structure of linear dynamical system over Zn. Bach and Bridy [6] gave an upper and a lower bound for the distinct number of functional graph defined by affine mapping over finite dimensional linear space over finite fields. But the study of linear dynamical systems over a general finite commutative ring R has difficulties since the factorization of polynomials in Rx is not unique. Brown and Vaughan [5] showed that Rn can be decompose into Rn=ker⁡fk⊕Im⁡fk by Fitting’s Lemma and Rn,f is the product of the dynamical systems induced on ker⁡fk and Im⁡fk. They also provided an algorithm to compute the minimal positive integer k in the above decomposition, but the algorithm is not efficient. Xu and Zou [7] obtained an efficient algorithm to compute k under a reasonable assumption on the size of the ring R. Deng [8] gave a criterion to determine whether a linear dynamical system is over the ring of integer modulo m.LetH be a finite abelian group written additively and EndH be the endomorphism ring of H. In this paper we are interested in the dynamical systems H,f defined by f∈EndH. These dynamical systems have nice structure and were studied in many special cases; see [9]. In this paper we are interested in the case in which X is a finite abelian group H written additive, and f:H→H is an endomorphism of H.The paper is organized as follows. In Section2, we give some notations and basic results on the structure of functional graphs GH,f. In Section 3, we obtain necessary and sufficient conditions for GH1,f1 and GH2,f2. We also give an explicit form of the automorphism group of GH,f. In Section 4, we obtain a criterion to determine whether GH,f is a fixed point system.


## 2. Elementary Properties ofGH,f

Acomponent of a digraph is a maximal connected subgraph of the associated nondirected graph. Theindegree of a vertex a of GX,f, denoted by indegXfa, is the number of directed edges coming into a. TheoutdegreeoutdegXfa of a is the number of directed edges leaving the vertex a. It is clear that the outdegree of any vertex in GX,f is equal to 1, and the indegree of a vertex a is the number of vertices coming to a. A vertex x in GX,f is called a cycle vertex if fkx=x for some positive integers k. In particular, a cycle vertex x is called a fixed point of GX,f if fx=x. Let AtX,f denote the number of t-cycles contained in GX,f. Let AX,f denote the set of positive integers which is the length of the cycle which appeared in GX,f. We need the following results about AtX,f and AX,f. In particular, let dX,f=x∈X:fx=x be the number of fixed point in X,f.Definition 1.
We define a height function on the vertices and components ofGX,f. Let a be a vertex of GX,f. Then we define ha to be the minimal nonnegative integer i such that fia is a cycle vertex in GX,f. We set hD=supa∈D⁡ha if D is a component of GX,f.Definition 2.
For any integeri≥0 and any vertex a∈GX,f, define(1)F0a=a,Fia=b∣fib=a,fi-1bis  not  a  cycle  vertex  ifi>0.Let Ta be the subdigraph of GX,f with the vertices set ⋃i=0∞Fia, and there is a directed arrow from x to y in Ta if fx=y and hx=hy+1. Hence, Ta is a directed tree with root a.LetH be a finite abelian group and f∈EndH. The basic properties of GH,f in this section are proved in some special cases; see [10–14]. We give some basic properties of these digraphs. The proof is similar, but we still present it.Lemma 3.
Letf∈EndH. Then(1)
the indegree of any vertex inGH,f is 0 or kerf.(2)
the number of the vertices with indegreekerf is H/kerf.Proof.
Letx be a vertex with positive indegree. Then y:fy=x is a coset of ker⁡f and they have the same number of elements. The statement (2) follows immediately from (1).We present two results on the tree structure attached to a vertex.Lemma 4.
Letc be a cycle vertex of GH,f. Then Tc≃T0.Proof.
For anyh>0 there exists an unique cycle vertex ch such that fhch=c since c is a cycle vertex. Now if x∈Fh0, we define a map φh:Fh0→Fhc as follows: (2)φhx=x+ch.Then fhx+ch=fhx+fhch=0+c=c. We observe that fh-1x is not a cycle vertex, but fh-1ch is a cycle vertex; then fh-1x+ch is not a cycle vertex since the set of all cycle vertices of GH,f is a subgroup of H. The map φh is well-defined and clearly injective. If b∈Fhc, then b-ch∈Fh0 and φhb-ch=b. φh is also surjective.
Now ifa∈Fh0 and b∈Fh-10 with fa=b, then(3)fφha=fa+ch=fa+fch=b+ch-1=φh-1b.Finally we set φ:T0→Tc: (4)φx=φix,if x∈Fi0. By (3) φ is an isomorphism.Corollary 5.
LetD1 and D2 be two components of GH,f. Then D1≃D2 if and only if they have the same cycle length.Proof.
If follows immediately from Lemma4.Lemma 6.
LetH1, H2 be two finite abelian groups and fi∈EndHi. Let ci∈GHi,fi with positive height. Then Tc1≃Tc2 if and only if Fjc1=Fjc2 for any j≥0.Proof.
Lethi=hTci. First we assume that Tc1≃Tc2 and let φ be an isomorphism. Since the length of the longest directed path in Tci is hi and this path ends at ci, it follows that φc1=c2. Thus, φFjc1⊆Fjc2 and Fjc1=Fjc2.
Conversely, suppose thatFjc1=Fjc2=nj for any j≥0. Then h=h1=h2. We induct on h. The case h=0,1 is trivial. Note that for any vertex a∈GHi,fi with positive height, by Definition 2Fka=x∈Hi:fikx=a=indegHifika. Since fik is also a group homomorphism, by Lemma 3 we have Fka=nk or 0 for any k=0,1,…,h. Let F1c1=a1,…,an1 and F1c2=b1,…,bn1. Let xi=a∈F1c1:hTa=i and yi=b∈F1c2:hTb=i. Since Fkc1=⋃a∈F1c1Fk-1a is a disjoint union for any k>1 and Fka=Fkc1=nk if and only if hTa≥k, one has Fkc1=nk=∑a∈Fk-1c1Fk-1a=nk-1x1+⋯+xk-1. It follows that(5)x0+x1+⋯+xh-1=n1n1x1+⋯+xh-1=n2⋮nh-1xh-1=nh.We derive that xi=ni+1/ni-ni+2/ni+1 for i∈0,1,…,h-2 and xh-2=nh/nh-1. We obtain yi=xi by replacing c1 by c2 in the above arguments. After reordering we may assume that hTai=hTbi for any i. Then Fjai=Fjbi for any fixed i and j. By induction, there exists digraph isomorphism φi:Tai→Tbi. We set φ:Tc1→Tc2, where φc1=c2 and φz=φiz if z∈Tai. Then φ is also a digraph isomorphism. This finishes the proof.


## 3. Automorphism Group ofGH,f

We first show whenGH,f1 is isomorphic to GH,f2 for f1,f2∈EndH.Lemma 7.
LetH1, H2 be two finite abelian groups and fi∈EndHi. Let Di be the component of GHi,fi containing the vertex 0. Then GH1,f1≃GH2,f2 if and only if(1)
D1≃D2;(2)
AtH1,f1=AtH2,f2 for any t.Proof.
It follows immediately from Lemma4 and Corollary 5.Theorem 8.
LetH1, H2 be two finite abelian groups and fi∈EndHi. Then GH1,f1≃GH2,f2 if and only if for any positive integer k(1)
kerf1k=kerf2k;(2)
kerid-f1k=kerid-f2k.Proof.
LetDi be the component of GHi,fi containing the vertex 0. Since x∈ker⁡fik if and only if fijx=0 for some 1≤j≤k, so ker⁡fik=⋃j=0kFjDi is a disjoint union. It follows that ker⁡fik=∑j=0kFjDi for any k≥1. Thus, ker⁡f1k=ker⁡f2k for any k≥1 if and only if FkD1=FkD2 for any k≥1. By Lemma 6, condition (1) is equivalent to (1) of Lemma 7. Note that ker⁡id-fik=x∈Hi:fikx=x=∑t∣ktAt(Hi,fi). Thus, condition (2) is equivalent to (2) of Lemma 7. The proof is finished by Lemma 7.LetH be a finite abelian group. By the structure of finite abelian group, we have (6)H≃⨁p⁡Hp,where p runs over the set of prime divisor of H and Hp is the unique Sylow p-subgroup of H. Moreover, if there is another factorization of H≃⨁⁡Fp in this way, it must have Hp≃Fp for each p.We also recall the product of graphs. LetG1 and G2 be two digraphs. The digraph product G1×G2 is the digraph whose vertices are the set of order pairs a1,a2, where ai is a vertex of Gi. There is a directed edge from a1,a2 to b1,b2 in G1×G2 if and only if there is a directed edge from a1 to b1 in G1 and there is a directed edge from a2 to b2 in G2.Lemma 9.
LetH be a finite abelian group and f∈EndH. Suppose that H=n=∏i=1rpiei is prime factorization. Then (7)GH,f≃GHp1,f×⋯×GHpr,f.Proof.
It follows immediately from the fact thatH=Hp1⊕Hp2⊕⋯⊕Hpr and fHp⊆Hp.Theorem 10.
LetH1, H2 be two abelian groups and fi∈EndHi. Then GH1,f1≃GH2,f2 if and only if GH1p,f1≃GH2p,f2 for any prime p.Proof.
First we assume thatGH1p,f1≃GH2p,f2. By Lemma 9, we have(8)GHi,fi≃GHip1,fi×GHip2,fi×⋯×GHipr,fi.So we obtain GH1,f1≃GH2,f2.
Conversely, suppose thatGH1,f1≃GH2,f2. Let gi,k=id-fik. By Theorem 8, kerf1k=kerf2k and kerg1,k=kerg2,k for any k>0. It follows that kerf1kH1p=kerf2kH2p and kerg1,kH1p=kerg2,kH2p. By Theorem 8 again, GH1p,f1≃GH2p,f2. The proof is finished.Next we would determine the automorphism group of the digraphGH,f. We need the wreath product of groups; see [4, 15]. We rewrite in a simple way. Let G be a group and K be a permutation group on 1,…,n; then the wreath product G≀K is generated by the direct product of n copies of G, together with the elements of K action on these n copies of G. The wreath product is associative, so we write G1≀G2≀⋯≀Gk for G1≀G2≀G3≀⋯≀Gk-1≀Gk.Theorem 11 (see [16]).
LetG be a graph. Suppose that the connected components of G consist of n1 copies and G1,…,nr copies of Gr, where G1,…,Gr are pairwise nonisomorphic. Then (9)AutG≃AutG1≀Sn1⊕⋯⊕AutGr≀Snr,where Sn is the symmetric group on a finite set of order n.By the above Theorem and Corollary5, we have (10)AutGH,f≃⨁i∈AH,f⁡AutXi≀SAiH,f,where Xi is a component of GH,f with cycle length i. Let T be the component containing 0 in GH,f. Sha [9] showed that AutXi≃AutT≀Ci, where Ci is the cyclic group of order i. Thus, (11)AutGH,f≃⨁i∈AH,f⁡AutT≀Ci≀SAiH,f.But he did not obtain the structure of AutT in general. We would determine the automorphism group of T.Lemma 12.
Letc∈GH,f be a vertex with hc>0. Suppose that hTc=r and kerfi=ni for i=1,2,…,r. Then (12)AutTc≃Sn1-n2/n1+1⊕⨁1<i1<i2<⋯<it≤r-1⁡Sn1-n2/n1+1≀Sxi1≀Sxi2≀⋯≀Sxit⊕⨁1=i1<i2<⋯<it≤r-1⁡Sn1≀Sxi1≀Sxi2≀⋯≀Sxit,where xi=ni+1/ni-ni+2/ni+1.Proof.
By induction onr, let yi=a∈F1c:hTa=i for i=0,1,…,r-1. Then nj-nj-1=Fjc=∑a∈F1c,hTa≥j-1Fj-1a=nj-1∑i=j-1r-1yi. Thus,(13)y0+y1+⋯+yr-1=n1n1y1+⋯+yr-1=n2-n1⋮nr-1yr-1=nr-nr-1.We derive that y0=n1-n2/n1+1 and yi=xi for i≥1. Let Ti=Tai for ai∈F1c and hTai=i. By Lemma 6, we have Tu≃Tai if u∈F1c and hTu=i. By Theorem 11 and by induction we have (14)AutTc≃Sy0⊕⨁j=1r-1⁡AutTj≀Sxj≃Sy0⨁j=1r-1⁡⨁1<i1<i2<⋯<it≤j-1⁡Sy0≀Sxi1≀Sxi2≀⋯≀Sxit≀Sxj⊕⨁1=i1<i2<⋯<it≤j-1⁡Sn1≀Sxi1≀Sxi2≀⋯≀Sxit≀Sxj≃Sy0⊕⨁1<i1<i2<⋯<it≤r-1⁡Sy0≀Sxi1≀Sxi2≀⋯≀Sxit⊕⨁1=i1<i2<⋯<it≤r-1⁡Sn1≀Sxi1≀Sxi2≀⋯≀Sxit.Theorem 13.
Suppose thatkerfi=ni and xi=ni+1/ni-ni+2/ni+1. Then (15)AutT0≃Sn1-n2/n1⊕⨁1<i1<i2<⋯<it≤r-1⁡Sn1-n2/n1+1≀Sxi1≀Sxi2≀⋯≀Sxit⊕⨁1=i1<i2<⋯<it≤r-1⁡Sn1≀Sxi1≀Sxi2≀⋯≀Sxit.Proof.
The proof is similar to Lemma12. We induct on r=hT0. Let zi=a∈F1c:hTa=i for i=0,1,…,r-1. Note that z0+z1+⋯+zr-1=n1-n0=n1-1 since 0 is a fixed point. Thus, (16)z0+z1+⋯+zr-1=n1-1n1z1+⋯+zr-1=n2-n1⋮nr-1zr-1=nr-nr-1.It follows that z0=n1-n2/n1 and zi=xi for i≥1. Let Ti=Tai for ai∈F10 and hTai=i. By induction, (17)AutTc≃Sz0⊕⨁j=1r-1⁡AutTj≀Sxj≃Sz0⨁j=1r-1⁡⨁1<i1<i2<⋯<it≤j-1⁡Sy0≀Sxi1≀Sxi2≀⋯≀Sxit≀Sxj⊕⨁1=i1<i2<⋯<it≤j-1⁡Sn1≀Sxi1≀Sxi2≀⋯≀Sxit≀Sxj≃Sn1-n2/n1⊕⨁1<i1<i2<⋯<it≤r-1⁡Sn1-n2/n1+1≀Sxi1≀Sxi2≀⋯≀Sxit⊕⨁1=i1<i2<⋯<it≤r-1⁡Sn1≀Sxi1≀Sxi2≀⋯≀Sxit.


## 4. Fixed Point Systems

A dynamical system is called a fixed point system if its cycle vertices are all fixed points. In this section we would describe whenGH,f is a fixed point system.Definition 14.
LetX1,f1 and X2,f2 be two dynamical systems. A morphism φ:X1,f1→X2,f2 is a map φ:X1→X2 such that f2φ=φf1.Lemma 15.
Letφ:X1,f1→X2,f2 be a morphism of dynamical systems. Suppose that X1,f1 is a fixed point system and φ is surjective. Then X2,f2 is also a fixed point system.Proof.
It follows immediately from Lemma  3.1 in [8].Lemma 16.
LetH be a finite abelian group and f∈EndH. Let fw:H→H,fwx=fx+w be the affine mapping for any w∈H. Then(1)
H,f≃H,fw if and only if H,fw has a fixed point;(2)
H,fw is a fixed point system if and only if it has a fixed point and H,f is a fixed point system.Proof.
It follows immediately from Lemma  3.3 in [8].The following lemma shows why we need to consider the affine system.Lemma 17.
LetH1, H2 be two finite abelian groups and fi∈EndHi. Suppose that φ:H1→H2 is a group homomorphism and is also a surjective morphism of dynamical systems. Let y0 be a fixed point in H2,f2 and K=φ-1y0. Then (K,f1K)≃(ker⁡φ,g), where gx=f1x+f1x0-x0 for some x0∈K.Proof.
It is clear thatK=x0+ker⁡φ is a coset of ker⁡φ. We define ψ:ker⁡φ→K, ψa=a+x0. Then φ is bijective and f1ψa=f1a+x0=f1a+f1x0=ψga. Thus, ψ is an isomorphism of dynamical systems.Recall thatdX,f denotes the number of fixed points of X,f.Lemma 18.
LetH1, H2 be two finite abelian groups and fi∈EndHi. Suppose that φ∈HomH1,H2 is a surjective morphism of dynamical systems. Let Fi=t∈Hi:fit=t. Then H1,f1 is a fixed point system if and only if the following two conditions are satisfied:(1)
H2,f2 is a fixed point system;(2)
dH1,f1=dker⁡φ,f1dH2,f2.Proof.
We writeF2=yi:1≤i≤F2 and φxi=yi. Since φ maps cycle vertices into cycle vertices, so the cycle vertices of H1,f1 are contained in ⋃i=1F2xi+ker⁡φ,f1, and dH1,f1=∑i=1F2dxi+ker⁡φ,f1. Thus, H1,f1 is a fixed point system if and only if xi+ker⁡φ,f1 is a fixed point system for any i=1,…,F2. By Lemma 17, xi+ker⁡φ,f1 is a fixed point system if and only if dxi+ker⁡φ,f1=dker⁡φ,f1 and ker⁡φ,f1 is a fixed point system. This finishes the proof.By Theorem10 we only need to deal with the case that H is a p-group. Let H=Zpa1⊕⋯⊕Zpan such that a1≤a2≤⋯≤an. Recall that any endomorphism of f of H has a matrix representation A=aij∈Zn×n, where pai-aj∣aij for i>j. If (18)u1u2⋮un=Av1v2⋮vn, then ui≡∑k=1naikvimodpai. We also write (19)u1u2⋮un=Av1v2⋮vnmodpa1pa2⋮pan.We recall the Smith normal form and invariant factor of matrices over a principal ideal ring.Definition 19.
LetR be a principal ideal ring and A∈Rn×n. There exist invertible matrices U,V∈Rn×n such that (20)S=UAV=s1⋱sm0⋱0,where si∣si+1 for 1≤i≤m-1. S is called the Smith normal form of A. The diagonal entries si are called the invariant factors of A and are unique up to units.Theorem 20 ([8], Theorem  5.2).
Letp be a prime and H=Zpan and A∈Zn×n. Then H,A is a fixed point system if and only if the following conditions are satisfied.(1)
AnA-I≡0modp;(2)
Each invariant factors ofA-I over Zpa is a unit or 0.Corollary 21.
LetH=Zpa1⊕⋯⊕Zpan and A=aij∈Zn×n, where a1≤a2≤⋯≤an and pai-aj∣aij for i≥j. Suppose that AnA-I≡0modp and each invariant factor of A-I over Zpan is a unit or 0. Then H,A is a fixed point system.Proof.
Since the canonical mappingφ:Zpann,A→H,A is a surjective morphism of dynamical systems, it follows from Lemma 18 and Theorem 20 that H,A is a fixed point system.However, the converse of Corollary21 is not true in general. Consider the following example.Example 22.
LetA=1130 and H1=Z3⊕Z3, H2=Z9⊕Z9, and H=Z3⊕Z9. By a direct computation, H1,A is a fixed point system with three fixed points 0,0, 1,0, and 2,0, and H2,A has three fixed points 0,0, 3,0, and 6,0, and two 3-cycle 1,3,4,3,7,3 and 2,6,8,6,5,6, and H,A is a fixed point system with 3 fixed points 0,0, 1,3, and 2,6.LetA=aij be an integer matrix and n∈Z. We write n∣A if n∣aij for any i,j.Theorem 23.
LetH=Zpa1n1⊕Zpa2n2⊕⋯⊕Zparnr with a1<a2<⋯<ar. Let T=Aij1≤i,j≤r be a matrix with partition Aij∈Znj×ni such that pai-aj∣Aij for i>j. Let Bij=paj-aiAij and (21)Tj=BjjBjj+1⋯BjrBj+1jBj+1j+1⋯Bj+1r⋮⋮⋮⋮BrjBrj+1⋯Brr,for j=1,…,r. Let a0=0 and Hj=Zpaj-aj-1∑i=jrni. Then H,T is a fixed point system if and only if(1)
Hj,Tj is a fixed point system for each j;(2)
dH,T=∏j=1rdHj,Tj.Proof.
We induct onr. The case r=1 is trivial. Let F1=Zpa2-a1n2⊕Zpa3-a1n3⊕⋯⊕Zpar-a1nr and (22)C1=A22A23⋯A2rA32A33⋯A3r⋮⋮⋮⋮Ar2Ar3⋯Arr.Define (23)φ:H⟶F1,φX1X2⋮Xr≡X2X3⋮Xrmodpa2-a1pa3-a1⋮par-a1,where Xi∈Zpaini. Since pai-a1∣Ai1, one has(24)φAX1X2⋮Xr=A21X1+A22X2+⋯+A2rXrA31X1+A32X2+⋯+A3rXr⋮Ar1X1+Ar2X2+⋯+ArrXr≡A22X2+⋯+A2rXrA32X2+⋯+A3rXr⋮Ar2X2+⋯+ArrXr≡C1φX1X2⋮Xrmodpa2-a1pa3-a1⋮par-a1.
It follows thatφ:H,A→F1,C1 is a surjective morphism of dynamical systems. By Lemma 18, H,A is a fixed point system if and only if F1,C1 is a fixed point system and dH,A=dker⁡φ,AdF1,C1. By induction, F1,C1 is a fixed point system if and only if Hj,Tj is a fixed point system for each j≥2 and dF1,C1=∏j=2rdHj,Tj. It remains to show that ker⁡φ,A≃H1,T1, where T1=paj-aiAij1≤i,j≤r.
We setψ:H1=Zpa1∑i=1rnr→H. (25)ψY1Y2⋮Yr≡Y1pa2-a1Y2⋮par-a1Yrmodpa1pa2⋮par,where Yi∈Zpa1ni. It is clear that ψ is injective and Im⁡ψ=ker⁡φ. We have (26)ψT1Y1Y2⋮Yr=A11Y1+pa2-a1A12Y2+⋯+par-a1A1rYrA21Y1+pa2-a1A22Y2+⋯+par-a1A2rYr⋮Ar1Y1+pa2-a1Ar2Y2+⋯+par-a1ArrYr≡AψY1Y2⋮Yrmodpa1pa2⋮par.Thus, H1,ψ≃Im⁡ψ,A=ker⁡φ,A. The proof is finished by induction.Remark 24.
By Theorem23, we can determine whether Hj,Tj is a fixed point system and also can compute dHj,Tj be using the Smith normal form of T-I. So the problem for determining whether H,T is a fixed point system is now reduced to solve the congruence equation (27)T-IX≡0modpa1pa2⋮par.Example 25.
LetH=Z2×Z4×Z16 and T=110223042. By Theorem 23, let T′=1201212012, and let (28)H1=Z23,T1=1201212012=100100010mod2,H2=Z22,T2=21212=0010mod2,H3=Z4,T3=2mod4.It is straightforward to check that H1,T1 is a fixed point system with two fixed points 0,0,0T,1,1,1T, H2,T2 is a fixed point system with one fixed point 0,0T, and H3,T3 is a fixed point system with two fixed points 0. Now we compute the number of fixed points of H,T. Let X=x,y,zT be a fixed point in H,T. Then TX=X and (29)y=0mod2,2x+y+3z=0mod4,4y+z=0mod8.We derive that y=0,2mod4 and z=0mod8 by the first and third equation. Hence, the second equation is equivalent to 2x+y=0mod4. It follows that x=0mod2 if y=0mod4, and x=1mod2 if y=2mod4. Thus, H,T has two fixed points 0,0,0T and 1,2,0T. By Theorem 23 again, H,T is a fixed point system.



---

*Source: 6295430-2017-08-08.xml*