Rules of a Group

1. Pre-defined list of actions that never changes - actions are called generators
2. move is reversible
3. move is deterministic (no stochastic process)
4. moves can be combined in any sequence - any sequence of generators is an action

G has 4 actions: the ‘identity’ action e, a horizontal flip h, a vertical flip v, and a 180 degree rotation r

\[G = \{e, h, v, r\}\]

We need two actions to generate G. In our diagram, each generator is represented by a different type of color. We write

\[G = \bigl \langle \ h, v \ \bigr \rangle\]

The map shows us how to get from one configuration to any other. There is more than one way to follow the arrows.

\[r = hv = vh\]

This is an abelian group or commutative group.

Every action in G is its own inverse. That is

\[e = e^2 = h^2 = v^2 = r^2\] \[e^{-1} = e, v^{-1} = v, h^{-1} = h, r^{-1} = r\]

An alternatve set of generators for the Rectangle Puzzle

The rectangle puzzle can also be generated by a horizontal flip and a 180 degree rotation

\[G = \bigl \langle h,r \bigr \rangle\]

Group Presentations

We use a group presentation of the following form:

\[G = \bigl \langle generators\ \big| \ relations \bigr \rangle\]

G is generated by the elements (generators) subject to a given relations relations.

The following is the presentation for this group:

\[V_{4} = \bigl \langle a,b \ \big |\ a^{2} = e,\ b^{2} = e,\ ab = ba\ \big \rangle\]

The presentation for this group is:

\[G = \bigl \langle t,f \ \big |\ f^{2} = e,\ tft =f \ \big \rangle\]

The presentation for this group is:

\[D_{3} = \bigl \langle r,f \ \big |\ r^{3} = e,\ f^{2} = e,\ r^{2}f = fr\ \big \rangle\]

Trivial Group

\[\displaylines{ \begin{align*} G &= \bigl \langle\ a, b \ \big|\ ab = b^{2}a, \ ba = a^{2}b \ \bigr \rangle\\ G &= \{e\}! \end{align*} }\]

Inverses

If g is a generator in a group G, then following the “g-arrow” backwards is an action that we call its inverse, and denoted by g^-1

If g is represented by a path in a Cayley diagram, then g^-1 is the action achieved by tracing out this path in reverse.

Note that by construction: \(gg^{1} = g^{-1}g = e\) Where e is the identity action. Sometimes this is denoted by e , 1, or 0

\[\displaylines{ \begin{align*} r^{-1} &= r^{2} & \text{because } rr^{2} &= e = r^{2}r\\ f^{-1} &= f & \text{because } ff &= e = ff\\ (rf)^{-1} &= rf & \text{because } (rf)(rf) &= e = (rf)(rf)\\ (r^{2}f)^{-1} &= r^{2}f & \text{because } (r^{2}f)(r^{2}f) &= e = (r^{2}f)(r^{2}f)\\ \end{align*} }\]

Multiplication Tables and the Abelian Group

\(\displaylines{ \begin{array}{|c|c|c|c|c|} \hline & \color{yellow}e & \color{red}v & \color{blue}h & \color{green}r\\ \hline \color{yellow}e & \color{yellow}e & \color{red}v & \color{blue}h & \color{green}r\\ \hline \color{red}v & \color{red}v & \color{yellow}e & \color{green}r & \color{blue}h\\ \hline \color{blue}h & \color{blue}h & \color{green}r & \color{yellow}e & \color{red} v\\ \hline \color{green}r & \color{green}r & \color{blue}h & \color{red} v & \color{yellow} e\\ \hline \end{array} }\)

We can tell that a certain group is abelian if it’s multiplication table is symmetric about the main diagonal as the one above.

Compare this to a non-abelian group like D₃

