# Symmetric group

The no­tion that group the­ory cap­tures the idea of “sym­me­try” de­rives from the no­tion of the sym­met­ric group, and the very im­por­tant the­o­rem due to Cayley that ev­ery group is a sub­group of a sym­met­ric group.

# Definition

Let $$X$$ be a set. A bi­jec­tion $$f: X \to X$$ is a per­mu­ta­tion of $$X$$. Write $$\mathrm{Sym}(X)$$ for the set of per­mu­ta­tions of the set $$X$$ (so its el­e­ments are func­tions).

Then $$\mathrm{Sym}(X)$$ is a group un­der the op­er­a­tion of com­po­si­tion of func­tions; it is the sym­met­ric group on $$X$$. (It is also writ­ten $$\mathrm{Aut}(X)$$, for the au­to­mor­phism group.)

We write $$S_n$$ for $$\mathrm{Sym}(\{ 1,2, \dots, n\})$$, the sym­met­ric group on $$n$$ el­e­ments.

# Ele­ments of $$S_n$$

We can rep­re­sent a per­mu­ta­tion of $$\{1,2,\dots, n\}$$ in two differ­ent ways, each of which is use­ful in differ­ent situ­a­tions.

## Dou­ble-row notation

Let $$\sigma \in S_n$$, so $$\sigma$$ is a func­tion $$\{1,2,\dots,n\} \to \{1,2,\dots,n\}$$. Then we write

$$\begin{pmatrix}1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \\ \end{pmatrix}$$
for $$\sigma$$. This has the ad­van­tage that it is im­me­di­ately clear where ev­ery el­e­ment goes, but the dis­ad­van­tage that it is quite hard to see the prop­er­ties of an el­e­ment when it is writ­ten in dou­ble-row no­ta­tion (for ex­am­ple, ”$$\sigma$$ cy­cles round five el­e­ments” is hard to spot at a glance), and it is not very com­pact.

## Cy­cle notation

Cy­cle no­ta­tion is a differ­ent no­ta­tion, which has the ad­van­tage that it is easy to de­ter­mine an el­e­ment’s or­der and to get a gen­eral sense of what the el­e­ment does. Every el­e­ment of $$S_n$$ can be ex­pressed in (dis­joint) cy­cle no­ta­tion in an es­sen­tially unique way.

## Product of transpositions

It is a use­ful fact that ev­ery per­mu­ta­tion in a (finite) sym­met­ric group may be ex­pressed as a product of trans­po­si­tions.

# Examples

• The group $$S_1$$ is the group of per­mu­ta­tions of a one-point set. It con­tains the iden­tity only, so $$S_1$$ is the triv­ial group.

• The group $$S_2$$ is iso­mor­phic to the cyclic group of or­der $$2$$. It con­tains the iden­tity map and the map which in­ter­changes $$1$$ and $$2$$.

Those are the only two abelian sym­met­ric groups. In­deed, in cy­cle no­ta­tion, $$(123)$$ and $$(12)$$ do not com­mute in $$S_n$$ for $$n \geq 3$$, be­cause $$(123)(12) = (13)$$ while $$(12)(123) = (23)$$.

• The group $$S_3$$ con­tains the fol­low­ing six el­e­ments: the iden­tity, $$(12), (23), (13), (123), (132)$$. It is iso­mor­phic to the dihe­dral group $$D_6$$ on three ver­tices. (Proof.)

# Why we care about the sym­met­ric groups

A very im­por­tant (and rather ba­sic) re­sult is Cayley’s The­o­rem, which states the link be­tween group the­ory and sym­me­try.

knows-req­ui­site(Con­ju­gacy class):

# Con­ju­gacy classes of $$S_n$$

It is a use­ful fact that the con­ju­gacy class of an el­e­ment in $$S_n$$ is pre­cisely the set of el­e­ments which share its cy­cle type. (Proof.) We can there­fore list the con­ju­gacy classes of $$S_5$$ and their sizes. <div>

# Re­la­tion­ship to the al­ter­nat­ing group

The al­ter­nat­ing group $$A_n$$ is defined as the col­lec­tion of el­e­ments of $$S_n$$ which can be made by an even num­ber of trans­po­si­tions. This does form a group (proof).

knows-req­ui­site(Nor­mal sub­group): In fact $$A_n$$ is a nor­mal sub­group of $$S_n$$, ob­tained by tak­ing the quo­tient by the sign ho­mo­mor­phism.

Children:

Parents:

• Group

The alge­braic struc­ture that cap­tures sym­me­try, re­la­tion­ships be­tween trans­for­ma­tions, and part of what mul­ti­pli­ca­tion and ad­di­tion have in com­mon.

• Re­quest for com­ment: is the defi­ni­tion of “cy­cle” some­thing that should be on its own page? They’re not about the sym­met­ric group per se, but I’ve only heard of cy­cles be­ing used in the con­text of sym­met­ric groups.

• For core/​defi­ni­tion pages I think we want to have su­per mod­u­lar con­tent (eas­ier brows­ing, lets peo­ple pick just the parts they want to learn, re­duces page scope creep), so putting it on its own page is good. It’s a child of this page, which seems like the ap­pro­pri­ate re­la­tion­ship.

• I took the plunge and put it on its own page.