Groups and Generators

Groups, subgroups, and sets

$G(\times )$: a group with operation $\times$.

$H\le 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$.

$⟨S⟩=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,\dots ,m_l\}$.

Remove $m_i$ then $|⟨M⟩|\ge 2|⟨M\setminus \{m_i\}⟩|$.

Permutation matrices

Assume $n\ge 3$.

For $S_n$, one $M=\{(12),(123\dots n)\}$.

For $S_4$, $(12)$ is:

$\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]$

and $(1234)$ is:

$\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]$

Then, for instance, $(134)$ is:

$(134)=(12)(1234)=$

$\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]$$\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]=$$\left[\begin{array}{cccc}0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]$