## Groups

**Please turn javascript on.**

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 h
_{1}= g h_{2}⇔ h_{1}= h_{2}

- g h
- k ∈ xH ∩ yH ⇒ xH = yH :
- must have, k = x h
_{1}= y h_{2}, - so x = y h
_{2}h_{1}^{-1}, - so xH = y h
_{2}h_{1}^{-1}H = yH.

- must have, k = x h
- 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_{0}, ..., 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
_{0}≥ G_{1}≥ G_{2}≥ ... ≥ 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.

#### -- Needs JavaScript on --

_{i}in G

_{i-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(n
^{3})-space, built in O(n^{6})-time (p.38). - M. Jerrum,
*A compact representation for permutation groups*, J. of Algorithms, 7, pp.60-78,**1986**. - Reduced O(n
^{2})-space complexity, built in O(n^{5})-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**.

**Please turn javascript on.**