Cycle graph (algebra)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For other uses, see Cycle graph (disambiguation).

In group theory, a sub-field of abstract algebra, a group cycle graph illustrates the various cycles of a group and is particularly useful in visualizing the structure of small finite groups. For groups with fewer than 16 elements, the cycle graph determines the group (up to isomorphism).

A cycle is the set of powers of a given group element a, where an, the n-th power of an element a is defined as the product of a multiplied by itself n times. The element a is said to generate the cycle. In a finite group, some non-zero power of a must be the group identity, e; the lowest such power is the order of the cycle, the number of distinct elements in it. In a cycle graph, the cycle is represented as a polygon, with the vertices representing the group elements, and the connecting lines indicating that all elements in that polygon are members of the same cycle.

Cycles[edit]

Cycles can overlap, or they can have no element in common but the identity. The cycle graph displays each interesting cycle as a polygon.

If a generates a cycle of order 6 (or, more shortly, has order 6), then a6 = e. Then the set of powers of a2, {a2, a4, e} is a cycle, but this is really no new information. Similarly, a5 generates the same cycle as a itself.

So, only the primitive cycles need be considered, namely those that are not subsets of another cycle. Each of these is generated by some primitive element, a. Take one point for each element of the original group. For each primitive element, connect e to a, a to a2, ..., an−1 to an, etc., until e is reached. The result is the cycle graph.

When a2 = e, a has order 2 (is an involution), and is connected to e by two edges. It is conventional to show only one edge in this case.

Properties[edit]

Dihedral group4 example.png
Dih4 kaleidoscope with red mirror and 4-fold rotational generators
Dih4 cycle graph.svg
Cycle graph for dihedral group Dih4.

As an example of a group cycle graph, consider the dihedral group Dih4. The multiplication table for this group is shown on the left, and the cycle graph is shown on the right with e specifying the identity element.

o e b a a2 a3 ab a2b a3b
e e b a a2 a3 ab a2b a3b
b b e a3b a2b ab a3 a2 a
a a ab a2 a3 e a2b a3b b
a2 a2 a2b a3 e a a3b b ab
a3 a3 a3b e a a2 b ab a2b
ab ab a b a3b a2b e a3 a2
a2b a2b a2 ab b a3b a e a3
a3b a3b a3 a2b ab b a2 a e

Notice the cycle e, a, a2, a3. It can be seen from the multiplication table that successive powers of a behave this way. The reverse is also true. In other words: (a3)2 = a2, (a3)3 = a and {{{1}}}. This behavior is true for any cycle in any group – a cycle may be traversed in either direction.

Cycle graph of the quaternion group Q8.

Cycles that contain a non-prime number of elements implicitly have cycles that are not shown in the graph. For the group Dih4 above, we might want to draw a line between a2 and e since (a2)2 = e, but since a2 is part of a larger cycle, this is not done.

There can be ambiguity when two cycles share an element that is not the identity element. Consider for example, the simple quaternion group, whose cycle graph is shown on the right. Each of the elements in the middle row when multiplied by itself gives −1 (where 1 is the identity element). In this case we may use different colors to keep track of the cycles, although symmetry considerations will work as well.

As above, the 2-element cycles should be connected by two lines, but this is usually abbreviated by a single line.

Two distinct groups may have cycle graphs that have the same structure, and can only be distinguished by the product table, or by labeling the elements in the graph in terms of the group's basic elements. The lowest order for which this problem can occur is order 16 in the case of Z2 × Z8 and the modular group, as shown below. (Note – the cycles with common elements are distinguished by symmetry in these graphs.)

Cycle graphs of two order 16 groups
GroupDiagramC2C8.svg GroupDiagramMOD16.svg
Z2 × Z8 Modular group

The multiplication table of Z2 × Z8 is shown below:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14
2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1
3 2 5 4 7 6 9 8 11 10 13 12 15 14 1 0
4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3
5 4 7 6 9 8 11 10 13 12 15 14 1 0 3 2
6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5
7 6 9 8 11 10 13 12 15 14 1 0 3 2 5 4
8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7
9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6
10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9
11 10 13 12 15 14 1 0 3 2 5 4 7 6 9 8
12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11
13 12 15 14 1 0 3 2 5 4 7 6 9 8 11 10
14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13
15 14 1 0 3 2 5 4 7 6 9 8 11 10 13 12

Other information derivable from cycle graphs[edit]

  • The inverse of an element could be identified in the cycle graph. It is the element whose distance from the identity is the same if going through the cycle in the opposite direction.

