8.6 Order of a group and of elements
With those two main examples in mind, we now explore some more properties of groups.
The order of a group G, denoted |G|, is the cardinality of the set G.
Similarly, we say a group G is finite if the set G is finite, and infinite otherwise.We have seen that |D_{2n}| = 2n (justifying our notation).
We have |(\mathbb{Z},+)| is infinite.
We have |(\{-1,1\},\cdot)|=2.
We have |S_n|=n!.
We’ll count the permutations of \{1,2,\dots,n\}. Let f\in S_n. Since f(1) can be any of the elements 1,2,\dots,n, there are n possibilities for f(1). For each of these, there are n-1 possibilities for f(2), since it can be any of the elements 1,2,\dots,n except for f(1). Given f(1),f(2), there are n-2 possibilities for f(3), since it can be any of the elements 1,2,\dots,n except for f(1) and f(2). And so on. So in total there are n(n-1)(n-2)\cdots2\cdot 1=n! permutations of \{1,2,\dots,n\}.
□
Let x be an element of a multiplicatively-written group G. Then:
If x^n=e for some n\in \mathbb{Z}_+, then the order of x, and denoted \operatorname{ord}(x) (or \operatorname{ord}_G(x) if it may be unclear what group G we’re referring to) is \operatorname{ord}(x)=\min\{n\in \mathbb{Z}_+:x^n=e\}, i.e. the least positive integer n such that x^n=e. [Note this is well defined by the Well Ordering Principle.]
If there is no n\in \mathbb{Z}_+ such that x^n=e, then we say that x has infinite order and write \operatorname{ord}(x)=\infty (or \operatorname{ord}_G(x)=\infty).
The order of a k-cycle in the symmetric group S_n is k.
It is clear that if we repeat a k-cycle (i_1,i_2,\dots,i_k) k times, each element i_j is sent back to itself (and if we repeat it l<k times, then i_1 is sent to i_{l+1}\neq i_1).
□
In fact, one benefit of disjoint cycle notation in S_n is that it makes it easy to calculate the order of a permutation.
If f is the product of disjoint cycles of lengths k_1,k_2,\dots,k_r, then \operatorname{ord}(f)=\operatorname{lcm}(k_1,k_2,\dots,k_r).
Consider when f^k is the identity permutation. For f^k(j_i)=j_i when j_i is one of the numbers involved in the k_i-cycle, we need k_i to divide k. But if k_i divides k for all i, then this applies to all the numbers moved by f. So the smallest such k is the lowest common multiple of k_1,\dots,k_r.
□
We’ll now see what we can say about the powers of an element of a group if we know its order, starting with elements of infinite order.
Let x be an element of a group G with \operatorname{ord}(x)=\infty. Then the powers x^i of x are all distinct: i.e., x^i\neq x^j if i\neq j are integers.
Suppose x^i=x^j. Without loss of generality we’ll assume i\geq j. Then for n=i-j\geq0, x^n=x^{i-j}=x^i(x^j)^{-1}=(x^i)(x^i)^{-1}=e, but since \operatorname{ord}(x)=\infty there is no positive integer n with x^n=e, so we must have n=0 and so i=j.
□
If x is an element of a finite group G, then \operatorname{ord}(x)<\infty.
If \operatorname{ord}(x)=\infty then the previous proposition tells us that the elements x^i (for i\in\mathbb{Z}) are all different, and so G must have infinitely many elements.
□
In fact, we’ll see later that the order |G| of a finite group severely restricts the possible (finite) orders of its elements. Next for elements of finite order.
Let x be an element of a group G with \operatorname{ord}(x)=n<\infty.
For an integer i, x^i=e if and only if i is divisible by n.
For integers i,j, x^i=x^j if and only if i-j is divisible by n.
x^{-1}=x^{n-1}.
The distinct powers of x are e,x,x^2,\dots,x^{n-1}.
- Firstly, if i is divisible by n, so that i=nk for some integer k, then x^i=x^{nk}=(x^n)^k=e^k=e, since x^n=e.
Conversely, suppose that x^i=e. We can write i=nq+r with q,r\in\mathbb{Z} and 0\leq r<n (by Theorem 5.2 ). Then e=x^i=x^{nq+r}=(x^n)^qx^r=e^qx^r=x^r. But n is the least positive integer with x^n=e and x^r=e with 0\leq r<n, so r can’t be positive, and we must have r=0. So i is divisible by n.
x^i=x^j if and only if x^{i-j}=x^i(x^j)^{-1}=e, which by a.) is the case if and only if i-j is divisible by n.
Take i=n-1, j=-1. Then i-j=n is divisible by n, and so x^{n-1}=x^{-1} by b.
For any integer i, write i=nq+r for q,r integers with 0\leq r<n. Then i-r is divisible by n, and so x^i=x^r by (2). So every power of x is equal to one of e=x^0,x=x^1,x^2,\dots, x^{n-1}. Conversely, If i,j\in\{0,1,\dots,n-1\} and i-j is divisible by n, then i=j, and so by b.) the elements e,x,\dots,x^{n-1} are all different.
□
If we know the order of an element of a group, then we can work out the order of any power of that element.
Let x be an element of a group G, and i an integer.
If \operatorname{ord}(x)=\infty and i\neq 0, then \operatorname{ord}(x^i)=\infty. (If i=0, then x^i=e, and so \operatorname{ord}(x^i)=1).
If \operatorname{ord}(x)=n<\infty, then \operatorname{ord}(x^i)=\frac{n}{\gcd(n,i)}.
Suppose i>0. If \operatorname{ord}(x^i)=m<\infty, then x^{im}=(x^i)^m=e with im a positive integer, contradicting \operatorname{ord}(x)=\infty. Similarly, if i<0 then x^{-im}=e with -im a positive integer, again giving a contradiction. So in either case \operatorname{ord}(x^i)=\infty.
Since \gcd(n,i) divides i, n divides \frac{ni}{\gcd(n,i)}, and so (x^i)^{{n}/{\gcd(n,i)}}=x^{{ni}/{\gcd(n,i)}}=e.
□