Question

Find the product of two permutations \(\sigma\) and \(\varphi\), where, \(\begin{aligned}&\text { (i) } \quad \sigma=\mid 1 & 2 & 3 & 4 \\\& & \end{aligned}\) \(\varphi=\begin{array}{rrrrr}1 & 2 & 3 & 4 & 5 \mid \\ \mid 4 & 1 & 2 & 5 & 3 \mid\end{array}\) (ii) \(\quad \sigma=\begin{array}{rrrrr}1 & 2 & 3 & 4 & 5 \\ & 14 & 1 & 2 & 5 & 3 \mid\end{array}\) \(\varphi=\begin{array}{rrrrr}4 & 1 & 2 & 5 & 3 \\ \mid 1 & 2 & 3 & 4 & 5 \mid\end{array}\) (iii) \(\quad \sigma=\begin{array}{rrrrrr}1 & 2 & 3 & 4 & 5 \\ & \mid 5 & 2 & 4 & 3 & 1\end{array}\) \(\varphi=\begin{array}{rrrrr}4 & 1 & 2 & 5 & 3 \\ 1 & 2 & 3 & 4 & 5 \mid\end{array}\) (iv) \(\quad \sigma=\)\begin{tabular}{rrrrrr|} 1 & 2 & 3 & 4 & \(5 \mid\) \\ & \(\mid 4\) & 1 & 2 & 5 & 3 \end{tabular} \(\varphi=\begin{array}{rllll}1 & 2 & 3 & 4 & 5 \mid \\ & 2 & 4 & 1 & 5 & 3\end{array} \mid\)

Short answer

For the given permutations in (ii), (iii), and (iv), the products are: (ii) $$\sigma\varphi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 5 & 3 \end{pmatrix}$$ (iii) $$\sigma\varphi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 4 & 1 \end{pmatrix}$$ (iv) $$\sigma\varphi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 4 & 5 & 3 \end{pmatrix}$$

Step-by-step solution

Understand the permutations

Let's write down the given permutations. $$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix}, \quad \varphi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 2 & 5 & 3 \end{pmatrix}$$

Perform the composition of permutations

Perform the composition of the permutations by applying \(\varphi\) first and then \(\sigma\): $$\sigma(\varphi(i)) = \begin{cases} \sigma(4) = 4, & i=1 \\ \sigma(1) = 1, & i=2 \\ \sigma(2) = 2, & i=3 \\ \sigma(5) = 5, & i=4 \\ \sigma(3) = 3, & i=5 \end{cases}$$

Write down the resulting permutation

Now write down the resulting permutation: $$\sigma \circ \varphi= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 2 & 5 & 3 \end{pmatrix}$$ So, the product of \(\sigma\) and \(\varphi\) for the given permutations in (i) is: $$\sigma\varphi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 2 & 5 & 3 \end{pmatrix}$$ Follow the same procedure for the remaining cases (ii), (iii), and (iv).

Key concepts

Permutations

Permutations play a vital role in various branches of mathematics, including finite discrete mathematics. A permutation is essentially a reordering of elements in a set in a particular sequence or arrangement. When discussing permutations in the context of mathematics, we typically refer to the permutations of a finite set of items. In particular, when referring to a permutation of the set \( \{1, 2, 3, ..., n\} \) where \( n \) is a natural number, we are describing a mapping from the set to itself that rearranges the order of the elements.

For instance, the permutation \( \sigma \) on the set \( \{1, 2, 3, 4\} \) might be represented as follows:\[\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 1 & 4 & 3 \end{pmatrix}\]This indicates that in the permutation \( \sigma \) the element 1 is mapped to 2, 2 to 1, 3 to 4, and 4 to 3. Understanding permutations is a foundational step for further studies in discrete mathematics, including the analysis of permutation groups, combinatorics, and graph theory.

Product of Permutations

The concept of the product of permutations comes into play when two or more permutations are combined to form a new permutation. This operation is also known as the composition of permutations. When we talk about the 'product', rather than referring to multiplication in the usual numerical sense, we mean the application of one permutation after another. So, if you have two permutations, \( \sigma \) and \( \varphi \) as in the given exercise, the product \( \sigma\varphi \) means you first apply \( \varphi \) and then apply \( \sigma \) to the result of \( \varphi \) on each element of the set.

Here's how the product is calculated. If you want to find out where the element \( i \) ends up after applying both permutations, you first find where \( \varphi \) sends \( i \) (\( \varphi(i) \) ), and then you find where \( \sigma \) sends that result (\( \sigma(\varphi(i)) \) ). In the exercise provided, this step-by-step process is demonstrated to arrive at the new permutation which represents the combination of both \( \sigma \) and \( \varphi \) in sequence.

Understanding the product of permutations is essential for solving problems in permutation groups, where the group operation is the composition of these permutations.

Finite Discrete Mathematics

Finite discrete mathematics is a branch of mathematics dealing with discrete elements that are countable and not continuous. It includes a wide array of topics, such as combinatorics, graph theory, and finite probability theory, and plays a crucial part in computer science, cryptography, and network design. Permutations are an integral component of finite discrete mathematics, as they're used to describe arrangements or orderings of finite sets.

The problems involving permutations, such as finding their products, help in understanding the behavior of more complex systems and algorithms in computer science, for example, when analyzing the possible outcomes of certain processes. This area of mathematics emphasizes clear, logical thinking and the ability to work with discrete models. An understanding of permutation composition, as demonstrated in the exercise, is a practical application of finite discrete mathematics that underpins many real-world problems solutions.