Cycle graph (algebra)

Example and properties

As an example of a group cycle graph, consider the dihedral group Dih₄. 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.

Notice the cycle {e, a, a², a³} in the multiplication table, with a⁴ = e. The inverse a⁻¹ = a³ is also a generator of this cycle: (a³)² = a², (a³)³ = a, and (a³)⁴ = e. Similarly, any cycle in any group has at least two generators, and may be traversed in either direction. 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. Two distinct cycles cannot intersect in a generator.

Cycles that contain a non-prime number of elements have cyclic subgroups that are not shown in the graph. For the group Dih₄ above, we could draw a line between a² and e since (a²)² = e, but since a² is part of a larger cycle, this is not an edge of the cycle 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. 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 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.

Non-uniqueness

The cycle graph of a group is not uniquely determined up to graph isomorphism; nor does it uniquely determine the group up to group isomorphism. That is, the graph obtained depends on the set of generators chosen, and two different groups (with chosen sets of generators) can generate the same cycle graph.

A single group can have different cycle graphs

For some groups, choosing different elements to generate the various primitive cycles of that group can lead to different cycle graphs. There is an example of this for the abelian group ${\displaystyle C_5\times C_2\times C_2}$, which has order 20. We denote an element of that group as a triple of numbers ${\displaystyle (i;j,k)}$, where ${\displaystyle 0\le i<5}$ and each of ${\displaystyle j}$ and ${\displaystyle k}$ is either 0 or 1. The triple ${\displaystyle (0;0,0)}$ is the identity element. In the drawings below, ${\displaystyle i}$ is shown above ${\displaystyle j}$ and ${\displaystyle k}$.

This group has three primitive cycles, each of order 10. In the first cycle graph, we choose, as the generators of those three cycles, the nodes ${\displaystyle (1;1,0)}$, ${\displaystyle (1;0,1)}$, and ${\displaystyle (1;1,1)}$. In the second, we generate the third of those cycles --- the blue one --- by starting instead with ${\displaystyle (2;1,1)}$.

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

Different groups can have the same cycle graph

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.

There is an example of this already for groups of order 16, the two groups being ${\displaystyle C_8\times C_2}$ and ${\displaystyle C_8{⋊}_5{C}_2}$. The abelian group ${\displaystyle C_8\times C_2}$ is the direct product of the cyclic groups of orders 8 and 2. The non-abelian group ${\displaystyle C_8{⋊}_5{C}_2}$ is that semidirect product of ${\displaystyle C_8}$ and ${\displaystyle C_2}$ in which the non-identity element of ${\displaystyle C_2}$ maps to the multiply-by-5 automorphism of ${\displaystyle C_8}$.

In drawing the cycle graphs of those two groups, we take ${\displaystyle C_8\times C_2}$ to be generated by elements s and t with

${\displaystyle s^8=t^2=1\text{and}ts=st,}$

where that latter relation makes ${\displaystyle C_8\times C_2}$ abelian. And we take ${\displaystyle C_8{⋊}_5{C}_2}$ to be generated by elements 𝜎 and 𝜏 with

${\displaystyle {\sigma }^8={\tau }^2=1\text{and}\tau \sigma ={\sigma }^5\tau .}$

Here are cycle graphs for those two groups, where we choose ${\displaystyle st}$ to generate the green cycle on the left and ${\displaystyle \sigma \tau }$ to generate that cycle on the right:

In the right-hand graph, the green cycle, after moving from 1 to ${\displaystyle \sigma \tau }$, moves next to ${\displaystyle {\sigma }^6,}$ because

${\displaystyle (\sigma \tau )(\sigma \tau )=\sigma (\tau \sigma )\tau =\sigma ({\sigma }^5\tau )\tau ={\sigma }^6.}$

History

Cycle graphs were investigated by the number theorist Daniel Shanks in the early 1950s as a tool to study multiplicative groups of residue classes. Shanks first published the idea in the 1962 first edition of his book Solved and Unsolved Problems in Number Theory. In the book, Shanks investigates which groups have isomorphic cycle graphs and when a cycle graph is planar. In the 1978 second edition, Shanks reflects on his research on class groups and the development of the baby-step giant-step method:

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.

Graph characteristics of particular group families

Certain group types give typical graphs:

Cyclic groups Z_n, 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 (Z_n)^m will have (n^m − 1)/(n − 1) n-element cycles sharing the identity element:

Dihedral groups Dih_n, order 2n consists of an n-element cycle and n 2-element cycles:

Dicyclic groups, Dic_n = Q_4n, order 4n:

Other direct products:

Symmetric groups – The symmetric group S_n 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 S_n.
See example: Subgroups of S₄

Extended example: Subgroups of the full octahedral group

The full octahedral group is the direct product ${\displaystyle S_4\times Z_2}$ of the symmetric group S₄ and the cyclic group Z₂.
Its order is 48, and it has subgroups of every order that divides 48.

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).

Like all graphs a cycle graph can be represented in different ways to emphasize different properties. The two representations of the cycle graph of S₄ are an example of that.