4
$\begingroup$

In an exercise, I must prove $S_{n}$ is generated by 2 elements. I'll ignore here the trivial case $n = 1$. Let $I_{n} = \{1, 2, 3, ..., n\}$. I then defined $f : I_{n} \rightarrow I_{n}$ by $f(1) = 2$, $f(2) = 1$, and $f(i) = i,$ for $i \neq 1, 2$. Also $g : I_{n} \rightarrow I_{n}$ by $g(1) = n$ and $g(i + 1) = i$ for $i \in \{1, ..., n - 1\}$. I claimed $f, g$ generate $S_{n}$, which is apparently correct. But my explanation is apparently completely wrong. I hope someone may undo my confusion.

So intuitively, $f$ is a swap permutation which swaps the first two elements, and $g$ is a shift permutation which shifts everything to the left. We note any permutation can be written as a series of "swaps" (transpositions). So it suffices to show $f, g$ generate the swaps. So suppose I want to compose $f$ and $g$ in such a way to swap $1 \leq i < j \leq n$. The algorithm would go somewhat like this: shift everything to the left until $i$ is the first element. Now apply swap once, then shift back again, apply swap, shift back, and so forth until you just swapped $i$ with $j$. Count how many times you shifted left after you first swapped. Now you shift right (which is just the inverse of shifting left), swap, shift right, swap, .. and do that just as many times as you shifted left. In the end you should be left with exactly $i, j$ swapped and everything else in its place. Let's do an example. Suppose I want to swap 1 and 4 in 1234. It'll go as:

2134 (swapped)

1342 (shifted left 1 time)

3142 (swapped)

1423 (shifted left 2 times)

