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.