Cayley table

From Wikipedia, the free encyclopedia

A Cayley table describes the structure of a group, say G = { g₁, ..., g_n} with operation *, by displaying a table in which the ith row and the jth column contains the product g_i*g_j. In essence, the Cayley table is the group-theoretic analogue of an addition or a multiplication table. Cayley tables are named after the mathematician Arthur Cayley.

Contents 1 History 2 Description 3 Properties and uses 3.1 Commutativity 3.2 Permutations 4 Constructing Cayley tables 4.1 Example 5 Generalizations 6 References 7 See also

[edit] History

Cayley tables were presented in an 1889 paper of Cayley's, On The Theory of Groups, and focused on the construction of colourgroups, graphical depictions of groups by coloured lines and routes. Arising naturally from this was a permutation representation of the group and thus a description of the group; Cayley gave tables (he termed them originally squares) for each group (up to isomorphism) of order less than thirteen.

[edit] Description

Cayley originally set up his "squares" so that the identity element was first, giving rise to the first row and column acting as column headers. One can also depict Cayley tables with separate row and column indices.

For example, the Cayley table of the cyclic group of order 3 is as follows:

a	b	c
b	c	a
c	a	b

where a is the identity element, and c = b².

The table tells us that cb = bc = a, for example.

[edit] Properties and uses

[edit] Commutativity

The Cayley table tells us whether a group is abelian. Abelian groups have symmetric Cayley tables, in the matrix sense.

[edit] Permutations

Let us denote the product a * b by juxtaposition, ie., we will write simply ab. Recall that the cancellation law holds for groups, namely, supposing a, x, y, b are elements of the group G, if a * x = b and a * y = b then x = y, and similarly, if x * a = b and y * a = b then x = y.

The consequence of this is that no two elements in a row are the same (since if a row represents element a, and a pair of different columns represent elements x and y, then if a * x = a * y then x = y and the different columns must be the same column, contradiction.) Likewise, no two elements in a column are the same.

This shows that each row and column is a permutation of the elements of G. Indeed, each of the rows/columns furnishes a permutation representation of G (see group action).

[edit] Constructing Cayley tables

It is also true that if a b = e and if b c = e, then a = c. This is true because (a b) c = e c = c, a (b c) = a e = a, but since a group is associative, (a b) c = a (b c) therefore a = c.

What this means is that if a pair of elements have the identity elements as their product, then the pair commutes. So a b = e if and only if b a = e.

It is possible for an element in a group to be its own inverse, so that when multiplied by itself it yields the identity element. If a is such an element then a² = e. If b ≠ a then a b ≠ e.

Therefore each non-identity element is either its own inverse or it pairs up with another element which is its unique inverse. It is possible to rearrange the order of the labelled columns such that the first columns to appear, reading from left to right, are those representing self-inverse elements, starting first with the identity element which is always a self-inverse. After all the columns of self-inverses should follow the columns representing pairs of inverses: each pair of inverses should be represented by a pair of adjacent columns.

If a table is initially left empty except for those entries containing the identity element, the resulting arrangement of identity elements can be viewed as an "identity skeleton" of the Cayley table.

Groups with different identity skeletons cannot be isomorphic, but an identity skeleton boils down simply to numbers of self-inverses versus number of inverse pairs.

As an example, groups with six elements could only possibly have three different identity skeletons in theory (up to isomorphism). (However, in actuality there is no six-element group with the first identity skeleton):

1	e	a	b	c	d	f
e	e
a		e
b			e
c				e
d					e
f						e

   

2	e	a	b	c	d	f
e	e
a		e
b			e
c				e
d						e
f					e

   

3	e	a	b	c	d	f
e	e
a		e
b				e
c			e
d						e
f					e

If an element x of a group is a self-inverse, so that x² = e, then for any elements a and b, x has the following properties:

x a = b ↔ x b = a,

a x = b ↔ b x = a.

This is true because if x a = b then x x a = x b, e a = x b, a = x b. If a x = b then a x x = b x, a e = b x, a = b x. (The swapping of factor and product may be referred to here as "trans-equality commutation" or "trans-commutation" for short.)

If all the elements of a group are self-inverses, then the group must be abelian (its product is commutative and its Cayley table has reflective symmetry with respect to its "diagonal of squares": its backward slash diagonal). This is true because if, for any a, b, c ∈ G,

a b = c

