Symmetric Group
A symmetric group $ S_n $ is defined by all the permutations (various arrangements) of the \( n \) elements within set $ X $, as well as every combination of these permutations. $$ S_n = ( X , \cdot ) $$
Here, the symbol ( $ \cdot $ ) represents the composition of two permutations.
It is referred to as being of degree \( n \) when it is a finite set containing \( n \) elements.
A permutation involves rearranging the elements of a set into a different sequence. Mathematically, it's defined as a bijective function that maps an ordered set onto itself.
Consider the set:
$$ X = \{1, 2, 3, 4, 5, 6 \} $$
One possible permutation is \( \{3, 5, 1, 2, 6, 4\} \), where the original sequence of elements has been altered.
$$ \tau: X \to X \\ 1 ⟶ 3 \\ 2 ⟶ 5 \\ 3 ⟶ 1 \\ 4 ⟶ 2 \\ 5 ⟶ 6 \\ 6 ⟶ 4 $$
This rearrangement ensures each number appears exactly once without repetition.
To represent this bijective correspondence $ \tau $ of the set with itself, we typically write the original sequence on the first line and its permutation on the second line of a matrix.
$$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$
This illustration encapsulates the concept of permutations within a symmetric group.
For instance, in the first column, 1 becomes 3, and in the second, 2 becomes 5, etc. $$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$ Some representations simplify the permutation by omitting the first row, implicitly assuming it's in ascending order as $ (1,2,3,4,5,6) $. Hence, the permutation can also be succinctly depicted as: $$ \tau = ( 3, 5, 1, 2, 6, 4 ) $$
All potential permutations form a symmetric group, denoted as S(X) or Sn, defined by the composition operation ( $ \cdot $ ).
$$ S_n = ( X , \cdot ) $$
This operation is intrinsic to the group, ensuring that the result of any composition remains within the group Sn.
Example
The symmetric group $ S_6=(X, \cdot) $ is constructed from the finite set $ X=\{ 1, 2, 3, 4, 5, 6 \} $ and the composition operation ( $ \cdot $ ).
$$ S_6 = \{ \tau_1 , \tau_2 , ... , \tau_{n!} \} $$
$$ S_6 = \{ (1,2,3,4,5,6) , (3,5,1,2,6,4) , (4,1,6,3,2,5) , ... \} $$
With \( n = 6 \), the set $ X = \{1, 2, 3, 4, 5, 6 \} $ allows for a total of 720 permutations.
$$ |S_n| = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720 $$
The notation \( |S_n| = n! \) denotes the cardinality of the group, indicating that there are \( n! \) permutations, equivalent to the product of all positive integers up to \( n \).
Permutation Composition
The symmetric group Sn comprises permutations of the set X and the operation of composing these permutations, denoted by the symbol $ \cdot $.
The composition of two permutations is where one permutation is applied followed by another, in the sequence they are presented.
The outcome is a new permutation that amalgamates the adjustments of both. Essentially, the output selected by the first permutation becomes the input for the second.
Example
Let's look at two permutations from the group S6:
$$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} $$
$$ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$
The resulting permutation from the composition of these two permutations belongs to the group S6:
$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$
Each element \( i \) is first transformed by \( \tau \), and the result is further modified by \( \sigma \) to produce \( \sigma(\tau(i)) \).
In composite functions, the inner function $ \tau() $ is evaluated first, followed by the outer $ \sigma() $, necessitating a right-to-left execution order.
The final permutation, \( \sigma \cdot \tau \), is computed as follows:
$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 4 & 6 & 1 & 3 \end{pmatrix} $$
This illustrates the permutation resulting from this specific sequence of operations.
The Inverse of a Permutation
In a symmetric group, the inverse of a permutation is obtained by simply swapping the top and bottom rows.
Consider the permutation $ \sigma $ as an example:
$$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} $$
The inverse permutation, $ \sigma^{-1} $, is then:
$$ \sigma^{-1} = \begin{pmatrix} 4 & 6 & 2 & 3 & 5 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix} $$
The Identity Permutation
Within a symmetric group, the identity permutation \( \epsilon \) is the permutation that maintains each element in its original position.
It serves as the neutral element of the group, meaning any permutation composed with the identity permutation results in the original permutation itself.
For example, in a symmetric group of six elements, the identity permutation is depicted as:
$$ \epsilon = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix} $$
This shows that each element \( i \) is mapped back to itself, \( i \to i \), across the entire set \( X = \{1, 2, 3, 4, 5, 6\} \).
The Symmetric Group is Non-Abelian
Typically, symmetric groups are non-abelian groups because they lack the commutative property.
For \( n > 2 \), the non-abelian nature of symmetric groups becomes evident as the order of operation impacts the final result.
As an illustration, consider the permutation resulting from $ \sigma \cdot \tau $, which is $ (2,5,4,6,1,3) $:
$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} $$
$$ \sigma \cdot \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 4 & 6 & 1 & 3 \end{pmatrix} $$
Reversing the order to $ \tau \cdot \sigma $ yields a distinct permutation, $ (2,4,5,1,6,3) $:
$$ \tau \cdot \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 2 & 3 & 5 & 1 \end{pmatrix} $$
$$ \tau \cdot \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 5 & 1 & 6 & 3 \end{pmatrix} $$
The results clearly differ, demonstrating the non-abelian properties of \( S_6 \) and all higher-degree symmetric groups.
Symmetric groups are commutative (abelian) only when \( n = 1 \) or \( n = 2 \). At these levels, permutations can be interchanged without altering the outcome, due to the limited number of permutations possible—the identity for \( n = 1 \) and both the identity and element swapping for \( n = 2 \), which are inverses of each other. Consider the set $X= \{ 1,2 \}$, which consists of just two elements. There are precisely two permutations possible for this set: $$ \epsilon = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} $$ $$ \tau = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} $$ In this scenario, the operations within the symmetric group $S_2$ demonstrate commutativity, as shown by the following calculations: $$ \epsilon \cdot \tau = \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} $$ $$ \tau \cdot \epsilon = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} $$ This results in the same outcome for both operations.
