Cayley table

From Wikipedia, the free encyclopedia

Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplication table. Many properties of a group – such as whether or not it is abelian, which elements are inverses of which elements, and the size and contents of the group's center – can be discovered from its Cayley table.

A simple example of a Cayley table is the one for the group {1, −1} under ordinary multiplication:

× 1 −1
1 1 −1
−1 −1 1

History[]

Cayley tables were first presented in Cayley's 1854 paper, "On The Theory of Groups, as depending on the symbolic equation θ n = 1". In that paper they were referred to simply as tables, and were merely illustrative – they came to be known as Cayley tables later on, in honour of their creator.

Structure and layout[]

Because many Cayley tables describe groups that are not abelian, the product ab with respect to the group's binary operation is not guaranteed to be equal to the product ba for all a and b in the group. In order to avoid confusion, the convention is that the factor that labels the row (termed nearer factor by Cayley) comes first, and that the factor that labels the column (or further factor) is second. For example, the intersection of row a and column b is ab and not ba, as in the following example:

* a b c
a a2 ab ac
b ba b2 bc
c ca cb c2

Properties and uses[]

Commutativity[]

The Cayley table tells us whether a group is abelian. Because the group operation of an abelian group is commutative, a group is abelian if and only if its Cayley table's values are symmetric along its diagonal axis. The cyclic group of order 3, above, and {1, −1} under ordinary multiplication, also above, are both examples of abelian groups, and inspection of the symmetry of their Cayley tables verifies this. In contrast, the smallest non-abelian group, the dihedral group of order 6, does not have a symmetric Cayley table.

Associativity[]

Because associativity is taken as an axiom when dealing with groups, it is often taken for granted when dealing with Cayley tables. However, Cayley tables can also be used to characterize the operation of a quasigroup, which does not assume associativity as an axiom (indeed, Cayley tables can be used to characterize the operation of any finite magma). Unfortunately, it is not generally possible to determine whether or not an operation is associative simply by glancing at its Cayley table, as it is with commutativity. This is because associativity depends on a 3 term equation, , while the Cayley table shows 2-term products. However, Light's associativity test can determine associativity with less effort than brute force.

Permutations[]

Because the cancellation property holds for groups (and indeed even quasigroups), no row or column of a Cayley table may contain the same element twice. Thus each row and column of the table is a permutation of all the elements in the group. This greatly restricts which Cayley tables could conceivably define a valid group operation.

To see why a row or column cannot contain the same element more than once, let a, x, and y all be elements of a group, with x and y distinct. Then in the row representing the element a, the column corresponding to x contains the product ax, and similarly the column corresponding to y contains the product ay. If these two products were equal – that is to say, row a contained the same element twice, our hypothesis – then ax would equal ay. But because the cancellation law holds, we can conclude that if ax = ay, then x = y, a contradiction. Therefore, our hypothesis is incorrect, and a row cannot contain the same element twice. Exactly the same argument suffices to prove the column case, and so we conclude that each row and column contains no element more than once. Because the group is finite, the pigeonhole principle guarantees that each element of the group will be represented in each row and in each column exactly once.

Thus, the Cayley table of a group is an example of a latin square.

Another, maybe simpler proof: the cancellation property implies that for each x in the group, the one variable function of y f(x,y)= xy must be a one to one map. And one to one maps on finite sets are permutations.

Constructing Cayley tables[]

Because of the structure of groups, one can very often "fill in" Cayley tables that have missing elements, even without having a full characterization of the group operation in question. For example, because each row and column must contain every element in the group, if all elements are accounted for save one, and there is one blank spot, without knowing anything else about the group it is possible to conclude that the element unaccounted for must occupy the remaining blank space. It turns out that this and other observations about groups in general allow us to construct the Cayley tables of groups knowing very little about the group in question.

The "identity skeleton" of a finite group[]

Because in any group, even a non-abelian group, every element commutes with its own inverse, it follows that the distribution of identity elements on the Cayley table will be symmetric across the table's diagonal. Those that lie on the diagonal are their own unique inverse.

Because the order of the rows and columns of a Cayley table is in fact arbitrary, it is convenient to order them in the following manner: beginning with the group's identity element, which is always its own inverse, list first all the elements that are their own inverse, followed by pairs of inverses listed adjacent to each other.

Then, for a finite group of a particular order, it is easy to characterize its "identity skeleton", so named because the identity elements on the Cayley table are clustered about the main diagonal – either they lie directly on it, or they are one removed from it.

It is relatively trivial to prove that groups with different identity skeletons cannot be isomorphic, though the converse is not true (for instance, the cyclic group C8 and the quaternion group Q are non-isomorphic but have the same identity skeleton).

Consider a six-element group with elements e, a, b, c, d, and f. By convention, e is the group's identity element. Because the identity element is always its own inverse, and inverses are unique, the fact that there are 6 elements in this group means that at least one element other than e must be its own inverse. So we have the following possible skeletons:

  1. all elements are their own inverses,
  2. all elements save d and f are their own inverses, each of these latter two being the other's inverse,
  3. a is its own inverse, b and c are inverses, and d and f are inverses.

In our particular example, there does not exist a group of the first type of order 6; indeed, simply because a particular identity skeleton is conceivable does not in general mean that there exists a group that fits it.

Any group in which every element is its own inverse is abelian: let a and b be elements of the group, then ab = (ab)−1 = b−1a−1 = ba.

Filling in the identity skeleton[]

Once a particular identity skeleton has been decided on, it is possible to begin filling out the Cayley table. For example, take the identity skeleton of a group of order 6 of the second type outlined above:

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

Obviously, the e-row and the e-column can be filled out immediately.

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

