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.\]
□