Identity Problem for Unitriangular Matrices of Dimension Four

Abstract

The Identity Problem in semigroup algorithmic theory asks the following: Given as input a set of square matrices $G = \{A_1, A_2, ..., A_k\}$, does the semigroup generated by G contain the identity matrix $I$? The Identity Problem has been shown to be undecidable even when restricted to matrices of low dimensions. For example, Bell et al. showed its undecidability for matrices in $SL(4, Z)$. Some decidability results for the Identity Problem include its NP-completeness for matrices in $SL(2, Z)$, as well as its PTIME decidability in the Heisenberg group $H_3$. In this talk, we show a decidability result of the Identity Problem for matrices in the group $UT(4, Z)$ of unitriangular integer matrices of dimension four. Some of the techniques used for this result may be generalized to tackle higher dimensional unipotent groups.

Bio

Ruiwen DONG is currently a PhD student in Computer Science at the University of Oxford. He obtained his MsC from Ecole Polytechnique, France, and his BsC from Peking University, China. His main areas of interests include semigroup algorithmic problems, rings and algebra, as well as symbolic computing.
Find his website here.