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?

  • $\begingroup$ What other information do you have about the semiring? You certainly can't construct a matrix representation just from what you have given. $\endgroup$
    – Tara B
    Mar 18, 2013 at 19:24
  • $\begingroup$ 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? $\endgroup$ Mar 18, 2013 at 20:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tara B
    Mar 18, 2013 at 22:04
  • $\begingroup$ 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? $\endgroup$ Mar 18, 2013 at 23:15
  • 1
    $\begingroup$ 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. =] $\endgroup$
    – Tara B
    Mar 19, 2013 at 15:28

1 Answer 1


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$...

  • $\begingroup$ Thanks for your answer. What is meant by the boolean semi-ring $\mathbb{B}$? $\endgroup$ Aug 30, 2014 at 8:26
  • $\begingroup$ Also, is your example of free monoid A* generated by only 2 elements, $a$ and $b$? $\endgroup$ Aug 30, 2014 at 8:27
  • 1
    $\begingroup$ 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$. $\endgroup$
    – J.-E. Pin
    Aug 30, 2014 at 10:50
  • $\begingroup$ 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$. $\endgroup$ Aug 30, 2014 at 14:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .