Primal identity in matrix semigroup

Question

Given a finite set of matrix $\{M_1,M_2,\cdots,M_n\}\subseteq \mathbb{C}^{d\times d}$, we consider the semigroup generated by matrix product.

We call $s_1\cdots s_k$ an identity index if $M_{s_1}M_{s_2}\dotsm M_{s_k}=I$.

Of course, the identity indices form a monoid by concatenating strings.

This monoid provides a set of elimination rules: a string $t_1\cdots t_r$ contains an identity index as its substring, then we eliminate this substring to get a shorter string.

We call an identity index not prime if it can be generated through concatenating shorter identity indices and applying elimination rules according to other identity indices. More precisely, $z$ is not prime if there is an identity $a$ and $z=xay$ for some $x$ and $y$.

Is there a finite characterization of this monoid?

Answer 1

This is more of a comment than an answer since I am not 100% clear on the question since I'm not sure exactly what you mean by "a finite characterization of this monoid".

A general fact, that may be helpful, is that if $A^*$ is a free monoid on $A$, and $\psi\colon A^*\to M$ is a monoid homomorphism, then $K=\psi^{-1}(1)$ is a free monoid on those elements of $A^+$ (the free semigroup on $A$) that map to $1$ and cannot be factored as a product of nonempty words mapping to $1$.

The proof of my claim is part of the theory of codes and can be found in the book of Berstel and Reutenauer. Retaining the above notation, let $P$ be the set of nonempty elements of $K$ which do not factor as a product of two nonempty elements of $K$. Then $P$ is what is called a bifix (or in old terminology biprefix) code. This means that no two distinct elements of $P$ are either a prefix or a suffix of each other. This follows because $K$ is a unitary submonoid of $A^*$. This means that if $u,uv\in K$, then $v\in K$ and if $u,wu\in K$, then $w\in K$, as can be seen by applying $\psi$. Hence if $u$ has a proper, nonempty prefix or suffix in $K$, then $u$ can be factored in $K$.

One can then uniquely factor any element of $K$ as a product of elements of $P$ recursively as follows. First note that if $w\in K$ is nonempty, then $w$ has a unique prefix (possibly $w$ itself) belonging to $P$, namely its shortest nonempty prefix $u$ belonging to $K$. The uniqueness follows since elements of $P$ are prefix incomparable. Then $w=uv$ with $u\in P$ uniquely determined and $v\in K$ since $K$ is unitary. So $v$ can recursively be uniquely written as a product of elements of $P$. Once could alternatively find this factorization starting from the right using that $P$ is bifix.

Notice I didn't take into account your elimination rules. Any prime element if your sense must belong to $P$. But it is possible an element of $P$ has a factor in $K$. But if $w\in P$ and $w=xky$ with $k\in K$, then $xy\in K$. And in fact, $xy\in P$ because if not, then either a proper prefix of $x$ or a proper suffix of $y$ belongs to $P$ contradicting that $P$ is a bifix code. So if you add relations saying that $w\approx xy$ if $w=xky$ with $k\in K$ corresponding to your elimination rules, you will still get a free monoid since all the words you identify are length $1$ with respect to the alphabet $P$ (but I am not sure if two prime words might be equivalent).