2.4: Generating Sets

In this section, we explore the concept of a generating set for a group.

Definition: Word

Let \(G\) be a group and let \(S\) be a subset of \(G\). A finite product (under the operation of \(G\)) consisting of elements from \(S\) or their inverses is called a word in \(S\). That is, a word in \(S\) is of the form \[s_{x_1}s_{x_2}\cdots s_{x_n},\] where each \(s_{x_i}\) is either an element from \(S\) or the inverse of an element from \(S\). Each \(s_{x_i}\) is called a letter and the set \(S\) is called the alphabet. By convention, the identity of \(G\) can be represented by the empty word, which is the word having no letters. The set of elements of \(G\) that can be written as words in \(S\) is denoted by \(\langle S\rangle\) and is called the group generated by \(S\).

It is important to pay close attention to our notation. While \(S\) and \(\langle S\rangle\) are both sets, the latter set is the set of elements we can build using letters and their inverses from \(S\). It turns out that if \(S\) is itself a group, then \(S=\langle S\rangle\). Otherwise, \(S\) is a proper subset of \(\langle S\rangle\).

Example \(\PageIndex{1}\)

Suppose \(G\) is a group such that \(a,b,c\in G\) and let \(S=\{a,b,c\}\). Then \(ab\), \(c^{-1}acc\), and \(ab^{-1}caa^{-1}bc^{-1}\) are words in \(\langle S\rangle\). If any one of these words is not equal to \(a\), \(b\), or \(c\), then \(\langle S\rangle\) is strictly larger than \(S\).

It is worth mentioning that we are slightly abusing notation here. For nonempty \(S\subseteq G\), we can form infinitely many words in \(\langle S\rangle\), but often there are many words that represent the same group element. We can partition the collection of words in the alphabet \(S\) into equivalence classes based on which group element a word represents. Strictly speaking, each group element is an equivalence class of words. When we say two words are equal in the group, what we really mean is that both words are in the same equivalence class.

Theorem \(\PageIndex{1}\): Subgroup Generated by \(S\)

If \(G\) is a group under \(*\) and \(S\) is a subset of \(G\), then \(\langle S\rangle\) is also a group under \(*\).

Definition: 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\). In other words, \(S\) is a generating set of \(G\) if every element of \(G\) can be expressed as a word in \(S\). In this case, we say \(S\) generates \(G\). 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\).

A generating set for a group is analogous to a spanning set for a vector space and a minimal generating set for a group is analogous to a basis for a vector space.

If we know what the elements of \(S\) actually are, then we will list them inside the angle brackets without the set braces. For example, if \(S=\{a,b,c\}\), then we will write \(\langle a, b, c\rangle\) instead of \(\langle \{a,b,c\}\rangle\). In the special case when the generating set \(S\) consists of a single element, say \(g\), we have \[G=\langle g\rangle =\{g^k\mid k\in\mathbb{Z}\}\] and say that \(G\) is a cyclic group. As we shall see, \(\langle g\rangle\) may be finite or infinite.

Example \(\PageIndex{2}\)

In Section 2.1, we discovered that the set of spins is a non-minimal generating set for \(\text{Spin}_{3\times 3}\) while the set \(T=\{s_{11}, s_{12}, s_{23}, s_{36}, s_{56}, s_{45}, s_{47}, s_{78}, s_{89}\}\) is a minimal generating set.

Problem \(\PageIndex{1}\)

Consider the rotation group \(R_4\) that we introduced in Problem 2.2.4. Let \(r\) be the element of \(R_4\) that rotates the square by \(90^\circ\) clockwise.

1. Describe the action of \(r^{-1}\) on the square and express \(r^{-1}\) as a word using \(r\) only.
2. Prove that \(R_4=\langle r\rangle\) by writing every element of \(R_4\) as a word using \(r\) only.
3. Is \(\{r\}\) a minimal generating set for \(R_4\)?
4. Is \(R_4\) a cyclic group?

Problem \(\PageIndex{2}\): Revisiting \(D_3\)

Consider the dihedral group \(D_3\) introduced in Problem 2.2.5. To give us a common starting point, let’s assume the triangle and hole are positioned so that one of the tips of the triangle is pointed up. Let \(r\) be rotation by \(120^\circ\) in the clockwise direction and let \(s\) be the reflection in \(D_3\) that fixes the top of the triangle.

1. Describe the action of \(r^{-1}\) on the triangle and express \(r^{-1}\) as a word using \(r\) only.
2. Describe the action of \(s^{-1}\) on the triangle and express \(s^{-1}\) as a word using \(s\) only.
3. Prove that \(D_3=\langle r,s\rangle\) by writing every element of \(D_3\) as a word in \(r\) or \(s\).
4. Is \(\{r,s\}\) a minimal generating set for \(D_3\)?
5. Explain why there is no single generating set for \(D_3\) consisting of a single element. This proves that \(D_3\) is not cyclic.

It is important to point out that the fact that \(\{r,s\}\) is a minimal generating set for \(D_3\) does not imply that \(D_3\) is not a cyclic group. There are examples of cyclic groups that have minimal generating sets consisting of more than one element (see Problem 2.6.4).

Problem \(\PageIndex{3}\): Alternate \(D_3\)

Let’s consider the group \(D_3\) again. Let \(s\) be the same reflection as in Problem \(\PageIndex{2}\) and let \(s'\) be the reflection in \(D_3\) that fixes the bottom right corner of the triangle.

1. Express \(r\) as a word in \(s\) and \(s'\).
2. Use part (a) together with Problem \(\PageIndex{2}\) to prove that \(\langle s,s'\rangle=D_3\).

Problem \(\PageIndex{4}\): Revisiting \(D_4\)

Consider the dihedral group \(D_4\) introduced in Problem 2.2.6. Let \(r\) be clockwise rotation by \(90^\circ\) and let \(s\) be the reflection over the vertical midline of the square.

1. Describe the action of \(r^{-1}\) on the square and express \(r^{-1}\) as a word using \(r\) only.
2. Describe the action of \(s^{-1}\) on the square and express \(s^{-1}\) as a word using \(s\) only.
3. Prove that \(\{r,s\}\) is generating set for \(D_4\).
4. Is \(\{r,s\}\) a minimal generating set for \(D_4\)?
5. Find a different generating set for \(D_4\).
6. Is \(D_4\) a cyclic group?

Problem \(\PageIndex{5}\): Revisiting \(S_3\)

Consider the symmetric group \(S_3\) that was introduced in Problem 2.2.7. Let \(s_1\) be the action that swaps the positions of the first and second coins and let \(s_2\) be the action that swaps the positions of the second and third coins. Prove that \(S_3=\langle s_1, s_2\rangle\).

Problem \(\PageIndex{6}\): Revisiting \(S_3\)

Find a minimal generating set for \((\mathbb{Z},+)\). Is \(\mathbb{Z}\) a cyclic group under addition?