Previous: FunctionsFunctions Up: Class notesClass notes
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.

Groups and other algebraic structures



Chapter 1  Groups, and other algebraic structures (section 8.1)

1.1  Introduction

A mathematical structure is a formal model which capture common properties or behavior of different sets.

It consists of an abstract set, together with operations and relations which obey certain rules.

For example the set of tasks to build a house, and the set of all courses available at CSM have something in common: the notion of prerequisite. This notion can be formalized using a structure of partially ordered set.

We will introduce here certain algebraic structures, which are useful to model arithmetic, as well as to the study of symmetries.

1.2  Permutations


Définition 1   Let A be a set. A permutation of A is a bijection from A to A.

Let SA be the set of all permutations of A.

Let Sn be the set of all permutations of {1,... n}.
A permutation sigma of Sn can be written in array form as follow:
sigma:= (
(
1 2 3 4 5 6
2 1 4 5 3 6
)
)		 ,

meaning that sigma(1)=2, sigma(2)=1, sigma(3)=4, and so on.
Exercice 1   Write all permutations in S1, S2, and S3.

What is the size of Sn?

1.2.1  Operation on Sn

Sn as a set is not very interesting.

Can we define operations on Sn?
Proposition 1   The composition ¤is an operation of Sn.
Indeed, the composition of two permutations is still a permutation.

We also call this operation product of permutations.
Exercice 2   Compute the following:
(
(
1 2 3 4 5 6
2 5 1 6 3 4
)
)
-1

 
= (
1 2 3 4 5 6
)
(
(
1 2 3 4 5
5 3 4 1 2
)
)		 ¤ (
(
1 2 3 4 5
3 1 4 2 5
)
)		 = (
1 2 3 4 5
)
(
(
1 2 3 4 5
5 3 4 1 2
)
)		 ¤ (
(
1 2 3 4 5
2 3 4 5 1
)
)		 = (
1 2 3 4 5
)

(
(
1 2 3 4 5
2 3 4 5 1
)
)
5

 
= (
1 2 3 4 5
)

The permutation above produces a cycle: 1->2->3->4->5->1
Définition 2   By (a,b,c,d), we denote the permutation sigma such that sigma(a)=b, sigma(b)=c, sigma(c)=d, sigma(d)=a, and sigma(x)=x for any other element x.

Such a permutation is called a cycle.

A cycle (i,j) of length two is called a transposition.

A transposition (i,i+1) is called elementary transposition.
Exercice 3   Write (3,4,2,1) and (2,1,3,4) in array notation.

Write the following permutations in array notation:
(3,4,2,1)= (
1 2 3 4 5
)

(2,1,3,4)= (
1 2 3 4 5
)

(1,2,3)¤(4,5)= (
1 2 3 4 5 6
)

(4,5)¤(1,2,3)= (
1 2 3 4 5 6
)

(1,2,3)¤(3,4)= (
1 2 3 4 5 6
)

(3,4)¤(1,2,3)= (
1 2 3 4 5 6
)

Proposition 2   The product of two disjoint cycles is commutative.

This is not the case for non-disjoint cycles.
Exercice 4   Are the following permutations cycles?
(
(
1 2 3 4 5
5 3 4 1 2
)
)

(
(
1 2 3 4 5 6
2 1 4 5 3 6
)
)


Problem 1   So there are permutations that are not cycles.

Would it be possible to write them using only cycles?

Théorème 1   Any permutation can be written as a product of disjoint cycles.

This product is unique, up to the order.
Exercice 5   Compute the following permutations
(2,3,1,5,4)5= (
1 2 3 4 5 6
)

(
(
1 2 3 4 5 6 7 8 9 10
5 10 2 1 6 4 8 3 7 9
)
)
131

 
= (
1 2 3 4 5 6 7 8 9 10
)

Writting a permutation in cycle notation is a good way to compute powers of this permutation.

1.2.2  Generators of Sn

If you have a list, you can use a permutation to change its order.

Well, Sn is pretty big, so this makes quite a lot of possible operations.

However, some operations can be obtained by combining other operations.

Could we try to reduce the size of Sn?
Définition 3   A subset G of Sn generates Sn if any permutation can be written as a product of elements of G.
Problem 2   Find a set of generators of Sn as small as possible.

Problem 3   Does the set of all cycles generate Sn?
Problem 4   How many cycles are there ?
Can you do better?

Problem 5   Does the set of all transpositions generate Sn?

How many transpositions are there?

Can you do better?

Problem 6   Does the set of all elementary transposition generate Sn?

How many elementary transpositions are there ?

By the way, how many elementary transpositions at most do you need to express a permutation?

Can you do better than n-1 generators?

1.3  Groups

1.3.1  Definitions and examples

The notation [A,¤] denote a set A together with an operation ¤."
Problem 1   Is there anything in common between [Sn,¤] and [Z +].

Définition 4   Let A be a set with an operation ¤
What are the properties of [Z,+]? What are the properties of [R*,·]?

Those structures have many common properties.
Définition 5   [G,¤] is a group if G is a non empty set, and ¤is a binary operation on G such that:
  1. ¤ is associative
  2. an identity element exists (in G).
  3. each element of G has an inverse (in G) with respect to ¤.
If the operation ¤is commutative, G is called a commutative group.
Exercice 6   Which of the following are groups ?
  1. [Z,+]
  2. [N,+]
  3. [Z,-]
  4. [{ true,false},/\}
  5. [R,+]
  6. [R,·]
  7. [Sn,¤]
  8. [nZ,+]
What's the point ?

1.3.2  Just some examples of results and questions about groups


Théorème 2   The identity of a group is unique.

The inverse of an element is unique.

The equations a¤ x=b and x¤ a=b have a unique solution.

The inverse of a product can be computed by (x¤ y)-1=y-1¤ x-1.
Définition 6   Let [G,¤] be a group, and Aincluded in or equal to G.

Then [A,¤] is a subgroup of [G,¤] if [A,¤] itself is a group.
Théorème 3   The size of a subgroup divides the size of the group.
Problem 2   Common problems about a group:
For playing with groups, there is a very nice program:

Valid HTML 4.0! Previous: FunctionsFunctions Up: Class notesClass notes
Groups and other algebraic structures / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:22 2007