# Isomorphic Digraphs from Affine Maps of Finite Cyclic Groups

Authors: Guixin Deng
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Letn be a positive integer. For any pair of integers k and a, let G(n,k,a) be the digraph whose set of vertices is {0,1,2,…,n-1}, and there exists a directed edge from vertex x to vertex y if kx+a≡y(modn). In this paper, we obtain a necessary and sufficient condition for which G(n,k1,a1)≃G(n,k2,a2).


---

## Body

## 1. Introduction

LetX be a nonempty set and let f be a mapping from X into itself. Then, we call G(X,f) the iteration digraph from f of X, where the set of vertices of G(X,f) is X and there is a directed edge from a vertex a∈G(X,f) to a vertex b∈G(X,f) if f(a)=b. In particular, there are many interesting structures on the digraphs when there is an algebraic structure on X.Many people study the iteration graphs from endomorphisms of finite abelian groups. The authors of [1] studied the digraph from the endomorphism f(x)=x2 of (ℤ/pℤ)*, where p is a prime. These results were generalized to the digraph from any endomorphism of (ℤ/pℤ)* in [2]. Sha and Hu [3] studied some elementary properties of the digraph from any endomorphism of 𝔽q*. They also obtained many elementary properties of the digraph from any endomorphism of finite cyclic groups in [3].Letn be a positive integer and lrt k,a be two integers. In this paper, we denote by G(n,k,a) the digraph obtained from the affine mapping x↦kx+a of ℤn, the ring of integers modulo n. In particular, we set G(n,k)=G(n,k,a) if n∣a, which is from an endomorphism x↦kx.We are mainly interested in the problem whenG(n,k1,a1)≃G(n,k2,a2). The authors in [2] gave an example G(10,2)≃G(10,8). Let p be a prime. Sha [4] showed that G(p,k1)≃G(p,k2) if and only if ordpk1=ordpk2. In [5], Deng and Yuan gave a necessary and sufficient condition for G(p-1,k1)≃G(p-1,k2), where p is a prime. In this paper, we obtain a necessary and sufficient condition for when G(n,k1,a1)≃G(n,k2,a2).The paper is organized as follows. In Section2, we study the G(n,k,a), where n is a power of a prime. The main results are proved in Section 3. We also determined the digraph from projective map on one-dimensional projective space over a finite field in the last section.


## 2.  Digraph Product and the Local Case

LetG be a digraph and let a be a vertex in G. A component of a digraph is a subdigraph which is a maximal connected subgraph. Each component of a finite iteration graph G(X,f) contains a unique cycle. Let Oi denote this i-cycle. Let A1(G) denote the number of cycle of length 1 in G.LetG1,G2,…,Gr be iteration digraphs. The product G1×G2×⋯×Gr is the digraph whose vertices are the ordered pairs (a1,a2,…,ar), where ai∈Gi and there is a directed edge from (a1,a2,…,ar) to (b1,b2,…,br) if and only if there is a directed edge in Gi from ai to bi for each 1≤i≤r. We use the following notation:
(1)∏i=1r‍Gi:=G1×G2×⋯×Gr.Lemma 1 (see [6]).
O
s
×
O
t is isomorphic to gcd(s,t)Olcm[s,t], which is a union of gcd(s,t) cycles, each having length lcm[s,t].Theorem 2.
Letn=∏i=1r‍piei be the prime factorization of n and let k,a be two integers. Then
(2)G(n,k,a)≅∏i=1r‍G(piei,k,a).Proof.
LetG=G(n,k,a) and Gi=G(piei,k,a). Assume that φ:ℤn→ℤp1e1×ℤp2e2×⋯×ℤprer is the canonical isomorphism of rings. Then φ induces an isomorphism of digraphs.


### 2.1. The Case of Linear Maps

