Question

Write each permutation in Exercise 3 as a product of transpositions.

(a) $\left(\begin{array}{cccccc}\mathbf{1}& \mathbf{2}& \mathbf{3}& \mathbf{4}& \mathbf{5}& \mathbf{6}\\ \mathbf{2}& \mathbf{1}& \mathbf{3}& \mathbf{5}& \mathbf{4}& \mathbf{7}\end{array}\begin{array}{c}\mathbf{7}\\ \mathbf{9}\end{array}\begin{array}{c}\mathbf{8}\\ \mathbf{8}\end{array}\begin{array}{c}\mathbf{9}\\ \mathbf{6}\end{array}\right)$ (b)$\left(\begin{array}{cccccc}\mathbf{1}& \mathbf{2}& \mathbf{3}& \mathbf{4}& \mathbf{5}& \mathbf{6}\\ \mathbf{3}& \mathbf{5}& \mathbf{1}& \mathbf{2}& \mathbf{4}& \mathbf{6}\end{array}\begin{array}{c}\mathbf{7}\\ \mathbf{8}\end{array}\begin{array}{c}\mathbf{8}\\ \mathbf{9}\end{array}\begin{array}{c}\mathbf{9}\\ \mathbf{7}\end{array}\right)$

(c) $\left(\begin{array}{cccccc}\mathbf{1}& \mathbf{2}& \mathbf{3}& \mathbf{4}& \mathbf{5}& \mathbf{6}\\ \mathbf{3}& \mathbf{5}& \mathbf{1}& \mathbf{2}& \mathbf{4}& \mathbf{9}\end{array}\begin{array}{c}\mathbf{7}\\ \mathbf{8}\end{array}\begin{array}{c}\mathbf{8}\\ \mathbf{7}\end{array}\begin{array}{c}\mathbf{9}\\ \mathbf{6}\end{array}\right)$ (d)$\left(\mathbf{14}\right)\left(\mathbf{27}\right)\left(\mathbf{523}\right)\left(\mathbf{34}\right)\left(\mathbf{1472}\right)$

(e)$\left(\mathbf{7236}\right)\left(\mathbf{85}\right)\left(\mathbf{571}\right)\left(\mathbf{1537}\right)\left(\mathbf{486}\right)$

Short answer

The product of transpositions is$\left(12\right)\left(23\right)\left(45\right)\left(56\right)\left(78\right)$.

Step-by-step solution

To obtain the permutation by computing the product of cycles

We have the definition of cycle that,

Let $a_1,a_2,\dots ,a_k$be the distinct elements of the set $\left\{1,2,3,\dots ,n\right\}$. Then, $\left(a_1{a}_2\dots a_k\right)$denotes the permutation in $S_n$that maps $a_1$to $a_2$, $a_2$torole="math" localid="1653544343946" $a_3,\dots ,a_{k-1}$ to$a_k$ and$a_k$ to$a_1$ and every other elements of set maps to themselves.

$\left(a_1{a}_2\dots a_k\right)$is called a cycle of length k or k - cycle.

Two cycles which have no elements in common are called disjoint cycles.

A cycle of length 2 is called a transposition.

Now, the given permutation is,

$\left(7236\right)\left(85\right)\left(571\right)\left(1537\right)\left(486\right)$

First, we compute the product of these cycles to obtain a permutation.

Here, the given product is a composition of functions. So, the right-hand permutation is performed first. Thus, we will start from 1 in the second cycle from right-hand.

$\left(7236\right)\left(85\right)\left(571\right)\left(1537\right)\left(486\right)=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 2& 3& 1& 5& 6& 4\end{array}\begin{array}{c}7\\ 8\end{array}\begin{array}{c}8\\ 7\end{array}\right)$

Here, 1 is mapped to 5, 5 is mapped to 3, 3 is mapped to 7.and 7 is mapped to 2.So, 1 is mapped to 2. Moving to left-hand permutation, 2 is mapped to 3.

Next, 3 is mapped to 7 and 7 is mapped to 1. So, 3 is mapped to 1.

Next, 4 is mapped to 8 and 8 is mapped to 5. So, 4 is mapped to 5.

Next, 5 is mapped to 3, 3 is mapped to 6.So, 5 is mapped to 6.

Next, 6 is mapped to 4.

Next, 7 is mapped to 1, 1 is mapped to 5, 5 is mapped to 8. So, 7 is mapped to 8.

Next, 8 is mapped to 6, 6 is mapped 7. So, 8 is mapped to 7.

To find the product of transpositions

From step 1 we get,

$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 2& 3& 1& 5& 6& 4\end{array}\begin{array}{c}7\\ 8\end{array}\begin{array}{c}8\\ 7\end{array}\right)$

Here, 1 is mapped to 2, 2 is mapped to 3, 3 is mapped back to 1; 4 is mapped to 5 and 5 is mapped to 6 and 6 is mapped back to 4; 7 is mapped to 8 and 8 is mapped back to 7.

By using Theorem 7.26 that,

‘Every permutation in$S_n$ is a product of (not necessarily disjoint) transpositions’, the product of transpositions is expressed as,

$\begin{array}{rcl}\left(7236\right)\left(85\right)\left(571\right)\left(1537\right)\left(486\right)& =& \left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 2& 3& 1& 5& 6& 4\end{array}\begin{array}{c}7\\ 8\end{array}\begin{array}{c}8\\ 7\end{array}\right)\\ & =& \left(123\right)\left(456\right)\left(78\right)\\ & =& \left(12\right)\left(23\right)\left(45\right)\left(56\right)\left(78\right)\end{array}$

Hence, the product of transpositions is $\left(12\right)\left(23\right)\left(45\right)\left(56\right)\left(78\right)$.