I'm interested in binary operations on a finite set S that are associative, period; no other constraints. 1. Are there "fast" methods for checking associativity given the operation table? 2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ? (RCS knows why I'm asking this question.)
"Fast" obviously doesn't mean "polynomial" in this context, because the obvious check-all-triples procedure is just O(|S|^3). It's also clear that we can't do better than O(|S|^2), since that wouldn't give us time to check all the cells of the table, and an arbitrary table might contrive to screw us on the very last cell we checked, so we can't skimp -- the algorithm has to "consider" every cell. I propose that a preliminary definition of "fast" might be "anything faster than cubic". I guess I would be surprised if we couldn't do at least a *little* better. On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The word you want is semigroup: http://en.wikipedia.org/wiki/Semigroup Well, there is this: http://en.wikipedia.org/wiki/Light's_associativity_test And you might find something of interest in the reference to this OEIS entry: number of semigroups of order n http://oeis.org/A001423 On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It looks like "Verification of Identities" by Rajagoplan and Schulman seems to be the best algorithm known: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A29F9C99B65004A490D... On Tue, Aug 19, 2014 at 7:21 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
The word you want is semigroup: http://en.wikipedia.org/wiki/Semigroup
Well, there is this: http://en.wikipedia.org/wiki/Light's_associativity_test
And you might find something of interest in the reference to this OEIS entry: number of semigroups of order n http://oeis.org/A001423
On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The algorithm of Rajagoplan and Schulman is easy to describe. It has one-sided error: that is we fix and epsilon > 0. The algorithm runs in time log(1/epsilon)*n^2 (where n is the size of S), and will only fail with probability < epsilon (using random choices). Here's the algorithm: Repeat the following log(1/epsilon) times: Pick 3 independent formal combinations of elements of S with coefficients in Z mod 2. Call them a, b, c. Verify that a(bc) = (ab)c, where the multiplication is done via formal linear combinations. If S isn't associative, with probability at least (1-epsilon)^log(1/epsilon) it will detect it this way. Victor On Tue, Aug 19, 2014 at 7:41 PM, Victor Miller <victorsmiller@gmail.com> wrote:
It looks like "Verification of Identities" by Rajagoplan and Schulman seems to be the best algorithm known:
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A29F9C99B65004A490D...
On Tue, Aug 19, 2014 at 7:21 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
The word you want is semigroup: http://en.wikipedia.org/wiki/Semigroup
Well, there is this: http://en.wikipedia.org/wiki/Light's_associativity_test
And you might find something of interest in the reference to this OEIS entry: number of semigroups of order n http://oeis.org/A001423
On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
But, this is a probabilistic algorithm which might fail. --Dan On Aug 19, 2014, at 9:22 PM, Victor Miller <victorsmiller@gmail.com> wrote:
The algorithm of Rajagoplan and Schulman is easy to describe. It has one-sided error: that is we fix and epsilon > 0. The algorithm runs in time log(1/epsilon)*n^2 (where n is the size of S), and will only fail with probability < epsilon (using random choices). Here's the algorithm:
Repeat the following log(1/epsilon) times:
Pick 3 independent formal combinations of elements of S with coefficients in Z mod 2. Call them a, b, c. Verify that a(bc) = (ab)c, where the multiplication is done via formal linear combinations.
If S isn't associative, with probability at least (1-epsilon)^log(1/epsilon) it will detect it this way.
Correction: I should have said that if S isn't associative that it will pass undetected with probability < epsilon. On Tue, Aug 19, 2014 at 9:22 PM, Victor Miller <victorsmiller@gmail.com> wrote:
The algorithm of Rajagoplan and Schulman is easy to describe. It has one-sided error: that is we fix and epsilon > 0. The algorithm runs in time log(1/epsilon)*n^2 (where n is the size of S), and will only fail with probability < epsilon (using random choices). Here's the algorithm:
Repeat the following log(1/epsilon) times:
Pick 3 independent formal combinations of elements of S with coefficients in Z mod 2. Call them a, b, c. Verify that a(bc) = (ab)c, where the multiplication is done via formal linear combinations.
If S isn't associative, with probability at least (1-epsilon)^log(1/epsilon) it will detect it this way.
Victor
On Tue, Aug 19, 2014 at 7:41 PM, Victor Miller <victorsmiller@gmail.com> wrote:
It looks like "Verification of Identities" by Rajagoplan and Schulman seems to be the best algorithm known:
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A29F9C99B65004A490D...
On Tue, Aug 19, 2014 at 7:21 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
The word you want is semigroup: http://en.wikipedia.org/wiki/Semigroup
Well, there is this: http://en.wikipedia.org/wiki/Light's_associativity_test
And you might find something of interest in the reference to this OEIS entry: number of semigroups of order n http://oeis.org/A001423
On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Given N in Z+, what is the largest possible size f(N) of a set X of NxN matrices over Z such that 1) Any pair of them multiply to the zero matrix; 2) Each member of X has no common factor among all N^2 of its entries. ??? Having spent only a few minutes on this, it seems clear that f(N) >= 1 + floor(N/2)^2 (exercise). Maybe it's obvious, but I don't even see why f(N) must be finite (though I'd guess it is). One could also ask the question in a variety of other ways, such as for matrices whose entries are all nonnegative integers. Or over certain rings. --Dan
On 21/08/2014 02:12, Dan Asimov wrote:
Given N in Z+, what is the largest possible size f(N) of a set X of NxN matrices over Z such that
1) Any pair of them multiply to the zero matrix;
2) Each member of X has no common factor among all N^2 of its entries.
???
Having spent only a few minutes on this, it seems clear that f(N) >= 1 + floor(N/2)^2 (exercise).
Maybe it's obvious, but I don't even see why f(N) must be finite (though I'd guess it is).
Any two matrices of the form [0 1 0] [0 0 0] [0 a 0] have zero product and no common factor among all entries. -- g
Nice simple example -- oh, well, I guess that was a non-question, sorry. Okay, here are two cases where there are only finitely many matrices, hence finitely many in the answers: 1) Consider NxN matrices with entries in Z/2Z. 2) Consider NxN matrices with entries in Z, each equal to 0 or 1. --Dan On Aug 21, 2014, at 1:33 AM, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 21/08/2014 02:12, Dan Asimov wrote:
Given N in Z+, what is the largest possible size f(N) of a set X of NxN matrices over Z such that
1) Any pair of them multiply to the zero matrix;
2) Each member of X has no common factor among all N^2 of its entries.
???
Having spent only a few minutes on this, it seems clear that f(N) >= 1 + floor(N/2)^2 (exercise).
Maybe it's obvious, but I don't even see why f(N) must be finite (though I'd guess it is).
Any two matrices of the form
[0 1 0] [0 0 0] [0 a 0]
have zero product and no common factor among all entries.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Look here for references: http://math.stackexchange.com/questions/168663/is-there-an-easy-way-to-see-a... On Tue, Aug 19, 2014 at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
As for your 2. Given a semigroup S you can embed it into a semigroup S^1 with identity in an obvious way and then treating S^1 as the basis of a vector space the mapping f defined by f(s)(x) = sx represents the semigroup as a semigroup of matrices. Much as any finite group can be represented by permutation matrices. On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just in case for each element x, left multiplication by x L_x: S -> S is a permutation of S, then the set Q = {L_x | x in S}: then by associativity L_x o L_y = L_(xy), and so by tossing in any inverses L'_x not already included, and likewise for an identity element, the semigroup Q can be embedded in a group G of permutations on |S| elements. G must be a subgroup of the full group Sym(|S|) of permutations, which is the group of isometries of the |S|-1 simplex in R^N where N = |S|-1. So G is a subgroup of the orthogonal group O(N), and so its multiplication -- and that of the original semigroup S as well -- can be represented by matrix multiplication. This I think I understand. But I see W. Edwin Clark says that matrix representation is possible for any finite semigroup at all, which would be very nice. I don't quite follow the reasoning, though. --Dan On Aug 19, 2014, at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
Dan, If S is a finite semigroup (just associative) make a vector space with dimension |S|. You can consider it the set of formal linear combinations of elements of S. Then multiplication by any element yields a linear map from the vector space to itself (and thus a matrix). This is faithful. Victor On Tue, Aug 19, 2014 at 7:47 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just in case for each element x, left multiplication by x
L_x: S -> S
is a permutation of S, then the set Q = {L_x | x in S}:
then by associativity L_x o L_y = L_(xy),
and so by tossing in any inverses L'_x not already included, and likewise for an identity element, the semigroup Q can be embedded in a group G of permutations on |S| elements.
G must be a subgroup of the full group Sym(|S|) of permutations, which is the group of isometries of the |S|-1 simplex in R^N where N = |S|-1.
So G is a subgroup of the orthogonal group O(N), and so its multiplication -- and that of the original semigroup S as well -- can be represented by matrix multiplication.
This I think I understand. But I see W. Edwin Clark says that matrix representation is possible for any finite semigroup at all, which would be very nice. I don't quite follow the reasoning, though.
--Dan
On Aug 19, 2014, at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This representation is not faithful in all cases. Suppose z in S and xy = z fpr all x,y. On Tue, Aug 19, 2014 at 11:12 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Dan, If S is a finite semigroup (just associative) make a vector space with dimension |S|. You can consider it the set of formal linear combinations of elements of S. Then multiplication by any element yields a linear map from the vector space to itself (and thus a matrix). This is faithful.
Victor
On Tue, Aug 19, 2014 at 7:47 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just in case for each element x, left multiplication by x
L_x: S -> S
is a permutation of S, then the set Q = {L_x | x in S}:
then by associativity L_x o L_y = L_(xy),
and so by tossing in any inverses L'_x not already included, and likewise for an identity element, the semigroup Q can be embedded in a group G of permutations on |S| elements.
G must be a subgroup of the full group Sym(|S|) of permutations, which is the group of isometries of the |S|-1 simplex in R^N where N = |S|-1.
So G is a subgroup of the orthogonal group O(N), and so its multiplication -- and that of the original semigroup S as well -- can be represented by matrix multiplication.
This I think I understand. But I see W. Edwin Clark says that matrix representation is possible for any finite semigroup at all, which would be very nice. I don't quite follow the reasoning, though.
--Dan
On Aug 19, 2014, at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Edwin, True. However if you look at the semigroup S^1 (add an extra element called 1, which acts is a right and left unit), then the representation is faithful. Victor On Tue, Aug 19, 2014 at 8:17 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
This representation is not faithful in all cases. Suppose z in S and xy = z fpr all x,y.
On Tue, Aug 19, 2014 at 11:12 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Dan, If S is a finite semigroup (just associative) make a vector space with dimension |S|. You can consider it the set of formal linear combinations of elements of S. Then multiplication by any element yields a linear map from the vector space to itself (and thus a matrix). This is faithful.
Victor
On Tue, Aug 19, 2014 at 7:47 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just in case for each element x, left multiplication by x
L_x: S -> S
is a permutation of S, then the set Q = {L_x | x in S}:
then by associativity L_x o L_y = L_(xy),
and so by tossing in any inverses L'_x not already included, and likewise for an identity element, the semigroup Q can be embedded in a group G of permutations on |S| elements.
G must be a subgroup of the full group Sym(|S|) of permutations, which is the group of isometries of the |S|-1 simplex in R^N where N = |S|-1.
So G is a subgroup of the orthogonal group O(N), and so its multiplication -- and that of the original semigroup S as well -- can be represented by matrix multiplication.
This I think I understand. But I see W. Edwin Clark says that matrix representation is possible for any finite semigroup at all, which would be very nice. I don't quite follow the reasoning, though.
--Dan
On Aug 19, 2014, at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Good point, Victor. But is there not some trick that will always represent the original semigroup S faithfully on some family of square matrices (preferably over R) ? The non-faithfulness comes precisely when L_x for L_y where x != y. I tried a few obvious possibilities, but retaining which element x is for L_x, even when Lx = L_y for x != y, makes it difficult for the matrices to remain closed under multiplication. But it seems as if enlarging the vector space from F^|S| to F^(2|S|) ought to provide enough flexibility to do it. --Dan On Aug 19, 2014, at 9:12 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Edwin, True. However if you look at the semigroup S^1 (add an extra element called 1, which acts is a right and left unit), then the representation is faithful.
Victor
On Tue, Aug 19, 2014 at 8:17 PM, W. Edwin Clark <wclark@mail.usf.edu> wrote:
This representation is not faithful in all cases. Suppose z in S and xy = z fpr all x,y.
On Tue, Aug 19, 2014 at 11:12 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Dan, If S is a finite semigroup (just associative) make a vector space with dimension |S|. You can consider it the set of formal linear combinations of elements of S. Then multiplication by any element yields a linear map from the vector space to itself (and thus a matrix). This is faithful.
Victor
On Tue, Aug 19, 2014 at 7:47 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just in case for each element x, left multiplication by x
L_x: S -> S
is a permutation of S, then the set Q = {L_x | x in S}:
then by associativity L_x o L_y = L_(xy),
and so by tossing in any inverses L'_x not already included, and likewise for an identity element, the semigroup Q can be embedded in a group G of permutations on |S| elements.
G must be a subgroup of the full group Sym(|S|) of permutations, which is the group of isometries of the |S|-1 simplex in R^N where N = |S|-1.
So G is a subgroup of the orthogonal group O(N), and so its multiplication -- and that of the original semigroup S as well -- can be represented by matrix multiplication.
This I think I understand. But I see W. Edwin Clark says that matrix representation is possible for any finite semigroup at all, which would be very nice. I don't quite follow the reasoning, though.
--Dan
On Aug 19, 2014, at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let S be a semigroup of order n. Define the semigroup S^1 = S union {e} where e is not in S. Define e^2=e and ex = x = xe for all x in S. Then S^1 is a semigroup with identity e. Let V be a vector space (over any field F) of dimension n+1, and identify S^1 with a basis of V. Define f:S->End(V) (essentially (n+1)x(n+1) matrices over F) by f(s)(x) = sx. Clearly f is a homomorphism and if f(s) = f(t) then f(s)(1) = f(t)(1) so s = t and f is 1-1. If S already has an identity you don't need to embed it into a monoid. Note that the image of f (as matrices) aconsists of 0,1 matrices. --Edwin On Tue, Aug 19, 2014 at 10:47 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just in case for each element x, left multiplication by x
L_x: S -> S
is a permutation of S, then the set Q = {L_x | x in S}:
then by associativity L_x o L_y = L_(xy),
and so by tossing in any inverses L'_x not already included, and likewise for an identity element, the semigroup Q can be embedded in a group G of permutations on |S| elements.
G must be a subgroup of the full group Sym(|S|) of permutations, which is the group of isometries of the |S|-1 simplex in R^N where N = |S|-1.
So G is a subgroup of the orthogonal group O(N), and so its multiplication -- and that of the original semigroup S as well -- can be represented by matrix multiplication.
This I think I understand. But I see W. Edwin Clark says that matrix representation is possible for any finite semigroup at all, which would be very nice. I don't quite follow the reasoning, though.
--Dan
On Aug 19, 2014, at 6:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry, one additional question: 3. how constraining is associativity, in the sense of reducing the number of different operators? E.g., commutativity cuts out nearly half of the degrees of freedom; what % of the degrees of freedom does associativity cut out ? At 06:02 PM 8/19/2014, Henry Baker wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
participants (6)
-
Allan Wechsler -
Dan Asimov -
Gareth McCaughan -
Henry Baker -
Victor Miller -
W. Edwin Clark