The structure ofG(n,k) has been studied in [2, 4, 5]. We present some results here.Lemma 3 (see [4]).
Letk,n be positive integers. Then one has the following.(i)
Ifp∣k for any prime p∣n, then G(n,k) is a tree attached to the fixed point 0.(ii)
Ifgcd(n,k)=1, then G(n,k)≃∪rarOr, where ar=(1/r)∑i∣r‍μ(i)gcd(n,kr/i-1) and μ is the Möbius function.Letvp(n) be the p-adic valuation of n for any prime p and integer n. It is the largest power of p dividing n for any prime p and integer n. We set vp(0)=∞ as usual. If X is a set of primes and n is a positive integer, we denote that
(3)nX=∏p∈X‍pvp(n).Lemma 4.
Letp be a prime. Let k,a be positive integers such that k,a≤pe-1. The following statements are equivalent:(i)
G(pe,k,a)≃G(pe,k);(ii)
gcd(pe,k-1,a)=gcd(pe,k-1);(iii)
vp(k-1)≤vp(a);(iv)
G(pe,k,a) has a fixed point.Proof.
By hypothesis the statements(ii), (iii), and (iv) are equivalent to that the congruence equation (k-1)x≡a(modpe) that has a solution. Suppose that G(pe,k,a)≃G(pe,k). Then G(pe,k,a) has a fixed point z since G(pe,k) has a fixed point 0. So kz+a≡z(modpe). On the other hand, if kz+a≡z(modpe), then x↦x+z is an isomorphism of G(pe,k) and G(pe,k,a).Remark 5.
Many people showed that the tree attached to any two cycle vertices inG(n,k) is isomorphic. Moreover, Deng and Yuan [5] showed that the tree attached to cycle vertices in G(p-1,k) is totally determined by gcd(p-1,k), where p is a prime. In fact, if we replace p-1 by n in the arguments in [5], then the result is also valid.


### 2.2. The Case of Affine Maps

Lemma 6.
Letk=lpt+1 be a positive integer, where p is a prime and p∤l, t≥1.(i)
Ifp>2 or t>1, then ordprk=max{1,pr-t} for any integers t≥1.(ii)
Ifp=2 and t=1, assuming that 2u∥k2-1, then
(4)ord2rk={1,r=1,2,2≤r≤u,2r-u+1,r>u.Proof.
Ifr≤t, then it is clear that ordprk=1=max{1,pr-t}. Firstly, we assume that r>t. By computation, pm-si∣∣(pmi) for any 1≤i≤pm-1 and psi∣∣i. But
(5)kpr-t-1=(lpt+1)pr-t-1=∑i=1pr-t‍(pr-ti)(lpt)i;
thus pr-t-si+ti∣∣(pr-ti)(lpt)i. It is clear that r-t-si+ti≥r. So pr∣kpr-t-1; considering that ordprk∣pr-t. So ordprk=p if r-t=1. Suppose that r-t>1. If p>2 or t>1, then
(6)kpr-t-1-1=(lpt+1)pr-t-1-1=∑i=1pr-t-1‍(pr-t-1i)(lpt)i=lpr-1+∑i=2pr-t-1‍(pr-t-1i)(lpt)i.
Therefore, r-t-1-si+ti≥r for any i≥2. Hence, pr∣(pr-t-1i)(lpt)i for i≥2 and pr∤kpr-t-1-1. Thus, ordprk=pr-t in this case.
Suppose that2∥k-1and2u∥k2-1, u≥3. It remains to show that ord2rk=2r-u+1 for r>u. Let k2=q2u+1, where 2∤q. By the discussion above we get 2r∥k2r-u+1-1 and 2r-1∥k2r-u-1. Therefore, ord2rk=2r-u+1 for r>u. This finishes the proof.Lemma 7.
Letp be a prime. Let k,a≤pe-1 be two positive integers such that vp(k-1)>vp(a). Then G(pe,k,a)≃pe-sOps, where(7)ps=ordpe+vp(k-1)-vp(a)k={pe-vp(a),2∤porvp(k-1)>1,2,p=2,v2(k-1)=1,ande+1≤v2(k-1),2e+2-v2(k2-1),p=2,v2(k-1)=1,ande+1>v2(k-1).Proof.
Letf(x)=kx+a. Then ft(x)=ktx+(∑i=0t-1‍ki)a. We consider the following congruence equation
(8)ktx+(∑i=0t-1‍ki)a≡x(modn).
Equation (8) has a solution if and only if gcd(pe,kt-1)∣gcd(pe,(kt-1)/(k-1)·a). In this case, pe∣kt-1 and pe∣(kt-1)/(k-1)·a, since vp(k-1)>vp(a). Since t is the minimal positive integer such that pe∣(kt-1)/(k-1)·a, we get t=ordpe+vp(k-1)-vp(a)k=ps. Moreover, each integer is a solution of (8). Thus, G(pe,k,a) is a union of cycles, each having length ps. The rest of the proof follows from Lemma 6.The structure of digraphG(pe,k,a) is clear now. We classify it as follows.Type(1): G(pe,k,a)≃G(pe,k) is a tree attached to a fixed point, which is determined by gcd(pe,k).Type(2): G(pe,k,a)≃G(pe,k) is a union of cycles, and the minimal length of these cycles is 1.Type(3): G(pe,k,a)≃pe-sOps, where 1≤s≤e.LetXi={p∣G(pvp(n),k,a)istype(i)}. By the properties of digraph product we see that
(9)G(n,k,a)≃G(nX1,k,a)×G(nX2,k,a)×G(nX3,k,a),
where G(nX1,k,a) is a tree attached to a fixed point, G(nX2,k,a) is a union of cycles, and the minimal length of these cycles is 1, and G3≃(nX3/l)Ol.


## 2.1. The Case of Linear Maps

The structure ofG(n,k) has been studied in [2, 4, 5]. We present some results here.Lemma 3 (see [4]).
Letk,n be positive integers. Then one has the following.(i)
Ifp∣k for any prime p∣n, then G(n,k) is a tree attached to the fixed point 0.(ii)
Ifgcd(n,k)=1, then G(n,k)≃∪rarOr, where ar=(1/r)∑i∣r‍μ(i)gcd(n,kr/i-1) and μ is the Möbius function.Letvp(n) be the p-adic valuation of n for any prime p and integer n. It is the largest power of p dividing n for any prime p and integer n. We set vp(0)=∞ as usual. If X is a set of primes and n is a positive integer, we denote that
(3)nX=∏p∈X‍pvp(n).Lemma 4.
Letp be a prime. Let k,a be positive integers such that k,a≤pe-1. The following statements are equivalent:(i)
G(pe,k,a)≃G(pe,k);(ii)
gcd(pe,k-1,a)=gcd(pe,k-1);(iii)
vp(k-1)≤vp(a);(iv)
G(pe,k,a) has a fixed point.Proof.
By hypothesis the statements(ii), (iii), and (iv) are equivalent to that the congruence equation (k-1)x≡a(modpe) that has a solution. Suppose that G(pe,k,a)≃G(pe,k). Then G(pe,k,a) has a fixed point z since G(pe,k) has a fixed point 0. So kz+a≡z(modpe). On the other hand, if kz+a≡z(modpe), then x↦x+z is an isomorphism of G(pe,k) and G(pe,k,a).Remark 5.
Many people showed that the tree attached to any two cycle vertices inG(n,k) is isomorphic. Moreover, Deng and Yuan [5] showed that the tree attached to cycle vertices in G(p-1,k) is totally determined by gcd(p-1,k), where p is a prime. In fact, if we replace p-1 by n in the arguments in [5], then the result is also valid.


## 2.2. The Case of Affine Maps

Lemma 6.
Letk=lpt+1 be a positive integer, where p is a prime and p∤l, t≥1.(i)
Ifp>2 or t>1, then ordprk=max{1,pr-t} for any integers t≥1.(ii)
Ifp=2 and t=1, assuming that 2u∥k2-1, then
(4)ord2rk={1,r=1,2,2≤r≤u,2r-u+1,r>u.Proof.
Ifr≤t, then it is clear that ordprk=1=max{1,pr-t}. Firstly, we assume that r>t. By computation, pm-si∣∣(pmi) for any 1≤i≤pm-1 and psi∣∣i. But
(5)kpr-t-1=(lpt+1)pr-t-1=∑i=1pr-t‍(pr-ti)(lpt)i;
thus pr-t-si+ti∣∣(pr-ti)(lpt)i. It is clear that r-t-si+ti≥r. So pr∣kpr-t-1; considering that ordprk∣pr-t. So ordprk=p if r-t=1. Suppose that r-t>1. If p>2 or t>1, then
(6)kpr-t-1-1=(lpt+1)pr-t-1-1=∑i=1pr-t-1‍(pr-t-1i)(lpt)i=lpr-1+∑i=2pr-t-1‍(pr-t-1i)(lpt)i.
Therefore, r-t-1-si+ti≥r for any i≥2. Hence, pr∣(pr-t-1i)(lpt)i for i≥2 and pr∤kpr-t-1-1. Thus, ordprk=pr-t in this case.
Suppose that2∥k-1and2u∥k2-1, u≥3. It remains to show that ord2rk=2r-u+1 for r>u. Let k2=q2u+1, where 2∤q. By the discussion above we get 2r∥k2r-u+1-1 and 2r-1∥k2r-u-1. Therefore, ord2rk=2r-u+1 for r>u. This finishes the proof.Lemma 7.
Letp be a prime. Let k,a≤pe-1 be two positive integers such that vp(k-1)>vp(a). Then G(pe,k,a)≃pe-sOps, where(7)ps=ordpe+vp(k-1)-vp(a)k={pe-vp(a),2∤porvp(k-1)>1,2,p=2,v2(k-1)=1,ande+1≤v2(k-1),2e+2-v2(k2-1),p=2,v2(k-1)=1,ande+1>v2(k-1).Proof.
Letf(x)=kx+a. Then ft(x)=ktx+(∑i=0t-1‍ki)a. We consider the following congruence equation
(8)ktx+(∑i=0t-1‍ki)a≡x(modn).
Equation (8) has a solution if and only if gcd(pe,kt-1)∣gcd(pe,(kt-1)/(k-1)·a). In this case, pe∣kt-1 and pe∣(kt-1)/(k-1)·a, since vp(k-1)>vp(a). Since t is the minimal positive integer such that pe∣(kt-1)/(k-1)·a, we get t=ordpe+vp(k-1)-vp(a)k=ps. Moreover, each integer is a solution of (8). Thus, G(pe,k,a) is a union of cycles, each having length ps. The rest of the proof follows from Lemma 6.The structure of digraphG(pe,k,a) is clear now. We classify it as follows.Type(1): G(pe,k,a)≃G(pe,k) is a tree attached to a fixed point, which is determined by gcd(pe,k).Type(2): G(pe,k,a)≃G(pe,k) is a union of cycles, and the minimal length of these cycles is 1.Type(3): G(pe,k,a)≃pe-sOps, where 1≤s≤e.LetXi={p∣G(pvp(n),k,a)istype(i)}. By the properties of digraph product we see that
(9)G(n,k,a)≃G(nX1,k,a)×G(nX2,k,a)×G(nX3,k,a),
where G(nX1,k,a) is a tree attached to a fixed point, G(nX2,k,a) is a union of cycles, and the minimal length of these cycles is 1, and G3≃(nX3/l)Ol.


## 3. The Main Results

We begin with some lemmas before we prove our main results.Lemma 8.
Suppose thatf is a permutation of a finite set X and G(X,f)≃∪i=1naiOi. Then G(X,fr)≃∪i=1ngcd(r,i)aiOi/gcd(i,r) for each r≥1.Proof.
Assume thatE={x1,x2,…,xl} is a cycle of length l in G(X,f) such that f(xi)=xi+1, for i=1,2,…,l-1 and f(xl)=x1. Suppose that xi is contained in a cycle of length m in G(X,fr). Then m=min{j:frj(xi)=xi}=min{j:l∣rj}=l/gcd(r,l). Hence, E splits into gcd(r,l) cycles with the same length l/gcd(r,l). This completes the proof.Lemma 9.
Letfi be a permutation of a finite set Xi, i=1,2. Then(i)
G(X1,f1)≃G(X2,f2) if and only if the numbers of fixed point of G(X1,f1r) and G(X2,f2r) are equal for each r≥1;(ii)
G(X1,f1)×Ol≃G(X2,f2)×Ol if and only if G(X1,f1l)≃G(X2,f2l) for each l≥1.Proof.
Suppose thatG(X1,f1)≃∪aiOi and G(X2,f2)≃∪bjOj.
Assume thatφ:G(X1,f1)→G(X2,f2) is an isomorphism of digraphs. Then f2(φ(x))=φ(f1(x)) for any x∈X1. By induction, f2r(φ(x))=φ(f1r(x)). Hence, φ is also an isomorphism of G(X1,f1r) and G(X2,f2r). Thus, A1(G(X,f1r))=A1(G(X,f2r)). Conversely, if G(X1,f1r)≃G(X2,f2r), then a1=b1. Assume that ai=bi for any i<r. By Lemma 8, A1(G(X1,f1r))=∑i∣r‍iai and A1(G(X2,f2r))=∑j∣r‍jbj. Hence, ∑i∣r‍iai=∑j∣r‍jbj and ar=br. The proof of statement (i) is complete by induction.
It remains to prove (ii). Assume thatG(Z,g)≃Ol. Then G(Xi,fi)×Ol≃G(Xi×Z,fi×g), where fi×g maps (x,z) to (fi(x),g(z)) for any (x,z)∈Xi×Z. Let Gir=G(Xi×Z,(fi×g)r). By Lemma 8,
(10)Gir≃G(Xi,fir)×G(Z,gr)≃G(Xi,fir)×gcd(r,l)Ol/gcd(r,l).
IfG(X1,f1)×Ol≃G(X2,f2)×Ol, then G1r≃G2r for each r≥1. Let r=l in (10). We get G(X1,f1l)≃G(X2,f2l). Conversely, if G(X1,f1l)≃G(X2,f2l), then by (10) A1(Gir)=0 if l∤r. If l∣r, then
(11)Gir≃G(Xi,fir)×gcd(r,l)Ol/gcd(r,l)≃lG(Xi,(fil)r/l).
Hence, G1r≃G2r if l∣r. Therefore, A1(G1r)=A1(G2r) for any r≥1. By statement (i), G(X1,f1)×Ol≃G(X2,f2)×Ol.In [3], Sha and Hu showed that G(p,k1)≃G(p,k2) if and only if ordpk1=ordpk2, where p is a prime and p∤ki. We generalized this result to the following.Lemma 10.
Letn, k1 and k2 be positive integers such that gcd(n,ki)=1, i=1,2. Then G(n,k1)≃G(n,k2) if and only if ordtk1=ordtk2 for any divisor t of n.Proof.
LetGir=G(n,kir). By Lemma 3 and Möbius inverse transform A1(Gir)=gcd(kir-1,n) for any r≥1. Suppose that ordtk1=ordtk2 for any divisor t of n. If t1∣gcd(k1r-1,n), let s=ordt1k1=ordt1k2; then s∣r. Thus t1∣gcd(k2r-1,n). By symmetry, we have t2∣gcd(k1r-1,n) if t2∣gcd(k2r-1,n). Thus, gcd(k1r-1,n)=gcd(k2r-1,n). By Lemma 9, G(n,k1)≃G(n,k2).
Conversely, ifG(n,k1)≃G(n,k2), then G1r≃G2r and gcd(k1r-1,n)=gcd(k2r-1,n) for any r≥1. If t∣n, let si=ordtki; then t∣gcd(k1s1-1,n)=gcd(k2s1-1,n). Hence, s2∣s1. By symmetry, s1∣s2. Thus, s1=s2. The proof is complete.Theorem 11.
Letn=∏i=1r‍piei be the prime factorization of n and let ki, ai be integers, i=1,2. Suppose that Yj={pi∣G(piei,kj,aj)isType(2)} and that the minimal length of cycles in G(n,ki,ai) is li. Then G(n,k1,a1)≃G(n,k2,a2) if and only if the following two conditions are satisfied.(i)
gcd(n,k1)=gcd(n,k2).(ii)
Y1=Y2=Y, l1=l2=l, and ordtk1l=ordtk2l for any divisor t of nY.Proof.
Suppose thatXj={pi∣G(piei,kj,aj)isType(1)} and that Zj={pi∣G(piei,kj,aj)isType(3)}. We have the following decomposition:
(12)G(n,ki,ai)≃G(nXi,ki,ai)×G(nYi,ki,ai)×G(nZi,ki,ai)≃G(nXi,ki)×G(nYi,ki)×nZiliOli,
where G(nXi,ki,ai) is a tree attached to a fixed point, G(nYi,ki,ai) is a union of cycles, and the minimal length of these cycles is 1.
Therefore,G(n,k1,a1)≃G(n,k2,a2) if and only if the following two conditions hold.(iii)
G(nX1,k1)≃G(nX2,k2).(iv)
nZ1/l1=nZ2/l2 and G(nY1,k1)×Ol1≃G(nY2,k2)×Ol2.
However, by Remark5, (i) is equivalent to (iii). It remains to show that (ii) is equivalent to (iv). If (ii) is satisfied, then Z1=Z2 and by Lemma 10  G(nY,k1l)≃G(nY,k2l). By Lemma 9, G(nY,k1)×Ol≃G(nY,k2)×Ol. Conversely, if (iv) holds, we have l1=l2=l since the minimal length of cycles in G(nYi,k1)×Oli is li. So nZ1=nZ2, Z1=Z2, Y1=Y2=Y, and G(nY,k1)×Ol≃G(nY,k2)×Ol. The rest of proof follows from Lemmas 9 and 10.Remark 12.
Suppose thatG(n,k1,a1)≃G(n,k2,a2). By Theorem 11, we see that both G(pvp(n),k1,a1) and G(pvp(n),k2,a2) are the same types for any prime p∣n. Moreover, they are isomorphic if they are Type (1) or (3).Example 13.
ConsiderG(40,37,1), G(40,29,1), and G(40,29,3). One has
(13)G(40,37,1)≃G(5,37,1)×G(8,37,1)≃G(5,2,1)×G(8,5,1)≃(O1∪O4)×O8≃5O8,G(40,29,i)≃G(5,29,i)×G(8,29,i)≃G(5,4,i)×G(8,5,i)≃(O1∪2O2)×O8≃5O8,
where i=1,3. Hence, G(40,37,1)≃G(40,29,1), but G(5,37,1)≄G(5,29,1). This shows that even if G(n,k1,a1)≃G(n,k2,a2), it may happen that G(pvp(n),k1,a1)≄G(pvp(n),k2,a2). But we also see that G(40,29,1)≃G(40,29,3), G(5,29,1)≃G(5,29,3), and G(8,29,1)≃G(8,29,3). In fact, we have the following result if k is fixed.Theorem 14.
Letn=∏i=1r‍piei be the prime factorization of n. The following three statements are equivalent for any integers k, a1, and a2:(i)
G(n,k,a1)≃G(n,k,a2);(ii)
gcd(n,k-1,a1)=gcd(n,k-1,a2);(iii)
G(piei,k,a1)≃G(piei,k,a2) for each i∈{1,2,…,r}.Proof.
LetXj={pi∣G(piei,k,aj)isType(1)}, Yj={pi∣G(piei,k,aj)isType(2)}, and Zj={pi∣G(piei,k,aj)isType(3)}.
(
i
)
⇒
(
ii
). By Theorem 11  X1=X2=X, Y1=Y2=Y, and Z1=Z2=Z. If pi∈X∪Y, then gcd(piei,k-1,aj)=gcd(piei,k-1), j=1,2. If pi∈Z, Suppose G(piei,k,aj)≃piei-siOpisi for any pi∈Z, where pisi=ordpiei+vpi(k-1)-vpi(aj)k. By Lemma 7, vpi(a1)=vpi(a2). Thus, gcd(piei,k-1,a1)=gcd(piei,k-1,a2) for any i. The result follows from that gcd(n,k-1,aj)=∏i=1r‍gcd(piei,kj,aj), j=1,2.
(
ii
)
⇒
(
iii
). Assume that gcd(piei,k-1,a1)=gcd(piei,k-1,a2)=piui for each i with ui≤ei. If vpi(k-1)=ui, then by Lemma 4  G(piei,k,a1)≃G(piei,k,a2)≃G(piei,k). If vpi(k-1)>ui, then vpi(a1)=vpi(a2)=ui. By Lemma 7 again G(piei,k,aj)≃piei-siOpisi, where pisi=ordpiei+vpi(k-1)-uik.
(
iii
)
⇒
(
i
) follows immediately from (2).


## 4. The Digraph from Projective Map

Letℙ1(𝔽q)=𝔽q2∖{(0,0)}/~ be the one-dimensional projective space over 𝔽q, where (a1,a2)~(b1,b2) if and only if there exists λ∈𝔽q* such that λai=bi. With any invertible 2×2 matrix A over 𝔽q, we associate the Möbius transformation of ℙ1(𝔽q) as z↦zA. Let f(x) be a polynomial over 𝔽q with f(0)≠0. Recall that o(f), the order of f(x), is the minimal positive integer d such that f(x)∣xd-1. We classify the digraph from Möbius transformation of ℙ1(𝔽q) as follows.Theorem 15.
LetG=G(ℙ1(𝔽q),A). Suppose that f(x) and m(x) are the characteristic polynomial and minimal polynomial of A, respectively. Then(i)
iff(x)=(x-λ)2 and m(x)=x-λ, then G≃(q+1)O1;(ii)
iff(x)=m(x)=(x-λ)2, then G≃O1∪(q/p)Op;(iii)
iff(x)=(x-λ1)(x-λ2) and λ1≠λ2, then G≃2O1∪((q-1)/s)Os, where s is the multiplicative order of λ1λ2-1;(iv)
iff(x) is irreducible over 𝔽q[x], then G≃((q+1)/s)Os, where s=o(f)/gcd(o(f),q-1).Proof.
(i)–(iii). We see thatA is similar to λI2, (λ10λ) and (λ100λ2) in cases (i), (ii), and (iii), respectively. But the digraphs are isomorphic from similar matrices. The results follows from a simple calculation.
It remains to prove(iv). Let 𝕂=𝔽q[x]/(f(x)). We can consider G as a subdigraph of G1=G(𝕂,A) under the natural inclusion 𝔽q⊆𝕂. Then f(x)=(x-λ)(x-λq) with some λ in 𝕂. By (iii), G1≃2O1∪((q2-1)/t)Ot, where t is the multiplicative order of λq-1 in 𝕂. By a direct computation, we see that zA∈𝔽q for z∈𝕂 if and only if z∈𝔽q. Hence, G is a union of cycles of G1. However, G has no fixed point since f(x) is irreducible. So the length of each cycle in G is t, and G≃((q+1)/t)Ot. Note that t=min{n>0∣λn(q-1)=1}, and that o(f)=min{n>0∣λn=1}. Therefore, t=o(f)/gcd(o(f),q-1). This finishes the proof.Corollary 16.
G
(
ℙ
1
(
𝔽
q
)
,
A
1
)
≃
G
(
ℙ
1
(
𝔽
q
)
,
A
2
) if and only if they have the same number of fixed points.



---

*Source: 398641-2013-09-02.xml*