Graph characteristics of particular group families[edit]

Certain group types give typical graphs:

Cyclic groups Zn, order n, is a single cycle graphed simply as an n-sided polygon with the elements at the vertices.

GroupDiagramMiniC1.svg GroupDiagramMiniC2.svg GroupDiagramMiniC3.svg GroupDiagramMiniC4.svg GroupDiagramMiniC5.svg GroupDiagramMiniC6.svg GroupDiagramMiniC7.svg GroupDiagramMiniC8.svg
Z1 Z2 = Dih1 Z3 Z4 Z5 Z6=Z3×Z2 Z7 Z8
GroupDiagramMiniC9.svg GroupDiagramMiniC10.svg GroupDiagramMiniC11.svg GroupDiagramMiniC12.svg GroupDiagramMiniC13.svg GroupDiagramMiniC14.svg GroupDiagramMiniC15.svg GroupDiagramMiniC16.svg
Z9 Z10=Z5×Z2 Z11 Z12=Z4×Z3 Z13 Z14=Z7×Z2 Z15=Z5×Z3 Z16
GroupDiagramMiniC17.svg GroupDiagramMiniC18.svg GroupDiagramMiniC19.svg GroupDiagramMiniC20.svg GroupDiagramMiniC21.svg GroupDiagramMiniC22.svg GroupDiagramMiniC23.svg GroupDiagramMiniC24.svg
Z17 Z18=Z9×Z2 Z19 Z20=Z5×Z4 Z21=Z7×Z3 Z22=Z11×Z2 Z23 Z24=Z8×Z3
GroupDiagramMiniC2.svg GroupDiagramMiniD4.svg GroupDiagramMiniC2x3.svg GroupDiagramMiniC2x4.svg
Z2 Z22 = Dih1 Z23 = Dih2×Dih1 Z24 = Dih22

When n is a prime number, groups of the form (Zn)m will have (nm − 1)/(n − 1) n-element cycles sharing the identity element.

GroupDiagramMiniD4.svg GroupDiagramMiniC2x3.svg GroupDiagramMiniC2x4.svg GroupDiagramMiniC3x2.svg
Z22 = Dih2 Z23 = Dih2×Dih1 Z24 = Dih22 Z32

Dihedral groups Dihn, order 2n consists of an n-element cycle and n 2-element cycles.

GroupDiagramMiniC2.svg GroupDiagramMiniD4.svg GroupDiagramMiniD6.svg GroupDiagramMiniD8.svg GroupDiagramMiniD10.svg GroupDiagramMiniD12.svg GroupDiagramMiniD14.svg GroupDiagramMiniD16.svg GroupDiagramMiniD18.png GroupDiagramMiniD20.png
Dih1 = Z2 Dih2 = Z22 Dih3 Dih4 Dih5 Dih6=Dih3×Z2 Dih7 Dih8 Dih9 Dih10=Dih5×Z2

Dicyclic groups, Dicn = Q4n, order 4n.

GroupDiagramMiniQ8.svg GroupDiagramMiniX12.svg GroupDiagramMiniQ16.svg GroupDiagramMiniQ20.png GroupDiagramMiniQ24.png
Dic2 = Q8 Dic3 = Q12 Dic4 = Q16 Dic5 = Q20 Dic6 = Q24

Other direct products:

GroupDiagramMiniC2C4.svg GroupDiagramMiniC2x2C4.svg GroupDiagramMiniC2C6.svg GroupDiagramMiniC2C8.svg GroupDiagramMiniC4x2.svg
Z4×Z2 Z4×Z22 Z6×Z2 Z8×Z2 Z42

Symmetric groups – The symmetric group Sn contains, for any group of order n, a subgroup isomorphic to that group. Thus the cycle graph of every group of order n will be found in the cycle graph of Sn. See example: Subgroups of S4

GroupDiagramMiniA4xC2.png
A4×Z2
Symmetric group 3; cycle graph.svg
S3 = Dih3
Symmetric group 4; cycle graph.svg
S4
Dihedral group of order 8; cycle graph; subgroup of S4 (elements 1,6...).svg
One of three Dih4 found in S4
Same as GroupDiagramMiniD8.svg

See also[edit]

External links[edit]

References[edit]

  • Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica 1990, §4.2.3 Cycles, Stars, and Wheels, pp. 144-147
  • Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed, 1993. pp. 83-98
  • Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 1999 p. 13
  • Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematics Cambridge, England: Cambridge University Press, 2003, §6.2.4 Cycles, Stars, and Wheels pp. 248-249