\[D_{3} = \bigl \langle r,f \ \big |\ r^{3} = e,\ f^{2} = e,\ r^{2}f = fr\ \big \rangle\] \[\displaylines{ \begin{array}{|c|c|c|c|c|c|c|c|} \hline & \color{yellow}e & \color{red}r & \color{lime}r^{2} & \color{blue}f & \color{green}rf & \color{pink}r^{2}f \\ \hline \color{yellow}e & \color{yellow}e & \color{red}r & \color{lime}r^{2} & \color{blue}f & \color{green}rf & \color{pink}r^{2}f\\ \hline \color{red}r & \color{red}r & \color{lime}r^{2} & \color{yellow}e & \color{green}rf & \color{pink}r^{2}f & \color{blue}f\\ \hline \color{lime}r^{2} & \color{lime}r^{2} & \color{yellow}e & \color{red}r & \color{pink}r^{2}f & \color{blue}f & \color{green}rf\\ \hline \color{blue}f & \color{blue}f & \color{pink} r^{2}f & \color{green}rf & \color{yellow}e & \color{lime} r^{2} & \color{red} r\\ \hline \color{green}rf & \color{green}rf & \color{blue}f & \color{pink}r^{2}f & \color{red} r & \color{yellow}e & \color{lime} r^{2}\\ \hline \color{pink}r^{2}f & \color{pink}r^{2}f & \color{green}rf & \color{blue}f & \color{lime}r^{2} & \color{red} r & \color{yellow}e\\ \hline \end{array} }\]

Quaternion Group

\[\displaylines{ Q_{4} = \{\pm1,\ \pm i,\ \pm j,\ \pm k\}\\ }\]

The generators j and k individually act like \(\displaylines{ i = \sqrt{-1} }\) because \(i^{2} = j^{2} = k^{2} = -1\)

Multiplication of \(\{\pm i, \ \pm j, \ \pm k \}\) works like the cross product unit vectors in \(\mathbb{R}^3\)

\[ij = k, jk = i, ki = j, ji = -k, kj = -i, ik = -j\]

Representations

\[\displaylines{ \begin{array}{lll} Q_{4} &= \bigl \langle \ i, j, k \ &\bigl|& i^{2} = j^{2} = k^{2} = ijk = -1\ \bigr \rangle\\ \ &= \bigl \langle \ i, j \ &\bigl|& i^{-4} = j^{4} = 1, iji = j \bigr \rangle\\ \end{array} }\]

Group Theory

\(h \in V_{4}\) \(h\) is an element of the group V₄

Binary Operations

Operations are methods for combining objects. \(+,\ -,\ \times, \ and %\) are all examples of operations. They are referred to as binary operations because they combine two objects into a single object

If \(*\) is a binary operation on a set \(\mathcal{S}\) then \(s * t \in \mathcal{S}\) In this case, we say that \(S\) is closed under the operation \(*\)

Combinining or “multiplying” two group elements (i.e. doing one action followed by the other) is a binary operation. We say that it is a binary operation on the group.

Any sequence of actions is an action. This ensures that the group is closed under the binary operation of multiplication.

Multiplication tables are useful because they depict the grou’s binary operation in full but not every table with symbols in it is going to be the multiplication for a group.

Associative

Recall that an operation is associative if parentheses are permitted anywhere but are not required. Ordinary addition and multiplication are associative but subtraction of integers is not associative:

\[4 - (1 - 2) \ne (4 - 1) - 2\]

The operation of combining actions in a group is associative. We can recall \(D_{3}\) where \(rfr = (rf)r = r(fr)\)

Classical Definition

A set \(G\) is a group if the following criteria are satisfied:

1. There is a binary operation \(*\) on \(G\).

2. \(*\) is associative.

3. There has to be an identity element \(e \in G\) That is:

   \[\displaylines{ \begin{array}{cc} e * g = g = g * e & \forall \ g \in G\\ \end{array} }\]

4. Every element \(g \in G\) has an inverse, \(g^{-1}\) satisfying:

   \[g * g^{-1} = e = g^{-1} * g\]

• Depending on the context, the binary operation may be denoted by

\[\displaylines{ \times, \cdot, +, \text{ or } \circ }\]

• We generally only use the \(+\) symbol if the group is abelian. Thus \(g + h = h + g\) (always), but in general, \(gh \ne hg\)

• Uniqueness of the identity and inverses is not built into the definition of a group. However, we can without much trouble, prove these properties.

• Every element of a group has a unique inverse

  • Let \(g\) be an element of a group \(G\). By Definition, it has at least one inverse.
  • Suppose that \(h\) and \(k\) are both inverses of \(g\). This means that \(gh = hg =\) and \(gk = kg = e\). It suffices to show that \(h = k\). Indeed,
  \[h = he = h(gk) = (hg)k =ek = k\]

