Completely Simple Semigroups,Lie Algebras,and the Road Coloring Problem

Consider a semigroup generated by matrices associated with an edge-coloring of a strongly connected, aperiodic digraph. We call the semigroup Lie-solvable if the Lie algebra generated by its elements is solvable. We show that if the semigroup is Lie-solvable then its kernel is a right group. Next, we study the Lie algebra generated by the kernel. Lie algebras generated by two idempotents are analyzed in detail. We find that these have homomorphic images that are generalized quaternion algebras. We show that if the kernel is not a direct product, then the Lie algebra generated by the kernel is not solvable by describing the structure of these algebras. Finally, we discuss an infinite class of examples that are shown to always produce strongly connected aperiodic digraphs having kernels that are not right groups.