Order (group theory)
Encyclopedia
In group theory
, a branch of mathematics
, the term order is used in two closely related senses:
The order of a group G is denoted by ord(G) or |G| and the order of an element a is denoted by ord(a) or |a|.
S3 has the following multiplication table.
This group has six elements, so ord(S3) = 6. By definition, the order of the identity, e, is 1. Each of s, t, and w squares to e, so these group elements have order 2. Completing the enumeration, both u and v have order 3, for u2 = v and u3 = vu = e, and v2 = u and v3 = uv = e.
If the order of group G is 1, then the group is called a trivial group
. Given an element a, ord(a) = 1 if and only if
a is the identity. If every (non-identity) element in G is the same as its inverse (so that a2 = e), then ord(a) = 2 and consequently G is abelian
since
by Elementary group theory. The converse of this statement is not true; for example, the (additive) cyclic group
Z6 of integers modulo
6 is abelian, but the number 2 has order 3:
.
The relationship between the two concepts of order is the following: if we write
for the subgroup
generated
by a, then
For any integer k, we have
In general, the order of any subgroup of G divides the order of G. More precisely: if H is a subgroup of G, then
As an immediate consequence of the above, we see that the order of every element of a group divides the order of the group. For example, in the symmetric group shown above, where ord(S3) = 6, the orders of the elements are 1, 2, or 3.
The following partial converse is true for finite group
s: if d divides the order of a group G and d is a prime number
, then there exists an element of order d in G (this is sometimes called Cauchy's theorem
). The statement does not hold for composite
orders, e.g. the Klein four-group
does not have an element of order four). This can be shown by inductive proof. The consequences of the theorem include: the order of a group G is a power of a prime p if and only if ord(a) is some power of p for every a in G.
If a has infinite order, then all powers of a have infinite order as well. If a has finite order, we have the following formula for the order of the powers of a:
for every integer k. In particular, a and its inverse a−1 have the same order.
There is no general formula relating the order of a product ab to the orders of a and b. In fact, it is possible that both a and b have finite order while ab has infinite order, or that both a and b have infinite order while ab has finite order. If ab = ba, we can at least say that ord(ab) divides lcm
(ord(a), ord(b)). As a consequence, one can prove that in a finite abelian group, if m denotes the maximum of all the orders of the group's elements, then every element's order divides m.
, giving the number of positive integers no larger than d and coprime
to it. For example in the case of S3, φ(3) = 2, and we have exactly two elements of order 3. The theorem provides no useful information about elements of order 2, because φ(2) = 1, and is only of limited utility for composite d such as d=6, since φ(6)=2, and there are zero elements of order 6 in S3.
s tend to reduce the orders of elements: if f: G → H is a homomorphism, and a is an element of G of finite order, then ord(f(a)) divides ord(a). If f is injective, then ord(f(a)) = ord(a). This can often be used to prove that there are no (injective) homomorphisms between two concretely given groups. (For example, there can be no nontrivial homomorphism h: S3 → Z5, because every number except zero in Z5 has order 5, which does not divide the orders 1, 2, and 3 of elements in S3.) A further consequence is that conjugate elements
have the same order.
es:
where the di are the sizes of the non-trivial conjugacy classes; these are proper divisors of |G| bigger than one, and they are also equal to the indices of the centralizers in G of the representatives of the non-trivial conjugacy classes. For example, the center of S3 is just the trivial group with the single element e, and the equation reads |S3| = 1+2+3.
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
, a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the term order is used in two closely related senses:
- The order of a groupGroup (mathematics)In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
is its cardinality, i.e., the number of its elements. - The order, sometimes period, of an element a of a group is the smallest positive integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
m such that am = e (where e denotes the identity elementIdentity elementIn mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
of the group, and am denotes the product of m copies of a). If no such m exists, a is said to have infinite order. All elements of finite groups have finite order.
The order of a group G is denoted by ord(G) or |G| and the order of an element a is denoted by ord(a) or |a|.
Example
Example. The symmetric groupSymmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
S3 has the following multiplication table.
| • | e | s | t | u | v | w |
|---|---|---|---|---|---|---|
| e | e | s | t | u | v | w |
| s | s | e | v | w | t | u |
| t | t | u | e | s | w | v |
| u | u | t | w | v | e | s |
| v | v | w | s | e | u | t |
| w | w | v | u | t | s | e |
This group has six elements, so ord(S3) = 6. By definition, the order of the identity, e, is 1. Each of s, t, and w squares to e, so these group elements have order 2. Completing the enumeration, both u and v have order 3, for u2 = v and u3 = vu = e, and v2 = u and v3 = uv = e.
Order and structure
The order of a group and that of an element tend to speak about the structure of the group. Roughly speaking, the more complicated the factorization of the order the more complicated the group.If the order of group G is 1, then the group is called a trivial group
Trivial group
In mathematics, a trivial group is a group consisting of a single element. All such groups are isomorphic so one often speaks of the trivial group. The single element of the trivial group is the identity element so it usually denoted as such, 0, 1 or e depending on the context...
. Given an element a, ord(a) = 1 if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
a is the identity. If every (non-identity) element in G is the same as its inverse (so that a2 = e), then ord(a) = 2 and consequently G is abelian
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
since
by Elementary group theory. The converse of this statement is not true; for example, the (additive) cyclic groupCyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
Z6 of integers modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
6 is abelian, but the number 2 has order 3:
.The relationship between the two concepts of order is the following: if we write
for the subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
generated
Generating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
by a, then
For any integer k, we have
- ak = e if and only if ord(a) dividesDivisorIn mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
k.
In general, the order of any subgroup of G divides the order of G. More precisely: if H is a subgroup of G, then
- ord(G) / ord(H) = [G : H], where [G : H] is the indexIndex of a subgroupIn mathematics, specifically group theory, the index of a subgroup H in a group G is the "relative size" of H in G: equivalently, the number of "copies" of H that fill up G. For example, if H has index 2 in G, then intuitively "half" of the elements of G lie in H...
of H in G, an integer. This is Lagrange's theoremLagrange's theorem (group theory)Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
.
As an immediate consequence of the above, we see that the order of every element of a group divides the order of the group. For example, in the symmetric group shown above, where ord(S3) = 6, the orders of the elements are 1, 2, or 3.
The following partial converse is true for finite group
Finite group
In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
s: if d divides the order of a group G and d is a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
, then there exists an element of order d in G (this is sometimes called Cauchy's theorem
Cauchy's theorem (group theory)
Cauchy's theorem is a theorem in the mathematics of group theory, named after Augustin Louis Cauchy. It states that if G is a finite group and p is a prime number dividing the order of G , then G contains an element of order p...
). The statement does not hold for composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
orders, e.g. the Klein four-group
Klein four-group
In mathematics, the Klein four-group is the group Z2 × Z2, the direct product of two copies of the cyclic group of order 2...
does not have an element of order four). This can be shown by inductive proof. The consequences of the theorem include: the order of a group G is a power of a prime p if and only if ord(a) is some power of p for every a in G.
If a has infinite order, then all powers of a have infinite order as well. If a has finite order, we have the following formula for the order of the powers of a:
- ord(ak) = ord(a) / gcdGreatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
(ord(a), k)
for every integer k. In particular, a and its inverse a−1 have the same order.
There is no general formula relating the order of a product ab to the orders of a and b. In fact, it is possible that both a and b have finite order while ab has infinite order, or that both a and b have infinite order while ab has finite order. If ab = ba, we can at least say that ord(ab) divides lcm
Least common multiple
In arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
(ord(a), ord(b)). As a consequence, one can prove that in a finite abelian group, if m denotes the maximum of all the orders of the group's elements, then every element's order divides m.
Counting by order of elements
Suppose G is a finite group of order n, and d is a divisor of n. The number of elements in G of order d is a multiple of φ(d), where φ is Euler's totient functionEuler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
, giving the number of positive integers no larger than d and coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to it. For example in the case of S3, φ(3) = 2, and we have exactly two elements of order 3. The theorem provides no useful information about elements of order 2, because φ(2) = 1, and is only of limited utility for composite d such as d=6, since φ(6)=2, and there are zero elements of order 6 in S3.
In relation to homomorphisms
Group homomorphismGroup homomorphism
In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that h = h \cdot h...
s tend to reduce the orders of elements: if f: G → H is a homomorphism, and a is an element of G of finite order, then ord(f(a)) divides ord(a). If f is injective, then ord(f(a)) = ord(a). This can often be used to prove that there are no (injective) homomorphisms between two concretely given groups. (For example, there can be no nontrivial homomorphism h: S3 → Z5, because every number except zero in Z5 has order 5, which does not divide the orders 1, 2, and 3 of elements in S3.) A further consequence is that conjugate elements
Conjugacy class
In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...
have the same order.
Class equation
An important result about orders is the class equation; it relates the order of a finite group G to the order of its center Z(G) and the sizes of its non-trivial conjugacy classConjugacy class
In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...
es:
where the di are the sizes of the non-trivial conjugacy classes; these are proper divisors of |G| bigger than one, and they are also equal to the indices of the centralizers in G of the representatives of the non-trivial conjugacy classes. For example, the center of S3 is just the trivial group with the single element e, and the equation reads |S3| = 1+2+3.