• Every group has a unique identity element. Suppose

  \[\displaylines{ \begin{align} G &= \bigl \langle \ e_1 \ \bigl | \ ge_1 = e_{1}g = g \bigr \rangle & \forall g \in G\\ &= \bigl \langle \ e_2 \ \bigl | \ ge_2 = e_{2}g = g \bigr \rangle & \forall g \in G\\ \end{align} }\]

Group Families

1. Cyclic Groups
2. Abelian Groups
3. Dihedral Groups
4. Symmetric Groups
5. Alternating Groups

A group is cyclic if it is generated by a single element. It is abelian if multiplication is commutative \(\displaylines{ \begin{array}{cc} a * b = b * a & \forall\ a, b \in G\\ \end{array} }\)

Cyclic Group

• A group is cyclic if it can be generated by a single element.

• Finite cyclic groups describe the symmetry of objects that have only rotational symmetry.

\[\displaylines{ C_n = \bigl \langle \ r \ \bigl | \ r^{n} = e \ \bigr \rangle }\]

• The generator would be a counterclockwise rotation a ‘click’ of \(\frac{2\pi}{n}\) where \(n\) is the number of “arms”

\[\displaylines{ C_{10} = \bigl \langle \ R \ \bigl | R^{10} = e \ \bigr\rangle\\ }\]

• The order of a group \(G\) is the number of distinct elements in \(G\) denoted by \(\lvert G \rvert\) which is its cardinality like a set using the absolute value sign.
• The cyclic group of order \(n\) (i.e. \(n\) rotations) is denoted \(C_n\) (or sometimes \(\mathbb{Z}_{n}\))
• The alternative notation \(\mathbb{Z}_{n}\) comes from the fact that the binary operation for \(C_{n}\) is just modular addition. To add two numbers in \(\mathbb{Z}_{n}\) add them as integers, divide by \(n\) and take the remainder \(\mod\ n\)
• For example, in \(\mathbb{Z}_{6} : \ 3 + 5 \equiv_{6} 2.\) “3 clicks + 5 clicks = 2 clicks”
• A common way to write elements in a cyclic group is with the integers \(0,1,2,\cdots,n - 1\) where
  • 0 is the identity
  • 1 is the single counterclockwise ‘click’
• Observe that the set \(\{0, 1,\cdots,n -1\}\) is closed under addition \(\mod n\) Meaning if we add \(\mod n\) any two numbers in this set, the result is another member of the set.
• In this setting, the cyclic group consists of the set \(\mathbb{Z}_{n} = \{0, 1,\cdots, n -1\}\) under the binary operation of \(+ \mod n\). The (additive) identity is \(0\).

Multiplicative Cyclic Groups

• If \(r\) is a generator representing \(\frac{2\pi}{n}\) then we can denote the \(n\) elements by:

  \[\mathcal{1,r,r^{2},\cdots,r^{n-1}}\]

• Think of \(r\) as the complex number \(e^{\frac{2\pi\ i}{n}}\) with the group operation being multiplication. \(C_n = n\)th roots of unity.

• Mathematica code to plot the \(nth\) roots of unity.

  rootPlot[equation_, variable_ : x, opts___] := 
   Module[{nSol, list}, nSol = NSolve[equation, variable]; 
    list = {Re[x], Im[x]} /. nSol;
    Return[ListPlot[list, PlotStyle -> PointSize[0.03], opts]];]
    
  rootPlot[x^(15) - 1 == 0, x, AspectRatio -> 1]
  

• Modular addition is apparent with \(r^{n} = 1,\ r^{n+1} = r,\ r^{n+2} = r^{2} \cdots\)

• The cyclic group can be thought of as the set \(C_{n} = \left\{ e^{\frac{2\pi \ i \ k}{n}} \ \bigr| \ k \in \mathbb{Z} \right\}\) under the binary operation of \(x\) With the (multiplicative) identity as \(1\)

• The unique infinite cyclic group (additively) is \((\mathbb{Z}, +)\) the integers under addition. The multiplicative notation is:

  \[\displaylines{ G = \bigl \langle \ r\ \bigl| \ \ \ \bigr\rangle = \bigl\{\ r^{k}\ :\ k \in \mathbb{Z} \ \bigr\} }\]

