Groups and Generators

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} $