Groups

LA home
Computing
Algorithms
 glossary
 Groups
  #demo

also see
maths
A group, G, is a set with a binary operator, ‘·’, such that (s.t.)
closure ∀ x & y ∈ G, x · y ∈ G,
identity ∃ ι ∈ G s.t. ∀ x ∈ G, x · ι = ι · x = x,
inverse  ∀ x ∈ G, ∃ x-1 ∈ G s.t. x · x-1 = x-1 · x = ι,
associativity  ∀ x, y & z ∈ G, (x · y) · z = x · (y · z).
 
(If,  ∀ x & y ∈ G, x · y = y · x,  then G is said to be abelian; not all groups are abelian.)
 
Examples:
The integers, Z, with addition as the operator.
The positive (>0) rational numbers, with multiplication as the operator.
The non-zero rational numbers, with multiplication as the operator.
The permutations of a finite set, taken as mappings, and with composition as the operator.
The automorphisms (symmetries) of a graph.
 
Notation: We often write 'xy' for 'x · y' when convenient.
 
H is a subgroup of G, H ≤ G, iff H ⊆ G as a set, and H is a group (with the same operator as G).
 
For g ∈ G, and H a subgroup of G,
gH = {g · h | h ∈ H} is a left-coset of H, and
Hg = {h · g | h ∈ H} is a right-coset of H.
Left-cosets partition G (ditto right-) :
|gH| = |H| :
g h1 = g h2 ⇔ h1 = h2
k ∈ xH ∩ yH ⇒ xH = yH :
must have, k = x h1 = y h2,
so x = y h2 h1-1,
so xH = y h2 h1-1 H = yH.
Either xH = yH, or xH ∩ yH = ∅.
It also follows that |H| divides |G|.
 
If gH = Hg, ∀g ∈G, H is said to be a normal subgroup of G.

Permutations

A permutation, p, over {1,...,n}, can be thought of as a mapping (function) on {1,...,n}, e.g.,
p = ( 123456 )   --input   or p = [2 3 1 4 6 5],
231465   --output
p(1)=2, p(2)=3, etc., and
inverse(p) = [3 1 2 4 6 5].
(There is also a cycle notation, e.g., p = (1 2 3)(4)(5 6) meaning 1→2→3→1, 4→4, and 5→6→5.)
The natural group operation is function-composition.
 
A (permutation) group, G, can be specified by a set of generators, {g0, ..., gm-1}. A permutation, p, is a member of G if and only if p can be expressed as a product of generators.
 
Sn, the symmetric groupn, is the group of all permutations of {1, ..., n}. Sn has n! members.
Sn is, for example, generated by the set of n-1 transposition {[2, 1, 3, 4, ..., n], [1, 3, 2, 4, ..., n], [1, 2, 4, 3, ..., n], ... [1, 2, ..., n, n-1]},
or by an n-cycle and a transposition, {[2, ..., n, 1], [2, 1, 3, ..., n]}, say.
 
An, the alternating groupn, is the group of all the even permutations of {1, ..., n}. An has n!/2 members.
 
Dihn, the dihedral groupn, is the group of symmetries of a polygon with n vertices. Dihn has 2n members.
Dihn is, for example, generated by a unit rotation, [2, 3, ..., n, 1], plus a reflection, [n, n-1, ..., 2, 1].  
 
Given a permutation group, G, on {1, ..., n}, there is a natural chain of subgroups,
G = G0 ≥ G1 ≥ G2 ≥ ... ≥ Gn-1 = Gn = {ι},
where Gi pointwise stabilises (fixes) {1, ..., i} (that is, g∈Gi & 1≤m≤i ⇒ g(m)=m).
Membership test.
For i = 1, ..., n, choose a representative of each coset of Gi in Gi-1 (choose the identity, ι, for Gi itself).
g is a member of G iff g can be expressed as a product of coset representatives, one for each Gi in Gi-1, i = 1, ..., n: move '1' to g(1), then move '2' to g(2), and so on. If successful, the expression is unique.
Beware, there are no data validity checks in the FORM:
--generators
--perm
--output
Row i in the table above gives coset representatives of Gi in Gi-1.

Reading

M. Furst, J. Hopcroft & E. Luks, Polynomial time algorithms for permutation groups, Proc. 21st Annual Symp. on the Foundations of Comp. Sci., pp.36-41, 1980.
Data-structure O(n3)-space, built in O(n6)-time (p.38).
 
M. Jerrum, A compact representation for permutation groups, J. of Algorithms, 7, pp.60-78, 1986.
Reduced O(n2)-space complexity, built in O(n5)-time.
 
C. C. Sims. Computation with permutation groups, Proc. 2nd Symposium on Symbolic and Algebraic Manipulation, pp.23-28, 1971.
 
J. A. Todd & H. S. M. Coxeter, A practical method for enumerating cosets of a finite abstract group, Proc. Edinb. Math. Soc., II., Ser. 5, pp.26-34, 1936.
www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Tuesday, 19-Sep-2017 14:56:38 EDT.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.