# Representation for idempotent semiring

I have a semi-ring whose multiplication is non-commutative, and addition is idempotent. That is, $ab \neq ba$ and $a + a = a$.

The semi-ring is freely generated from a finite set $\Sigma$, the semi-ring itself would be of infinite rank.

We can also assume $\times$ distributes into $+$ from the left (or right, doesn't matter). There are also the usual identity elements 0 and 1.

How may I construct matrix representations for it? What would be the constraints for those matrices? Can someone give a simple example?

• What other information do you have about the semiring? You certainly can't construct a matrix representation just from what you have given. Mar 18, 2013 at 19:24
• Do I need to say that multiplication distributes into addition (from both sides), and that there are 0 and 1 as identity elements of + and $\times$ respectively? Mar 18, 2013 at 20:21
• Aren't those things part of the definition of a semiring? So are the only facts you know about your structure that it is a semiring with non-commutative addition and idempotent multiplication? In that case I suppose you can abstractly say something about a matrix representation for it, but you of course can't explicitly construct one, since you don't actually have an explicit object to start with. Mar 18, 2013 at 22:04
• But I don't understand if the matrix addition and multiplication would correspond to the same operations on the semi-ring. Seems that at least addition would be different? Mar 18, 2013 at 23:15
• I doubt you want to allow the matrix entries to be from a semiring. Otherwise the trivial representation by $1\times 1$ matrices would work. =] Mar 19, 2013 at 15:28

## 1 Answer

I am not sure whether it is possible to find a matrix representation but since there was no answer for over a year, let me just mention two possibly useful facts.

Let $A$ be a finite set. Then the free idempotent semiring generated by $A$ appears to be $\mathbb{B}\langle A\rangle$, the set of non-commutative polynomials (with variables in $A$) over the Boolean semiring $\mathbb{B}$. Equivalently, it is the semiring of finite languages over the alphabet $A$.

Now, there is a well-known embedding of the free monoid $A^*$ into the set of $2 \times 2$ matrices with coefficients in $\mathbb{N}$ and determinant $1$, given by $$a \to \begin{pmatrix}1&1\\0&1\end{pmatrix} \qquad b \to \begin{pmatrix}1&0\\1&1\end{pmatrix}$$ That being said, I don't see how to extend this embedding to $\mathbb{B}\langle A\rangle$...

• Thanks for your answer. What is meant by the boolean semi-ring $\mathbb{B}$? Aug 30, 2014 at 8:26
• Also, is your example of free monoid A* generated by only 2 elements, $a$ and $b$? Aug 30, 2014 at 8:27
• Right, but you can in turn embed any free monoid with a countable basis $B = \{a_n \mid n \in \mathbb{N} \}$ by sending $a_k$ to $a^kb$. Aug 30, 2014 at 10:50
• PS: I found this definition: an associative ring R (maybe without identity) is called a Boolean ring if each of its element $a \in R$ is an idempotent, ie, $a^2 = a$. Aug 30, 2014 at 14:10