Cycle graph (algebra)

Last updated May 20, 2024

In group theory, a subfield of abstract algebra, a cycle graph of a group is an undirected graph that illustrates the various cycles of that group, given a set of generators for the group. 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 aⁿ, 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 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. In a cycle graph, the cycle is represented as a polygon, with its vertices representing the group elements and its edges indicating how they are linked together to form the cycle.

Definition

Each group element is represented by a node in the cycle graph, and enough cycles are represented as polygons in the graph so that every node lies on at least one cycle. All of those polygons pass through the node representing the identity, and some other nodes may also lie on more than one cycle.

Suppose that a group element a generates a cycle of order 6 (has order 6), so that the nodes a, a², a³, a⁴, a⁵, and a⁶ = e are the vertices of a hexagon in the cycle graph. The element a² then has order 3; but making the nodes a², a⁴, and e be the vertices of a triangle in the graph would add no new information. So, only the primitive cycles need be considered, those that are not subsets of another cycle. Also, the node a⁵, which also has order 6, generates the same cycle as does a itself; so we have at least two choices for which element to use in generating a cycle --- often more.

To build a cycle graph for a group, we start with a node for each group element. For each primitive cycle, we then choose some element a that generates that cycle, and we connect the node for e to the one for a, a to a², ..., a^k−1 to a^k, etc., until returning to e. The result is a cycle graph for the group.

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.

Note that this correspondence between groups and graphs is not one-to-one in either direction: Two different groups can have the same cycle graph, and two different graphs can be cycle graphs for a single group. We give examples of each in the non-uniqueness section.

Example and properties

Dih₄ kaleidoscope with red mirror and 4-fold rotational generators	Cycle graph for dihedral group Dih₄.

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.

^o	e	b	a	a²	a³	ab	a²b	a³b
e	e	b	a	a²	a³	ab	a²b	a³b
b	b	e	a³b	a²b	ab	a³	a²	a
a	a	ab	a²	a³	e	a²b	a³b	b
a²	a²	a²b	a³	e	a	a³b	b	ab
a³	a³	a³b	e	a	a²	b	ab	a²b
ab	ab	a	b	a³b	a²b	e	a³	a²
a²b	a²b	a²	ab	b	a³b	a	e	a³
a³b	a³b	a³	a²b	ab	b	a²	a	e

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.

