GRAPHS
DAVID DOLˇZAN∗, MATJAˇZ KONVALINKA†, AND POLONA OBLAK†
Abstract. In this paper, we calculate diameters of connected components of commuting graphs ofGLn(S), for an integern≥2 and a commutative antinegative entire semiringS, unlessnis a non-prime odd number andShas at least two invertible elements.
Key words. Commuting graph, Diameter, Semiring, Symmetric group
AMS subject classifications. 05C50, 20B30
1. Introduction. Asemiringis a setSequipped with binary operations + and
· such that (S,+) is a commutative monoid with identity element 0, and (S,·) is a monoid with identity element 1. In addition, operations + and · are connected by distributivity and 0 annihilates S. A semiring is commutative ifab = ba for all a, b∈S.
A semiringS is calledantinegative, ifa+b= 0 implies thata=b= 0. Antineg- ative semirings are also called antirings. A semiring is said to be entire if ab = 0 implies that a= 0 orb= 0. The set of all (multiplicatively) invertible elements of a semiringSwill be denoted byU(S). Thecentralizer CS(x) ofx∈Sis defined as the set of all elements ofS commuting withx.
The simplest example of an antinegative semiring is thebinary Boolean semiring, the set {0,1} in which addition and multiplication are the same as inZexcept that 1+1 = 1. Moreover, the set of nonnegative integers (or reals) with the usual operations of addition and multiplication is a commutative antinegative entire semiring. Inclines, additively idempotent semirings in which products are less than or equal to either factor, are commutative antinegative semirings. Distributive lattices are inclines, and thus antinegative semirings. Also, tropical semirings are commutative antinegative semirings.
∗Department of Mathematics, University of Ljubljana, Slovenia (david.dolzan@fmf.uni-lj.si, matjaz.konvalinka@fmf.uni-lj.si). Supported by Research Programs P1-0222 and L1-069 of the Slove- nian Research Agency
†Department of Computer and Information Science, University of Ljubljana, Slovenia (polona.oblak@fri.uni-lj.si). Supported by Research Program P1-0222 of the Slovenian Research Agency
1
We will denote by Mn(S) the set of all n×n matrices over a semiring S and by GLn(S) the set of all invertible matrices in Mn(S). The symmetric group of permutations on a set of nelements will be denoted bySn. A cycle ofSn of length nis called along cycle.
The matrix with the only nonzero entry 1 in theith row andjth column will be denoted by Ei,j. Let diag(a1, . . . , an) denote the diagonal matrix Pn
i=1aiEi,i. The n×nidentity matrix will be denoted byIn. For anyσ∈Snwe define the permutation matrixPσ=Pn
i=1Ei,σ(i).
For a semigroup G, we denote by Γ(G) thecommuting graph ofG. The vertex setV(Γ(G)) of Γ(G) is the set of elements inG\Z(G), whereZ(G) ={g∈G:gh= hgfor allh∈G} is the centre ofG. An unordered pair of verticesx∼y is an edge of Γ(G) ifx6=y andxy=yx.
The sequence of edges x0∼x1, x1∼x2, . . . , xk−1∼xk is calleda path of length k and is denoted byx0 ∼x1 ∼. . . ∼xk. The distance between two vertices is the length of the shortest path between them. The diameter of the graph is the longest distance between any two vertices of the graph.
In [5, Theorem 4], it was shown that the diameter of Γ(Sn) is 5 for all nexcept when n−1 or nis a prime. Also, by [7, Theorem 3.1], if n−1 or n is prime, then Γ(Sn) is not connected. In [4, Theorem 1], it was shown that ifS is a commutative antinegative entire semiring, thenA∈Mn(S) is invertible if and only if
A=DPσ,
whereD is an invertible diagonal matrix andPσ is a permutation matrix.
Recently, the interplay between various algebraic structures and their commuting graphs has been studied, see e.g. [1, 2, 3, 5, 6, 7, 8, 9]. For example, it was recently proved in [8] that a ring is isomorphic to the full matrix ring of 2×2 matrices over a finite field if and only if their commuting graphs are isomorphic. It is conjectured that this is also true for the algebra ofn×nmatrices whenevern≥3. Moreover, the diameters of commuting graphs of rings Mn(F) of n×n matrices have been studied extensively. It was proved in [1] that ifF is an algebraically closed field andn≥3, then the diameter of Γ(Mn(F)) is always equal to 4. If the fieldFis not algebraically closed, then Γ(Mn(F)) need not be connected. In the case the graph is connected, its diameter is known to be at most 6 and it is conjectured that it is at most 5. The connectivity and diameters of Γ(GLn(S)) were recently studied in [1] for division rings S and in [6] for the ringS=Zm; that is, the ring of integers modulom.
In this paper, we calculate diameters of connected components of commuting graphs ofGLn(S) for a commutative antinegative entire semiringS, both whenShas only one invertible element, and when it has several such elements. In the first case, it follows from [4, Theorem 1] thatGLn(S) is isomorphic toSn. Note that when n is a non-prime odd number and|U(S)| ≥2, we state the diameter as a conjecture.
2. The main result. The purpose of our paper is to prove the following.
Theorem 2.1. Let S be a commutative antinegative entire semiring and n ≥ 2. We have the following table of diameters of connected components of graphs Γ(GLn(S)), depending onn andu=|U(S)|:
u= 1 u≥2
n= 2 (0) (1u+1)
n= 3 (1,03) (3,1u2)
n= 4 (3,14) (4)
n≥5, n∈P (5,1(n−2)!) (3,1un−1(n−2)!) n≥6, n−1∈P (4,1n(n−3)!) (4)
n /∈2N∪P (5) (4)or(5) n∈2N, n−1∈/P (5) (4)
Here,(ak11, . . . , akrr)means that the graph hask1+· · ·+krconnected components such that ki of them have diameterai, for i= 1, . . . , r.
Remark 2.2. In [5, Theorem 7], the values for n ≥ 4 even and u ≥ 2 were erroneously stated to equal 5, since Lemma 6, as stated in [5], does not hold. The weaker version of Lemma 6 is about to be published in the errata and proves that there exist two matrices at distance 4, which implies that in the case u≥2, n not prime andS integral, the diameter of Γ(GLn(S))is either 4 or 5.
For the proof, we need the following seven propositions. The first one describes the edges in the commuting graph. The next three establish upper bounds for the diameter, and the last three establish lower bounds. Conjecture 2.10 would imply that the diameter of Γ(GLn(S)) is 5 ifnis odd and non-prime andu≥2.
Proposition 2.3. Let D = diag(d1, . . . , dn) and E = diag(e1, . . . , en). In Γ(GLn(S)), we haveDPα∼EPβ if and only ifαβ=βαand
di dβ(i)
= ei eα(i)
.
Proposition 2.4. Take n ≥ 4 even and u ≥ 2. For every two long cycles α, β ∈ Sn and diagonal invertible matrices D and E, the distance in Γ(GLn(S))
between DPα andEPβ is at most4.
Proposition 2.5. Take n ≥ 6 even with n−1 prime and u = 1. Then the distance in Γ(GLn(S)) between Pα and Pβ is at most 4 whenever α and β are not cycles of length n−1.
Proposition 2.6. Let n≥7 be an odd prime and u= 1. Then the distance in Γ(GLn(S))between Pα andPβ is at most5 wheneverαandβ are not long cycles.
Proposition 2.7. [3, Lemma 6.17] Assume that u = 1 and n and n−1 are not prime. Then the distance in Γ(GLn(S))between Pα andPβ is at least 5, where α= (1, . . . , n)andβ = (1, . . . , n−1).
Proposition 2.8. Assume that n = 2m ≥ 6 and u = 1. Then the distance in Γ(GLn(S)) between Pα and Pβ is at least 4, where α = (1, . . . ,2m) and β = (1, m+ 2, . . . ,2m,2, . . . , m+ 1).
Proposition 2.9. Assume that n= 2m+ 1≥5 andu= 1. Then the distance in Γ(GLn(S))between Pα andPβ is at least5, where α= (1, . . . ,2m)(2m+ 1)and β= (1, ..., m, m+ 2, ...,2m+ 1)(m+ 1).
Conjecture 2.10. Assume that n= 2m+ 1≥5 andu≥2. Then the distance in Γ(GLn(S))between Pα andPβ is at least5, where α= (1, . . . ,2m+ 1)and β = (1, . . . , m, m+ 2, . . . ,2m+ 1, m+ 1).
Let us see how these propositions prove our main theorem.
Let us start with n = 2. For u = 1, the graph Γ(GL2(S)) consists of a single vertex. If u ≥ 2, the vertices are diag(d1, d2) for d1, d2 ∈ U(S), d1 6= d2, and diag(d1, d2)P(12) for arbitrary d1, d2 ∈ U(S). All diagonal matrices commute with each other. By Proposition 2.3, vertices diag(d1, d2) and diag(e1, e2)P(12) are not connected (d1/d2 = e1/e1 = 1 would imply d1 =d2), and vertices diag(d1, d2)P(12) and diag(e1, e2)P(12) are connected if and only ifd1/d2=e1/e2. That means that for eachu∈U(S), we get a clique of all matrices diag(d1, d2)P(12) withd1/d2=u.
Assume n = 3. For u = 1, the graph Γ(GL3(S)) has 5 vertices, corresponding to S3\ {id}, and the only edge of the graph connects (123) and (132). If n = 3 and u≥2, thenDP(123), whereD = diag(d1, d2, d3), is adjacent toaDP(123) for all a∈U(S)\ {1}, and toaD0P(132), wherea∈ U(S) and D0 = diag(d1d2, d2d3, d3d1).
For everya, b∈U(S), we get a clique that contains diag(1, a, b)P(123). Furthermore, for every transpositionτ,DPτ is adjacent to some non-scalar diagonal matrixF, and since all diagonal matrices commute, the diameter of this connected component is at most 3. There is no non-scalar diagonal matrix that commutes both with P(12) and P(23), so the diameter equals 3.
Ifn= 4 andu= 1, every one of the eight 3-cycles is adjacent only to its inverse.
That gives us four 2-cliques. The rest of the graph is shown in Figure 2.1; the large triangle contains (12)(34), (13)(24) and (14)(23). It is obvious that the diameter is 3.
Fig. 2.1.The large connected component ofS4.
For n= 4 and u≥2, every permutation that is not a long cycle is adjacent to a diagonal non-identity matrix: if T 6= {1,2,3,4} consists of the elements of some cycle ofπ, then DPπ∼diag(e1, e2, e3, e4), where ei = 1 ifi∈T andei=aifi /∈T, where a∈U(S)\ {1} is fixed. Since for a long cycleα, we have DPα ∼D0Pα2 ∼F for someD0, F,DPαis at distance at most 4 fromEPβ, whereβ is not a long cycle.
By Proposition 2.4, two long cycles are at distance at most 4. That means that the diameter is at most 4. Finally, let us prove that DP α and EPβ are at distance at least 4, where D = diag(1, a, a, a), α= (1234), E = diag(1,1, a, a) and β = (1243), where a ∈ U(S)\ {1}. Then DPα is adjacent to D0Pα for D0 = bdiag(1, a, a, a), whereb∈U(S), toD00Pα2 forD00=bdiag(1, a, a,1), whereb∈U(S), and toD000Pα3
for D000 =bdiag(1, a,1,1), where b ∈U(S). Similarly,EPβ is adjacent toE0Pβ for E0 =bdiag(1,1, a, a), where b ∈ U(S), to E00Pβ2 for E00 =bdiag(1, a, a, a2), where b∈U(S), and to E000Pβ3 forE000 =bdiag(1, a, a,1), whereb∈U(S). Nowαandα3 do not commute with either β,β2 orβ3, andβ andβ3 do not commute with either α,α2 orα3. Furthermore,D00Pα2 andE00Pβ2 are not adjacent.
Take n ≥5 prime andu= 1. If α is a long cycle, thenPα is adjacent only to Pαk fork= 2, . . . , n−1. So we get an (n−1)-clique for every long cycle that maps 1 to, say, 2, and there are (n−2)! such cycles. If n= 5, the diameter of the large connected component (with 95 vertices) is easily verified to be 5. For n≥7,Pα and Pβforαandβ that are not long cycles are at distance at most 5 by Proposition 2.6.
By Proposition 2.9, the diameter of this connected component is 5.
Suppose thatn≥5 is prime andu≥2. Ifαis a long cycle, thenDPαis adjacent to aDPα for a∈U(S)\ {1} and to aD0Pαk, where a∈ U(S), k = 2, . . . , n−1 and D0 is uniquely determined. That means that we get cliques that correspond toDPα,
whereD= diag(1, a1, . . . , an−1) andαis a long cycle that maps 1 to 2. So there are un−1(n−2)! such cliques. Forαthat is not a long cycle,DPαcommutes with a non- scalar diagonal matrix, and diagonal matrices commute, so the rest of the graph is connected and has diameter at most 3. It is clear that there is no non-scalar diagonal matrix that commutes both withP(1,...,n−1) andP(2,...,n), so the diameter is 3.
Assume thatn≥6,n−1 is prime andu= 1. Every (n−1)-cycle is adjacent only to its powers, so we get cliques corresponding to (n−1)-cycles that fixi, 1≤i≤n, and map, say, the smallest element of{1, . . . , i−1, i+ 1, . . . , n}to the second smallest.
There aren(n−3)! such cycles. If α, β are not cycles of length n−1, the distance betweenPαandPβis at most 4 by Proposition 2.5. By Proposition 2.8, the diameter of the large connected component is 4.
Assume thatn≥6,n−1 is prime andu≥2. Forα, β long cycles, the distance betweenDPα andEPβ is at most 4 by Proposition 2.4. Also, DPα is at distance 2 from a non-scalar diagonal matrix. For all otherα,DPαcommutes with a non-scalar diagonal matrix. That means that the diameter is at most 4, It is easy to check that P(1,...,n)andP(1,...,n−1)are at distance 4, so the diameter is 4. Ifn≥6 is even,n−1 is not a prime andu≥2, the proof that the diameter is 4 is exactly the same.
Ifn, n−1 are not primes andu= 1, then we know that Γ(GLn(S)) is connected, with diameter at most 5, see [5, Theorem 7(b)]. By Proposition 2.7, the diameter is indeed 5.
Assume thatn≥9 is odd and not prime andu≥2. Take a long cycleα. Fork|n, 1< k < n,DPα∼D0Pαk for someD0, and D0Pαk∼F for some non-scalar diagonal matrix F. If β is not a long cycle, it is adjacent to a non-scalar diagonal matrix.
Therefore the graph Γ(GLn(S)) is connected with diameter ≤ 5. If α = (1, . . . , n) and β = (1, . . . , n−2, n, n−1) are different long cycles and k, l|n, k, l 6= n, then βl(αk(n)) =βl(k) =k+l andαk(βl(n)) =αk(l−1) =k+l−1, so there is no path of length ≤3 between Pα and Pβ. That means that the diameter is at least 4. If Conjecture 2.10 holds, the diameter is indeed 5.
This completes the proof of the theorem.
3. Proofs of Propositions.
Proof of Proposition 2.3. Write A = DPα, B = EPβ. Then (AB)ij = P
kaikbkj = 0 unless j = β(α(i)), in which case it is aiα(i)bα(i)β(α(i)) = dieα(i). Similarly, (BA)ij is nonzero (and equal toeidβ(i)) ifj=α(β(i)). ThereforeDPαand EPβ are adjacent in Γ(GLn(S)) if and only ifαβ=βαanddieα(i)=eidβ(i).
Proof of Proposition 2.4. Writen= 2m.
We claim that there exist diagonal matrices D0, E0, F and a permutation τ so that
DPα∼D0Pαm ∼F Pτ∼E0Pβm ∼EPβ,
where eitherτ6= id orF 6=aI.
Note that both αm and βm are products of m 2-cycles. There are two cases.
First, there can be a non-empty proper subset T of{1, . . . ,2m} such thatαm(T) = βm(T) = T. In this case, define F = diag(fi), where fi = 1 if i∈ T andfi =a if i6=T, wherea∈U(S)\ {1}. We haveD0Pαm ∼F∼E0Pβm for allD0andE0, and by Proposition 2.4 there exist suchD0 andE0 thatDPα∼D0Pαm andEPβ∼E0Pβm.
If such a T does not exist, then the set {1, βm(1), αmβm(1), βmαmβm(1), . . .}, which is obviously non-empty and closed underαmandβm, must equal{1, . . . ,2m}.
That means that
π= (1, βm(1), αmβm(1), βmαmβm(1), . . .)
is a cycle of length 2m. Defineτ =π2. In other words, ifi= (αmβm)k(1) for some k, thenτ(i) =αmβm(i), and ifi=βm(αmβm)k(1) for somek, thenτ(i) =βmαm(i).
Sincem≥2,τ6= id.
We claim that τ αm = αmτ. If i = (αmβm)k(1) for some k, then αm(i) = βm(αmβm)k−1(1) (fori= 1, we can takek=m), and soτ(αm(i)) =βmαm(αm(i)) = βm(i). On the other hand, τ(i) = αmβm(i), so αm(τ(i)) = βm(i). The proof for i=βm(αmβm)k(1) for some kis similar, as is the proof thatτ βm=βmτ.
Sinceα∼αm, the conditionDPα∼D0Pαm is equivalent todi/dαm(i)=d0i/d0α(i). It is easy to see that one set ofd0i’s (and the only one up to scalar) that satisfies the equations is
d0i=
m−1
Y
j=0
dαj(i).
It is clear from these formulas that for everyk, 0≤k≤m−1, we have d0id0αm(i)=d1· · ·d2m
In other words,d0id0αm(i)is independent ofi.
Similarly, up to a scalar, the only solution ofEPβ∼E0Pβm is e0i=
m−1
Y
j=0
eβj(i).
ande0ie0βm(i)is independent ofi.
Our goal is to find F so that D0Pαm ∼ F Pτ ∼ E0Pβm. The first condition is equivalent tod0i/d0τ(i)=fi/fαm(i). Now note that since
d0i
d0τ(i) · d0αm(i)
d0τ(αm(i))
= d0id0αm(i)
d0τ(i)d0αm(τ(i)))
= 1,
the equations forfi/fαm(i) andfαm(i)/fiare equivalent. In other words, it is enough that we have
fi
fαm(i)
= d0i
d0τ(i) fori= (αmβm)k(1) and similarly
fi fβm(i)
= e0i
e0τ(i) fori=βm(αmβm)k(1).
We have 2m equations for fi’s, and each fi appears exactly once in the numera- tor and exactly once in the denominator. Furthermore, since τ((αmβm)k(1)) = (αmβm)k+1(1), the right-hand sides of the first m equations multiply into 1, and similarly the right-hand sides of the second m equations multiply into 1. In other words, these equations have a solution (which is unique up to a scalar factor).
We can even be completely explicit: let us prove that one solution to these equa- tions is
fi= 1
d0αmβm(i)e0βm(i)
ifi= (αmβm)k(1),
fi= 1
d0αm(i)e0βmαm(i)
ifi=βm(αmβm)k(1).
Ifi= (αmβm)k(1) (without loss of generality,k≥1), thenαm(i) =βm(αmβm)k−1(1) andfαm(i)= (d0αm(αm(i))e0βmαm(αm(i)))−1= (d0ie0βm(i))−1 and so
fi fαm(i)
=
d0ie0βm(i)
d0αmβm(i)e0βm(i)
= d0i d0τ(i).
The proof thatfi/fβm(i)=e0i/e0τ(i)fori=βm(αmβm)k(1) is completely analogous.
This completes the proof of Proposition 2.4.
Example 3.1. Take n = 8, α= (15386724), β = (16823754). We have α4 = (16)(23)(48)(57),β4= (13)(24)(58)(67),π= (13248576) andτ= (1287)(3456).
To better understand whereτ comes from, let the 2-cycles ofαm andβmbe vertices of a regular octagon so that(1, α4(1))is the left-most vertex, so that two 2-cycles are adjacent if and only if one of them is a cycle ofα4and the other one is a cycle of β4 and they have a common element. Furthermore, choose such an order of the elements of a 2-cycle that neighbours have the common element in the same place.
(84) (24) (23) (13) (16)
(76) (75)
(85)
Fig. 3.1.Constructingτ.
The first elements of2-cycles form one cycle ofτ (in, say, clockwise direction), and second elements form the other cycle of τ. Clearly, conjugating withτ shifts the 2-cycles clockwise by 2, so both α4 and β4 are preserved under conjugation with τ.
See Figure 3.1.
We have
d01=d1d5d3d8, d05=d5d3d8d6, d03=d3d8d6d7, d08=d8d6d7d2,
d06=d6d7d2d4, d07=d7d2d4d1, d02=d2d4d1d5, d04=d4d1d5d3
and similarly
e01=e1e6e8e2, e06=e6e8e2e3, e08=e8e2e3e7, e02=e2e3e7e5,
e03=e3e7e5e4, e07=e7e5e4e1, e05=e5e4e1e6, e04=e4e1e6e8. The equations forfi’s (after removing half the equations as described above) are
f1/f6=d01/d02, f2/f3=d02/d08, f8/f4=d08/d07, f7/f5=d07/d01
and
f3/f1=e03/e04, f4/f2=e04/e05, f5/f8=e05/e06, f6/f7=e06/e03. If we setf1= (d02e03)−1, the only solution is
f1= 1
d02e03, f3= 1
d02e04, f2= 1
d08e04, f4= 1 d08e05,
f8= 1
d07e05, f5= 1
d07e06, f7= 1
d01e06, f6= 1 d01e03.
Proof of Proposition 2.5. Again, write n = 2m. Suppose thatα and β are long cycles. It is enough to find τ 6= id that commutes with αm and βm. One suchτis the involution that maps (αmβm)k(1) to (αmβm)kαm(1), (βmαm)kβm(1) to (βmαm)k+1(1), and preserves all elements that cannot by reached from 1 by applying αm and βm. Compare with the construction of τ in the proof of Proposition 2.4.
Then τ is a well-defined involution that commutes with αm and βm. We leave the details for the reader.
Assume that neitherαnorβ is a long cycle. Let us first examine the case where αis a cycle of length less thann−1, orαdecomposes as a product of disjoint cycles, where at least one cycle has length less thanm. Thenαcommutes with a permutation πwith at leastm+ 1 fixed points. Now,βeither also commutes with a permutationρ with at leastm+ 1 fixed points, in which caseπandρhave a common transposition in their centralizers, or β =ρ1ρ2 is a product of two disjointm-cycles. In the latter case, β commutes with both ρ1 and ρ2 and we can choose the one that has more of its fixed points in common withπ. If α andβ are both products of two disjoint m-cycles, we can also always choose one m-cycle from each permutation such that they have at least two common fixed points and therefore a common transposition in their centralizers.
Letαbe a long cycle. Ifβ =ρ1. . . ρr, where there existsisuch that the length of ρi is at least 2 and at most m−1, then β commutes with ρi which has at least m+ 1 fixed points. Thus,ρi commutes with at least one transposition in the cyclic decomposition of αm. Suppose nowβ =ρ1ρ2 is a product of two m-cycles. If the cycleρj is disjoint from some transpositionτ in the cyclic decomposition ofαm, then α∼αm ∼τ ∼ρj ∼β is a path in Γ(GLn(S)), thus the distance between αand β is at most 4. Otherwise, each transposition in the cyclic decomposition of αm has one element from ρ1 = (a1, . . . , am) and one element from ρ2 = (b1, . . . , bm). We can assume that τ = (a1, b1) is a transposition in the cyclic decomposition of αm, since we can cyclically permute the elements ofρ2. Now, β ∼(a1, b1)· · ·(am, bm)∼
τ ∼αm ∼α is a path of length 4 in Γ(GLn(S)) between αand β. It only remains to show that α and β = ρ1 are also at distance at most 4, where ρ1 is a cycle of length at most n−2. In this case, β has at least 2 fixed points, say b1, b2, so it commutes with the transposition τ = (b1, b2). Since τ hasn−2 > m fixed points, it commutes with at least one transposition σ in the cyclic decomposition of αm. Therefore,α∼αm∼σ∼τ ∼β is a path of length 4 in Γ(GLn(S)) betweenαand β.
Proof of Proposition 2.6. Sincen is prime, we can writen= 2m+ 1, where m ≥3. Assume first that α is a cycle. If α is a cycle of length n−1, then αm is a product of m disjoint transpositions, therefore α is at distance 2 to the disjoint transpositionsπ1, . . . , πm. Ifαis a cycle of length less thann−1, thenαcommutes with at least one transposition (consisting of two fixed points ofα), so α is also at distance 2 to at least m disjoint transpositions. Now, if β is also a cycle, we can similarly see that it is at distance 2 tomdisjoint transpositionsρ1, . . . , ρm, but since m ≥3 there exist i and j such thatπi and ρj are disjoint and therefore commute, proving thatαandβ are at distance 5 or less. Otherwise, we have a decomposition β = ρ1· · ·ρr into a product of disjoint cycles of increasing length. Note that the length of ρ1 has to be at most m, so ρ1 commutes with every transposition with elements from the set of at leastm+ 1≥4 elements, so one of these transpositions has to be disjoint with, say,π1. Now, the only remaining case is when neitherαnor β are cycles. But then bothαandβare at distance two to a set of all transpositions consisting of elements from some sets of size at least 4, so we can always choose two disjoint transpositions that commute, which proves that αand β are indeed at distance 5 or less.
Proof of Proposition 2.8. Suppose otherwise, i.e. there exists a path α ∼ αk ∼ βl ∼ β in Γ(GLn(S)) for some integers 1 ≤ k, l ≤ 2m. Since commuting with a permutation is equivalent to commuting with its inverse, we can suppose that 1≤k, l≤m. So,
αkβl(1) =
(m+l+k+ 1 (mod 2m), l≤m−1
k+ 2, l=m.
Sinceαk andβl commute, we have thatαkβl(1) =βlαk(1). Ifl≤m−1, we have
m+l+k+1 (mod 2m) =βlαk(1) =βl(k+1) =
k+l+ 1, l≤m−k 1, l=m−k+ 1
k+l, m−k+ 2≤l≤m−1,
a contradiction. In the latter case,l=m, we obtain that k+ 2 =βmαk(1) =βm(k+ 1) =
(k+m k >1
1 k= 1,
which is again a contradiction.
Proof of Proposition 2.9. We have to prove that there is no path of length 4 or less between α and β. Note that α and β commute only with the powers of themselves, so suppose there existsγsuch thatγ commutes withαk andβl for some kand l. First, we prove that we can assume thatk divides 2m. Letd= gcd(k,2m).
Letsandtbe integers such thatks+ 2mt=d. Sinceα∼αk ∼γis a path in Γ(Sn), α ∼αsk ∼ γ is also a path in Γ(Sn). Since αsk =αd(1−2mt) =αd(α2m)−t = αd, α∼αd∼γ is a path in Γ(Sn). We can similarly assume thatl divides 2m.
Suppose first thatk≤l. Since 2m+ 1 is the only fixed point of the permutation αk andαk(γ(2m+ 1)) =γ(αk(2m+ 1)) =γ(2m+ 1), we see that 2m+ 1 is also a fixed point ofγ. Similarly,m+ 1 is a fixed point ofβand thus also a fixed point ofγ.
Iff ≤mis a fixed point forγ, then by applyingαak for a suitable integera, we can achieve thatf +ak, 1≤f+ak≤m, is also a fixed point ofγ. We can choosea such thatf+ak≤mandf+(a+1)k > m. This implies thatβl(f+ak) =f+ak+l+1 is also a fixed point for γ. But similarly, for any fixed pointf ≥m we can chooseb such thatf+bk≤2m+ 1 andf+ (b+ 1)k >2m+ 1, soβl(f+bk) =f+bk+l−2m−1 is also a fixed point for γ. Since we can repeat either of these two steps arbitrarily many times, by also applying αk (and thus getting rid of 2m, akand bk), we arrive at the conclusion thatf+c(l+ 1) +d(l−1) is a fixed point forγ for anycandd.
Iflis even, this implies thatγis an identity. Iflis odd, all odd numbers are fixed points forγ, sinceβl(2m+ 1) =l is a fixed point. If mis odd, all even numbers are also fixed points, sincem+ 1 is an even fixed point forγ. On the other hand, ifmis even, thenl < mandβl(1) =l+ 1 is an even fixed point.
Let us now look at the case l < k. Since αk commutes withγ andγ commutes withβl, for eachτ also (τ ατ−1)k commutes with γ0 =τ γτ−1and γ0 commutes with (τ βτ−1)l. If we chooseτ= (m+ 1, . . . ,2m+ 1), we getα0 =τ ατ−1= (1, . . . , m,2m+ 1, m+ 1, . . . ,2m−1)(2m) and β0 = τ βτ−1 = (1, . . . ,2m)(2m+ 1). We can now proceed similarly as above. Namely, let f ≤m be a fixed point forγ0. By applying β0al for a suitable integer a, we can achieve thatf +al, 1 ≤f +al ≤m, is also a fixed point ofγ0. We can chooseasuch thatf +al≤mandf + (a+ 1)l > m. This implies thatα0k(f+al) =f+al+k−1 (sincek > l,α0k(f+al)6= 2m+ 1) is also a fixed point forγ0. But similarly, for any fixed pointf ≥mwe can choosebsuch that
f+bl≤2mandf+ (b+ 1)l >2m, soα0k(f+bl) =f+bl+k+ 1−2mis also a fixed point forγ0. Since we can repeat either of these two steps arbitrarily many times, by also applying βl (and thus getting rid of 2m, al andbl), we arrive at the conclusion thatf+c(k+ 1) +d(k−1) is a fixed point forγ0 for anycandd. But since both 2m and 2m+ 1 are fixed points forγ0,γ0 has to be an identity.
REFERENCES
[1] S. Akbari, A. Mohammadian, H. Radjavi, and P. Raja. On the diameters of commuting graphs.
Linear Algebra Appl., 418(1):161–176, 2006.
[2] S. Akbari and P. Raja. Commuting graphs of some subsets in simple rings. Linear Algebra Appl., 416(2-3):1038–1047, 2006.
[3] J. Ara´ujo, W. Bentz, and J. Konieczny. The commuting graph of the symmetric inverse semi- group. arXiv:1205.1664, May 2012.
[4] D. Dolˇzan and P. Oblak. Invertible and nilpotent matrices over antirings.Linear Algebra Appl., 430(1):271–278, 2009.
[5] D. Dolˇzan and P. Oblak. Commuting graphs of matrices over semirings. Linear Algebra Appl., 435(7):1657–1665, 2011.
[6] M. Giudici and A. Pope. The diameters of commuting graphs of linear groups and matrix rings over the integers modulom.Australas. J. Combin., 48:221–230, 2010.
[7] A. Iranmanesh and A. Jafarzadeh. On the commuting graph associated with the symmetric and alternating groups. J. Algebra Appl., 7(1):129–146, 2008.
[8] A. Mohammadian. On commuting graphs of finite matrix rings.Comm. Algebra, 38(3):988–994, 2010.
[9] Y. Segev. The commuting graph of minimal nonsolvable groups.Geom. Dedicata, 88(1-3):55–66, 2001.
