Permutation Tables, Permutation Cycles and Transpositions

1. \(N\) Distinct Items can be arranged in \(N\) Different Locations. These locations are/can be Indexed from \(1\) to \(N\).
2. Using these Indexed Locations, Any Linear Permutation Without Repeatition of \(N\) Distinct Items can be mathematically represented in one of following 3 ways
   1. A Permutation Table consisting of \(2\) Rows and \(N\) Columns as given in the following
      
      \(\begin{pmatrix}S_1 & S_2 & S_3 & \cdots & S_N \\ D_1 & D_2 & D_3 & \cdots & D_N\end{pmatrix}\)   ...(1)
      
      In any Permutation Table as given in expression (1) above, the Top Row gives the Source Indices i.e. the Indexed Locations of Items Before Applying the Permutation and the Bottom Row gives the Destination Indices i.e. the Indexed Locations of Items After Applying the Permutation.
   2. In form of Destination Indices of the Permutation Table whose Source Indices are laid out in Order of Increasing Value From 1 to \(N\)
   3. A Single Permutation Cycle or Product of Two or More Disjoint Permutation Cycles
3. The following examples give \(3\) of the Linear Permutations Without Repeatition of \(6\) Distinct Items \(P_1\), \(P_2\) and \(P_3\) represented by the Permutation Tables
   
   \(P_1=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\4 & 2 & 1 & 6 & 5 & 3\end{pmatrix}\)   ...(2)
   
   \(P_2=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\5 & 1 & 6 & 2 & 3 & 4\end{pmatrix}\)   ...(3)
   
   \(P_3=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\3 & 6 & 5 & 2 & 1 & 4\end{pmatrix}\)   ...(4)
   
   In Permutation \(P_1\) represented by Permtation Table given in equation (2), the Item at \(1^{st}\) Location Moves to the \(4^{th}\) Location, Item at \(4^{th}\) Location Moves to the \(6^{th}\) Location, Item at \(6^{th}\) Location Moves to the \(3^{rd}\) Location and Item at \(3^{rd}\) Location Moves to the \(1^{st}\) Location. The Locations of \(2^{nd}\) and \(5^{th}\) Items remain unchanged.
   
   In Permutation \(P_2\) represented by Permtation Table given in equation (3), the Item at \(1^{st}\) Location Moves to the \(5^{th}\) Location, Item at \(5^{th}\) Location Moves to the \(3^{rd}\) Location, Item at \(3^{rd}\) Location Moves to the \(6^{th}\) Location, Item at \(6^{rd}\) Location Moves to the \(4^{th}\) Location, Item at \(4^{th}\) Location Moves to the \(2^{nd}\) Location and Item at \(2^{nd}\) Location Moves to the \(1^{st}\) Location.
   
   In Permutation \(P_3\) represented by Permtation Table given in equation (4), the Item at \(1^{st}\) Location Moves to the \(3^{rd}\) Location, Item at \(3^{rd}\) Location Moves to the \(5^{th}\) Location, Item at \(5^{th}\) Location Moves to the \(1^{st}\) Location, Item at \(2^{nd}\) Location Moves to the \(6^{th}\) Location, Item at \(6^{th}\) Location Moves to the \(4^{th}\) Location and Item at \(4^{th}\) Location Moves to the \(2^{nd}\) Location.
   
   Please Note that As long as the Mapping of Source Index Locations to Destination Index Locations remain the same, Interchanging the Columns of any Permutation Table does not change the Actual Permutation. For example, all the following Permutation Tables represent the Same Permutation \(P_1\)
   
   \(P_1=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\4 & 2 & 1 & 6 & 5 & 3\end{pmatrix}=\begin{pmatrix}5 & 3 & 2 & 6 & 1 & 4\\5 & 1 & 2 & 3 & 4 & 6\end{pmatrix} =\begin{pmatrix}4 & 1 & 5 & 6 & 3 & 2\\6 & 4 & 5 & 3 & 1 & 2\end{pmatrix}\)   ...(5)
   
   Likewise, Permutations \(P_2\) and \(P_3\) can be represented by all of the following Permutation Tables which are just formed by Interchanging of the Columns
   
   \(P_2=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\5 & 1 & 6 & 2 & 3 & 4\end{pmatrix}=\begin{pmatrix}5 & 3 & 4 & 1 & 6 & 2\\3 & 6 & 2 & 5 & 4 & 1\end{pmatrix} =\begin{pmatrix}3 & 6 & 1 & 5 & 2 & 4\\6 & 4 & 5 & 3 & 1 & 2\end{pmatrix}\)   ...(6)
   
   \(P_3=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\3 & 6 & 5 & 2 & 1 & 4\end{pmatrix}=\begin{pmatrix}2 & 4 & 6 & 1 & 3 & 5\\6 & 2 & 4 & 3 & 5 & 1\end{pmatrix} =\begin{pmatrix}6 & 5 & 2 & 3 & 1 & 4\\4 & 1 & 6 & 5 & 3 & 2\end{pmatrix}\)   ...(7)
