Cycle graph (algebra)

Cycle graph (algebra)

In group theory, a sub-field of abstract algebra, a group cycle graph illustrates the various cycles of a group and is particularly useful in visualizing the structure of small finite groups. For groups with fewer than 16 elements, the cycle graph determines the group (up to isomorphism).

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. The element a is said to generate the cycle. In a finite group, some non-zero power of a must be the group identity, e; the lowest such power is the order of the cycle, the number of distinct elements in it. In a cycle graph, the cycle is represented as a series of polygons, with the vertices representing the group elements, and the connecting lines indicating that all elements in that polygon are members of the same cycle.

Contents

Cycles

Cycles can overlap, or they can have no element in common but the identity. The cycle graph displays each interesting cycle as a polygon.

If a generates a cycle of order 6 (or, more shortly, has order 6), then a6 = e. Then the set of powers of a², {a², a4, e} is a cycle, but this is really no new information. Similarly, a5 generates the same cycle as a itself.

So, we only need to consider the primitive cycles, those that are not subsets of another cycle. Each of these is generated by some primitive element, a. Take one point for each element of the original group. For each primitive element, connect e to a, a to a², ... an-1 to an, ... until you come back to e. The result is the cycle graph.

(Technically, the above description implies that if a² = e, so a has order 2 (is an involution), it's connected to e by two edges. It's conventional to only use one.)

Properties

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

Cycle graph for dihedral group Dih4.
o e b a a2 a3 ab a2b a3b
e e b a a2 a3 ab a2b a3b
b b e a3b a2b ab a3 a2 a
a a ab a2 a3 e a2b a3b b
a2 a2 a2b a3 e a a3b b ab
a3 a3 a3b e a a2 b ab a2b
ab ab a b a3b a2b e a3 a2
a2b a2b a2 ab b a3b a e a3
a3b a3b a3 a2b ab b a2 a e

Notice the cycle e, a, a², a³ . It can be seen from the multiplication table that successive powers of a in fact behave this way. The reverse case is also true. In other words: (a³)²=a² , (a³)³=a  and (a³)4=e . This behavior is true for any cycle in any group - a cycle may be traversed in either direction.

Cycle graph of the quaternion group Q8.

Cycles that contain a non-prime number of elements implicitly have cycles that are not connected in the graph. For the group Dih4 above, we might want to draw a line between a² and e  since (a²)²=e  but since a² is part of a larger cycle, this is not done.

There can be ambiguity when two cycles share an element that is not the identity element. Consider for example, the simple quaternion group, whose cycle graph is shown on the 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 above, the 2-element cycles should be connected by two lines, but this is usually abbreviated by a single line.

Two distinct groups may have cycle graphs that have the same structure, and can only be distinguished by the product table, or by labeling the elements in the graph in terms of the groups basic elements. The lowest order for which this problem can occur is order 16 in the case of Z2 x Z8 and the modular group, as shown below. (Note - the cycles with common elements are distinguished by symmetry in these graphs.)

Cycle graph of the order 16 group Z2 x Z8.
Cycle graph of the order 16 modular group.


The multiplication table of Z2 x Z8 is shown below:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14
2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1
3 2 5 4 7 6 9 8 11 10 13 12 15 14 1 0
4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3
5 4 7 6 9 8 11 10 13 12 15 14 1 0 3 2
6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5
7 6 9 8 11 10 13 12 15 14 1 0 3 2 5 4
8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7
9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6
10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9
11 10 13 12 15 14 1 0 3 2 5 4 7 6 9 8
12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11
13 12 15 14 1 0 3 2 5 4 7 6 9 8 11 10
14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13
15 14 1 0 3 2 5 4 7 6 9 8 11 10 13 12

Other information derivable from cycle graphs

  • The inverse of an element could be identified in the cycle graph. It is the element whose distance is the same from the opposite direction.

Graph characteristics of particular group families

Certain group types give typical graphs:

  • Cyclic groups Zn is a single cycle graphed simply as an n-sided polygon with the elements at the vertices.
GroupDiagramMiniC1.png
GroupDiagramMiniC2.png
GroupDiagramMiniC3.png
GroupDiagramMiniC4.png
GroupDiagramMiniC5.png
GroupDiagramMiniC6.png
GroupDiagramMiniC7.png
GroupDiagramMiniC8.png
Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8
  • When n is a prime number, groups of the form (Zn)m will have (nm-1)/(n-1) n-element cycles sharing the common identity element.
GroupDiagramMiniD4.png
GroupDiagramMiniC2x3.png
GroupDiagramMiniC2x4.png
GroupDiagramMiniC3x2.png
Z2² Z2³ Z24 Z3²
  • Dihedral groups Dihn consists of an n-element cycle and n 2-element cycles.
GroupDiagramMiniC2.png
GroupDiagramMiniD4.png
GroupDiagramMiniD6.png
GroupDiagramMiniD8.png
GroupDiagramMiniD10.png
GroupDiagramMiniD12.png
GroupDiagramMiniD14.png
Dih1 Dih2 Dih3 Dih4 Dih5 Dih6 Dih7
  • Symmetric groups - The symmetric group Sn 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 as a subgraph of the cycle graph of Sn. See example: Subgroups of S4
Cycle graph of the symmetric group S4
   
One of three Dih4 subgraphs found in the S4 cycle graph

It's the same graph like GroupDiagramMiniD8.png

See also

External links

References

  • Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Cycle graph (disambiguation) — A cycle graph or cyclic graph is a connected, 2 regular graph.Cycle graph or cyclic graph may also refer to: * Cycle graph (algebra), a diagram representing the cycles determined by taking powers of group elements * Circulant graph * A graph… …   Wikipedia

  • Cycle (mathematics) — This article is about group theory. For cycles in homological algebra, see Chain complex#Fundamental terminology. For cycles in graph theory, see Cycle (graph theory). In mathematics, and in particular in group theory, a cycle is a permutation of …   Wikipedia

  • Cycle space — This article is about a concept in graph theory. For space allocated to bicycles, see segregated cycle facilities. In graph theory, an area of mathematics, a cycle space is a vector space defined from an undirected graph; elements of the cycle… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Cycle notation — For the cyclic decomposition of graphs, see Cycle decomposition (graph theory). For cycling terminology, see glossary of bicycling. In combinatorial mathematics, the cycle notation is a useful convention for writing down a permutation in terms of …   Wikipedia

  • Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

  • Regular graph — In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency. A regular graph with vertices of degree k is called a kregular graph or regular graph of degree… …   Wikipedia

  • Hypercube graph — The hypercube graph Q4 Vertices 2n Edges 2n−1n …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Abstract algebra — This article is about the branch of mathematics. For the Swedish band, see Abstrakt Algebra. The permutations of Rubik s Cube have a group structure; the group is a fundamental concept within abstract algebra. Abstract algebra is the subject area …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”