Schreier's subgroup lemma

Schreier's subgroup lemma

Schreier's subgroup lemma is a theorem in group theory used in the Schreier-Sims algorithm and also for finding a presentation of a subgroup.

Suppose H is a subgroup of G, which is finitely generated with generating set S, that is, "G" = <"S">. Let R be a right transversal of H in G.

We make the definition that given g&isin;G, overline{g} is the chosen representative in the transversal R of the coset Hg, that is, :gin Hoverline{g}

Then H is generated by the set:{rs(overline{rs})^{-1}|rin R, sin S}

Example

Let us establish the evident fact that the group Z3=Z/3Z is indeed cyclic. Via Cayley's theorem, Z3 is a subgroup of the symmetric group "S"3. Now,: Bbb{Z}_3={ e, (1 2 3), (1 3 2) }: S_3={ e, (1 2), (1 3), (2 3), (1 2 3), (1 3 2) }where e is the identity permutation. Note "S"3 = < { "s"1=(1 2), "s"2=(1 2 3) } >.

Calculating the cosets of Z3 in "S"3, we have: (1 2)Bbb{Z}_3 = S_3setminusBbb{Z}_3 = { (1 2), (1 3), (2 3) }: (1 3)Bbb{Z}_3 = S_3setminusBbb{Z}_3 = { (1 2), (1 3), (2 3) }: (2 3)Bbb{Z}_3 = S_3setminusBbb{Z}_3 = { (1 2), (1 3), (2 3) }

: eBbb{Z}_3 = Bbb{Z}_3: (1 2 3)Bbb{Z}_3 = Bbb{Z}_3: (1 3 2)Bbb{Z}_3 = Bbb{Z}_3

So, we can select a transversal { "t"1="e", "t"2=(1 2) }, and we have : egin{matrix}t_1s_1 = (1 2),&quadmathrm{so}quad&overline{t_1s_1} = (1 2)\t_1s_2 = (1 2 3) ,&quadmathrm{so}quad& overline{t_1s_2} = e\t_2s_1 = e ,&quadmathrm{so}quad& overline{t_2s_1} = e\t_2s_2 = (2 3) ,&quadmathrm{so}quad& overline{t_2s_2} = (1 2) \end{matrix}

Finally, : t_1s_1overline{t_1s_1}^{-1} = e: t_1s_2overline{t_1s_2}^{-1} = (1 3 2): t_2s_1overline{t_2s_1}^{-1} = e : t_2s_2overline{t_2s_2}^{-1} = (1 3 2)

Thus, by Schreier's subgroup lemma, { e, (1 3 2) } generates Z3, but having the identity in the generating set is redundant, so we can remove it to obtain another generating set for Z3, { (1 3 2) } (as expected).

References

* Seress, A. Permutation Group Algorithms. Cambridge University Press, 2002.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Schreier-Sims algorithm — The Schreier Sims algorithm is an efficient method of computing a base and strong generating set (BSGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS …   Wikipedia

  • Nielsen–Schreier theorem — In group theory, a branch of mathematics, the Nielsen–Schreier theorem is the statement that every subgroup of a free group is itself free.[1][2][3] It is named after Jakob Nielsen and Otto Schreier. Contents …   Wikipedia

  • Otto Schreier — (March 3, 1901 in Vienna, Austria – June 2, 1929 in Hamburg, Germany) was an Austrian mathematician who made major contributions in combinatorial group theory and in the topology of Lie groups. He studied mathematics at the University of Vienna… …   Wikipedia

  • Zassenhaus lemma — In mathematics, the butterfly lemma or Zassenhaus lemma, named after Hans Julius Zassenhaus, is a technical result on the lattice of subgroups of a group. Lemma: Suppose (G, Omega) is a group with operators and A and C are subgroups. Suppose:B… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • List of group theory topics — Contents 1 Structures and operations 2 Basic properties of groups 2.1 Group homomorphisms 3 Basic types of groups …   Wikipedia

  • List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

  • Isomorphism theorem — In mathematics, specifically abstract algebra, the isomorphism theorems are three theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules,… …   Wikipedia

  • Free abelian group — In abstract algebra, a free abelian group is an abelian group that has a basis in the sense that every element of the group can be written in one and only one way as a finite linear combination of elements of the basis, with integer coefficients …   Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”