Permutations and supports
My original response
The support of the permutation is the set of elements where the permutation has any effect.
Points outside the support are left where they are by the permutation.
Points in the support are all moved around (to other points in the support), and none of them stay where they were. So all the action takes place in the support.
The identity permutation has empty support.
Two permutations have disjoint support if ... well, if their supports are disjoint! You can just say that such permutations are disjoint for short.
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. 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.)
For example, consider the permutation \(\rho\) of the \(7\)-set \(\{1,2,3,4,5,6,7\}\) written, as a product of disjoint cycles (including some \(1\)-cycles), as
\(\rho=(1\,5\,7)(2\,6)(3)(4)\,.\)
(The \(1\)-cycles are optional here and have no effect). Then
\(\mathrm{supp}(\rho)= \{1,5,7\} \cup \{2,6\}\) = \(\{1,2,5,6,7\}\).
This only works for products of disjoint cycles, though. For example, you can quickly check that \((1\,2) (3\,2\,1) = (1\,3)\). In this example, \(2\) is actually in the support of both cycles, but not in the support of the product of these cycles.
Follow-up post
Here (below, after an introduction) is a nice exercise related to the above.
Introduction concerning transpositions
Note that a transposition is another name for a \(2\)-cycle. These just swap two different elements of the set you are working with (which must have at least two elements). 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). So if \(\tau\) is a transposition we can say that \(\tau^2\) is the identity permutation. (There are also some other permutations with this property which are not transpositions. What are they?)
To be clear, for any permutation \(\tau\), \(\tau^2\) means that you multiply the permutation \(\tau\) by itself, using the usual multiplication of permutations, which is the same as composition of functions. So for any permutation \(\tau\), we have
\(\tau^2=\tau\tau=\tau \circ \tau\).
If \(\tau\) is a transposition, then \(\tau^2\) is the identity permutation. (But the converse is not true, unless your set has fewer than \(4\) elements and you assume that \(\tau\) is not the identity permutation!)
Exercise
Let \(X\) be a non-empty set. (If you want, you can assume that \(X\) is finite, or even that \(X=\{1,2,\dots,n\}\) for some natural number \(n\) if you like, but it isn't necessary.) Here is a fact about permutations of \(X\). (Where we talk about transpositions below, we mean permutations of \(X\) that are \(2\)-cycles.)
Let \(\rho\) be a permutation of \(X\) and suppose that supp\((\rho)\) is a non-empty, finite set. (So \(\rho\) is not the identity permutation, but \(\rho\) only moves finitely many elements.) Note here that supp\((\rho)\) must have at least two elements. (Why?)
Let \(k\) be the number of elements in supp\((\rho)\).
Prove that \(\rho\) is a product of some finite number of transpositions, and that it is possible to do this using strictly fewer than \(k\) transpositions in the product.
(You won't need to use the same transposition more than once, but if you do it counts more than once.)
Hint: Induction on \(k\), or design an algorithm based on the following idea.
Suppose you have some bottles in front of you numbered \(1\) to \(10\), but they are in the "wrong" order. How can you put them into the right order (left to right, \(1\) to \(10\)) if all you are allowed to do is swap two bottles at a time? How would you guarantee to do it with at most \(9\) swaps, even if all of the bottles are in the wrong places? Can you think of several different strategies?
Warning! if you can do a particular case with exactly \(8\) swaps then it turns out that you can't do that case with exactly \(9\) swaps, even if you tried completely different swaps! (But that's another story, about "odd" and "even" permutations.)
Have a go!
Comments
Post a Comment