Cycle graph (algebra)
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 less 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 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 series of polygons, 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
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 we only need to consider the primitive cycles, those which 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, ... until you come back to e. The result is the cycle graph.
(Technically, the above description implies that if a2 = e, so a has order 2 (is an involution), it's connected to e by two edges. It's conventional to only use one.)
Properties
As an example of a group cycle graph, consider 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 in fact behave this way. The reverse case is also true. In other words: (a3)2=a2 , (a3)3=a and (a3)4=e . This behavior is true for any cycle in any group - a cycle may be traversed in either direction.
Cycles which contain a non-prime number of elements will implicitly have cycles which are not connected 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 which 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 groups basic elements. The lowest order for which this problem can occur is order 16 in the case of Z2 x Z8 and the modular group, as shown below. (Note - the cycles with common elements are distinguished by symmetry in these graphs.)
Other information derivable from cycle graphs
- The inverse of any element can be located on the cycle graph. The inverse of an element is simply its opposite element in the same cycle. If a cycle contains an even number of elements then there will be one element which is its own opposite, and therefore is its own inverse. For example, in the Dih4 graph above, the inverse of a is its opposite, a3, while a2 is its own inverse.
Graph characteristics of particular group families
Certain group types give typical graphs:
- Cyclic groups Zn is a single cycle graphed simply as an n-sided polygon with the elements at the vertices.
 |
 |
 |
 |
 |
 |
 |
 |
|---|---|---|---|---|---|---|---|
| Z1 | Z2 | Z3 | Z4 | Z5 | Z6 | Z7 | Z8 |
- When n is a prime number, groups of the form (Zn)m will have (nm-1)/(n-1) n-element cycles sharing the common identity element.
 |
 |
 |
 |
|---|---|---|---|
| Z22 | Z23 | Z24 | Z32 |
- Dihedral groups Dihn consists of an n-element cycle and n 2-element cycles.
|
|
 |
 |
 |
 |
 |
|---|---|---|---|---|---|---|
| Dih1 | Dih2 | Dih3 | Dih4 | Dih5 | Dih6 | Dih7 |
- 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 as a subgraph of the cycle graph of Sn.
See also
External link
Reference
- Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993.