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$$:
A good example is the identity permutation of $$f$$:
You can also make composite premutations. Here is an example:
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$$:
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:
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:
- A $$k$$-cycle can be written in $$k$$ different ways, each of the same order.
e.g. $$\left(\begin{array}{c}1&2&3&4\end{array}\right)=\left(\begin{array}{c}2&3&4&1\end{array}\right)=\left(\begin{array}{c}3&4&1&2\end{array}\right)=\left(\begin{array}{c}4&1&2&3\end{array}\right)$$ - If $$f$$ is a $$k$$-cycle, then $$f^k$$= identity, since it will have made a number $$n$$ go $$k$$ places around the cycle to end up where it started.
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:
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)$$.
