Identities in upper triangular tropical matrix semigroups and the bicyclic monoid (Q1703232)

The tropical semiring \(\mathbb{T}\) is the semiring with underlying set \(\mathbb{R} \cup \{ -\infty\}\) whose binary operations are defined for all \(a, b \in \mathbb{T}\) by \(a\oplus b= \max(a, b)\) and \(a\otimes b= a+ b\). The semigroup \(UT_n(\mathbb{T})\) is the set of all \(n\times n\) matrices with entries in \(\mathbb{T}\) such that all entries below the main diagonal are \(-\infty\) (often considered as the zero element of \(\mathbb{T}\)) whose binary operation is the matrix multiplication induced from the operation \(\oplus\) and \(\otimes\). In this paper, a necesssary sufficient condition for a semigroup identity to hold in \(UT_n(\mathbb{T})\) is provided by analysing a more general class of semigroups called chain structured tropical matrix semigroups. A polynomial time algorithm to check if an identity holds in \(UT_n(\mathbb{T})\) is also given. This is applied to the bicyclic monoid after showing that the bicyclic monoid and \(UT_2(\mathbb{T})\) satisfy the same semigroup identities. A faithful representation of the free monogenic inverse semigroup by \(UT_3(\mathbb{T})\) is also studied.