discrete math: Given sigma and tau, find (sigma)^5 (tau)^{-1}

adamkaz

New member
Joined
May 13, 2018
Messages
1
I do not understand this task:



9. Given the following:

. . . . .\(\displaystyle \sigma\, =\, \left(\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&9\\3&2&7&6&5&1&4&9&8\end{array}\right)\)

. . . . .\(\displaystyle \tau\, =\, \left(\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&9\\5&8&4&3&1&6&7&2&9\end{array}\right)\)

Find the following:

. . . . .\(\displaystyle \sigma^5\, \tau^{-1}\)

A (14) (298) (35)

B (15) (298) (34)

C (15) (289) (34)

D (14) (289) (35)




Which is correct and why? Thanks
 

Attachments

  • 1.jpg
    1.jpg
    39.9 KB · Views: 9
Last edited by a moderator:
I do not understand this task:



9. Given the following:

. . . . .\(\displaystyle \sigma\, =\, \left(\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&9\\3&2&7&6&5&1&4&9&8\end{array}\right)\)

. . . . .\(\displaystyle \tau\, =\, \left(\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&9\\5&8&4&3&1&6&7&2&9\end{array}\right)\)

Find the following:

. . . . .\(\displaystyle \sigma^5\, \tau^{-1}\)

A (14) (298) (35)

B (15) (298) (34)

C (15) (289) (34)

D (14) (289) (35)




Which is correct and why? Thanks

It will help if you tell us what parts you do understand, so we know where to start.

The question gives two permutations written in two-line notation, and asks for the result of a composition in cycle notation. Do you know what a permutation is? Do you understand the notation? Do you understand composition of permutations? Please show whatever part you can do.
 
Last edited by a moderator:
Supposing that you understand the notation but don't know how to solve the problem, you might start by finding where 1 goes under the composite permutation, which will be either 4 or 5, and will cut the number of choices in half. Then think about 2.
 
I do not understand this task:



9. Given the following:

. . . . .\(\displaystyle \sigma\, =\, \left(\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&9\\3&2&7&6&5&1&4&9&8\end{array}\right)\)

. . . . .\(\displaystyle \tau\, =\, \left(\begin{array}{ccccccccc}1&2&3&4&5&6&7&8&9\\5&8&4&3&1&6&7&2&9\end{array}\right)\)

Find the following:

. . . . .\(\displaystyle \sigma^5\, \tau^{-1}\)

A (14) (298) (35)

B (15) (298) (34)

C (15) (289) (34)

D (14) (289) (35)




Which is correct and why? Thanks
Sometimes in a textbook they will do the left permutation first and then move to the right while other textbooks will start with the right most permutation and work to the left. We have no idea at all which way you were taught. At least tell us that and say you need help from there.
I'll give you a hint. In the left permutation 1 goes to 3 and 3 goes to 7 and 7 goes to 4 etc. Look at the permutation and figure out where I got this from. Once you understand that and tell us if the left or right permutation comes first we can help. Even if you don't know then just give us an example from your book or notes and we'll try to figure it out.
 
Last edited by a moderator:
\(\displaystyle \tau= \begin{pmatrix}123456789 \\ 327651498\end{pmatrix}\) which means 1 goes to 3, 2 stays 2, 3 goes to 7, 4 goes to 6, 5 stays 5, six goes to 1, 7 goes to 4, 8 goes to 9 and 9 goes to 8. \(\displaystyle \tau^{-1}\) is the opposite: 1 goes to 6, 2 stays 2, 3 goes to 1, 4 goes to 7, 5 stays 5, 6 goes to 4, 7 goes to 3, 8 goes to 9, and 9 goes to 8. That can be written as \(\displaystyle \tau^{-1}= \begin{pmatrix}\frac{123456789}{621754398}\end{pmatrix}\).