• For the infinite cyclic group \((\mathbb{Z}, +)\) only \(1\) or \(-1\) can be gnerators.

• Any number from \(\bigl\{0,1,\cdots,n-1\bigr\}\) that is relatively prime to \(n\) will generate \(\mathbb{Z}_{n}\)

  • 1 and 5 will generate \(\mathbb{Z}_{6}\) while \(1,2,3,\) and \(4\) all generate \(\mathbb{Z}_{5}\)

\[\displaylines{ \begin{array}{ccc} \mathbb{Z}_{6} = \bigl \langle 1 \bigr \rangle = \bigl \langle 5 \bigr \rangle & \mathbb{Z}_{5} = \bigl \langle 1 \bigr \rangle = \bigl \langle 2 \bigr \rangle = \bigl \langle 3 \bigr \rangle = \bigl \langle 4 \bigr \rangle & \mathbb{Z}_{10} = \bigl \langle 1 \bigr \rangle = \bigl \langle 2 \bigr \rangle = \bigl \langle 3 \bigr \rangle = \bigl \langle 7 \bigr \rangle = \bigl \langle 9 \bigr \rangle \end{array} }\]

• Modular addition multiplication table of cyclic groups

\[\displaylines{ \begin{array}{|c|c|c|c|c|c|} \hline & \color{red}0 & \color{yellow}1 & \color{lime}2 & \color{cyan}3 & \color{magenta}4 \\ \hline \color{red}0 & \color{red}0 &\color{yellow}1 & \color{lime}2 & \color{cyan}3 & \color{magenta}4 \\ \hline \color{yellow}1 &\color{yellow}1 & \color{lime}2 & \color{cyan}3 & \color{magenta}4 & \color{red}0\\ \hline \color{lime}2 & \color{lime}2 & \color{cyan}3 & \color{magenta}4 & \color{red}0 & \color{yellow}1\\ \hline \color{cyan}3 & \color{cyan}3 & \color{magenta}4 & \color{red}0 & \color{yellow}1 & \color{lime}2\\ \hline \color{magenta}4 & \color{magenta}4 & \color{red}0 &\color{yellow}1 & \color{lime}2 & \color{cyan}3 \\ \hline \end{array} }\]

• If the headings on the multiplication table are arranged in a natural order such as \((0,1,2,\cdots,n -1)\) or \((e,r,r^{2},\dots,r^{n-1})\) then each row is a cyclic shift to the left of the row above it.

• Cyclic groups play a fundamental role in other complicated groups. We refer them as the orbit of element \(r\). This includes 2 cycle orbits such as flipping.

• Every element in a group traces out an orbit.

  

  ​

\[\displaylines{ \begin{array}{|c|c|} \hline element & orbig\\ \hline e & \{e\}\\ \hline r & \{e,r,r^{2}\}\\ \hline r^{2} & \{e,r^2,r\}\\ \hline f & \{e,f\}\\ \hline rf & \{e,rf\}\\ \hline r^{2}f & \{e,r^{2}f\}\\ \hline \end{array} }\]

• The order of an element \(g \in G\) denoted \(\lvert g \rvert\) , is the size of its orbit. That is, \(\lvert g \rvert := \lvert \langle\ g \ \rangle \rvert\) (Recall that the order of \(G\) is defined to be \(\lvert G \rvert\))

• In general, the orbit of an element \(g\) is set:

\[\bigl \langle \ g\ \bigr \rangle := \bigl\{ \ g^{k}:\ k \in \mathbb{Z}\ \bigr\}\]

• The orbit of an element \(g\) is the collection of element that you can get to by doing \(g\) or its inverse any number of times.
• In any group \(G\) the orbit of an element \(g \in G\) is a cyclic group that “sits inside” \(G\). This is an example of a subgroup.

Abelian Groups

• A group where the order of actions is irrelevant due to them being commutative.

• A group \(G\) is abelian if \(ab = ba\) for all \(a,\ b \in G\).

