![]() ![]() How can you put them into the right order (left to right, to ) if all you are allowed to do is swap two bottles at a time? How would you guarantee to do it with at most swaps, even if all of the bottles are in the wrong places? Can you think of several different strategies? Suppose you have some bottles in front of you numbered to, but they are in the “wrong” order. Hint: Induction on, or design an algorithm based on the following idea. (You won’t need to use the same transposition more than once, but if you do it counts more than once.) ![]() Prove that is a product of some finite number of transpositions, and that it is possible to do this using strictly fewer than transpositions in the product. (So is not the identity permutation, but only moves finitely many elements.) Note here that supp must have at least two elements. Let be a permutation of and suppose that supp is a non-empty, finite set. (Where we talk about transpositions below, we mean permutations of that are -cycles.) (If you want, you can assume that is finite, or even that for some natural number if you like, but it isn’t necessary.) Here is a fact about permutations of. (But the converse is not true, unless your set has fewer than elements and you assume that is not the identity permutation!) If is a transposition, then is the identity permutation. To be clear, for any permutation, means that you multiply the permutation by itself, using the usual multiplication of permutations, which is the same as composition of functions. (There are also some other permutations with this property which are not transpositions. So if is a transposition we can say that is the identity permutation. Note that if you multiply a transposition by itself you get the identity permutation (the second application puts the two elements back where they started). These just swap two different elements of the set you are working with (which must have at least two elements). Note that a transposition is another name for a -cycle. Here (below, after an introduction) is a nice exercise related to the above. In this example, is actually in the support of both cycles, but not in the support of the product of these cycles. This only works for products of disjoint cycles, though. (The -cycles are optional here and have no effect). For most cycles the support is the set of elements mentioned in the cycle, but … 1-cycles have empty support! (A 1-cycle is just the identity permutation.)įor example, consider the permutation of the -set written, as a product of disjoint cycles (including some -cycles), as When you write a permutation as a product of disjoint cycles (including 1-cycles if you want), then the support of the whole permutation is the union of the supports of the disjoint cycles. Two permutations have disjoint support if … well, if their supports are disjoint! You can just say that such permutations are disjoint for short. The identity permutation has empty support. So all the action takes place in the support. Points in the support are all moved around (to other points in the support), and none of them stay where they were. Points outside the support are left where they are by the permutation. The support of the permutation is the set of elements where the permutation has any effect. Here are a post and a follow-up comment of mine from my first-year Pure Piazza forum, in response to a question asking about the notation (the support of a permutation ). See also the Blogger version of this post at where the maths looks a bit clearer. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |