How in general does one construct a cycle graph for a group?

Question

I think I know how to interpret a cycle graph for a group, but I don’t know how to construct one. In particular, I don’t know a general rule of how to find the “basic elements” which to take the powers of.

Is there a general algorithm for constructing the cycle graph of a finite group, which always ensures that you get the correct unique cycle graph?

Answer 1

You can just take one element at a time (though I don't know about computational efficiency or stuff like that). Start with the graph containing only the identity element (and no edges). In each step after this, you:

1. Pick an element not already in the graph.
2. Compute the cyclic subgroup generated by the element and add the cycle to the graph (connecting to already existing nodes as needed).
3. If the graph contains a sub-cycle of the new cycle, you delete the sub-cycle.

Repeat until you have added all the (finitely many) elements.

Let's say we want to make the cycle graph for $Z_4 \times Z_2 = \langle x\rangle\times \langle y \rangle$. We start with the identity element, and then we pick an arbitrary element, say $x^2$. We see that $\langle x^2 \rangle = \{1, x^2\}$, so we get the graph:

x^2
 |
 1

Now we pick another element, say x, and we find that $\langle x \rangle = \{1, x, x^2, x^3\}$. Since the cycle $\{1, x^2\}$ on the graph is a subset of the new cycle, we replace it:

  x^2
 /   \
x^3   x
 \   /
   1

Let's pick $xy$ now. We get $\langle xy \rangle = \{1, xy, x^2, x^3y\}$, so we draw:

       x^2
    ⟋ /  \ ⟍
x^3y x^3   x xy
    ⟍ \  / ⟋
        1

(Please excuse the ascii...). Now we take $y$ and find $\langle y \rangle = \{1, y\}$, so we draw:

       x^2
    ⟋ /  \ ⟍
x^3y x^3   x xy
    ⟍ \  / ⟋
        1
        |
        y

and finally we take $x^2y$, giving $\langle x^2y \rangle = \{1, x^2y\}$, which gives us the finished cycle graph:

       x^2
    ⟋ /  \ ⟍
x^3y x^3   x xy
    ⟍ \  / ⟋
        1
       / \
      y  x^2y

(Note that it is kind of silly to start with $x^2$, since it will certainly be contained in the cycle generated by $x$. I did it for illustrative purposes of course.)

EDIT: How to find primitive elements, or "basic elements" as you call them. Let's say you want to know if a particular element $g$ will be a generator for a cycle on the cycle graph. Then you have to check if $g$ can be written as a power of another element, which has order strictly greater than that of $g$. If this is not the case, then $g$ is a primitive element.

If we don't know anything about the structure of the group, this would amount to basically drawing up the full graph. However, if we know the group, we can find out more quickly. For example, if $g$ is of maximal order in the group, then it must be a primitive element. This immediately shows that $x$ and $xy$ in our example will be primitive elements. Note that we can easily find them without computing anything. Similarly, if $D_{2n} = \langle r, s \rangle$ is the dihedral group of order $2n$, then $r$ will be a primitive element.

Generalising the situation in the example, I noticed the following: If $Z_{p^{a_1}}\times \cdots \times Z_{p^{a_t}} = \langle x_1\rangle\times \cdots \times \langle x_t \rangle$ is a direct product of cyclic groups, where the order of each one is a power of the same prime, then $x_1, \ldots, x_t$ will all be primitive elements. This is not true for any other direct product of cyclic groups with more than one component.