Geometry and algorithms for upper triangular tropical matrix identities

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.