Please Login to access more options.

Problem 45 (Spans Of Permutations Are Subgroups)

Let $X=\{1,2,3,\ldots,n\}$. Let $S_n$ be the set of all permutations of $X$ (so we know there are $n!$ such permutations).

  1. Show that $S_n$ is a group under function composition $\circ$.
  2. If $H$ is a subset of $S_n$ that is closed (under composition combinations of permutations), prove that $H$ is a group under function composition.
  3. Let $S$ be a nonempty subset of $S_n$. Show that $\text{span}(S)$ is a group under function composition.

Solution

Let $n\in\mathbb{N}$ and $X=\{1,2,\ldots, n\}$. We now show that $S_n$ is a group under function composition. We know that the composition of two permutations is a permutation, so $S_n$ is closed under function composition. Function composition is associative. The identity permutation $id:X\to X$ defined by $id(x)=x$ for every $x\in \{1,2,\ldots, n\}$ is the identity of $S_n$. Clearly $id$ is a permutation on $X$, hence $id\in S_n$. Also, a direct computation shows that $(\alpha\circ id)(x) = \alpha(x) = (id\circ \alpha)(x)$ for every permutation $\alpha\in S_n$ and $x\in X$. If $\alpha\in S_n$, then by definition $\alpha$ is a bijective function. The inverse of $\alpha$ in $S_n$ is the inverse function $\alpha^{-1}$ (it shouldn't be a surprise that function inverse notation matches group theory notation). Note that $\alpha^{-1}\in S_n$ as the inverse of a permutation on $X$ is still a permutation on $X$. In addition, by the definition of an inverse function we have that $\alpha\circ \alpha^{-1} =\alpha^{-1} \circ \alpha=id$. This completes the proof that $S_n$ is a group.

Now suppose that $H\subset S_n$, and suppose that $H$ is closed (meaning $text{span}(H)=H$). First off, the problem, as stated, is false. If $H$ is the empty set, then $H$ is not a group. So suppose that $H$ is nonempty. Since $H$ is closed, we know that if $x\in H$ and $y\in H$, then $x^1\circ y^1=x\circ y\in H$. This proves that function composition is a binary operation on $H$. The operation is associative as function composition is associative. Since we assumed $H$ is nonempty, then pick $x\in H$. Note that being closed as a set of permutations means that both $x^0$ and $x^{-1}$ are elements of $H$. These two elements are clearly the identity of $H$ and the inverse of $x$ (the same computation as the previous paragraph will prove this).

To finish this problem, we now prove that if $S$ is a nonempty subset of $S_n$, then $\text{span}(S)$ is a group. We have already shown that $\span(S)$ is closed. The previous paragraph, with $H=\text{span}(S)$, completes the proof.

Tags

Change these as needed.

  • Week6 - Which week are you writing this problem for?
  • Ben - Sign your name by just changing "YourName" to your wiki name.
  • Complete
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.