Light's associativity test
Encyclopedia
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 and tedious. Light's associativity test greatly simplifies the task.
The Cayley tables of these operations are constructed and compared. If the tables coincide then x · ( a · y ) = ( x · a ) · y for all x and y. This is repeated for every element of the set A.
The example below illustrates a further simplification in the procedure for the construction and comparison of the Cayley tables of the operations '
' and ' 
'.
It is not even necessary to construct the Cayley tables of '
' and ' 
' for all elements of A. It is enough to compare Cayley tables of ' 
' and ' 
' corresponding to the elements in a proper generating subset of A.
The set { c, e } is a generating set for the set A under the binary operation defined by the above table, for, a = e · e, b = c · c, d = c · e. Thus it is enough to verify that the binary operations '
' and ' 
' corresponding to c coincide and also that the binary operations ' 
' and ' 
' corresponding to e coincide.
To verify that the binary operations '
' and ' 
' corresponding to c coincide, choose the row in Table 1 corresponding to the element c :
This row is copied as the header row of a new table (Table 3):
Under the header a copy the corresponding column in Table 1, under the header b copy the corresponding column in Table 1, etc, and construct Table 4.
The column headers of Table 4 are now deleted to get Table 5:
The Cayley table of the binary operation '
' corresponding to the element c is given by Table 6.
Next choose the c column of Table 1:
Copy this column to the index column to get Table 8:
Against the index entry a in Table 8 copy the corresponding row in Table 1, against the index entry b copy the corresponding row in Table 1, etc, and construct Table 9.
The index entries in the first column of Table 9 are now deleted to get Table 10:
The Cayley table of the binary operation '
' corresponding to the element c is given by Table 11.
One can verify that the entries in the various cells in Table 6 agrees with the entries in the corresponding cells of Table 11. This shows that x · ( c · y ) = ( x · c ) · y for all x and y in A. If there were some discrepancy then it would not be true that x · ( c · y ) = ( x · c ) · y for all x and y in A.
That x · ( e · y ) = ( x · e ) · y for all x and y in A can be verified in a similar way by constructing the following tables (Table 12 and Table 13):
' and ' 
'. It is enough to copy the column corresponding to the header c in Table 1 to the index column in Table 5 and form the following table (Table 14) and verify that the a -row of Table 14 is identical with the a -row of Table 1, the b -row of Table 14 is identical with the b -row of Table 1, etc. This is to be repeated mutatis mutandis for all the elements of the generating set of A.
can be written to carry out Light's associativity test. Kehayopulu and Argyris have developed such an algorithm
for Mathematica
.
Let T = { t1, t2,
, tm } be a magma
in which the operation is denoted by juxtaposition. Let X = { x1, x2,
, xn } be a set. Let there be a mapping from the Cartesian product
T × X to X denoted by (t, x) tx and let it be required to test whether this map has the property
x = s(tx) for all s, t in T and all x in X.
A generalization of Light's associativity test can be applied to verify whether the above property holds or not. In mathematical notations, the generalization runs as follows: For each t in T, let L(t) be the m × n matrix of elements of X whose i - th row is
x1, (tit)x2,
, (tit)xn ) for i = 1, 
, m
and let R(t) be the m × n matrix of elements of X, the elements of whose j - th column are
, t2(txj),
, tm(txj) ) for j = 1, 
, n.
According to the generalised test (due to Bednarek), that the property to be verified holds if and only if L(t) = R(t) for all t in T. When X = T, Bednarek's test reduces to Light's test.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Light's associativity test is a procedure
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
invented by F W Light for testing whether a 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....
defined in a finite set by a Cayley multiplication table
Cayley table
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...
is associative. Direct verification of the associativity of a binary operation specified by a Cayley table is cumbersome and tedious. Light's associativity test greatly simplifies the task.
Description of the procedure
Let a binary operation ' · ' be defined in a finite set A by a Cayley table. Choosing some element a in A, two new binary operations are defined in A as follows:- x
y = x · ( a · y ) - x
y = ( x · a ) · y
The Cayley tables of these operations are constructed and compared. If the tables coincide then x · ( a · y ) = ( x · a ) · y for all x and y. This is repeated for every element of the set A.
The example below illustrates a further simplification in the procedure for the construction and comparison of the Cayley tables of the operations '
' and ' '.It is not even necessary to construct the Cayley tables of '
' and ' ' for all elements of A. It is enough to compare Cayley tables of ' ' and ' ' corresponding to the elements in a proper generating subset of A.Example
Consider the binary operation ' · ' in the set A = { a, b, c, d, e } defined by the following Cayley table (Table 1):| · | a | b | c | d | e |
|---|---|---|---|---|---|
| a | a | a | a | d | d |
| b | a | b | c | d | d |
| c | a | c | b | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
The set { c, e } is a generating set for the set A under the binary operation defined by the above table, for, a = e · e, b = c · c, d = c · e. Thus it is enough to verify that the binary operations '
' and ' ' corresponding to c coincide and also that the binary operations ' ' and ' ' corresponding to e coincide.To verify that the binary operations '
' and ' ' corresponding to c coincide, choose the row in Table 1 corresponding to the element c :| · | a | b | c | d | e |
|---|---|---|---|---|---|
| a | a | a | a | d | d |
| b | a | b | c | d | d |
| c | a | c | b | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
This row is copied as the header row of a new table (Table 3):
| a | c | b | d | d | |
|---|---|---|---|---|---|
Under the header a copy the corresponding column in Table 1, under the header b copy the corresponding column in Table 1, etc, and construct Table 4.
| a | c | b | d | d | |
|---|---|---|---|---|---|
| a | a | a | d | d | |
| a | c | b | d | d | |
| a | b | c | d | d | |
| d | d | d | a | a | |
| d | e | e | a | a |
The column headers of Table 4 are now deleted to get Table 5:
| a | a | a | d | d | |
| a | c | b | d | d | |
| a | b | c | d | d | |
| d | d | d | a | a | |
| d | e | e | a | a |
The Cayley table of the binary operation '
' corresponding to the element c is given by Table 6.  (c) |
a | b | c | d | e |
|---|---|---|---|---|---|
| a | a | a | a | d | d |
| b | a | c | b | d | d |
| c | a | b | c | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
Next choose the c column of Table 1:
| · | a | b | c | d | e |
|---|---|---|---|---|---|
| a | a | a | a | d | d |
| b | a | b | c | d | d |
| c | a | c | b | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
Copy this column to the index column to get Table 8:
| a | |||||
| c | |||||
| b | |||||
| d | |||||
| e |
Against the index entry a in Table 8 copy the corresponding row in Table 1, against the index entry b copy the corresponding row in Table 1, etc, and construct Table 9.
| a | a | a | a | d | d |
| c | a | c | b | d | d |
| b | a | b | c | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
The index entries in the first column of Table 9 are now deleted to get Table 10:
| a | a | a | d | d | |
| a | c | b | d | d | |
| a | b | c | d | d | |
| d | d | d | a | a | |
| d | e | e | a | a |
The Cayley table of the binary operation '
' corresponding to the element c is given by Table 11.  (c) |
a | b | c | d | e |
|---|---|---|---|---|---|
| a | a | a | a | d | d |
| b | a | c | b | d | d |
| c | a | b | c | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
One can verify that the entries in the various cells in Table 6 agrees with the entries in the corresponding cells of Table 11. This shows that x · ( c · y ) = ( x · c ) · y for all x and y in A. If there were some discrepancy then it would not be true that x · ( c · y ) = ( x · c ) · y for all x and y in A.
That x · ( e · y ) = ( x · e ) · y for all x and y in A can be verified in a similar way by constructing the following tables (Table 12 and Table 13):
 (e) |
