This homework set is due Wednesday, February 29th, at the beginning of lecture, but feel free to turn it in earlier if possible. Recall that “show” means “prove”.
Let be a set (finite or infinite), and let . In detail, we are saying that are permutations of the set , that is, is a bijection, and similarly for
- Show that and are again permutations of . Show that . Find a formula for in terms of and . Show that if , then , and that if , then
(Here, as usual, denotes the composition of and , where we apply first. As we will see, the properties in this exercise will be taken as basic properties all groups must have.)
Suppose that is finite. The conjugate of by , denoted , is the permutation . The reason why we use “exponential” notation is the following:
- Show that . Show that .
Conjugation proves to be very useful:
- Say that and are conjugate iff, for some permutation , we have . Show that “ and are conjugate” is an equivalence relation.
[Edit (Feb. 24, 2012): There was a bad typo when I first posted this (I said , which is not what we want). The correct version is above. Thanks to Chantel Kelly for noticing this.]
- Show that sends to , that is, , iff sends to , that is . This will be of great help when computing moves in Rubik’s cube.
- Show that and are conjugate in .
- More generally, prove the following theorem due to Cauchy: Two permutations and in are conjugate iff the cycles in their respective disjoint cycle decompositions have the same lengths when arranged from shortest to longest. Conclude that, in particular, two conjugate permutations have the same parity.
[It may help to treat first a few particular cases, for example, first check that if is a -cycle, then any conjugate of is also a -cycle, and any -cycle is a conjugate of .]
- How many equivalence classes does the relation “ and are conjugate in ” have?
[Again, it may be helpful to look in concrete at a few small values of first.]
- Show that for any integer , and conclude that has the same order as any of its conjugates.
Now let’s look at some statistics. This last problem is very open ended:
In class I showed a little program in Sage:
The function just defined is precisely the function we studied in class; it counts the number of swaps or crosses of a given permutation. For example,
creates a list that assigns to each element of the value . Then, in , it stores the largest of these numbers.
For example, if , then . In general, as we saw in class, if , then .
Sage has the slightly annoying feature that is interpreted as , excluding , so the program:
creates a list that to each , assigns the number of permutations with . Then, it shows the corresponding graph. When so , we have:
- Explain as many features of this graph as you can. For example, show that for any , the graph is always going to be symmetric. Show that for any with , there are permutations with . Why is the graph unimodal, that is, increasing up to its middle point? Can you find for each/some the number of permutations with ?
Here is a quick hint to show symmetry: Define . In class we showed that and is the only permutation in with so many swaps. Show that, for any , , and that if then . Explain why this implies symmetry of the graph.
- This is more ambitious, so I will count it as extra credit. Even if you do not see how to answer this, ideas or partial results are welcome. The graph above certainly looks “bell shaped”. Is this actually the case?
One way of checking this graphically for a few values would be to “normalize” the plot. One naive approach is to normalize the and coordinates, so we would divide the coordinate by so now varies from 0 to 1, and we would divide the coordinate by its height, so also varies from 0 to 1. Then we could plot simultaneously the graphs for several values of . Ideally, we would like to take the “limit” of these graphs. (The graphs below are constructed this way.)
Another (less naive) approach is to take a function that continuously interpolates the graph, and to scale it so that its area is 1. One can then plot it against the graph of the standard normal density. As increases, one can check whether our graph indeed approaches the Bell curve. (I would be interested in seeing these graphs, illustrating this relation, even if you do not see how to verify the result theoretically.)
For what is worth, the program:
shows simultaneously the normalized plots for , according to the first approach. (I have added empty spaces to indicate the extent of loops; Sage uses indentation instead, but I could not replicate this here.) Its output is:
[1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1]
[1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1]
[1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, 3017, 3450, 3736, 3836, 3736, 3450, 3017, 2493, 1940, 1415, 961, 602, 343, 174, 76, 27, 7, 1]
[1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, 11021, 14395, 17957, 21450, 24584, 27073, 28675, 29228, 28675, 27073, 24584, 21450, 17957, 14395, 11021, 8031, 5545, 3606, 2191, 1230, 628, 285, 111, 35, 8, 1]
In the literature, the swap function is usually called the number of inversions. A paper specifically dealing with it is:
- Barbara H. Margolius, “Permutations with Inversions“, Journal of integer sequences, vol. 4 (2), 2001.
This question is part of a well studied topic, Permutation Statistics. I can provide some additional references if you are interested.