• Cyclic groups are abelian. In a cyclic group \(\langle r \rangle\), every element can be written as \(r^{k}\) for some \(k\). Clearly, \(r^{k}r^{m} = r^{m}r^{k}\) for all \(k\) and \(m\).

• Not all abelian groups are cyclic (i.e. \(V_4\)).

• To check that a group \(G\) is abelian, it suffices to only check that \(ab = ba\) for all pairs of generators because it holds for all elements in the generators.

• \(C_4 \times C_2\) is an abelian group

  

• While the following \(D_4\) and \(Q_4\) are not

  

Dihedral Groups

• Dihedral groups are groups that describe the symmetry of regular n-gons

• Dihedral groups describe 2D objects that have rotational and reflective symmetry. The Dihedral group that describes the symmetries of a regular n-gon is written \(D_n\) or \(D_{2n}\).

• All actions of \(C_n\) are also actions of \(D_n\) but \(D_n\) have \(2n\) actions namely:

  • \(n\) rotations
  • \(n\) reflections

• Dihedral groups only need 2 generators such as:

  1. \(r =\) clockwise rotation by \(\frac{2\pi}{n} radians\) (a single ‘click’)
  2. \(f =\) flip (fix an axis of symmetry)

• These actions can be written as:

  \[\displaylines{ D_n = \bigl \{ \underbrace{e, r, r^2,\cdots,r^{n-1}}_\text{rotations}, \underbrace{ f,rf,r^2f,\cdots,r^{n-1}f }_\text{reflections}\bigr\}\\ }\]

• This is a possible presentation of \(D_n\)

  \[\displaylines{ D_n = \bigl \langle r,f \ \bigl| \ r^n = e, \ f^2 = e, \ rfr = f \bigr \rangle }\]

  

• There is a related infinite dihedral group \(D_\infty\) with presentation which is isomorphic to the previous freize group.

  \[\displaylines{ D_\infty = \bigl \langle r,f \ \bigl|\ f^2 = e, \ rfr = f \bigr \rangle }\]

  

• If \(s\) and \(t\) are two reflections of an n-gon across adjacent axes of symmetry (i.e. axes incident at \(\frac{\pi}{n} radians\)) then \(st\) is a rotation by \(\frac{2\pi}{n}\)

  

• To see an explicit example take \(s = rf\) and \(t = f\) in \(D_n\) where \(st = (rf)f = r\)

• Thus \(D_n\) can be generated by two reflections with the following presentation

  \[\displaylines{ \begin{align*} D_n & = \bigl \langle s, t \ \bigl|\ s^2 = e, \ t^2 = e, \ (st)^n = e \ \bigr \rangle\\ & = \bigl \{\underbrace{e, st, ts, (st)^2, (ts)^2}_\text{rotations},\cdots,\underbrace{s, sts, tst,\cdots}_\text{reflections} \bigr \}\\ \end{align*} }\]
• If \(n \ge 3\), then \(D_n\) is non-abelian, because \(rf \ne fr\). However, the following relations are very useful: \(rf = fr^{n-1}\), \(fr = r^{n-1}f\)
• The maximal orbits of \(D_n\) consist of:
  • \(1\) orbit of size \(n\) consisting of \(\{ e, r, \cdots, r^{n-1} \}\)
  • \(n\) orbits of size \(2\) consisting of \(\{ e, r^{k}f \}\) for \(k = 0, 1, \cdots, n -1\)
• Note that the size-\(n\) orbit may have smaller subsets that are orbits.
  • For example, \(\{e, r^{2}, r^{4}, \cdots, r^{n-2}\}\) and \(\{e, r^{\frac{n}{2}} \}\) are orbits if \(n \pmod 2 = 0\)

