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.
Best Answer
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.