1
$\begingroup$

I have the disjoint cycle: $$(156)(2437).$$ Apparently the "method" would get us: $$(1,6)(1,5)(2,7)(2,3)(2,4).$$ Basically you take the first number, and put it as a transposition of the last number and go backwards till you use all of them. I don't understand where this comes form. I don't know why this method works. Does it even work for my case? Oh and the order is 12 with the permutation being odd.

I think I understand $$(1,5)(5,6)(2,4)(4,3)(3,7)$$ much better. Is this a correct way to do transpositions as well?

$\endgroup$
  • 1
    $\begingroup$ Shouldn't it be $(15)(16)(24)(23)(27)$? Permutations are conventionally composed from left to right, and it seems that by comparing the disjoint cycle representation to the product of transpositions representation, that this is where you've had difficulty. $\endgroup$ – hardmath Apr 2 '14 at 6:34
  • 2
    $\begingroup$ I disagree with hardmath in that permutations, being functions, are also often composed from right to left. A bit unnatural, but a consequence of the usual convention of the name of the function preceding that of the variable. Admittedly I have seen it done both ways, but IMVHO (YMMV) it is more common to compose from right to left. $\endgroup$ – Jyrki Lahtonen Apr 2 '14 at 6:39
  • 1
    $\begingroup$ My book composes from right to left. $\endgroup$ – H5159 Apr 2 '14 at 6:40
  • 1
    $\begingroup$ @JyrkiLahtonen: it depends on which action you used, left or right. in elemenry books are mostly used left action. $\endgroup$ – mesel Apr 2 '14 at 6:40
  • 1
    $\begingroup$ @Frumpy then what is the trouble? Just verify that both expressions are the same permutation, by definition of right-to-left multiplication. $\endgroup$ – Dan Shved Apr 2 '14 at 6:41
1
$\begingroup$

Assuming we are composing from right to left, the original product of transpositions:

$$ (1,6)(1,5)(2,7)(2,3)(2,4) $$

can be applied to each item to show it agrees with the product of disjoint cycles:

$$ (156)(2437) $$

For example, let's apply the product of transpositions to $1$. Going from right to left, the first three transpositions leave $1$ fixed as it doesn't appear yet. Then $(1,5)$ sends $1$ to $5$, and since $5$ is not "moved" by the last transposition, that's how $1$ is mapped by the permutation as a whole.

Similarly in the product of disjoint cycles, $1$ is not affected by the first (rightmost) cycle, and in the end we see $1$ goes to $5$ by the second cycle $(156)$.

So these agree as functions on the mapping of $1$ to $5$. Showing the equality amounts to showing they agree on all inputs (elements of the domain).

$\endgroup$
  • $\begingroup$ Could you show me what happens when we look at 2, so I can see how it works if the element isn't ignored. Edit: if we look at 2, we see that 2 is sent to 4 by the first transposition, but then 4 does not come up again, so 2 will go to 4? And if we look at 3, we see that 3 is being sent to 2, and then 2 is being sent to 7, which means 3 is being ant to 7? $\endgroup$ – H5159 Apr 2 '14 at 6:57
  • $\begingroup$ @Frumpy That's exactly how you do it! $\endgroup$ – Christoph Apr 2 '14 at 7:05
  • $\begingroup$ Yes, I think you've got it! In the product of disjoint cycles, it's a little confusing because it reads each cycle from left to right (but since the cycles are disjoint, it doesn't matter what order we put the two cycles in), and $(2437)$ means $2$ goes to $4$, $4$ goes to $3$, $3$ goes to $7$, and finally $7$ goes to $2$. $\endgroup$ – hardmath Apr 2 '14 at 7:05
  • 1
    $\begingroup$ Yeah that is where my confusion was coming from. It goes left to right and is intuitive in the disjoint form. But in the transposition form, what you do is you start with your first element, find it, going from right to left and see how each transposition you pass changes it. If it doesn't change it you leave it, if it does you go to "that place." So basically I just checked, both the transpositions I have shown are correct. By the way, the permutation is odd because the number of transpositions are odd. And the order is 12 correct? $\endgroup$ – H5159 Apr 2 '14 at 7:08
  • 2
    $\begingroup$ @Frumpy: You seem to be applying the permutation more than once. If you apply it once, then it maps 2 to 4. Of course the permutation maps 4 somewhere also (it maps all the items 1 through 7 to some value, rearranging them so we call it "permutation"). But if you apply the mapping once, the disjoint cycle representation tells us quite clearly where 2 goes (check your original Question). $\endgroup$ – hardmath Apr 17 '14 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.