a | b | c | d | e |
|---|---|---|---|---|---|
| a | d | d | d | a | a |
| b | d | d | d | a | a |
| c | d | d | d | a | a |
| d | a | a | a | d | d |
| e | a | a | a | d | d |
 (e) |
a | b | c | d | e |
|---|---|---|---|---|---|
| a | d | d | d | a | a |
| b | d | d | d | a | a |
| c | d | d | d | a | a |
| d | a | a | a | d | d |
| e | a | a | a | d | d |
A further simplification
It is not necessary to construct the Cayley tables (Table 6 and table 11) of the binary operations ' ' and ' '. It is enough to copy the column corresponding to the header c in Table 1 to the index column in Table 5 and form the following table (Table 14) and verify that the a -row of Table 14 is identical with the a -row of Table 1, the b -row of Table 14 is identical with the b -row of Table 1, etc. This is to be repeated mutatis mutandis for all the elements of the generating set of A.| a | c | b | d | d | |
|---|---|---|---|---|---|
| a | a | a | a | d | d |
| c | a | c | b | d | d |
| b | a | b | c | d | d |
| d | d | d | d | a | a |
| e | d | e | e | a | a |
Algorithm for Light's associativity test
Computer softwareComputer software
Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it....
can be written to carry out Light's associativity test. Kehayopulu and Argyris have developed such an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for Mathematica
Mathematica
Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...
.
Extension of Light's associativity test
Light's associativity test can be extended to test associativity in a more general context.Let T = { t1, t2,
, tm } be a magmaMagma (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....
in which the operation is denoted by juxtaposition. Let X = { x1, x2,
, xn } be a set. Let there be a mapping from the Cartesian productCartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
T × X to X denoted by (t, x) tx and let it be required to test whether this map has the property
x = s(tx) for all s, t in T and all x in X.
A generalization of Light's associativity test can be applied to verify whether the above property holds or not. In mathematical notations, the generalization runs as follows: For each t in T, let L(t) be the m × n matrix of elements of X whose i - th row is
x1, (tit)x2,
, (tit)xn ) for i = 1, , mand let R(t) be the m × n matrix of elements of X, the elements of whose j - th column are
, t2(txj),
, tm(txj) ) for j = 1, , n.According to the generalised test (due to Bednarek), that the property to be verified holds if and only if L(t) = R(t) for all t in T. When X = T, Bednarek's test reduces to Light's test.