# generators and relations of symmetric group

Let $S_{n}$ be symmetric group. Then it is given by generators $\tau_{i}$ where $i=1,2,\ldots,n-1$ and relations $${\tau_{i}}^2$$ $$\tau_{i}\tau_{j}=\tau_{j}\tau_{i}\text{ for }i\neq j\pm1$$ $$\tau_{i}\tau_{i+1}\tau_{i}=\tau_{i+1}\tau_{i}\tau_{i+1}$$ I will be pleased if someone can present me detailed proof of this fact.

-
I would like to know if there is a conceptually different (yet reasonable) proof besides the reflection group approach. So, I am offering a bounty on this question. – Phira Nov 29 '12 at 18:17
Please note that I think that the current answer does contain enough detail to be an answer to the original question, but I didn't want to start a new question with basically the same content, and this was the closest one in the choices for bounty messages. – Phira Nov 29 '12 at 18:29
In the book "Braid groups" by Kassel and Turaev, there is an elementary proof in chapter 4.1. books.google.de/… – Julian Kuelshammer Nov 29 '12 at 18:29
If you don’t want the reflection group aspect, you can do it completely combinatiorally, using parabolic subgroups in Coxeter groups. It is however a “reflection group approach in disguise”, so I don’t know if this is what you’re looking for. – Ewan Delanoy Nov 29 '12 at 19:59
@EwanDelanoy Basically, I am looking for an answer that can easily be given to students who have just learned the basics about groups (such an answer is now here), and I am also very interested in other elegant answers of any theoretical level that use some neat trick I am unaware of. So, I am not really looking for a way to "disguise" the advanced aspect. – Phira Nov 29 '12 at 22:19

If I understand the question, it is to show that the symmetric group $S_n$ is exactly the universal group on those generators with those relations. That is, that it is the quotient of the free group on $n$ generators by the smallest normal subgroup containing the relators.

The potential issue would be that $S_n$ might be a proper quotient of the actual universal group with those relations.

One device to understand $S_n$ is as a Coxeter group: the actual universal group $W$ with generators $s_j$ and relations as in the question is by definition a Coxeter group, and the _reflection_representation_ $W\rightarrow O(V)$ to the orthogonal group of the corresponding invariant quadratic form (from the Coxeter data) is proven injective by consideration of the length function on the group. It is not entirely trivial to prove this (see the Corollary on p. 7 of http://www.math.umn.edu/~garrett/m/buildings/book.pdf, for example).

To see that $S_n$ is isomorphic to $W$, rather than to a proper quotient, we need a natural representation of $S_n$ on an $(n-1)$-dimensional vector space $V$ preserving a quadratic form isomorphic to the Coxeter form. Indeed, and unsurprisingly, the restriction of the Killing form to the diagonal matrices in the Lie algebra $sl(n)$ of $SL(n)$ is preserved by the conjugation (Adjoint) action of $n$-by-$n$ permutation matrices, and is a scalar multiple of the Coxeter quadratic form.

This may seem circuitous or long-winded, but it is fairly conceptual, and applies to concrete realizations of the (spherical) Weyl groups of the other classical groups, as well.

-

Set $\tau_i=(i\ i+1)\in S_n$ for $i=1,\dots,n-1$. It's easily seen that these traspositions verify the given relations.

Theorem. Let $G$ be a group defined by $\tau_i$ and the given relations. Then $G\simeq S_n$.

Proof.

It's well known that $S_n$ is a homomorphic image of $G$. If we show that $|G|\leq |S_n|$, then we are done.

Induction on $n$. There is nothing to prove for $n=1$. Suppose $n>1$.

By the induction hypothesis $H=\langle\tau_2,\dots,\tau_n\rangle\simeq S_{n-1}$ and therefore it is enough to prove that $[G:H]\le n$.

Let $H_1=H, H_2=H_1\tau_1,\dots, H_n=H_{n-1}\tau_{n-1}$. We have $H_{i+1}\tau_i=H_i$ for $i=1,\dots,n-1$. Furthermore, if $i\neq j,j+1$, then $H_i\tau_j=H_i$. In order to show this let's set $\sigma_i=\tau_1\cdots\tau_{i-1}$ and note that $H_i=H\sigma_i$.

If $j\ge i+1$, then $\tau_j$ commutes with $\sigma_i$ and we get $$H_i\tau_j=H\sigma_i\tau_j=H\tau_j\sigma_i=H\sigma_i=H_i.$$ (We have used $H\tau_j=H$ which is true because $\tau_j\in H$).

If $1\le j<i-1$, then $\sigma_i=\sigma_j\tau_j\tau_{j+1}\sigma$, where $\sigma$ commutes with $\tau_j$. Thus $$H_i\tau_j=H\sigma_j\tau_j\tau_{j+1}\sigma\tau_j=H\sigma_j(\tau_j\tau_{j+1}\tau_j)\sigma=H\sigma_j(\tau_{j+1}\tau_j\tau_{j+1})\sigma=H\tau_{j+1}\sigma_j\tau_{j}\tau_{j+1}\sigma=H\sigma_j\tau_j\tau_{j+1}\sigma=H\sigma_i=H_i.$$ (We have used $H\tau_{j+1}=H$ which is true because $\tau_{j+1}\in H$).

Since $G=\langle\tau_1,\dots,\tau_n\rangle$, the relations above show that any right coset in $G$ modulo $H$ coincides with one of the $H_i$, and this is enough to conclude that $[G:H]\le n$.

Remark. I know this proof since I was a student, but I don't remember the source.

-
Thanks! Would you mind to emphasize the "idea" lines with ">" (first two sentences and the "By the induction hypothesis" sentence)? I will wait out the bounty to see if another proof comes along, but don't worry, if someone else posts another nifty different proof, I will just put on a second bounty to reward everyone. – Phira Nov 29 '12 at 21:23
That's not what I meant, so I just did it myself, hope you don't mind. – Phira Nov 29 '12 at 21:45