Geometry and algorithms for upper triangular tropical matrix identities

Research output: Contribution to journalArticlepeer-review

Abstract

We provide geometric methods and algorithms to verify, construct and enumerate pairs of words (of specified length over a fixed m-letter alphabet) that form identities in the semigroup UT_n(T) of n x n upper triangular tropical matrices. In the case n = 2 these identities are precisely those satisfied by the bicyclic monoid, whilst in the case n = 3 they form a subset of the identities which hold in the plactic monoid of rank 3. To each word we associate a signature sequence of lattice polytopes, and show that two words form an identity for UT_n(T) if and only if their signatures are equal. Our algorithms are thus based on polyhedral computations and achieve optimal time complexity in some cases. For n = m = 2 we prove a Structural Theorem, which allows us to quickly enumerate the pairs of words of fixed length which form identities for UT_2(T). This allows us to recover a short proof of Adjan's theorem on minimal length identities for the bicyclic monoid, and to construct minimal length identities for UT_3(T), providing counterexamples to a conjecture of Izhakian in this case. We conclude with six conjectures at the intersection of semigroup theory, probability and combinatorics, obtained through analysing the outputs of our algorithms.

Bibliographical metadata

Original languageEnglish
JournalJournal of Algebra
Early online date1 Apr 2019
DOIs
Publication statusPublished - 2019