Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

(Prof. Dr. Thomas Beth, Dr. Markus Grassl)

2. Vorlesung: Bahnen und Transversalen

• Bahn eines Elements m der Menge M
  • Graph mit Gruppenelementen als gerichtete Kanten, Elemente der Menge M als Knoten
  • Berechnung der Bahn via Breitensuche
  • Schreiervektor:
    Spannbaum im Graph der Bahn
  • Test, ob m₁ in der Bahn von m liegt
  • Berechnung eines Elementes g mit m^g=m₁
• Transversale T:
  • Vertretersystem der Nebenklassen einer Untergruppe H in G mit
    
    1. nur das neutrale Element liegt im Schnitt von G und H
    2. G=H*T (als Mengen)
    3. |T|=[G:H]=|G|/|H|
  • Projektion τ von G auf T mit
    1. Hg=Hτ(g)
    2. τ(g)=id für Elemente g aus H
  • Berechnung von τ(g) via Schreiervektor
• Satz von Schreier:
  Es seien S eine Menge von Erzeugern der Gruppe G sowie T eine (Rechts-)Transversale einer Untergruppe H von G mit zugehöriger Projektion τ.
  Dann wird die Untergruppe H erzeugt von den Elementen tsτ(ts)^-1 für Elemente t aus T und s aus S.