Groups, subgroups, and sets
$G(\times)$: a group with operation $\times$.
$H \leq G$: $H$ is a subgroup of $G$ under induced $\times$.
$S \subseteq G$: $S$ is a subset of $G$.
Generating set
Generating set iff every element of $G$ is a product of elements in $S$.
$\langle S \rangle = G$.
Minimal generating set
$M$: generating set with minimum number of elements for $|G| = n$.
$\log_2 n$: upper bound on $|M|$.
Group identity is never in $M$.
Suppose $M = \{ m_1, m_2, \ldots, m_l \}$.
Remove $m_i$ then $|\langle M \rangle | \geq 2 |\langle M \setminus \{ m_i \} \rangle |$.
Permutation matrices
Assume $n \geq 3$.
For $S_n$, one $ M=\{ (1\ 2) , (1 \ 2 \ 3 \ \ldots n) \}$.
For $S_4$, $(1\ 2)$ is:
$ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $
and $(1 \ 2 \ 3 \ 4)$ is:
$ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix} $
Then, for instance, $(1 \ 3 \ 4)$ is:
$ (1 \ 3 \ 4) = (1 \ 2)(1 \ 2 \ 3 \ 4) = $
$ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $$ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix}= $$ \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix} $