Groups

Set of permutation matrices

$P$: $n \times n$ permutation matrix.

$S_n = \{ P \}$: set of all permutation matrices.

Operations

$ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $ $ \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{bmatrix}= $ $\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix} $

$ P_1 \times P_2$: matrix multiplication is a binary operation.

$ P_1 \times P_2$ is another permutation matrix - $ S_n $ is closed.

$ I $: the identity matrix is a permutation matrix.

$ (A \times B) \times C = A \times (B \times C)$: matrix multiplication is associative.

$ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $$ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}= $$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $

$ P^{-1} $: inverse permutation.

$ \{ P \} $ is a group under matrix multiplication.

Subgroups

$ \{ Q \} \subseteq \{ P \} $: subset.

Some subsets are closed themselves and contain the identity.

Such subsets are called subgroups.

Subgroups contain the inverses of all their elements.

Some (most) subsets are not subgroups.

Order

$ n! $: number of permuations of $n$ elements.

$ n! $: number of $n \times n$ permutation matrices.