1.10. Groups#

We introduce the notion of groups in this section.

Note

All functions in this section are total functions.

1.10.1. Definition#

A group is a set with a single binary operation. It is one of the simplest algebraic structures.

Definition 1.115 (Group)

Let \(G\) be a set. Let \(\cdot : G \times G \to G\) be a binary operation defined on \(G\) mapping \((g_1, g_2) \to \cdot (g_1, g_2)\) and denoted as

\[ \cdot (g_1, g_2)\triangleq g_1 \cdot g_2. \]

If the binary operation \(\cdot\) satisfies the following properties:

  1. [Closure] The set \(G\) is closed under the binary operation \(\cdot\). i.e.

    \[ \forall g_1, g_2 \in G, g_1 \cdot g_2 \in G. \]

  2. [Associativity] For every \(g_1, g_2, g_3 \in G\)

    \[ g_1 \cdot (g_2 \cdot g_3) = (g_1 \cdot g_2) \cdot g_3 \]

  3. [Identity element] There exists an element \(e \in G\) such that

    \[ g \cdot e = e \cdot g = g \quad \forall g \in G \]

  4. [Inverse element] For every \(g \in G\) there exists an element \(g^{-1} \in G\) such that

    \[ g \cdot g^{-1} = g^{-1} \cdot g = e \]

then the set \(G\) together with the operator \(\cdot\) denoted as \((G, \cdot)\) is known as a group.

Above properties are known as group axioms. Note that commutativity is not a requirement of a group.

Remark 1.22

Frequently, the group operation is the regular mathematical addition. In those cases, we write \(g_1 \cdot g_2\) as \(g_1 + g_2\). Otherwise, we will write \(g_1 \cdot g_2\) as \(g_1 g_2\).

Often, we may simply write a group \((G, \cdot)\) as \(G\) when the underlying operation \(\cdot\) is clear from the context.

1.10.1.1. Commutative groups#

A commutative group is a richer structure than a group. Its elements also satisfy the commutativity property.

Definition 1.116 (Commutative group)

Let \((G, \cdot)\) be a group such that its binary operation \(\cdot\) satisfies an additional property:

  1. [Commutativity] For every \(g_1, g_2 \in G\)

    \[ g_1 g_2 = g_2 g_1 \]

Then \((G,\cdot)\) is known as a commutative group or an Abelian group.

1.10.2. Permutation Groups#

Definition 1.117 (Permutation)

Let \(X\) be a nonempty set. A bijective function \(\pi : X \to X\) is called a permutation of \(X\).

The set of all permutations of a set \(X\) is denoted by \(\Sym(X)\).

Theorem 1.37 (Permutation group)

Let \(X\) be a nonempty set. The set of all permutations of \(X\), namely \(\Sym(X)\), is a group under the operation of function composition.

It is known as the permutation group of \(X\) and denoted as \((\Sym(X), \circ)\).

Proof. Since every permutation \(\pi: X \to X\) is a bijection, hence it has a unique inverse function \(\pi^{-1}: X \to X\) which is also a permutation (as it is also a bijection).

Closure

  1. Let \(\pi\) and \(\sigma\) be permutations.

  2. Then they are both bijections.

  3. Hence Their composition \(\pi \circ \sigma\) is also a bijection.

  4. Hence \(\pi \circ \sigma\) is also a permutation.

  5. Hence \(\Sym(X)\) is closed under function composition.

Associativity

  1. Function composition is by definition associative.

Identity element

  1. Consider the identity function \(\id_X : X \to X\) defined as

    \[ \id_X(x) = x \Forall x \in X. \]

  2. \(\id_X\) is a bijection. Hence \(\id_X \in\Sym(X)\).

  3. For any \(\pi \in \Sym(X)\), we can see that \(\pi \circ \id_X = \pi\).

  4. Similarly, \(\id_X \circ \pi = \pi\).

  5. Hence \(\id_X\) serves as an identity permutation.

Inverse

  1. Since bijections are invertible, hence for every permutation, there exists an inverse permutation.

Hence \((\Sym(X), \circ)\) is a group.

1.10.2.1. Permutations on Finite Sets#

Let \(X\) be a finite set written as \(X = \{ x_1, \dots, x_n \}\). A convenient way of writing a permutation of a finite set is

(1.3)#\[\begin{split}\pi = \begin{pmatrix} x_1 & x_2 & \dots & x_n \\ \pi(x_1) & \pi(x_2)& \dots & \pi (x_n) \end{pmatrix}\end{split}\]

  1. We can see that the two rows are two different (ordered) arrangements of the elements of \(X\).

  2. One can think of a permutation as a rearrangement of the elements of the set \(X\).

  3. Recall from Definition 1.84 that for a finite set, there exists a bijection from the set \(\{1, \dots, n \}\) to the set \(X\) given by \(i \mapsto x_i\).

  4. Hence, for every permutation of a finite \(X\), there exists a corresponding permutation of the set \(\{1, \dots, n \}\).

1.10.2.2. Symmetric Groups#

Definition 1.118 (Symmetric group of degree \(n\))

Consider the set \(X = \{1, \dots, n \}\). The set of all permutations of \(X\) under the operation of function composition is known as the symmetric group of degree \(n\) and is denoted by \(S_n\).

Example 1.24 (Symmetric group \(S_4\))

  1. Let \(X = \{ 1, 2, 3, 4 \}\).

  2. Let \(\pi\) and \(\sigma\) be two permutations given by

    \[\begin{split} \pi = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 \end{pmatrix} \text{ and } \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix}. \end{split}\]

  3. \(\pi^{-1}\) is given by

    \[\begin{split} \pi^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}. \end{split}\]

  4. \(\sigma^{-1}\) is given by

    \[\begin{split} \sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{pmatrix}. \end{split}\]

  5. Then \(\pi \sigma\) is given by

    \[\begin{split} \pi \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}. \end{split}\]

    We have \((\pi \sigma) (i) = \pi (\sigma (i))\). E.g. \((\pi \sigma) (3) = \pi (4) = 2\).

  6. Then \(\sigma \pi\) is given by

    \[\begin{split} \pi \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2 \end{pmatrix}. \end{split}\]

  7. We can see that \(\pi \sigma \neq \sigma \pi\). Hence the permutation group is not commutative.

Theorem 1.38 (Cardinality of symmetric group)

Let \(X\) be a finite set with \(n\) elements. Then \(|\Sym(X)| = n!\).

Proof. We can write a permutation as

\[\begin{split} \pi = \begin{pmatrix} x_1 & x_2 & \dots & x_n \\ y_1 & y_2 & \dots & y_n \end{pmatrix} \end{split}\]

  1. We need to count the number of ways of constructing the second row.

  2. There are \(n\) ways of choosing \(y_1\).

  3. Once \(y_1\) has been chosen, there are \(n-1\) ways of choosing \(y_2\) since \(y_1\) cannot be chosen again as \(\pi\) is injective.

  4. Similarly, there are \(n-2\) ways of choosing \(y_3\) since \(y_1\) and \(y_2\) have already been chosen and cannot be chosen again.

  5. We continue in this manner.

  6. Finally, there is just one way of choosing \(y_n\).

  7. Each choice of \(y_i\) can occur with each choice of \(y_j\).

  8. Hence total number of permutations is given by

    \[ n (n - 1) (n -2) \dots 1 = n!. \]