3
$\begingroup$

I am truly lost as to what this problem is asking. I did post this on another forum and received what my have been wonderful advice. However, even after multiple hours and many "Google" searches I am still confused. Please anyone....

The problem states: If $\sigma$ is a permutation of a set $A$, we say that $\sigma$ moves $a\in A$ iff $\sigma(a)\neq a$.

For the symmetric group $S_{36}$ of all permutations of 36 elements, let $H$ be a subset of $S_{36}$ containing all permutations that move no more than four elements. Is $H$ a subgroup of $S_{36}$? Prove.

I am not looking for an answer but more an explanation of what the problem is saying. I do not know what "move no more than four elements" means. I am feeling really stupid. Any help appreciated.

$\endgroup$
4
$\begingroup$

Let's look at $S_3$ instead. There are six permutations: $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)$, and $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array}\right)$.

$\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\right)$ moves no elements. $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array}\right)$, and $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right)$ move two elements. $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)$ and $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right)$ move three elements. Just look at how many are left where they started. With Arturo's answer, you should be on your way.

$\endgroup$
  • $\begingroup$ @Ross Millikan: Oops: our notations just collided; I'm using cycle notation, you are using abbreviated 2-line notation... I just added a coda to my answer to clarify that. $\endgroup$ – Arturo Magidin Dec 14 '10 at 22:19
  • $\begingroup$ @Arturo Magadin: Right you are. I though spelling it out this way would help OP, but didn't look at the notation closely enough. $\endgroup$ – Ross Millikan Dec 14 '10 at 22:38
  • $\begingroup$ @Ross: Actually, I was adding the cycle notation while you were editing, so it was not lack of observation on your part. $\endgroup$ – Arturo Magidin Dec 15 '10 at 0:57
  • $\begingroup$ @Arturo Magadin: I think we are in synch now. $\endgroup$ – Ross Millikan Dec 15 '10 at 1:02
  • $\begingroup$ @Ross: Except for the spelling of my last name, anyway. (-; $\endgroup$ – Arturo Magidin Dec 15 '10 at 1:04
3
$\begingroup$

Imagine you have 36 volumes of an encyclopedia in front of you. A permutation $\sigma\in S_{36}$ is a set of instructions of how to swap positions of the volumes of that encyclopedia. For instance, the permutation $\sigma=(1,2,3,4)$ (this is cycle notation: it says element 1 is sent to element 2, element 2 is sent to element 3, 3 to 4, and 4 to 1; if you are used to two-line or abbreviated two-line notation, then this is the permutation that has $$\left(\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & \cdots & 36\\ 2 & 3 & 4 & 1 & 5 & 6 & \cdots & 36 \end{array}\right).$$ as its two-line description) tells you to take volumes $1$ through $4$, and move volume $1$ to the second position, volume $2$ to the third position, volume $3$ to the fourth position, and volume $4$ to the first position. Even though $\sigma$ is a permutation of all 36 volumes, in fact you only need to move four of the volumes to perform the permutation $\sigma$. So we say that $\sigma$ fixes 32 volumes (volumes 5 through 36 are left untouched) and moves 4 volumes (volumes 1 through 4).

For each permutation $\sigma\in S_n$, which acts on the set $[n]=\{1,2,\ldots,n\}$, you can ask for the set $\mathrm{Fix}(\sigma) = \{ a\in[n]\mid \sigma(a)=a\}$, the set of elements fixed by $\sigma$.

What are the elements "moved" by $\sigma$? They are the elements of $[n]-\mathrm{Fix}(\sigma)$, the complement of $\mathrm{Fix}(\sigma)$.

A $\sigma\in S_{36}$ will lie in $H$ if and only if $[36]-\mathrm{Fix}(\sigma)$ has at most $4$ elements; that is, if and only if $\sigma$ fixes at least 32 of the elements of the numbers in $[36]=\{1,2,3,\ldots,36\}$.

The question is whether $H$ is a subgroup. It is easy to check that it is nonempty and closed under inverses (though you should do that). The trick is going to be figuring out if it is closed under products: if you have $\sigma$ and $\tau$, and each of them fix at least $32$ elements (though possibly not the same 32 elements), can $\sigma\tau$ fix fewer than 32 elements?

$\endgroup$
  • 1
    $\begingroup$ For Closure: "...can στ fix fewer than 32 elements?" yes. My reasoning: Let σ, τ be in set H. If σ moves elements {1, 2, 3, 4} of A and τ moves elements {5, 6, 7, 8} of A, then στ can move up to 7 elements and therefore, H is not closed under permutation multiplication and H is not a subgroup. Am I close? Argh! $\endgroup$ – JaxASL Dec 15 '10 at 0:20
  • $\begingroup$ @user4755: You are close. If $\sigma$ moves {1,2,3,4} among themselves and $\tau$ moves {5,6,7,8} among themselves, then $\sigma\tau$ would move all eight. But you are right that it moves more than four and that proves H is not closed and not a subgroup. $\endgroup$ – Ross Millikan Dec 15 '10 at 0:24

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.