Generating set of a group

From Example Problems
Jump to navigation Jump to search

In abstract algebra, a generating set of a group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses.

More generally, if S is a subset of a group G, then <S>, the subgroup generated by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} , is the smallest subgroup of G containing every element of S; equivalently, <S> is the subgroup of all elements of G that can be expressed as the finite product of elements in S and their inverses.

If G = <S>, then we say S generates G; and the elements in S are called generators or group generators. If S is the empty set, then <S> is the trivial group {e}, since we consider the empty product to be the identity.

When there is only a single element x in S, <S> is usually written as <x>. In this case, <x> is the cyclic subgroup of the powers of x, a cyclic group, and we say this group is generated by x. Equivalent to saying an element x generates a group is saying that it has order |G|, or that <x> equals the entire group G.

If S is finite, then a group G = <S> is called finitely generated. The structure of finitely generated abelian groups in particular is easily described. Many theorems that are true for finitely generated groups fail for groups in general.

Every finite group is finitely generated since <G> = G. The integers under addition are an example of an infinite group which is finitely generated by both <1> and <−1>, but the group of rationals under addition cannot be finitely generated. No uncountable group can be finitely generated.

Different subsets of the same group can be generating subsets; for example, if p and q are integers with gcd(pq) = 1, then <{pq}> also generates the group of integers under addition.

The most general group generated by a set S is the group freely generated by S. Every group generated by S is isomorphic to a factor group of this group, a feature which is utilized in the expression of a group's presentation.

An interesting companion topic is that of non-generators. An element x of the group G is a non-generator if every set S containing x that generates G, still generates G when x is removed from S. In the integers with addition, the only non-generator is 0. The set of all non-generators forms a subgroup of G, the Frattini subgroup.

Examples

The group of units U(Z9) is the group of all integers relatively prime to 9 under multiplication mod 9 (U9 ={1,2,4,5,7,8}). All arithmetic here is done modulo 9. Seven is not a generator of U(Z9), since

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{7^i\pmod{9}\ |\ i \in \mathbb{N}\} = \{7,4,1\}.}

while 2 is, since:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{2^i\pmod{9}\ |\ i \in \mathbb{N}\} = \{2,4,8,7,5,1\}.}

On the other hand, the symmetric group of size n is not cyclic, so it is not generated by any one element. However, it is generated by the two permutations (1 2) and (1 2 3 ... n). For example, for S3 we have:

e = (1 2)(1 2)
(1 2) = (1 2)
(2 3) = (1 2)(1 2 3)
(1 3) = (1 2 3)(1 2)
(1 2 3) = (1 2 3)
(1 3 2) = (1 2)(1 2 3)(1 2)

Infinite sets can also have finite generating sets. The additive group of integers has 1 as a generating set. The element 2 is not a generating set, as the odd numbers will be missing. The two-element subset {3, 5} is a generating set, since (-5) + 3 + 3 = 1.

See also

External links

sl:generator