4123 (swapped 4 and 1; I'll start shifting right now)

3412 (shifted right 1 time)

4312 (swapped)

2431 (shifted right 2 times)

4231 (swapped)

And we are done! Apparently the problem with this is that $f$ doesn't actually swap the first and second elements, there is no order, it just swaps 1 with 2. Under which interpretation this makes little sense. My question is: is my way of thinking about this completely wrong? Is it merely coincidental that I achieved a correct answer? And if it is wrong, how should I be thinking about permutations? I am not familiar with the cycle notation.

$\endgroup$
  • $\begingroup$ Hopefully all fixed now :p $\endgroup$ – Pedro Jun 2 '13 at 6:01
3
$\begingroup$

Your solution is basically correct, though not very well formulated. But you are not clear about how you represent a permutation, and whether "applying" a permutation corresponds to multiplication on the left or on the right, and this makes it difficult to point precisely to what you should do different. But in any case you can salvage your kind of reasoning by making the proper choices.

In group theory permutations are defined as functions (bijections), not as permuted sequences. So first let us fix the correspondence: a sequence $(a_1,\ldots,a_n)$ (with $\{a_1,\ldots,a_n\}=\{1,\ldots,n\}$) represents the permutation $\sigma$ that sends $i\mapsto a_i$ for all$~i$. (This seems a natural choice, but a choice nonetheless.) Next we need to be clear about left and right in permutation composition; since you write (permutation) functions before their argument, let us choose as usual that the composition $f.g$ is $i\mapsto f(g(i))$ (the permutation on the right gets to operate first). Again this is a natural choice, but some prefer to have $f$ act first (typically those who prefer to write $i^f$ instead of $f(i)$); I just want to make my choice clear.

With these choices, if $\sigma$ is represented by $(a_1,\ldots,a_n)$, then $\pi.\sigma$ is represented by $$ \bigl(\pi(\sigma(1)),\ldots,\pi(\sigma(n))\bigr) = \bigl(\pi(a_1),\ldots,\pi(a_n)\bigr), $$ in other words left multiplication by$~\pi$ corresponds to applying the function $\pi$ to the values of individual entries of the sequence, not to permuting the entries of the sequence according to$~\pi$. However if we multiply on the right by$~\pi$, the situation is different: $\sigma.\pi$ is represented by $$ \bigl(\sigma(\pi(1)),\ldots,\sigma(\pi(n))\bigr) = \bigl(a_{\pi(1)},\ldots,a_{\pi(n)}\bigr). $$ Here it is the positions that are permuted. Since you use this in your argument, it can be made valid if you stipulate that each successive permutation applied to the sequence corresponds to a right-multiplication.

I should warn about a slight twist that remains: right multiplication by $\pi$ does permute the entries in the sequence, but it does so in such a way that the new entry at position $i$ is $a_{\pi(i)}$, which is the one that used to be in position$~\pi(i)$; the old value $a_i$ will be found after permutation at position $\pi^{-1}(i)$. This is what you probably associate with permuting the entries according to the inverse permutation$~\pi^{-1}$. Indeed this is true for the usual definition of permutations acting (from the left!) on sequences, as I detailed in this answer. If you think of it, it is normal that when right-multiplication is related to a left-action on sequences, an inversion should be used in the process.

No doubt this somewhat unfortunate consequence of the otherwise natural choices above is what motivates people to make the opposite choice for one of the two. As I said it is often the second that is reversed, but this has other notational consequences that can be confusing. For me the real culprit is the first choice: it would be more natural to represent $\sigma$ as the result of permuting the standard sequence $(1,2,\ldots,n)$ according to$~\sigma$, and this gives $(\sigma^{-1}(1),\sigma^{-1}(2),\ldots,\sigma^{-1}(n))$ rather than $(\sigma(1),\sigma(2),\ldots,\sigma(n))$. However, I would not really advocate doing this, as this would make the confusion between notations even worse.

$\endgroup$
1
$\begingroup$

Here's an easier way to think about. For $0 \le j \le n - 1$, consider the element

$$(1 \dots n)^{-j}(12)(1 \dots n)^{j}$$

Let $k \in \{1, \dots, n\}$. Under the rightmost cycle, $k \to (k + j) \bmod n$. (Think of $0$ as the symbol $n$, here).

If $(k+j) \bmod n \not \equiv 1, 2$, then under the entire permutation, $k \to k$. If $1 \equiv (k + j) \bmod n$, then $k \equiv (1 - j) \mod n$, and $k \to (2 - j) \bmod n$. Hence, $(1 \dots n)^{-j}(12)(1 \dots n)^{j}$ is a transposition of adjacent elements, and we know adjacent transposition generate $S_n$.

$\endgroup$
1
$\begingroup$

As you say, applying $f$ only switches $1$ and $2$, it does not 'switch the first two entries in a permutation's cycle notation' (to paraphrase what you want to happen); such a thing is not even generically well-defined because there are multiple ways of representing a permutation with cycles.

The reason it works out is that if you could switch any two elements in a permutation's cycle representation, then you would indeed be able to generate all the necessary transpositions. But you haven't outlined how you would go about doing that with just $f$ and $g$.

Here is a suggestion: show that adjacent transpositions generate all transpositions, which suffices for the task because transpositions generate all the rest of $S_n$, as you know. You only need to construct every adjacent transposition $(i~i+1)$ for $i=1,\cdots,n-1$. To do this, keep in mind the effect that not products but conjugations have on cycle representations:

$$\sigma (a_1~a_2~\cdots~a_{l_1})\cdots(b_1~b_2~\cdots~b_{l_m})\sigma^{-1}=(\sigma a_1~\sigma a_2~\cdots~\sigma a_{l_1})\cdots(\sigma b_1~\sigma b_2~\cdots~\sigma b_{l_m}).$$

So what permutations do you get upon repeatedly conjugating $f=(1~2)$ by $g=(1~2~\cdots~n)$?

$\endgroup$
  • $\begingroup$ The question does not mention cycle notation for permutation, and as far as I can tell does not suggest their implicit used in any way either. Instead a "permuted sequence" representation (one-line notation) seems to be used. $\endgroup$ – Marc van Leeuwen Jun 2 '13 at 8:11
1
$\begingroup$

I think you would prefer better notation, in which the proof is more visually obvious. Consider: $$f = \begin{matrix} 1 & 2 & \dots & n \\ 2 & 1 & \dots & n \end{matrix} \qquad g = \begin{matrix} 1 & 2 & \dots & n \\ n & 1 & \dots & n - 1\end{matrix} $$ where the correspondence between an $i$ in the first row and $j$ in the second row is that $j = f(i)$ or $g(i)$, respectively. Your goal is to express the transpositions ("swaps" is not a standard term) in terms of $f$ and $g$. Before I do that, there is a further simplification you missed:

Lemma: $S_n$ is generated by the "adjacent transpositions" $s_i$ exchanging $i$ with $i + 1$ (modulo $n$).

The diagram for $s_i$ is: $$s_i = \begin{matrix} 1 & \dots & i & i + 1 & \dots & n \\ 1 & \dots & i + 1 & i & \dots & n \end{matrix}$$ (with $s_n$ wrapping around). This is just $f$, "moved" $i - 1$ places to the right. Note that $g$ "moves" everything $1$ place to the right, so $g^{i - 1}$ moves $i - 1$ places. Therefore the following permutation is $s_i$: $$\begin{matrix} 1 & \dots & i & i + 1 & \dots & n \\ n - i + 2 & \dots & 1 & 2 & \dots & n - i + 1& \quad (g^{i - 1}) \\ n - i + 2 & \dots & 2 & 1 & \dots & n - i + 1& \quad (f) \\ 1 & \dots & i + 1 & i & \dots & n & \quad (g^{-(i - 1)}) \end{matrix}$$ where each row is marked with what we applied to the previous row. Note that every row but the first is out of order, but we just apply the indicated function to whatever value is in each place. Also, values such as $n - i + 2$ should be taken modulo $n$, for example when $i = 1$.

$\endgroup$
  • $\begingroup$ Since the question stipulates $g(1)=n$, I don't think you have got the correct two-line notation for $g$. $\endgroup$ – Marc van Leeuwen Jun 2 '13 at 8:08
  • $\begingroup$ @Marc It seems I wrote $g^{-1}$. $\endgroup$ – Ryan Reich Jun 2 '13 at 14:30
1
$\begingroup$

It would be very convenient to represent permutations in disjoint cycle notation, as anon has used. But if you want to use your notation of representing a permutation as a linear arrangement, you could understand why $f,g$ generate $S_n$, as follows.

Given any permutation, we need to obtain the given permutation starting from $[1,2,\ldots,n]$ by repeatedly using $f$ (switching the first and second coordinates) and $g$ (doing a cyclic shift of the elements). A right cyclic shift by $i$ coordinates can be effected by applying the left cyclic shift $g$ a total of $n-i$ times.

First observe that any permutation can be obtained from the initial one by just swapping two consecutive coordinates at a time. For example, to go from 1234 to 4231, as you've done, you swap the first and second coordinate, then second and third, then third and fourth, to bring 1 to the fourth coordinate. Next, you can bring 3 to the third coordinate, 2 to second coordinate, and 4 will automatically be in the first coordinate.

It remains to be shown that swapping two consecutive coordinates can be achieved through a sequence of $f$'s and $g$'s. Swapping the first two coordinates is allowed since it is just $f$. To swap the $i$-th and $i+1$-th coordinate, just apply the cyclic shift $g$ a certain number of times ($(n-i)$ times) to bring the numbers in the $i$th and $i+1$th coordinate to the 1st and 2nd coordinate, then swap the first and second coordinate by applying $f$, then apply $g$ again the appropriate number of times to shift back these two numbers from the 1st and 2nd coordinate to the $i$th and $i+1$th coordinates, respectively. In this manner, and I think you can visualize this intuitively, the numbers in any two consecutive coordinates can be swapped using the operation of cyclic shift, swapping the first two coordinates only, and cyclic shift again.

To understand further, you could learn about conjugation. It turns out that every permutation can be expressed as a disjoint union of cycles, and an important result here is that the type of a permutation (i.e. the lengths of these different cycles) remains the same if you conjugate a permutation $a$ by another permutation $b$, i.e. $bab^{-1}$ has the same cycle structure as $a$. So, if $a=(1,2)$ is an element of a permutation group, and $b=(1,2,\ldots,n)$ is also in the group, then by composing these two together in the special way $bab^{-1}$, we are effecting a cyclic shift, swap, and reverse cyclic shift to obtain that $(2,3)$ is also in the group (or $(1,n)$ rather than $(2,3)$, depending on whether you compose left to right or right to left). The point is that such a product will again be some 2-cycle because conjugation preserves the type of a permutation. So we quickly obtain all consecutive swaps in this manner; for example, conjugating $(2,3)$ by $b$ gives $(3,4)$, and so on.

More generally, it can be shown that if $(i,j)$ denotes a swap of the $i$th and $j$th coordinate, then a set of swaps $A$ generates $S_n$ if and only if the transposition graph of $A$ is connected. In our case, by repeatedly conjugating $a=(1,2)$ with $b$, we are able to obtain the path graph on the $n$ vertices $\{1,2,\ldots,n\}$. Since this graph is connected, $a$ and $b$ generate $S_n$.

$\endgroup$

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.