Minimal generating set
I am having a difficult time wrapping my head around this idea of minimal generating set. The book gives a definition for it and i've tried looking it up but the definitions are obviously similar. Can someone break it down to simpler terms and provide a basic example?
Here is my books def.
Generating Set: If $G$ is a group and $S$ is a subset of $G$ such that $G=\langle S\rangle$, then $S$ is called a generating set of $G$.
Minimal Generating Set: A generating set $S$ for $G$ is a minimal generating set if $S\setminus\{x\}$ is no longer a generating set for $G$ for all $x\in S$.
$\endgroup$ 23 Answers
$\begingroup$You can think about it as the idea from linear algebra of a basis for a space compared to a set of vectors which span the space.
A basis is a set of linearly independent elements, where removing one of the elements would result in it being unable to generate every element in that space.
In other words, you can think of a minimal generating set as a basis for the group, which has no redundant elements while a generating set may have redundant elements.
For example, to generate $\mathbb R^3$ we have a basis $\begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix}, \begin{bmatrix}0\\0\\1\end{bmatrix}$ (a minimal generating set), but this space is still generated by the set of vectors $\begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix}, \begin{bmatrix}0\\0\\1\end{bmatrix}, \begin{bmatrix}0\\0\\3\end{bmatrix}$ (a generating set).
$\endgroup$ 3 $\begingroup$For example $\{6,10\}$ is a generating set for the group $2\Bbb Z$ of even integers under addition. In other words, every even integer $n\in 2\Bbb Z$ can be written as a couple of $6$'s and $10$'s (or their additive inverses) added together, i.e., $n=6a+10b$ for some integers $a,b\in\Bbb Z$. Note that $\{6,10\}$ is also a minimal generating system for $2\Bbb Z$ because after removing any of its elements, the rest will not generate the whole group. Indeed, $10\notin \langle 6\rangle =6\Bbb Z$ and $6\notin \langle 10\rangle =10\Bbb Z$. In fact $2$ is in neither.
$\endgroup$ 3 $\begingroup$A generating set captures the idea that starting with only a few elements of the group and then applying the group operation can be enough to (eventually) create, or generate, every element of the group.
Minimality in mathematics is the property of being as small as possible. There is no other thing of the category or description that does what it should and is also smaller than the one you have. Note that this doesn't exclude the possibility for multiple minimal objects of the same size, that is, minimality is not necessarily unique.
A minimal generating set according to the definition provided is thus a set of elements of the group that can be used to eventually form the whole group, but, if even one of those elements is missing, loses that ability.
Note that often a minimal object is the absolute smallest possible object meeting that description. For example, while $\{4,3\}$ is a generating set for $\Bbb{Z}_6$ under addition and removal of either element leaves a non-generating set, there is already a smaller generating set: $\{1\}$.
Because this can cause confusion due to different ideas about what "is allowed to be" minimal, a set with some defined desired property for which the removal of any element also removes the desired property, may instead be called a critical set instead, to avoid ambiguity. Your definition of a minimal generating set should rather be applied to a critical generating set, with minimality reserved for only the smallest possible case(s). To continue with the same example, the set $\{3,4\}$ is a critical generating set, while $\{1\}$ and $\{5\}$ are true minimal generating sets.
$\endgroup$ 1