\[\displaylines{ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline & \color{red}e & \color{orange}r & \color{yellow}r^{2} & \color{lime}r^{3} & \color{green}f & \color{blue}rf & \color{magenta}r^{2}f & \color{pink}r^{3}f \\ \hline \color{red}e& \color{red}e & \color{orange}r & \color{yellow}r^{2} & \color{lime}r^{3} & \color{green}f & \color{blue}rf & \color{magenta}r^{2}f & \color{pink}r^{3}f \\ \hline \color{orange}r & \color{orange}r &\color{yellow}r^{2} & \color{lime}r^3 & \color{red}e & \color{blue}rf & \color{magenta}r^{2}f & \color{pink}r^{3}f & \color{green}f \\ \hline \color{yellow}r^{2} & \color{yellow}r^{2} & \color{lime}r^3 & \color{red}e & \color{orange}r & \color{magenta}r^{2}f & \color{pink}r^{3}f & \color{green}f & \color{blue}rf \\ \hline \color{lime}r^3 & \color{lime}r^3 & \color{red}e & \color{orange}r & \color{yellow}r^{2} & \color{pink}r^{3}f & \color{green}f & \color{blue}rf & \color{magenta}r^{2}f\\ \hline \color{green}f & \color{green}f & \color{pink}r^{3}f & \color{magenta}r^{2}f & \color{blue}rf & \color{red}e & \color{lime}r^3 & \color{yellow}r^{2} & \color{orange}r \\ \hline \color{blue}rf & \color{blue}rf & \color{green}f & \color{pink}r^{3}f & \color{magenta}r^{2}f & \color{orange}r & \color{red}e & \color{lime}r^3 & \color{yellow}r^{2}\\ \hline \color{magenta}r^{2}f & \color{magenta}r^{2}f & \color{blue}rf & \color{green}f & \color{pink}r^{3}f & \color{yellow}r^{2} & \color{orange}r & \color{red}e & \color{lime}r^3 \\ \hline \color{pink}r^{3}f & \color{pink}r^{3}f & \color{magenta}r^{2}f & \color{blue}rf & \color{green}f & \color{lime}r^3 & \color{yellow}r^{2} & \color{orange}r & \color{red}e \\ \hline \end{array} \\ \\ }\]

• We can observe that the we can divide the four quadrants of the multiplication table and see how it is divided into rotations and flips

\[\displaylines{ \begin{array}{|c|c|c|} \hline & \color{red}e & \color{orange}r & \color{yellow}r^{2} & \color{lime}r^{3} & \color{green}f & \color{blue}rf & \color{magenta}r^{2}f & \color{pink}r^{3}f \\ \hline \color{red}e & \text{rot} & \text{rot} & \text{rot} & \text{rot} & \text{flip} & \text{flip} & \text{flip} & \text{flip} \\ \hline \color{orange}r & \text{rot} & \text{rot} & \text{rot} & \text{rot} & \text{flip} & \text{flip} & \text{flip} & \text{flip} \\ \hline \color{yellow}r^{2} & \text{rot} & \text{rot} & \text{rot} & \text{rot} & \text{flip} & \text{flip} & \text{flip} & \text{flip} \\ \hline \color{lime}r^3 & \text{rot} & \text{rot} & \text{rot} & \text{rot} & \text{flip} & \text{flip} & \text{flip} & \text{flip} \\ \hline \color{green}f & \text{flip} & \text{flip} & \text{flip} & \text{flip} & \text{rot} & \text{rot} & \text{rot} & \text{rot} \\ \hline \color{blue}rf & \text{flip} & \text{flip} & \text{flip} & \text{flip} & \text{rot} & \text{rot} & \text{rot} & \text{rot} \\ \hline \color{magenta}r^{2}f & \text{flip} & \text{flip} & \text{flip} & \text{flip} & \text{rot} & \text{rot} & \text{rot} & \text{rot} \\ \hline \color{pink}r^{3}f & \text{flip} & \text{flip} & \text{flip} & \text{flip} & \text{rot} & \text{rot} & \text{rot} & \text{rot} \\ \hline \end{array} }\]

• The partition of \(D_n\) as depicted above forms the structure of the group \(C_2\). Shrinking a group this way is called taking a quotient

• Taking a quotient \(D_4\) maps it to \(C_2\) (\(\mathcal{O} :D_4 \mapsto C_2\))

  \[\displaylines{ \begin{array}{|c|c|c|} \hline & \color{red}e & \color{green}f \\ \hline \color{red}e & \color{red}e & \color{green}f \\ \hline \color{green}f & \color{green}f & \color{red}e \\ \hline \end{array} }\]

Symmetric Groups