(To write \(\displaystyle \tau\) in cycle notation, 1 goes to 3 goes to 7 goes to 4 goes to 6 goes to 1: (13746). stays 2. 5 stays 5. 8 goes to 9 goes 2 8: (89). ]tex]\tau= (13746)(89)[/tex]. \(\displaystyle \tau^{-1}\) takes 1 to 6 to 4 to 7 to 3 to 1: (16473). (We don't have to start at 1. If we started at 6 we would get (64731), just the reverse of (16573). \(\displaystyle \tau^{-1}= (16473)(89)\).)

\(\displaystyle \sigma= \begin{pmatrix}123456789 // 584316729\end{pmatrix}\). 1 goes to 5, 5 goes to 1. 2 goes to 8, 8 goes to 2. 3 goes to 4, 4 goes to 3. 6 stays 6, 7 stays 7 and 9 stays 9! That can be written cycle notation as (15)(28)(34). That's good because it makes it very easy to find the 5 power. If we do each of those 5 times, and odd number of times, its just as if we did just 1: \(\displaystyle \sigma^5= \begin{pmatrix}123456789 // 584316729\end{pmatrix}\)!

Now, what \(\displaystyle \sigma^5\tau^{-1}\) actually is depends, as Jomo said, on whether your convention is "right to left" and "left to right". Going "left to right" we would first do \(\displaystyle \sigma^5\) which, as I said before, just \(\displaystyle \sigma\) again. And, as before, in cycle notation (which I find easier to use), that is (15)(28)(34). \(\displaystyle \tau^{-1}\), in cycle notation, was (16473)(89). \(\displaystyle \sigma^5\tau^{-1}= [(15)(28)(34)][(16473)(89)\). Combining them, 1 goes to 5 which stays 5, 2 goes to 8 which goes to 9. 3 goes to 4 that goes to 7. 4 goes to 3 that goes to 1. 5 goes to 1 which goes to 6. 6 stays 6 which goes to 4. 7 stays 7 which goes to 3. 8 goes to 2 which stays 2, 9 stays 9 which goes to 8: 1 goes to 5, 2 goes to 9, 3 goes go 7, 4 goes to 1, 5 goes to 6, 6 goes to 4, 7 goes to 3, 8 goes to 2, and 9 goes to 8: \(\displaystyle \begin{pmatrix}123456789 \\ 597164328\end{pmatrix}\). In cycle notation that is (1564)(298)(37).

"Right to left" would be "1 to 6 stays 6", "2 stays 2 goes to 8", "3 goes to 1 goes to 5", "4 goes to 7 stays 7", "5 stays 5 goes to 1", "6 goes to 4 goes to 3", "7 goes to 3 goes to 4", "8 goes to 9 stays 9", 9 goes to 8 goes to 2". That is 1 goes to 6, 2 goes to 8, 3 goes to 5, 4 goes to 7, 5 goes to 1, 6 goes to 3, 7 goes to 4, 8 goes to 9, 9 goes to 2: \(\displaystyle \begin{pmatrix}123456789 \\ 685713492\end{pmatrix}\). In cycle notation that is (1635)(289)(47).
 
\(\displaystyle \tau= \begin{pmatrix}123456789 \\ 327651498\end{pmatrix}\) which means 1 goes to 3, 2 stays 2, 3 goes to 7, 4 goes to 6, 5 stays 5, six goes to 1, 7 goes to 4, 8 goes to 9 and 9 goes to 8. \(\displaystyle \tau^{-1}\) is the opposite: 1 goes to 6, 2 stays 2, 3 goes to 1, 4 goes to 7, 5 stays 5, 6 goes to 4, 7 goes to 3, 8 goes to 9, and 9 goes to 8. That can be written as \(\displaystyle \tau^{-1}= \begin{pmatrix}123456789 \\ 621754398\end{pmatrix}\)

(To write \(\displaystyle \tau\) in cycle notation, 1 goes to 3 goes to 7 goes to 4 goes to 6 goes to 1: (13746). stays 2. 5 stays 5. 8 goes to 9 goes 2 8: (89). ]tex]\tau= (13746)(89)[/tex]. \(\displaystyle \tau^{-1}\) takes 1 to 6 to 4 to 7 to 3 to 1: (16473). (We don't have to start at 1. If we started at 6 we would get (64731), just the reverse of (16573). \(\displaystyle \tau^{-1}= (16473)(89)\).)

\(\displaystyle \sigma= \begin{pmatrix}123456789 \\ 584316729\end{pmatrix}\). 1 goes to 5, 5 goes to 1. 2 goes to 8, 8 goes to 2. 3 goes to 4, 4 goes to 3. 6 stays 6, 7 stays 7 and 9 stays 9! That can be written cycle notation as (15)(28)(34). That's good because it makes it very easy to find the 5 power. If we do each of those 5 times, and odd number of times, its just as if we did just 1: \(\displaystyle \sigma^5= \sigma= \begin{pmatrix}123456789 \\ 584316729\end{pmatrix}\)!

Now, what \(\displaystyle \sigma^5\tau^{-1}\) actually is depends, as Jomo said, on whether your convention is "right to left" and "left to right". Going "left to right" we would first do \(\displaystyle \sigma^5\) which, as I said before, just \(\displaystyle \sigma\) again. And, as before, in cycle notation (which I find easier to use), that is (15)(28)(34). \(\displaystyle \tau^{-1}\), in cycle notation, was (16473)(89). \(\displaystyle \sigma^5\tau^{-1}= [(15)(28)(34)][(16473)(89)\). Combining them, 1 goes to 5 which stays 5, 2 goes to 8 which goes to 9. 3 goes to 4 that goes to 7. 4 goes to 3 that goes to 1. 5 goes to 1 which goes to 6. 6 stays 6 which goes to 4. 7 stays 7 which goes to 3. 8 goes to 2 which stays 2, 9 stays 9 which goes to 8: 1 goes to 5, 2 goes to 9, 3 goes go 7, 4 goes to 1, 5 goes to 6, 6 goes to 4, 7 goes to 3, 8 goes to 2, and 9 goes to 8: \(\displaystyle \begin{pmatrix}123456789 \\ 597164328\end{pmatrix}\). In cycle notation that is (1564)(298)(37).

"Right to left" would be "1 to 6 stays 6", "2 stays 2 goes to 8", "3 goes to 1 goes to 5", "4 goes to 7 stays 7", "5 stays 5 goes to 1", "6 goes to 4 goes to 3", "7 goes to 3 goes to 4", "8 goes to 9 stays 9", 9 goes to 8 goes to 2". That is 1 goes to 6, 2 goes to 8, 3 goes to 5, 4 goes to 7, 5 goes to 1, 6 goes to 3, 7 goes to 4, 8 goes to 9, 9 goes to 2: \(\displaystyle \begin{pmatrix}123456789 \\ 685713492\end{pmatrix}\). In cycle notation that is (1635)(289)(47).
 
Last edited:
Top