305 – Homework III

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 X be a set (finite or infinite), and let f,g,h\in S_X. In detail, we are saying that f,g,h are permutations of the set X, that is, f:X\to X is a bijection, and similarly for g,h.

  • Show that fg and f^{-1} are again permutations of X. Show that (fg)h=f(gh). Find a formula for (fg)^{-1} in terms of f^{-1} and g^{-1}. Show that if fg=fh, then g=h, and that if gf=hf, then g=h.

(Here, as usual, fg denotes the composition of f and g, where we apply f first. As we will see, the properties in this exercise will be taken as basic properties all groups must have.)

Suppose that X is finite. The conjugate of f by g, denoted f^g, is the permutation g^{-1}fg. The reason why we use “exponential” notation is the following:

  • Show that (fg)^h=f^h g^h. Show that (f^g)^h=f^{gh}.

Conjugation proves to be very useful:

  • Say that f and g are conjugate iff, for some permutation h, we have f^h=g. Show that “f and g are conjugate” is an equivalence relation.

[Edit (Feb. 24, 2012): There was a bad typo when I first posted this (I said f^g=h, which is not what we want). The correct version is above. Thanks to Chantel Kelly for noticing this.]

  • Show that f sends i to j, that is, (i)f=j, iff f^g sends (i)g to (j)g, that is ((i)g)f^g=(j)g. This will be of great help when computing moves in Rubik’s cube.
  • Show that f=(6,9)(1,3,4)(2,5,7,8) and g=(1,7)(2,3,5)(4,9,6,8) are conjugate in S_9.
  • More generally, prove the following theorem due to Cauchy: Two permutations f and g in S_n 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 f is a k-cycle, then any conjugate of f is also a k-cycle, and any k-cycle is a conjugate of f.]

  • How many equivalence classes does the relation “f and g are conjugate in S_n” have?

[Again, it may be helpful to look in concrete at a few small values of n first.]

  • Show that (f^g)^k=(f^k)^g for any integer k, and conclude that f 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:

\mbox{\tt def swap(h):}

\mbox{\tt N=parent(h).degree()}

\mbox{\tt return sum([len([i2 for i2 in range(i1+1,N+1)} \mbox{\tt if h(i2)<h(i1)]) for i1 in range(1,N)])}

The function \mbox{\tt swap} just defined is precisely the swap function we studied in class; it counts the number of swaps or crosses of a given permutation. For example,

\mbox{\tt G=SymmetricGroup(7)}

\mbox{\tt g=G([(1,2,3),(4,6)])}

\mbox{\tt h=G([(1,2)])}

\mbox{\tt g*h;swap(g*h);h*g;swap(h*g)}

outputs

(2,3)(4,6)
4
(1,3)(4,6)
6

The program

\mbox{\tt swaps=[swap(g) for g in G]}

\mbox{\tt M=max(swaps)}

creates a list that assigns to each element g of G the value swap(g). Then, in M, it stores the largest of these numbers.

For example, if G=S_7, then M=21. In general, as we saw in class, if G=S_n, then M=\binom{n}2.

Sage has the slightly annoying feature that {\tt range(n)} is interpreted as \{0,1,\dots,n-1\}, excluding n, so the program:

\mbox{\tt L=[swaps.count(i) for i in range(M+1)]}

\mbox{\tt list}_\mbox{\tt plot(L).show()}

creates a list that to each 0\le i\le M, assigns the number of permutations f with swap(f)=i. Then, it shows the corresponding graph. When G=S_7 so M=21, we have:

  • Explain as many features of this graph as you can. For example, show that for any n, the graph is always going to be symmetric. Show that for any i with 0\le i\le \binom{n}2, there are permutations f with swap(f)=i. Why is the graph unimodal, that is, increasing up to its middle point? Can you find for each/some i the number of permutations f with swap(f)=i?

Here is a quick hint to show symmetry: Define F(i)=n+1-i. In class we showed that swap(F)=\binom{n}2 and F is the only permutation in S_n with so many swaps. Show that, for any g, swap(gF)=\binom{n}2 - swap(g), and that if g\ne h then gF\ne hF. 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 x and y coordinates, so we would divide the x coordinate by \binom{n}2 so x now varies from 0 to 1, and we would divide the y coordinate by its height, so y also varies from 0 to 1. Then we could plot simultaneously the graphs for several values of n. 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 n 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:

\mbox{\tt def swap(h):}

\mbox{\tt N=parent(h).degree()}

\mbox{\tt return sum([len([i2 for i2 in range(i1+1,N+1)} \mbox{\tt if h(i2)<h(i1)]) for i1 in range(1,N)])}

\mbox{\tt P=[]}

\mbox{\tt L=[]}

\mbox{\tt V=[]}

\mbox{\tt for N in range(11):}

\mbox{\tt P.append([])}

\mbox{\tt L.append([])}

\mbox{\tt V.append([])}

\mbox{\tt for N in range(6,10):}

\mbox{\tt G=SymmetricGroup(N)}

\mbox{\tt swaps=[swap(g) for g in G]}

\mbox{\tt M=max(swaps)}

\mbox{\tt L[N]=[swaps.count(i) for i in range(M+1)]}

\mbox{\tt print L[N]}

\mbox{\tt Q=RR(max(L[N]))}

\mbox{\tt V[N]=[RR((L[N][i])/Q) for i in range(M+1)]}

\mbox{\tt G=RR(M)}

\mbox{\tt V[N]=[(RR(i/G),V[N][i]) for i in range(M+1)]}

\mbox{\tt P[N]=points(V[N])}

\mbox{\tt R=P[6]+P[7]+P[8]+P[9]}

\mbox{\tt show(R)}

shows simultaneously the normalized plots for n=6,7,8,9, 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:

This question is part of a well studied topic, Permutation Statistics. I can provide some additional references if you are interested.

Advertisement

This entry was posted on Friday, February 17th, 2012 at 5:13 pm and is filed under 305: Abstract Algebra I. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: