Groups HT23, Permutations

Created: February 24, 2023 | About these notes | View in context | Study these flashcards

Flashcards

How is the set of permutations of a set $S$ denoted?
\[\text{Sym}(S)\]

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?
\[\vert S _ n \vert \ge 3\]

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

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

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)}$?
\[\text{(b c a)}\]

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

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)}$?
\[3, 3, 2\]

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$?
\[\text{lcm}(l _ 1, \ldots, l _ k)\]

How many $5$-cycles are there in $S _ {11}$?
\[\frac{11 \times 10 \times 9 \times 8 \times 7}{5} = \frac{11!}{5 \times 6!}\]

How many $3,3,2$ cycles are there in $S _ {11}$?
\[\frac{8!}{3 \times 3 \times 2! \times 2}\]

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?
\[\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!)}\]

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?
\[\exists \rho \in S _ n \text{ s.t. } \sigma = \rho^{-1}\tau\rho\]

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\]

?
\[(\text{a}\rho\text{ b}\rho\text{ c}\rho \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?
\[\text{(1 6)(1 3)(1 2)(5 4)}\]

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$?
\[\vert A _ n \vert = \frac{1}{2}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$?
\[\delta _ {i\sigma j}\]

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.



Related posts