Cayley table
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
[edit]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
[edit]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
[edit]Commutativity
[edit]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 group {1, −1} above and the cyclic group of order 3 (see below) 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, written as D3, does not have a symmetric Cayley table.
Permutations
[edit]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 element a has an inverse, we can multiply by this inverse and deduce that 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.
Examples
[edit]Cyclic group of order 3
[edit]The cyclic group of order 3, known as Z3 or C3, can be thought of as the group of addition modulo 3. Its Cayley table is as follows:
| + | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
Dihedral group of order 6
[edit]The dihedral group of order 6, usually written as D3, is the smallest non-Abelian group. Its Cayley table is therefore not symmetrical about the diagonal.
This group describes the symmetries of an equilateral triangle under rotations and reflections.
Let e be the identity element, a,b,c the three reflections, and d and f the two rotations. Then the Cayley table is
| 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 |
The three reflections are their own inverses, so e appears in the diagonal entries corresponding to a2, b2 and c2. Since these reflections do not commute, this section of the table is not symmetrical about the diagonal. For example, a b = d but b a = f.
The subgroup of D3 consisting of rotations only (that is, the subgroup containing only e, d and f) is isomorphic to the cyclic group of order 3 shown above.
The group D3 is isomorphic to the symmetric group S3 of the permutations of three objects. For example, if we label the vertices of our equilateral triangle with the numbers 1,2,3 then the reflection symmetries a,b,c interchange two of the three labels, while the rotations correspond to a cyclic permutation of the three labels.
Permutation matrix generation
[edit]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 the example of D3, mentioned above, 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
[edit]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
[edit]References
[edit]- Cayley, Arthur. "On the theory of groups, as depending on the symbolic equation θn = 1", Philosophical Magazine, Vol. 7 (1854), pp. 40–47. Available on-line at Google Books as part of his collected works.
- Cayley, Arthur. "On the Theory of Groups", American Journal of Mathematics, Vol. 11, No. 2 (Jan 1889), pp. 139–157. Available at JSTOR.