HOME

TheInfoList



OR:

Named after the 19th century
British British may refer to: Peoples, culture, and language * British people, nationals or natives of the United Kingdom, British Overseas Territories, and Crown Dependencies. ** Britishness, the British identity and common culture * British English, ...
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...
Arthur Cayley Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics. As a child, C ...
, a Cayley table describes the structure of a
finite group Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...
by arranging all the possible products of all the group's elements in a square table reminiscent of an
addition Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
or
multiplication table In mathematics, a multiplication table (sometimes, less formally, a times table) is a mathematical table used to define a multiplication operation for an algebraic system. The decimal multiplication table was traditionally taught as an essenti ...
. Many properties of a groupsuch as whether or not it is abelian, which elements are inverses of which elements, and the size and contents of the group's
center Center or centre may refer to: Mathematics *Center (geometry), the middle of an object * Center (algebra), used in various contexts ** Center (group theory) ** Center (ring theory) * Graph center, the set of all vertices of minimum eccentrici ...
can be discovered from its Cayley table. A simple example of a Cayley table is the one for the group under ordinary
multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
:


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 illustrativethey 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 In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
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:


Properties and uses


Commutativity

The Cayley table tells us whether a group is abelian. Because the group operation of an abelian group is
commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
, a group is abelian
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...
its Cayley table's values are
symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
along its diagonal axis. The group above and the cyclic group of order 3 under ordinary multiplication 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 In mathematics, D3 (sometimes alternatively denoted by D6) is the dihedral group of degree 3, or, in other words, the dihedral group of order 6. It is isomorphic to the symmetric group S3 of degree 3. It is also the smallest possible non-abel ...
, does not have a symmetric Cayley table.


Associativity

Because
associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
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 In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have ...
, which does not assume associativity as an axiom (indeed, Cayley tables can be used to characterize the operation of any finite
magma Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
). 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, (ab)c=a(bc), while the Cayley table shows 2-term products. However,
Light'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. The naive procedure for verification of the associa ...
can determine associativity with less effort than brute force.


Permutations

Because the
cancellation 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 (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that . An ...
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 In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
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 equalthat is to say, row ''a'' contained the same element twice, our hypothesisthen ''ax'' would equal ''ay''. But because the cancellation law holds, we can conclude that if ''ax'' = ''ay'', then ''x'' = ''y'', a
contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
. 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 In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...
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 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. An example of a 3×3 Latin sq ...
. Another, maybe simpler proof: the
cancellation 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 (or is left-cancellative) if for all ''b'' and ''c'' in ''M'', always implies that . An ...
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. It should be noted, however, that a Cayley table constructed using the method that follows may fail to meet the associativity requirement of a group, and therefore represent a quasigroup.


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 constructed in the manner described in the previous paragraph are clustered about the main diagonaleither 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 In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
, though the converse is not true (for instance, the
cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
''C8'' and the
quaternion group In group theory, the quaternion group Q8 (sometimes just denoted by Q) is a non-abelian group of order eight, isomorphic to the eight-element subset \ of the quaternions under multiplication. It is given by the group presentation :\mathrm_8 ...
''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. 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''−1''a''−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: Obviously, the ''e''-row and the ''e''-column can be filled out immediately. Once this is done there are several possible options on how to proceed. We will focus on the value of ''ab''. By the Latin square property, 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 contradictionmeaning simply that they were in fact not valid 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): Since the Cayley table is a Latin square, the only possibly valid value of ''ad'' is ''f,'' and similarly the only possible value of ''af'' is ''d''. Filling in these values, the Cayley table now looks like this (new elements in blue): Unfortunately, all elements of the group are already present either above or to the left of ''bd'' in the table so there is no value of ''bd'' that satisfies the Latin square property. This means that the option we selected will be (''ab'' = ''c'') has led us to a point where no value can be assigned to ''bd'' without causing contradictions. We have therefore shown 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): The remaining products of a, shown in blue, may now be entered using the Latin square property. For example, ''c'' is missing from row ''a'' and cannot occur twice in column ''c'', hence ''ac = f''. Similarly, the remaining products of b, shown in green, may then be entered: The remaining products, each of which is the only missing value in either a row or a column, may now be filled in using the Latin square property, shown in orange: 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 In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...
''D''3


Example of a quasigroup constructed using the above method

The Cayley table that follows may be constructed by entering an identity skeleton, filling in the first row and column, and then postulating that ''ab = c''. The alternative assumption ''ab = d'' results in a homomorphism. The rest of the table follows as a Latin square. However, by reference to the table ''(ac)b = db = a'', while ''a(cb) = ad = b''. It therefore fails the associativity axiom and represents a quasigroup rather than a group.


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 ''n''th column corresponds to the inverse of the element in the ''n''th row. In our example of ''D''3, 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. This particular example lets us create six
permutation matrices In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
(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 In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise: \delta_ = \begin 0 &\text i \neq j, \\ 1 &\ ...
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. {, border="2" cellpadding="5" align="center" !style="background:#efefef;", !style="background:#efefef;", e !style="background:#efefef;", a !style="background:#efefef;", b !style="background:#efefef;", c !style="background:#efefef;", f !style="background:#efefef;", d , - !style="background:#efefef;", e , 0 , , 1 , , 0 , , 0 , , 0 , , 0 , - !style="background:#efefef;", a , 1 , , 0 , , 0 , , 0 , , 0 , , 0 , - !style="background:#efefef;", b , 0 , , 0 , , 0 , , 0 , , 1 , , 0 , - !style="background:#efefef;", c , 0 , , 0 , , 0 , , 0 , , 0 , , 1 , - !style="background:#efefef;", d , 0 , , 0 , , 1 , , 0 , , 0 , , 0 , - !style="background:#efefef;", f , 0 , , 0 , , 0 , , 1 , , 0 , , 0 This shows us directly that any group of order ''n'' is a subgroup of the
permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
''S''''n'', 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
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
s,
quasigroup In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have ...
s, and
magmas Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
, but some of the properties above do not hold.


See also

*
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. An example of a 3×3 Latin sq ...
*
Sudoku Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...


References

* 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 The ''American Journal of Mathematics'' is a bimonthly mathematics journal published by the Johns Hopkins University Press. History The ''American Journal of Mathematics'' is the oldest continuously published mathematical journal in the United ...
'', Vol. 11, No. 2 (Jan 1889), pp. 139–157
Available at JSTOR.
Finite groups