then since a is self-inverse, then b and c can "trans-commute":

a c = b,

but since c is also a self-inverse, then a and b can trans-commute:

b c = a,

and since b is a self-inverse, a and c can trans-commute:

b a = c,

therefore

a b = b a

and since this is true for all pairs a-b in the group, then the group is abelian.

If a pair of elements x and y form an inverse pair, so that x y = y x = e, then for any elements a and b the x-y pair has the following properties (which may be referred to here as "trans-mutations"):

x a = b ↔ y b = a,

a x = b ↔ b y = a.

This is true because if x a = b then y x a = y b, e a = y b, a = y b. If a x = b then a x y = b y,
a e = b y, a = b y.

[edit] Example

These properties can be useful for constructing Cayley tables of groups. E.g. if it is desired to find a six-element group with the second identity skeleton, then start out by filling the identity row and column; and suppose a b = c,

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	c
b	b		e
c	c			e
d	d					e
f	f				e

Since a is self-inverse and a b = c then a c = b by trans-commute. Since c is self-inverse and a c = b then b c = a by trans-commute. Since b is self-inverse and since a b = c then c b = a, and since b c = a then b a = c. Since a is self-inverse and since b a = c then c a = b. Since a d ≠ d because a ≠ e, then a d = f (f is the only element in G left). Then since the a-row contains all elements except d, then a f = d.

Since d is inverse pair with f, and since a d = f, then f f = a, and then d a = f. Then since the a-column contains all elements except d, then f a = d.

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	c	b	f	d
b	b	c	e	a
c	c	b	a	e
d	d	f				e
f	f	d			e	a

The b-row is already occupied with {e, a, b, c} and is only missing {d, f}. Its only open intersections are b d, b f; but the d- and f-columns are already occupied with {d, f}, so the missing intersections cannot be filled with anything. The construction has crashed.

Start over, this time letting a b = d.

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	d
b	b		e
c	c			e
d	d					e
f	f				e

Since a is self-inverse and a b = d then a d = b by trans-commute. Since d pairs with f and since a d = b then b f = a by trans-mute. Then since b is self-inverse and b f = a then b a = f by trans-commute. Since a is self-inverse and since b a = f then f a = b. Since f pairs with d and since f a = b then d b = a by trans-mute.

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	d		b
b	b	f	e			a
c	c			e
d	d		a			e
f	f	b			e

Since a-row is missing {c, f} and since a f ≠ f (because e f = f) then a f = c. Then since a is self-inverse and since a f = c then a c = f by trans-commute. Also, since f pairs with d and since a f = c then c d = a by trans-mute. Since c is self-inverse and since a c = f then f c = a. Since f pairs with d and since f c = a, then d a = c by trans-mute. Since a is self-inverse and since d a = c then c a = d by trans-commute.

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	d	f	b	c
b	b	f	e			a
c	c	d		e	a
d	d	c	a			e
f	f	b		a	e

Since b-row is missing {c, d}, and since b c ≠ c, then b c = d, therefore b d = c (by trans-commutation or by row completion). Since d pairs with f and since b d = c then c f = b by trans-mutation. Since c is self-inverse and since c f = b, then c b = f by trans-commute. Since b is self-inverse and since c b = f, then f b = c by trans-commute. Since f pairs with d and since f b = c, then d c = b by trans-mute.

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	d	f	b	c
b	b	f	e	d	c	a
c	c	d	f	e	a	b
d	d	c	a	b		e
f	f	b	c	a	e

Since d-row is missing only f, then let d d = f. Since d pairs with f and since d d = f, then f f = d by trans-mute. The completed Cayley table of a six-element non-abelian group, isomorphic to the dihedral group D₃, is shown below:

*	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	e	d	f	b	c
b	b	f	e	d	c	a
c	c	d	f	e	a	b
d	d	c	a	b	f	e
f	f	b	c	a	e	d

Note that, given which three elements are their own inverse, there are two possible isomorphic groups: we have chosen a b = d where we could have chosen a b = f.

[edit] Generalizations

The above properties hold for groups, because of its structure. It is natural to consider Cayley tables for other algebraic structures, such as for semigroups, but some of the properties above do not hold.

[edit] References

• Cayley, Arthur. On the Theory of Groups, American Journal of Mathematics, vol. 11 (1889), pp. 139-157.

[edit] See also

• Dihedral group of order 6
• Latin square