Once this is done there are several possible options on how to proceed. We will focus on the value of ab. Since each element of the group must appear once and only once in each row, and once and only once in each column, the only possibly valid values of ab are c, d, or f. However we can see that swapping around the two elements d and f would result in exactly the same table as we already have, save for arbitrarily selected labels. We would therefore expect both of these two options to result in the same outcome, up to isomorphism, and so we need only consider one of them.

It is also important to note that one or several of the values may (and do, in our case) later lead to contradiction – meaning simply that they were in fact not vaild values at all.

ab = c[]

By alternatingly multiplying on the left and on the right it is possible to extend one equation into a loop of equations where any one implies all the others:

  • Multiplying ab = c on the left by a gives b = ac
  • Multiplying b = ac on the right by c gives bc = a
  • Multiplying bc = a on the left by b gives c = ba
  • Multiplying c = ba on the right by a gives ca = b
  • Multiplying ca = b on the left by c gives a = cb
  • Multiplying a = cb on the right by b gives ab = c

Filling in all of these products, the Cayley table now looks like this (new elements in red):

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

We will now focus on the value of ad. Since each element of the group must appear once and only once in each row, and once and only once in each column, the only possibly valid value of ad is f.

By alternatingly multiplying on the left and on the right it is possible to extend one equation into a loop of equations where any one implies all the others:

  • Multiplying ad = f on the left by a gives d = af
  • Multiplying d = af on the right by d gives d2 = a
  • Multiplying d2 = a on the left by f gives d = fa
  • Multiplying d = fa on the right by a gives da = f
  • Multiplying da = f on the left by f gives a = f2
  • Multiplying a = f2 on the right by d gives ad = f

Filling in all of these products, the Cayley table now looks like this (new elements in blue):

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 a e
f f d e a

We will now focus on the value of bd. Unfortunately, since each element of the group must appear once and only once in each row, and once and only once in each column, there are no valid values of bd.

This means that the option we selected (ab = c) has lead us to a point where no value can be assigned to bd without causing contradictions. We have therfore showed that ab ≠ c.

If we in a similar way show that all options lead to contradictions, then we must conclude that no group of order 6 exists with the identity skeleton that we started with.

ab = d[]

By alternatingly multiplying on the left and on the right it is possible to extend one equation into a loop of equations where any one implies all the others:

  • Multiplying ab = d on the left by a gives b = ad
  • Multiplying b = ad on the right by f gives bf = a
  • Multiplying bf = a on the left by b gives f = ba
  • Multiplying f = ba on the right by a gives fa = b
  • Multiplying fa = b on the left by d gives a = db
  • Multiplying a = db on the right by b gives ab = d

Filling in all of these products, the Cayley table now looks like this (new elements in red):

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

We will now focus on the value of ac. Since each element of the group must appear once and only once in each row, and once and only once in each column, the only possibly valid value of ac is f.

By alternatingly multiplying on the left and on the right it is possible to extend one equation into a loop of equations where any one implies all the others:

  • Multiplying ac = f on the left by a gives c = af
  • Multiplying c = af on the right by d gives cd = a
  • Multiplying cd = a on the left by c gives d = ca
  • Multiplying d = ca on the right by a gives da = c
  • Multiplying da = c on the left by f gives a = fc
  • Multiplying a = fc on the right by c gives ac = f

Filling in all of these products, the Cayley table now looks like this (new elements in blue):


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

We will now focus on the value of bc. Since each element of the group must appear once and only once in each row, and once and only once in each column, the only possibly valid value of bc is d.

By alternatingly multiplying on the left and on the right it is possible to extend one equation into a loop of equations where any one implies all the others:

  • Multiplying bc = d on the left by b gives c = bd
  • Multiplying c = bd on the right by f gives cf = b
  • Multiplying cf = b on the left by c gives f = cb
  • Multiplying f = cb on the right by b gives fb = c
  • Multiplying fb = c on the left by d gives b = dc
  • Multiplying b = dc on the right by c gives bc = d

Filling in all of these products, the Cayley table now looks like this (new elements in green):

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

Finally, since each element of the group must appear once and only once in each row, and once and only once in each column, the only possibly valid value of d2 is f, and the only possibly valid value of f2 is d.

Filling in these products, the Cayley table now looks like this (new elements in orange):

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


As we have managed to fill in the whole table without obtaining a contradiction, we have found a group of order 6, and inspection reveals it to be non-abelian. This group is in fact the smallest non-abelian group, the dihedral group D3:


Permutation matrix generation[]

The standard form of a Cayley table has the order of the elements in the rows the same as the order in the columns. Another form is to arrange the elements of the columns so that the nth column corresponds to the inverse of the element in the nth row. In our example of D3, we need only switch the last two columns, since f and d are the only elements that are not their own inverses, but instead inverses of each other.

e a b c f=d−1 d=f−1
e e a b c f d
a a e d f c b
b b f e d a c
c c d f e b a
d d c a b e f
f f b c a d e

This particular example lets us create six permutation matrices (all elements 1 or 0, exactly one 1 in each row and column). The 6x6 matrix representing an element will have a 1 in every position that has the letter of the element in the Cayley table and a zero in every other position, the Kronecker delta function for that symbol. (Note that e is in every position down the main diagonal, which gives us the identity matrix for 6x6 matrices in this case, as we would expect.) Here is the matrix that represents our element a, for example.

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

This shows us directly that any group of order n is a subgroup of the permutation group Sn, order n!.

Generalizations[]

The above properties depend on some axioms valid for groups. It is natural to consider Cayley tables for other algebraic structures, such as for semigroups, quasigroups, and magmas, but some of the properties above do not hold.

See also[]

References[]

Retrieved from ""