Introduction to Group Theory

Cycles and Transpositions

Before cycles and transportations, you need to know the definition of a function and how it works.

Functions: Let there be two sets $$A$$ and $$B$$. A function $$f$$ from $$A$$ to $$B$$ maps an element $$a \in A$$ to a unique element $$f\left(a\right) \in B$$. A function can also be called a mapping or a map. The notation $$f : A \mapsto B$$ means the function $$f$$ is mapping from $$A$$ to $$B$$. The set $$A$$ is referred to as the domain, and $$B$$ is referred to as the image or codomain. Two functions, $$f : A \mapsto B$$ and $$g : C \mapsto D$$ are equal only when $$A=C, B=D$$ and $$f\left(a\right)=g\left(a\right) \forall a \in A (=C)$$.

Composition: Let there be sets $$A, B, C$$ such that $$B$$ is the codomain of $$A$$, and $$C$$ is the codomain of $$B$$; i.e. there exist functions $$f$$ and $$g$$ such that $$f : A \mapsto B$$ and $$g : B \mapsto C$$. The composite $$g \circ f$$ (pronounced g circle f) is the function $$g \circ f : A \mapsto C \forall a \in A; g \circ f\left(a\right) = g\left(f\left(a\right)\right)$$. An example of a function might be $$A=B=C=\mathbb{R}$$ and $$f\left(x\right)=2x+3, g\left(x\right)=5x+2 \forall x \in \mathbb{R}; g \circ f\left(x\right)=g\left(f\left(x\right)\right)=5\left(2x+3\right)+2=10x+17$$. Notice that in the example given, the composite function $$f \circ g\left(x\right) \in \mathbb{R}$$. Observe that for the above example $$f \circ g\left(x\right) = 10x+17 \neq g \circ f\left(x\right) = 10x+7$$.

Inverse function: Let $$A$$ and $$B$$ be sets and let $$f : A \mapsto B$$. An inverse is a function $$g : B \mapsto A$$ such that for $$a \in A, g \circ f\left(a\right)=a, \forall a \in A$$. For a function to have an inverse it must be a bijection. Before bijection is defined, we need to define surjection and injection.

Surjection: For the function $$f : A \mapsto B$$, for each $$b \in B$$ there exists at least one element $$a \in A$$ such that $$f\left(a\right)=b$$.

Injection: For the functoin $$f : A \mapsto B$$, there exists at most one element $$a \in A$$ such that $$f\left(a\right)=b$$. This also means that for $$a_1,a_2 \in A, f\left(a_1\right)=f\left(a_2\right) \Rightarrow a_1=a_2$$.

Bijection: A function is bijective when it is both injective and surjective, i.e. for the function $$f : A \mapsto B$$, for each $$b \in B$$, there exists a unique element $$a \in A$$ such that $$f\left(a\right)=b$$. This is also referred to as one-to-one correspondence.

Now that you have some basic knowledge of functions, it's time to talk about permutations. A permutation is a bijective function from a set $$A$$ to itself. This is frequently denoted in a 2-row formation, as shown here for the function $$f$$:

f = \left(\begin{array}{c} 1 & 2 & ... & n \\ f\left(1\right) & f\left(2\right) & ... & f\left(n\right) \end{array}\right)

A good example is the identity permutation of $$f$$:

\left(\begin{array}{c} 1 & 2 & ... & n \\ 1 & 2 & ... & n \end{array}\right)

You can also make composite premutations. Here is an example:

\require{amsmath} \begin{align} f & = \left(\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 3 & 5 & 1 \end{array}\right) \\ g & = \left(\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{array}\right) \\ g \circ f & = \left(\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 2 & 1 & 5 \end{array}\right) \end{align}

since $$1 \mapsto 2 \mapsto 3, 2 \mapsto 4 \mapsto 4$$, etc.

This, at long last, leads to cycles and transformations. Consider the permutation $$f$$:

f = \left(\begin{array}{c} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{array}\right)
Cyclic Permutation

As you can see, $$f$$ maps $$1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 4$$, etc. Because $$5 \mapsto 1$$, this is an example of a cyclic permutation. The circle to the right is designed to give you a visual understanding of this cyclic permutation. Cycles are usually written in a one-line format. Using the permutation $$f$$ agove, the permutation can be written as $$\left(\begin{array}{c}1&2&3&4&5\end{array}\right)$$. Each number is moved one place to the right, with the last number mapping back to the first. A permutation can be broken down into multiple cycles as well. This is called cycle decomposition. Here's an example:

Let $$f$$ be a permutation such that:

f = \left(\begin{array}{c} 1&2&3&4&5&6&7 \\ 3&1&4&2&7&6&5 \end{array}\right)

As you can see, there are three different cycles: $$\left(\begin{array}{c}1&3&4&2\end{array}\right)\left(\begin{array}{c}5&7\end{array}\right)\left(6\right)$$. This allows the breakdown of permutations into one row notation.

Now that the basics of cycles are known, there are some interesting properties of cycles that should be noted:

Last but not least are Transpositions. A transpostion is a cycle $$\left(\begin{array}{c}i&j\end{array}\right)$$ of length 2 that interchanges (transposes) $$i$$ and $$j$$. Cycles can be expressed as the product of transpositions:

Let $$f=\left(\begin{array}{c}3&4&1&2\end{array}\right)$$. Using transpositions, we can change it:

\begin{align} &\left(\begin{array}{c}1&2&3&4\end{array}\right) \\ &\left(\begin{array}{c}4&1&2&3\end{array}\right) \\ \hbox{apply} \left(\begin{array}{c}1&2\end{array}\right) &\left(\begin{array}{c}1&4&2&3\end{array}\right) \\ \hbox{apply} \left(\begin{array}{c}2&3\end{array}\right) &\left(\begin{array}{c}1&2&4&3\end{array}\right) \\ \hbox{apply} \left(\begin{array}{c}3&4\end{array}\right) &\left(\begin{array}{c}1&2&3&4\end{array}\right) \end{align}

Therefore, the cycle $$\left(\begin{array}{c}1&2&3&4\end{array}\right)$$ can be expressed as $$\left(\begin{array}{c}1&2\end{array}\right)\left(\begin{array}{c}2&3\end{array}\right)\left(\begin{array}{c}3&4\end{array}\right)$$.