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} \)