## 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, ∃ ι ∈ G s.t. ∀ x ∈ G, x · ι = ι · x = x, ∀ x ∈ G, ∃ x-1 ∈ G s.t. x · x-1 = x-1 · x = ι, ∀ 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 = ( 1 2 3 4 5 6 ) --input or p = [2 3 1 4 6 5], 2 3 1 4 6 5 --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 #ad:
 The C++ Cookbook mastering the language
 ↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated). Created with "vi (Linux)",  charset=iso-8859-1,   fetched Sunday, 16-Jun-2024 06:35:37 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.