Groups

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 h₁ = g h₂ ⇔ h₁ = h₂

k ∈ xH ∩ yH ⇒ xH = yH :

must have, k = x h₁ = y h₂,

so x = y h₂ h₁^-1,

so xH = y h₂ h₁^-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, {g₀, ..., g_m-1}. A permutation, p, is a member of G if and only if p can be expressed as a product of generators.

 

S_n, the symmetric group_n, is the group of all permutations of {1, ..., n}. S_n has n! members.

S_n 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.

 

A_n, the alternating group_n, is the group of all the even permutations of {1, ..., n}. A_n has n!/2 members.

 

Dih_n, the dihedral group_n, is the group of symmetries of a polygon with n vertices. Dih_n has 2n members.

Dih_n 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 = G₀ ≥ G₁ ≥ G₂ ≥ ... ≥ G_n-1 = G_n = {ι},

where G_i pointwise stabilises (fixes) {1, ..., i} (that is, g∈G_i & 1≤m≤i ⇒ g(m)=m).

Membership test.

For i = 1, ..., n, choose a representative of each coset of G_i in G_i-1 (choose the identity, ι, for G_i itself).

g is a member of G iff g can be expressed as a product of coset representatives, one for each G_i in G_i-1, i = 1, ..., n: move '1' to g(1), then move '2' to g(2), and so on. If successful, the expression is unique.

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(n³)-space, built in O(n⁶)-time (p.38).

 

M. Jerrum, A compact representation for permutation groups, J. of Algorithms, 7, pp.60-78, 1986.

Reduced O(n²)-space complexity, built in O(n⁵)-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.