6
$\begingroup$

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?

$\endgroup$
4

1 Answer 1

7
+50
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks! could you explain this: "This immediately shows that x and xy in our example will be primitive elements. Note that we can easily find them without computing anything." I don't see this immediately. $\endgroup$
    – user56834
    Mar 26, 2019 at 16:46
  • $\begingroup$ We know that the order of an element in $Z_4\times Z_2$ divides the order of the group, i.e. 8. Since the group is not cyclic, no element has order 8, so the biggest possible order is 4. Now $x$ generates $Z_4$, so $x$ has order 4. For $xy$ we have: $|xy| = {\rm lcm}(|x|,|y|) = {\rm lcm}(4,2) = 4$. So they both have maximal order, meaning they are primitive elements. We can also note that $xy$ is not a power of $x$, so they generate different cycles. $\endgroup$
    – Milten
    Mar 26, 2019 at 19:56
  • $\begingroup$ I suppose there was a little bit of computation, but we didn't have to compute the powers of the elements. $\endgroup$
    – Milten
    Mar 26, 2019 at 19:59
  • $\begingroup$ IN your 3rd, 4th, and 5th graph you have non-ASCII characters. $\endgroup$
    – Somos
    Mar 27, 2019 at 17:35
  • $\begingroup$ Oh, does that mess it up on other computers? Do you have a suggestion on how to fix it? You are welcome to edit. $\endgroup$
    – Milten
    Mar 27, 2019 at 17:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .