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.