• A permutation is an action that rearranges a collection of things. For example:

  stateDiagram-v2
    state A {
    direction LR
    state "1" as s1a
    state "2" as s2a
    state "3" as s3a
    state "4" as s4a
      s4a --> s1a
    s1a --> s2a
    s2a --> s3a
    s3a --> s4a
    
    }
    state B {
      direction LR
      state "1" as s1b
      state "2" as s2b
      state "3" as s3b
      state "4" as s4b
      s1b --> s2b
      s2b --> s1b
      s3b --> s4b
      s4b --> s3b
    }
    state C {
      direction LR
    state "1" as s1c
    state "2" as s2c
    state "3" as s3c
    state "4" as s4c
    s1c --> s3c
    s2c --> s4c
    s3c --> s1c
    s4c --> s2c
    }
    state D {
      direction LR
    state "1" as s1d
    state "2" as s2d
    state "3" as s3d
    state "4" as s4d
    s2d --> s3d
    s3d --> s2d
    s1d --> s1d
    s4d --> s4d
    }
    
  

• In order for the set of permutations for \(n\) objects to form a group we need to understand how to combine permutations. For example \(A \times B = C\)

    stateDiagram-v2
  	state A {
  	direction LR
  	state "1" as s1a
  	state "2" as s2a
  	state "3" as s3a
  	state "4" as s4a
  	s4a --> s1a
  	s1a --> s2a
  	s3a --> s4a
  	s2a --> s3a
  	}
  	state B {
  	direction LR
  	state "1" as s1b
  	state "2" as s2b
  	state "3" as s3b
  	state "4" as s4b
  	s1b --> s3b
  	s4b --> s2b
  	s3b --> s1b
  	s2b --> s4b
  	}
    state C {
    direction RL
    state "1" as s1e
    state "2" as s2e
    state "3" as s3e
    state "4" as s4e
    s1e --> s4e
    s4e --> s3e
    s3e --> s2e
    s2e --> s1e
    }
  

• There are \(n! = n(n-1)\cdots 3\cdot2\cdot1\) premutations of \(n\) items. For eample \(4! = 24\) permutation pictures on 4 objects. To verify this we just have to check the appropriate rules of one of our definitions of a group hold.

• To find the inverse of a permutation we just reverse the arrows such as:

  stateDiagram-v2
    state A {
    direction LR
  	state "1" as s1a
  	state "2" as s2a
  	state "3" as s3a
  	state "4" as s4a
  	s4a --> s1a
  	s1a --> s2a
  	s3a --> s4a
  	s2a --> s3a
    }
    state B {
    direction RL
    state "1" as s1e
    state "2" as s2e
    state "3" as s3e
    state "4" as s4e
    s1e --> s4e
    s4e --> s3e
    s3e --> s2e
    s2e --> s1e
    }
  

• The group of all permutations of \(n\) items is called the symmetric group (on \(n\) objects) and is denoted by \(\mathcal{S}_n\)

• Group \(\mathcal{S}_3\) is the same as the dihedral group \(D_3\) but this is the only time the symmetric group and dihedral grop coincide because \(3! = 6 = 2 \times 3 = 6\) but \(4! = 24 \gt 4\times 2 = 8\)

• Although the set of all permutations of \(n\) items forms a group, creating a group does not require all permutations.

• We can form groups by taking a subset of the permutations. For example, the cyclic group \(C_n\) and the dihedral group \(D_n\) can be both thought of groups of certain permutations \(\bigl\{1,\cdots,n\bigr\}\) becase they represent.

• We can use notation \((1\ 2\ 3\ 4)\)

• Every permutation can be decomposed into a product of disjount cycles.

