Cayley table
Encyclopedia
A Cayley table, after the 19th century British
mathematician
Arthur Cayley
, 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 easily deduced by examining its Cayley table.
A simple example of a Cayley table is the one for the group {1, −1} under ordinary multiplication
:
, 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 first factor (termed nearer factor by Cayley) in any row of the table is the same, and that the second factor (or further factor) in any column is the same, as in the following example:
Cayley originally set up his tables so that the identity element was first, obviating the need for the separate row and column headers featured in the example above. For example, they do not appear in the following table:
In this example, the cyclic group
Z3, a is the identity element, and thus appears in the top left corner of the table. It is easy to see, for example, that b2 = c and that cb = a. Despite this, most modern texts — and this article — include the row and column headers for added clarity.
. Because the group operation of an abelian group is commutative, a group is abelian if and only if its Cayley table is 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.
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 is the case 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.
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
.
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:
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.
It is noteworthy (and trivial to prove) that any group in which every element is its own inverse is abelian.
Obviously, the e row and the e column can be filled out immediately. Once this has been done, it may be necessary (and it is necessary, in our case) to make an assumption, which may later lead to a contradiction — meaning simply that our initial assumption was false. We will assume that ab = c. Then:
Multiplying ab = c on the left by a gives b = ac. Multiplying on the right by c gives bc = a. Multiplying ab = c on the right by b gives a = cb. Multiplying bc = a on the left by b gives c = ba, and multiplying that on the right by a gives ca = b. After filling these products into the table, we find that the ad and af are still unaccounted for in the a row; as we know that each element of the group must appear in each row exactly once, and that only d and f are unaccounted for, we know that ad must equal d or f; but it cannot equal d, because if it did, that would imply that a equaled e, when we know them to be distinct. Thus we have ad = f and af = d.
Furthermore, since the inverse of d is f, multiplying ad = f on the right by f gives a = f2. Multiplying this on the left by d gives us da = f. Multiplying this on the right by a, we have d = fa.
Filling in all of these products, the Cayley table now looks like this:
Because each row must have every element of the group represented exactly once, it is easy to see that the two blank spots in the b row must be occupied by d or f. However, if one examines the columns containing these two blank spots — the d and f columns — one finds that d and f have already been filled in on both, which means that regardless of how d and f are placed in row b, they will always violate the permutation rule. Because our algebraic deductions up until this point were sound, we can only conclude that our earlier, baseless assumption that ab = c was, in fact, false. Essentially, we guessed and we guessed incorrectly. We, have, however, learned something: ab ≠ c.
The only two remaining possibilities then are that ab = d or that ab = f; we would expect these two guesses to each have the same outcome, up to isomorphism, because d and f are inverses of each other and the letters that represent them are inherently arbitrary anyway. So without loss of generality, take ab = d. If we arrive at another contradiction, we must assume that no group of order 6 has the identity skeleton we started with, as we will have exhausted all possibilities.
Here is the new Cayley table:
Multiplying ab = d on the left by a, we have b = ad. Right multiplication by f gives bf = a, and left multiplication by b gives f = ba. Multiplying on the right by a we then have fa = b, and left multiplication by d then yields a = db. Filling in the Cayley table, we now have (new additions in red):
Since the a row is missing c and f and since af cannot equal f (or a would be equal to e, when we know them to be distinct), we can conclude that af = c. Left multiplication by a then yields f = ac, which we may multiply on the right by c to give us fc = a. Multiplying this on the left by d gives us c = da, which we can multiply on the right by a to obtain ca = d. Similarly, multiplying af = c on the right by d gives us a = cd. Updating the table, we have the following, with the most recent changes in blue:
Since the b row is missing c and d, and since b c cannot equal c, it follows that b c = d, and therefore b d must equal c. Multiplying on the right by f this gives us b = cf, which we can further manipulate into cb = f by multiplying by c on the left. By similar logic we can deduce that c = fb and that dc = b. Filling these in, we have (with the latest additions in green):
Since the d row is missing only f, we know d2 = f, and thus f2 = d. As we have managed to fill in the whole table without obtaining a contradiction, we have found a group of order 6: inspection reveals it to be non-abelian. This group is in fact the smallest non-abelian group, the dihedral group
D3:
s, quasigroup
s, and magmas
, but some of the properties above do not hold.
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Arthur Cayley
Arthur Cayley
Arthur Cayley F.R.S. was a British mathematician. He helped found the modern British school of pure mathematics....
, describes the structure of a finite group
Finite group
In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
by arranging all the possible products of all the group's elements in a square table reminiscent of an addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
or multiplication table
Multiplication table
In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system....
. Many properties of a group — such as whether or not it is abelian
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
, which elements are inverses
Inverse element
In abstract algebra, the idea of an inverse element generalises the concept of a negation, in relation to addition, and a reciprocal, in relation to multiplication. The intuition is of an element that can 'undo' the effect of combination with another given element...
of which elements, and the size and contents of the group's center
Center (group theory)
In abstract algebra, the center of a group G, denoted Z,The notation Z is from German Zentrum, meaning "center". is the set of elements that commute with every element of G. In set-builder notation,...
— can be easily deduced by examining its Cayley table.
A simple example of a Cayley table is the one for the group {1, −1} under ordinary multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
:
| × | 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 abelianAbelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
, the product ab with respect to the group's binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
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 first factor (termed nearer factor by Cayley) in any row of the table is the same, and that the second factor (or further factor) in any column is the same, as in the following example:
| * | a | b | c |
|---|---|---|---|
| a | a2 | ab | ac |
| b | ba | b2 | bc |
| c | ca | cb | c2 |
Cayley originally set up his tables so that the identity element was first, obviating the need for the separate row and column headers featured in the example above. For example, they do not appear in the following table:
| a | b | c |
| b | c | a |
| c | a | b |
In this example, the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
Z3, a is the identity element, and thus appears in the top left corner of the table. It is easy to see, for example, that b2 = c and that cb = a. Despite this, most modern texts — and this article — include the row and column headers for added clarity.
Commutativity
The Cayley table tells us whether a group is abelianAbelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
. Because the group operation of an abelian group is commutative, a group is abelian if and only if its Cayley table is 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
Dihedral group of order 6
The smallest non-abelian group has 6 elements. It is a dihedral group with notation D3 and the symmetric group of degree 3, with notation S3....
, does not have a symmetric Cayley table.
Associativity
Because associativityAssociativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
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
Quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible...
, which does not assume associativity as an axiom (indeed, Cayley tables can be used to characterize the operation of any finite magma
Magma (algebra)
In abstract algebra, a magma is a basic kind of algebraic structure. Specifically, a magma consists of a set M equipped with a single binary operation M \times M \rightarrow M....
). Unfortunately, it is not generally possible to determine whether or not an operation is associative simply by glancing at its Cayley table, as is the case with commutativity. This is because associativity depends on a 3 term equation,
, while the Cayley table shows 2-term products. However, Light's associativity testLight's associativity test
In mathematics, Light's associativity test is a procedure invented by F W Light for testing whether a binary operation defined in a finite set by a Cayley multiplication table is associative. Direct verification of the associativity of a binary operation specified by a Cayley table is cumbersome...
can determine associativity with less effort than brute force.
Permutations
Because the cancellation propertyCancellation property
In mathematics, the notion of cancellative is a generalization of the notion of invertible.An element a in a magma has the left cancellation property if for all b and c in M, a * b = a * c always implies b = c.An element a in a magma has the right cancellation...
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
Reductio ad absurdum
In logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition's being false would imply 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
Latin square
In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...
.
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 inverse; those that do not have another, 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
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
C8 and the quaternion group
Quaternion group
In group theory, the quaternion group is a non-abelian group of order eight, isomorphic to a certain eight-element subset of the quaternions under multiplication...
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:
- all elements are their own inverses,
- all elements save d and f are their own inverses, each of these latter two being the other's inverse,
- 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.
It is noteworthy (and trivial to prove) that any group in which every element is its own inverse is abelian.
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. Once this has been done, it may be necessary (and it is necessary, in our case) to make an assumption, which may later lead to a contradiction — meaning simply that our initial assumption was false. We will assume that ab = c. Then:
| 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 |
Multiplying ab = c on the left by a gives b = ac. Multiplying on the right by c gives bc = a. Multiplying ab = c on the right by b gives a = cb. Multiplying bc = a on the left by b gives c = ba, and multiplying that on the right by a gives ca = b. After filling these products into the table, we find that the ad and af are still unaccounted for in the a row; as we know that each element of the group must appear in each row exactly once, and that only d and f are unaccounted for, we know that ad must equal d or f; but it cannot equal d, because if it did, that would imply that a equaled e, when we know them to be distinct. Thus we have ad = f and af = d.
Furthermore, since the inverse of d is f, multiplying ad = f on the right by f gives a = f2. Multiplying this on the left by d gives us da = f. Multiplying this on the right by a, we have d = fa.
Filling in all of these products, the Cayley table now looks like this:
| 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 |
Because each row must have every element of the group represented exactly once, it is easy to see that the two blank spots in the b row must be occupied by d or f. However, if one examines the columns containing these two blank spots — the d and f columns — one finds that d and f have already been filled in on both, which means that regardless of how d and f are placed in row b, they will always violate the permutation rule. Because our algebraic deductions up until this point were sound, we can only conclude that our earlier, baseless assumption that ab = c was, in fact, false. Essentially, we guessed and we guessed incorrectly. We, have, however, learned something: ab ≠ c.
The only two remaining possibilities then are that ab = d or that ab = f; we would expect these two guesses to each have the same outcome, up to isomorphism, because d and f are inverses of each other and the letters that represent them are inherently arbitrary anyway. So without loss of generality, take ab = d. If we arrive at another contradiction, we must assume that no group of order 6 has the identity skeleton we started with, as we will have exhausted all possibilities.
Here is the new Cayley table:
| 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 |
Multiplying ab = d on the left by a, we have b = ad. Right multiplication by f gives bf = a, and left multiplication by b gives f = ba. Multiplying on the right by a we then have fa = b, and left multiplication by d then yields a = db. Filling in the Cayley table, we now have (new additions 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 |
Since the a row is missing c and f and since af cannot equal f (or a would be equal to e, when we know them to be distinct), we can conclude that af = c. Left multiplication by a then yields f = ac, which we may multiply on the right by c to give us fc = a. Multiplying this on the left by d gives us c = da, which we can multiply on the right by a to obtain ca = d. Similarly, multiplying af = c on the right by d gives us a = cd. Updating the table, we have the following, with the most recent changes 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 |
Since the b row is missing c and d, and since b c cannot equal c, it follows that b c = d, and therefore b d must equal c. Multiplying on the right by f this gives us b = cf, which we can further manipulate into cb = f by multiplying by c on the left. By similar logic we can deduce that c = fb and that dc = b. Filling these in, we have (with the latest additions 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 |
Since the d row is missing only f, we know d2 = f, and thus f2 = d. As we have managed to fill in the whole table without obtaining a contradiction, we have found a group of order 6: inspection reveals it to be non-abelian. This group is in fact the smallest non-abelian group, the dihedral group
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
D3:
| * | 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 |
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 semigroupSemigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
s, quasigroup
Quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible...
s, and magmas
Magma (algebra)
In abstract algebra, a magma is a basic kind of algebraic structure. Specifically, a magma consists of a set M equipped with a single binary operation M \times M \rightarrow M....
, but some of the properties above do not hold.