Cycle graph (algebra)

Cycle graphs are particularly useful in visualizing the structure of small finite groups.

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.

In a finite group, some non-zero power of a must be the group identity, which we denote either as e or 1; the lowest such power is the order of the element a, the number of distinct elements in the cycle that it generates.

Suppose that a group element a generates a cycle of order 6 (has order 6), so that the nodes a, a2, a3, a4, a5, and a6 = e are the vertices of a hexagon in the cycle graph.

The element a2 then has order 3; but making the nodes a2, a4, and e be the vertices of a triangle in the graph would add no new information.

When a group element a has order 2 (so that multiplication by a is an involution), the rule above would connect e to a by two edges, one going out and the other coming back.

Except when the intent is to emphasize the two edges of such a cycle, it is typically drawn[1] as a single line between the two elements.

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.

More generally, the number of generators of a cycle with n elements is given by the Euler φ function of n, and any of these generators may be written as the first node in the cycle (next to the identity e); or more commonly the nodes are left unmarked.

Cycles that contain a non-prime number of elements have cyclic subgroups that are not shown in the graph.

There can be ambiguity when two cycles share a non-identity element.

For example, the 8-element quaternion group has cycle graph shown at right.

In this case we may use different colors to keep track of the cycles, although symmetry considerations will work as well.

As noted earlier, the two edges of a 2-element cycle are typically represented as a single line.

The inverse of an element is the node symmetric to it in its cycle, with respect to the reflection which fixes the identity.

[2] For some groups, choosing different elements to generate the various primitive cycles of that group can lead to different cycle graphs.

[2] We denote an element of that group as a triple of numbers

The two resulting graphs are not isomorphic because they have diameters 5 and 4 respectively.

Two different (non-isomorphic) groups can have cycle graphs that are isomorphic, where the latter isomorphism ignores the labels on the nodes of the graphs.

It follows that the structure of a group is not uniquely determined by its cycle graph.

is the direct product of the cyclic groups of orders 8 and 2.

In drawing the cycle graphs of those two groups, we take

to be generated by elements 𝜎 and 𝜏 with Here are cycle graphs for those two groups, where we choose

Cycle graphs were investigated by the number theorist Daniel Shanks in the early 1950s as a tool to study multiplicative groups of residue classes.

[3] Shanks first published the idea in the 1962 first edition of his book Solved and Unsolved Problems in Number Theory.

[4] In the book, Shanks investigates which groups have isomorphic cycle graphs and when a cycle graph is planar.

[5] In the 1978 second edition, Shanks reflects on his research on class groups and the development of the baby-step giant-step method:[6] The cycle graphs have proved to be useful when working with finite Abelian groups; and I have used them frequently in finding my way around an intricate structure [77, p. 852], in obtaining a wanted multiplicative relation [78, p. 426], or in isolating some wanted subgroup [79].Cycle graphs are used as a pedagogical tool in Nathan Carter's 2009 introductory textbook Visual Group Theory.

[7] 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: 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: Dihedral groups Dihn, order 2n consists of an n-element cycle and n 2-element cycles: Dicyclic groups, Dicn = Q4n, order 4n: Other direct products: Symmetric groups – The symmetric group Sn contains, for any group of order n, a subgroup isomorphic to that group.

See example: Subgroups of S4 The full octahedral group is the direct product

In the examples below nodes that are related to each other are placed next to each other, so these are not the simplest possible cycle graphs for these groups (like those on the right).