• For example, in \(\mathcal{S}_{10}\) we can write the following as \(\color{#44B5FF}(1\ 4\ 6\ 5) \color{#FF4464}(2\ 3)\color{#43FF4F}(8\ 10\ 9)\)

  stateDiagram-v2
    direction RL
    state "2" as s2a
  	state "3" as s3a
  	direction LR
    
  	state "1" as s1a
    state "4" as s4a
  	state "5" as s5a
  	state "6" as s6a
    	
  	direction RL
    
      
      
  	state "7" as s7a
  	state "8" as s8a
  	state "9" as s9a
  	state "10" as s10a
    
    
    
  	s8a --> s10a
  	s10a --> s9a
  	s9a --> s8a
    s3a --> s2a
  	s2a --> s3a
  	s1a --> s4a
  	s4a --> s6a
  	s6a --> s5a
  	s5a --> s1a
    
  

• Disjoint cycles commute. For example: \(\color{#44B5FF}(1\ 4\ 6\ 5) \color{#FF4464}(2\ 3)\color{#43FF4F}(8\ 10\ 9) = \color{#FF4464}(2\ 3)\color{#43FF4F}(8\ 10\ 9) \color{#44B5FF}(1\ 4\ 6\ 5)\)

• Here is an example cycle notation for \(\mathcal{S}_4\) \(\color{#44B5FF}(1\ 2) \color{#FF4464}(3\ 4)\)

  stateDiagram-v2
    direction LR
    state "1" as s1a
    state "2" as s2a
    state "3" as s3a
    state "4" as s4a
    s1a --> s2a
    s2a --> s1a
    s3a --> s4a
    s4a --> s3a
  

• This is \(\color{#44B5FF}(2\ 3)\)

  stateDiagram-v2
    direction LR
    state "1" as s1d
    state "2" as s2d
    state "3" as s3d
    state "4" as s4d
    s2d --> s3d
    s3d --> s2d
  

• This is \(\color{#44B5FF}(1\ 3)\color{#FF4464}(2\ 4)\)

  stateDiagram-v2
  	direction TB
  	state "1" as s1b
  	state "2" as s2b
  	state "3" as s3b
  	state "4" as s4b
  	s1b --> s3b
  	s4b --> s2b
  	s3b --> s1b
  	s2b --> s4b
  

• This is \(\)\color{#44B5FF}(1\ 3\ 2)$$

   stateDiagram-v2
  	direction LR
  	state "1" as s1b
  	state "2" as s2b
  	state "3" as s3b
  	state "4" as s4b
  	s1b --> s3b
  	s3b --> s2b
  	s2b --> s1b

• It doesn’t matter where we start when writing the cycles.

\[\displaylines{ (1\ 3\ 2) = (3\ 2\ 1) = (2\ 1\ 3) = (1\ 2)(2\ 3) = (1\ 2)(2\ 3)(2\ 3)((2\ 3)\\ (1\ 2)(2\ 3) = (1\ 3\ 2) }\]

• We can write combined permutations as \((1\ 2\ 3\ 4) \cdot (1\ 3)(2\ 4) = (1\ 4\ 3\ 2)\)

  stateDiagram-v2
    state A {
    direction LR
    state "1" as s1a
    state "2" as s2a
    state "3" as s3a
    state "4" as s4a
    s4a --> s1a
    s1a --> s2a
    s3a --> s4a
    s2a --> s3a
    }
    state B {
    direction LR
    state "1" as s1b
    state "2" as s2b
    state "3" as s3b
    state "4" as s4b
    s1b --> s3b
    s4b --> s2b
    s3b --> s1b
    s2b --> s4b
    }
  state C {
  direction RL
  state "1" as s1e
  state "2" as s2e
  state "3" as s3e
  state "4" as s4e
  s1e --> s4e
  s4e --> s3e
  s3e --> s2e
  s2e --> s1e
  }
  

• \[(1\ 2\ 3)(2\ 3\ 4) = (1\ 3)(2\ 4)\]

Transpositions

• A transposition is a permutation that swaps two objects and fixes the rest, e.g.:

\[\displaylines{ 1 \ 2 \cdots i - 1 \\ i + 1 \cdots j - 1 \\ j + 1 \cdots n -1 n\\ (i\ j) }\]

• The group \(\mathcal{S}_n\) is generated by transpositions. This means that every permutation can be constructed by successively exchanging pairs of objects. If \(n\) people are standing in a row and we want to arrange them in some other order, we can do this by successively having pairs of people swap places.
• We only need adjacent transpositions to generate \(\mathcal{S}_n\):

\[\mathcal{S}_n = \bigl \langle (1\ 2), (2\ 3), \cdots,(n - 1\ n)\bigr \rangle\]

• The parity of the number of transpositions of a fixed permutation is unique. That means a fixed permutation can either be written with an even number of transpositions, or an odd number of transpositions but not both. This gives us a notion of even permutations and odd permutations

---