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