cycle graph (group)
   HOME

TheInfoList



OR:

In
group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, a subfield of
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
, a group cycle graph illustrates the various cycles of a
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...
and is particularly useful in visualizing the structure of small
finite group Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...
s. A cycle is the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 Collective identity is the shared sense of belonging to a group. In sociology In 1989, Alberto Melucci published ''Nomads of the Present'', which introduces his model of collective identity based on studies of the social movements of the 1980s ...
, ''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 polygon, with the vertices representing the group elements, and the connecting lines indicating that all elements in that polygon are members of the same cycle.


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 ''a''6 = ''e''. Then the set of powers of ''a''2, is a cycle, but this is really no new information. Similarly, ''a''5 generates the same cycle as ''a'' itself. So, only the ''primitive'' cycles need be considered, namely those that are not
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of another cycle. Each of these is generated by some ''primitive element'', ''a''. Take one
point Point or points may refer to: Places * Point, Lewis, a peninsula in the Outer Hebrides, Scotland * Point, Texas, a city in Rains County, Texas, United States * Point, the NE tip and a ferry terminal of Lismore, Inner Hebrides, Scotland * Point ...
for each element of the original group. For each primitive element, connect ''e'' to ''a'', ''a'' to ''a''2, ..., ''a''''n''−1 to ''a''''n'', etc., until ''e'' is reached. The result is the cycle graph. When ''a''2 = ''e'', ''a'' has order 2 (is an
involution Involution may refer to: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
), and is connected to ''e'' by two edges. Except when the intent is to emphasize the two edges of the cycle, it is typically drawn as a single line between the two elements.


Properties

As an example of a group cycle graph, consider the
dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...
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. Notice the cycle in the multiplication table, with ''a''4 = ''e''. The inverse ''a''−1 = ''a''3 is also a generator of this cycle: (, , and . 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 Dih4 above, we could draw a line between ''a''2 and ''e'' since , but since ''a''2 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 In group theory, the quaternion group Q8 (sometimes just denoted by Q) is a non-abelian group of order eight, isomorphic to the eight-element subset \ of the quaternions under multiplication. It is given by the group presentation :\mathrm_8 ...
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.


History

Cycle graphs were investigated by the number theorist
Daniel Shanks Daniel Shanks (January 17, 1917 – September 6, 1996) was an American mathematician who worked primarily in numerical analysis and number theory. He was the first person to compute π to 100,000 decimal places. Life and education Shanks was b ...
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 Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...
. In the 1978 second edition, Shanks reflects on his research on
class group In number theory, the ideal class group (or class group) of an algebraic number field is the quotient group where is the group of fractional ideals of the ring of integers of , and is its subgroup of principal ideals. The class group is a mea ...
s and the development of the
baby-step giant-step In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. The discrete log problem is of fundamental ...
method: 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 group In group theory, a branch of abstract algebra in pure mathematics, 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 bina ...
s 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 A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, groups of the form (Z''n'')''m'' will have ''n''-element cycles sharing the identity element:
Dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...
s Dih''n'', order 2''n'' consists of an ''n''-element cycle and ''n'' 2-element cycles:
Dicyclic group In group theory, a dicyclic group (notation Dic''n'' or Q4''n'', Coxeter&Moser: Generators and Relations for discrete groups: : Rl = Sm = Tn = RST) is a particular kind of non-abelian group of order 4''n'' (''n'' > 1). It is an extension of the ...
s, Dicn = Q4''n'', order 4''n'': Other
direct product In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one ta ...
s:
Symmetric group 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 \m ...
s – 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 S4


Example: Subgroups of the full octahedral group

The
full octahedral group A regular octahedron has 24 rotational (or orientation-preserving) symmetries, and 48 symmetries altogether. These include transformations that combine a reflection and a rotation. A cube has the same set of symmetries, since it is the polyhed ...
is the
direct product In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one ta ...
S_4 \times Z_2 of the symmetric group S4 and the cyclic group Z2.
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 S4 are an example of that.


See also

*
List of small groups The following list in mathematics contains the finite groups of small order up to group isomorphism. Counts For ''n'' = 1, 2, … the number of nonisomorphic groups of order ''n'' is : 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, ...
*
Cayley graph 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 (named after Arthur Cayle ...


External links

*


References

* Skiena, S. (1990). Cycles, Stars, and Wheels. ''Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica'' (pp. 144-147). * {{Citation , first=Daniel , last=Shanks , author-link=Daniel Shanks , title=Solved and Unsolved Problems in Number Theory , edition=2nd , year=1978 , orig-year=1962 , isbn=0-8284-0297-3 , publisher=Chelsea Publishing Company , location=New York * Pemmaraju, S., & Skiena, S. (2003). Cycles, Stars, and Wheels. ''Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica'' (pp. 248-249). Cambridge University Press. Abstract algebra Group theory Application-specific graphs