Cycle graph of the quaternion group Q8. GroupDiagramQ8.svg — Cycle graph of the quaternion group Q₈.

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.^[2]

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 $C_{5}\times C_{2}\times C_{2}$ , which has order 20.^[2] We denote an element of that group as a triple of numbers $(i;j,k)$ , where $0\leq i<5$ and each of $j$ and $k$ is either 0 or 1. The triple $(0;0,0)$ is the identity element. In the drawings below, $i$ is shown above $j$ and $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 $(1;1,0)$ , $(1;0,1)$ , and $(1;1,1)$ . In the second, we generate the third of those cycles --- the blue one --- by starting instead with $(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 $C_{8}\times C_{2}$ and $C_{8}\rtimes _{5}C_{2}$ . The abelian group $C_{8}\times C_{2}$ is the direct product of the cyclic groups of orders 8 and 2. The non-abelian group $C_{8}\rtimes _{5}C_{2}$ is that semidirect product of $C_{8}$ and $C_{2}$ in which the non-identity element of $C_{2}$ maps to the multiply-by-5 automorphism of $C_{8}$ .

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

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

where that latter relation makes $C_{8}\times C_{2}$ abelian. And we take $C_{8}\rtimes _{5}C_{2}$ to be generated by elements 𝜎 and 𝜏 with

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

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

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

(\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.^[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]

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:

Z₁	Z₂ = Dih₁	Z₃	Z₄	Z₅	Z₆ = Z₃×Z₂	Z₇	Z₈


Z₉	Z₁₀ = Z₅×Z₂	Z₁₁	Z₁₂ = Z₄×Z₃	Z₁₃	Z₁₄ = Z₇×Z₂	Z₁₅ = Z₅×Z₃	Z₁₆

Z₁₇	Z₁₈ = Z₉×Z₂	Z₁₉	Z₂₀ = Z₅×Z₄	Z₂₁ = Z₇×Z₃	Z₂₂ = Z₁₁×Z₂	Z₂₃	Z₂₄ = Z₈×Z₃

Z₂	Z₂² = Dih₂	Z₂³ = Dih₂×Dih₁	Z₂⁴ = Dih₂²

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:

Z₂² = Dih₂	Z₂³ = Dih₂×Dih₁	Z₂⁴ = Dih₂²	Z₃²

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

Dih₁ = Z₂	Dih₂ = Z₂²	Dih₃ = S₃	Dih₄	Dih₅	Dih₆ = Dih₃×Z₂	Dih₇	Dih₈	Dih₉	Dih₁₀ = Dih₅×Z₂

Dicyclic groups, Dic_n = Q_4n, order 4n:

Dic₂ = Q₈	Dic₃ = Q₁₂	Dic₄ = Q₁₆	Dic₅ = Q₂₀	Dic₆ = Q₂₄

Other direct products:

Z₄×Z₂	Z₄×Z₂²	Z₆×Z₂	Z₈×Z₂	Z₄²

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

S₄ × Z₂

A₄ × Z₂

Dih₄ × Z₂

S₃ × Z₂

The full octahedral group is the direct product $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).

S₄ × Z₂(order 48)	A₄ × Z₂(order 24)	Dih₄ × Z₂(order 16)	S₃ × Z₂= Dih₆ (order 12)


S₄(order 24)	A ₄(order 12)	Dih₄ (order 8)	S₃= Dih₃ (order 6)

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.

The cycle graph of S₄ shown above emphasizes the three Dih₄ subgroups.

This different representation emphasizes the symmetry seen in the inversion sets on the right.

Related Research Articles

In mathematics, an associative algebraA over a commutative ring K is a ring A together with a ring homomorphism from K into the center of A. This is thus an algebraic structure with an addition, a multiplication, and a scalar multiplication. The addition and multiplication operations together give A the structure of a ring; the addition and scalar multiplication operations together give A the structure of a module or vector space over K. In this article we will also use the term K-algebra to mean an associative algebra over K. A standard first example of a K-algebra is a ring of square matrices over a commutative ring K, with the usual matrix multiplication.

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group $defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .$

In mathematics, a permutation of a set can mean one of two different things:

In mathematics, an alternating group is the group of even permutations of a finite set. The alternating group on a set of $n$ elements is called the alternating group of degree $n$ , or the alternating group on $n$ letters and denoted by $A n$ or $Alt(n).$

In mathematics, when X is a finite set with at least two elements, the permutations of X (i.e. the bijective functions from X to X) fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity (oddness or evenness) of a permutation $of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ (x) > σ (y) .$

In abstract algebra, a cyclic group or monogenous group is a group, denoted C_n, that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as an integer power of g in multiplicative notation, or as an integer multiple of g in additive notation. This element g is called a generator of the group.

In mathematics, the free groupF_S over a given set S consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. The members of S are called generators of F_S, and the number of generators is the rank of the free group. An arbitrary group G is called free if it is isomorphic to F_S for some subset S of G, that is, if there is a subset S of G such that every element of G can be written in exactly one way as a product of finitely many elements of S and their inverses.

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory.

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An $n \times n$ permutation matrix can represent a permutation of $n$ elements. Pre-multiplying an $n$ -row matrix $M$ by a permutation matrix $P$ , forming $PM$ , results in permuting the rows of $M$ , while post-multiplying an $n$ -column matrix $M$ , forming $MP$ , permutes the columns of $M$ .

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.

In mathematics, the braid group on $n$ strands, also known as the Artin braid group, is the group whose elements are equivalence classes of $n$ -braids, and whose group operation is composition of braids. Example applications of braid groups include knot theory, where any knot may be represented as the closure of certain braids ; in mathematical physics where Artin's canonical presentation of the braid group corresponds to the Yang–Baxter equation ; and in monodromy invariants of algebraic geometry.

In geometric topology, a field within mathematics, the obstruction to a homotopy equivalence $of finite CW-complexes being a simple homotopy equivalence is its Whitehead torsion which is an element in the Whitehead group . These concepts are named after the mathematician J. H. C. Whitehead.$

In abstract algebra, Hilbert's Theorem 90 (or Satz 90) is an important result on cyclic extensions of fields (or to one of its generalizations) that leads to Kummer theory. In its most basic form, it states that if L/K is an extension of fields with cyclic Galois group G = Gal(L/K) generated by an element $and if is an element of L of relative norm 1, that is$

In mathematics, especially in the area of algebra known as group theory, the holomorph of a group $, denoted, is a group that simultaneously contains and its automorphism group . It provides interesting examples of groups, and allows one to treat group elements and group automorphisms in a uniform context. The holomorph can be described as a semidirect product or as a permutation group.$

In mathematics, specifically in abstract algebra, a torsion-free abelian group is an abelian group which has no non-trivial torsion elements; that is, a group in which the group operation is commutative and the identity element is the only element with finite order.

In mathematics, the von Neumann paradox, named after John von Neumann, is the idea that one can break a planar figure such as the unit square into sets of points and subject each set to an area-preserving affine transformation such that the result is two planar figures of the same size as the original. This was proved in 1929 by John von Neumann, assuming the axiom of choice. It is based on the earlier Banach–Tarski paradox, which is in turn based on the Hausdorff paradox.

In mathematics, the height of an element g of an abelian group A is an invariant that captures its divisibility properties: it is the largest natural number N such that the equation Nx = g has a solution x ∈ A, or the symbol ∞ if there is no such N. The p-height considers only divisibility properties by the powers of a fixed prime number p. The notion of height admits a refinement so that the p-height becomes an ordinal number. Height plays an important role in Prüfer theorems and also in Ulm's theorem, which describes the classification of certain infinite abelian groups in terms of their Ulm factors or Ulm invariants.

In mathematics, there are two natural interpretations of the place-permutation action of symmetric groups, in which the group elements act on positions or places. Each may be regarded as either a left or a right action, depending on the order in which one chooses to compose permutations. There are just two interpretations of the meaning of "acting by a permutation $" but these lead to four variations, depending whether maps are written on the left or right of their arguments. The presence of so many variations often leads to confusion. When regarding the group algebra of a symmetric group as a diagram algebra it is natural to write maps on the right so as to compute compositions of diagrams from left to right.$

In algebraic topology and graph theory, graph homology describes the homology groups of a graph, where the graph is considered as a topological space. It formalizes the idea of the number of "holes" in the graph. It is a special case of a simplicial homology, as a graph is a special case of a simplicial complex. Since a finite graph is a 1-complex, the only non-trivial homology groups are the 0-th group and the 1-th group.

References

↑ Sarah Perkins (2000). "Commuting Involution Graphs for A˜n, Section 2.2, p.3, first figure" (PDF). Birkbeck College, Malet Street, London, WC1E 7HX: School of Economics, Mathematics and Statistics. Retrieved 2016-01-31.{{cite web}}: CS1 maint: location (link)
1 2 Stanford, Caleb; Verret, Gabriel. "Is the cycle graph of a group unique?". Mathematics Stack Exchange.
↑ Shanks 1978, p. 246.
↑ Shanks 1978, p. xii.
↑ Shanks 1978, pp. 83–98, 206–208.
↑ Shanks 1978, p. 225.
↑ Carter, Nathan (2009), Visual Group Theory, Classroom Resource Materials, Mathematical Association of America, ISBN 978-0-88385-757-1

Skiena, S. (1990). Cycles, Stars, and Wheels. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (pp. 144-147).
Shanks, Daniel (1978) [1962], Solved and Unsolved Problems in Number Theory (2nd ed.), New York: Chelsea Publishing Company, ISBN 0-8284-0297-3
Pemmaraju, S., & Skiena, S. (2003). Cycles, Stars, and Wheels. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (pp. 248-249). Cambridge University Press.

External links

Weisstein, Eric W. "Group Cycle Graph". MathWorld .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Sarah Perkins (2000). "Commuting Involution Graphs for A˜n, Section 2.2, p.3, first figure" (PDF). Birkbeck College, Malet Street, London, WC1E 7HX: School of Economics, Mathematics and Statistics. Retrieved 2016-01-31.{{cite web}}: CS1 maint: location (link)

[MathSENotUnique-2] 1 2 Stanford, Caleb; Verret, Gabriel. "Is the cycle graph of a group unique?". Mathematics Stack Exchange.

[FOOTNOTEShanks1978246-3] Shanks 1978, p. 246.

[FOOTNOTEShanks1978xii-4] Shanks 1978, p. xii.

[FOOTNOTEShanks197883–98,_206–208-5] Shanks 1978, pp. 83–98, 206–208.

[FOOTNOTEShanks1978225-6] Shanks 1978, p. 225.

[7] Carter, Nathan (2009), Visual Group Theory, Classroom Resource Materials, Mathematical Association of America, ISBN 978-0-88385-757-1

[1]

[2]

[3]

[4]

[5]

[6]

[7]