4. Permutation Tables in which the Source Index Locations and Destination Index Locations are same for all Items represent the Identity Permutation. The following gives some examples of Permutation Tables for the Identity Permutation \(I\)
   
   \(I=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\1 & 2 & 3 & 4 & 5 & 6\end{pmatrix}=\begin{pmatrix}5 & 3 & 2 & 6 & 1 & 4\\5 & 3 & 2 & 6 & 1 & 4\end{pmatrix} =\begin{pmatrix}4 & 1 & 5 & 6 & 3 & 2\\4 & 1 & 5 & 6 & 3 & 2\end{pmatrix}\)   ...(8)
5. Although Permutation Tables can be laid out in any order (as demonstrated by equations (5), (6), (7) and (8)), they are generally laid out in Order of Increasing Value of Source Indices From 1 to \(N\) to facilitate representation of the Permutation in form of Destination Indices.
6. Permutation Cycles provide an alternate and a concise method of representing Linear Permutations / Permutation Tables. Any Linear Permutation / Permutation Table can consist of either a Single Permutation Cycle or Product of Two or More Disjoint Permutation Cycles. The following give the Permutation Table and corresponding Permutation Cycle representation for Permutations \(P_1\), \(P_2\) and \(P_3\)
   
   \(P_1=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\4 & 2 & 1 & 6 & 5 & 3\end{pmatrix}=(1\hspace{.1cm}4\hspace{.1cm}6\hspace{.1cm}3)\)   ...(9)
   
   \(P_2=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\5 & 1 & 6 & 2 & 3 & 4\end{pmatrix}=(1\hspace{.1cm}5\hspace{.1cm}3\hspace{.1cm}6\hspace{.1cm}4\hspace{.1cm}2)\)   ...(10)
   
   \(P_3=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\3 & 6 & 5 & 2 & 1 & 4\end{pmatrix}=(1\hspace{.1cm}3\hspace{.1cm}5)(2\hspace{.1cm}6\hspace{.1cm}4)=(2\hspace{.1cm}6\hspace{.1cm}4)(1\hspace{.1cm}3\hspace{.1cm}5)\)   ...(11)
7. The following gives the Steps to Find out Permutation Cycles of a Permutation Table
   1. Find the First Source Index in the Permutation Table for which the Source Index is Different than Destination Index and label that as the Current Source Index.
   2. Set the Current Source Index as the \(1^{st}\) Element of the Current Permutation Cycle.
   3. If the Destination Index Corresponding to Current Source Index is Not Same as \(1^{st}\) Element of the Current Permutation Cycle then set that Destination Index as the New Current Source Index and then set this Current Source Index as the Next Element of the Permutation Cycle. Repeat this Step to find All Subsequent Elements of the Current Permutation Cycle till the Destination Index Corresponding to Current Source Index is Same as \(1^{st}\) Element of the Current Permutation Cycle (which causes the Current Permutation Cycle to Complete).
   4. Find the Next Source Index in the Permutation Table for which the Source Index is Different than Destination Index which is Not an Element of Any of the Previous Permutation Cycles and label that as the Current Source Index for the Next Permutation Cycle (which now becomes the Current Permutation Cycle).
   5. Repeat the Steps b through d to find all the Permutation Cycles.
8. The following gives the Steps to Create a Permutation Table when corresponding Permutation Cycles are given
   1. Insert all the Elements of the Permutation Cycle as Source Indices into the Permutation Table.
   2. For every \(K^{th}\) Element of the Permutation Cycle inserted as a Source Index, set the \({(K+1)}^{th}\) Element as the Corresponding Destination Index. If the \(K^{th}\) Element is the Last Element of the Permutation Cycle, then set the \(1^{st}\) Element as the Destination Index for the Source Index corresponding to the \(K^{th}\) Element.
   3. If More than One Permutation Cycle is present, repeat the steps a through b for all Permutation Cycles.
   4. Subsequently, Insert the Elements Missing from the Permutation Cycles as Source Indices and Corresponding Destination Indices into the Permutation Table.
9. The following are some Properties of Permutation Cycles
   1. The Number of Elements in a Permutation Cycle is called the Cycle Length of Permutation Cycle.
   2. The Cycle Length of Permutation Cycle for Identity Permutation is 0.
   3. Rotating the Elements of any Permutation Cycle Clockwize or Anticlockwize does not change the Permutation Cycle. For example (\(2\hspace{.1cm}5\hspace{.1cm}3\hspace{.1cm}4\)), (\(4\hspace{.1cm}2\hspace{.1cm}5\hspace{.1cm}3\)), (\(3\hspace{.1cm}4\hspace{.1cm}2\hspace{.1cm}5\)) and (\(5\hspace{.1cm}3\hspace{.1cm}4\hspace{.1cm}2\)) represent the same Permutation Cycle.
   4. As given for the Permutation \(P_3\) in equation (11) above, the Order in which 2 or More Disjoint Permutation Cycles are written/multiplied Does Not Matter.
   5. Permutation Cycles of Cycle Length \(2\) (i.e. consisting of only \(2\) Elements) are called Transpositions. A Transposition is an Interchange of Locations/Positions any 2 Items.
   6. Any Permutation Cycle of Cycle Length \(N\) (where \(N > 2\)) can be Represented as / Decomposed into a Product of \(N-1\) Transpositions.