# Notes - Groups HT23, Permutations

### Flashcards

How is the set of permutations of a set $S$ denoted?

Given any set $S$, what is the symmetry group of $S$?

The group $(\text{Sym}(S), \circ)$, i.e. permutations of $S$ under composition.

What is the $n$-th symmetric group $S _ n$?

The group $(\text{Sym}(\{1, \ldots, n\}), \circ)$.

What are the conditions for the $n$-th symmetric group $S _ n$ to be non-abelian?

Say $\sigma, \tau \in S _ n$. How would you write $\tau(\sigma(k))$ in shorthand notation?

Say $\sigma, \tau \in S _ n$. What does the notation $k \sigma \tau$ represent?

Can you state the definition of $\sigma \in S _ n$ being a cycle?

There are distinct elements $a _ 1, a _ 2, \ldots, a _ k$ in $\{1, 2, \ldots, n\}$ such that $a _ i \sigma = a _ {i+1}$ for $1 \le i < k$ and $a _ k \sigma = a _ 1$.

What is an equivalent cycle to $\text{(a b c)}$?

What does it mean for two cycles $(a _ 1 \ldots a _ k)$ and $(b _ 1 \ldots b _ k)$ to be disjoint?

How can you “decompose” any permutation?

Into a product of disjoint cycles.

Decomposing a permutation into a product of disjoint cycles is unique to an extent. What can change?

- The cycling of elements in cycles
- Permuting the order of the cycles

What is the cycle type of $\text{(1 2 3)(4)(5 6)(7 8 9)}$?

Let $\sigma = \rho _ 1 \cdots \rho _ k$ be an expression for $\sigma$ as disjoint cycles of lengths $l _ 1, \ldots, l _ k$. Then what is the order of $\sigma$?

How many $5$-cycles are there in $S _ {11}$?

How many $3,3,2$ cycles are there in $S _ {11}$?

Say you have a permutation in $S _ n$ that is the product of:

- $k _ 1$ cycles of length $l _ 1$
- $k _ 2$ cycles of length $l _ 2$
- …
- $k _ n$ cycles of length $l _ n$

How many possibilities for this permutation are there?

Can you state the formal definition of what it means for two permutations $\sigma, \tau \in S _ n$ to be conjugate and then what this actually translates to?

Being conjugate means they represent the same permutation where we ignore how the elements are labelled.

If $\sigma, \tau \in S _ n$ are two conjugate transformations, i.e. $\exists \rho \in S _ n$ such that $\sigma = \rho^{-1} \tau \rho$, then what is true about their cycle types?

The cycle types are equal.

What is

\[\rho^{-1} \text{(a b c} \cdots \text{f)} \rho\]
?

What is a transposition?

A permutation that is a $2$-cycle.

What does it mean for a permutation to be odd/even?

It can be written as an odd/even number of transpositions.

How could you write the permutation $\text{(1 6 3 2)(5 4)}$ as a product of transpositions?

What is the subgroup of $S _ n$ consisting of all even permutations called?

The alternating group $A _ n \leqslant S _ n$.

What is the order of the alternating group $A _ n$?

Where is the entry containing a $1$ in row $i$ for a permutation matrix $P _ \sigma$?

In column $i\sigma$.

In terms of the Kronecker delta $\delta$, what’s the $(i, j)$-th entry of the permutation matrix $P _ \sigma$?

When proving that two permutations $\sigma, \tau \in S _ n$ are conjugate, i.e. $\exists \rho \in S _ n$ such that $\sigma = \rho^{-1} \tau \rho$ if and only if they have the same cycle type, how do you notate $\tau$ in terms of its disjoint cycles when proving the forward direction?

Let $\tau = \psi _ 1 \psi _ 2 \cdots \psi _ r$ where each $\psi _ i$ are the disjoint cycles and then consider

\[\sigma = \rho^{-1} (\psi_1 \psi_2 \cdots \psi_r) \rho\]When proving that two permutations $\sigma, \tau \in S _ n$ are conjugate, i.e. $\exists \rho \in S _ n$ such that $\sigma = \rho^{-1} \tau \rho$ if and only if they have the same cycle type, how do you get started?

Line up $\tau$ and $\sigma$ so their cycles match and work out the $\rho$ that goes between them

\[\begin{aligned} \tau &= &(a_1 a_2 \cdots a_m)&&(b_1 b_2 \cdots b_n) &&(c_1 c_2 \cdots c_p) \cdots \\\\ \sigma &= &(\alpha_1 \alpha_2 \cdots \alpha_m) &&(\beta_1 \beta_2 \cdots \beta_n) &&(\gamma_1 \gamma_2 \cdots \gamma_p) \cdots \\\\ \end{aligned}\]### Proofs

Prove that disjoint cycles commute.

Todo.

Prove that every permutation $g \in S _ n$ can be written as a product of disjoint cycle.

Todo.

Let $\sigma = \rho _ 1 \cdots \rho _ k$ be an expression for $\sigma$ as disjoint cycles of lengths $l _ 1, \ldots, l _ k$. Prove that the order of $\sigma$ is given by the expression $\text{lcm}(l _ 1, \ldots, l _ k)$

Todo.

Say you have a permutation in $S _ n$ that is the product of:

- $k _ 1$ cycles of length $l _ 1$
- $k _ 2$ cycles of length $l _ 2$
- …
- $k _ n$ cycles of length $l _ n$
Prove that the number of possibilities is given by:

\[\frac{n!}{(l_1^{k_1} \times l_2^{k_2} \times \cdots \times l_n^{k_n}) (k_1 ! \times k_2! \times \cdots \times k_n!)}\]

Todo.

Prove that two permutations $\sigma, \tau \in S _ n$ are conjugate, i.e. $\exists \rho \in S _ n$ such that $\sigma = \rho^{-1} \tau \rho$ if and only if they have the same cycle type.

Todo.

Prove that any permutation $\sigma \in S _ n$ can be written as a product of transpositions.

Todo.

Prove that no permutation $\sigma \in S _ n$ can be both odd and even at the same time, i.e. it can’t be equal to a product of an even number of transpositions and a product of an odd number of transpositions.

Todo.