Identities in unitriangular and gossip monoids

Abstract

We establish a criterion for a semigroup identity to hold in the monoid of $n\times n$ upper unitriangular matrices with entries in a commutative semiring $S$. This criterion is combinatorial modulo the arithmetic of the multiplicative identity element of $S$. In the case where $S$ is idempotent, the generated variety is the variety ${\mathbf{J}}_{\mathbf{n}-1}$, which by a result of Volkov is generated by any one of: the monoid of unitriangular Boolean matrices, the monoid $R_n$ of all reflexive relations on an $n$ element set, or the Catalan monoid $C_n$. We propose $S$-matrix analogues of these latter two monoids in the case where $S$ is an idempotent semiring whose multiplicative identity element is the `top' element with respect to the natural partial order on $S$, and show that each generates ${\mathbf{J}}_{\mathbf{n}-1}$. As a consequence we obtain a complete solution to the finite basis problem for lossy gossip monoids.

14 pages