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