Fraleigh Section 9 Question 27

Question

Question 27 on Section 9 of Fraleigh 7th edition:

Part (a) Asks us to prove that a permutation in $S_n$ can be written as a product of at most $n - 1$ transpositions.

I feel that this is not true. There are endless counter examples to this. Simply write $i = (1, 2)(1, 2)(1, 2)(1, 2)$ gives the identity permutation in $S_3$.

Or, write $(3, 4)(1, 2)(2, 3)(3, 1)$ gives a permutation in $S_4$.

Thanks for the help, and I will continue asking questions about Fraleigh because I am doing a complete self study, so this is my only resource for asking questions.

Answer 1

The proof is easy when you think about arranging $n$ objects. Use the first transposition to put the first object in place, the second to place the second object. When you get the $(n-1)^{th}$ object in place you discover that everything is in order as it is impossible to have just one object out of place.

That's not too difficult to translate into the language of transpositions.

Answer 2

"Can be written in a certain form" means that there exists a way of writing something in that form. The claim that the exercise wants to to prove is that if $s$ is any element of $S_n$, then there exists some sequence of $n-1$ or fewer transpositions whose product is $s$. Obviously you can multiply together as many transpositions as you want, but the point here is that you never get anything new by multiplying together more than $n-1$ of them.

Here is a different example of the same thing, possibly helpful:

Every positive integer can be written in the form $(2k+1)\cdot 2^m$ for some integers $k$ and $m$.

Does this mean that the integer 1,428 is written in this form? No, of course it doesn't, because it isn't. It only means that there exist numbers $k$ and $m$ for which $(2k+1)\cdot 2^m = 1428$—in this case $k=178$ and $m=2$.