I was working on a problem with a friend where we were given two 5×5 matrices $A$ and $B$ with entries in $\{0, 1, -1\}$, which must generate a semigroup (under matrix multiplication) of order $>800$.
On the theory side of things, the principle is that we want
$$
f(i_1, i_2, i_3, \cdots) = A^{i_1}B^{i_2}A^{i_3}\cdots = \prod_{i=1}^\infty A^{i_{2n-1}}A^{i_{2n}}
$$
to have finite range, mapping $\mathbb{N}^\mathbb{N}\to \mathbb{M}_{5\times 5}(\mathbb Z)$ (there is no restriction on the entries of matrices in the semigroup, only on the entries of the generators $A$ and $B$). We tried toying arround with the ideas of nilpotent matrices, idempotent matrices, relationships between $A$ and $B$, but couldn't come up with any explicit theory or any guiding principles for how we should choose $A$ and $B$.
There are some minor facts we know. Clearly, $\det(A),\det(B)\in\{0,1,-1\}$ otherwise there will be an infinite number of distinct powers $A^n$ and $B^n$. Also, there clearly need to be a finite number of powers of $A$ and $B$, so they're either nilpotent, eventually idempotent, or something else, but then we're not sure what to do to check combinations of $A$ and $B$.
EDIT: As it turns out, the only reason our code below terminated for those $A$ and $B$ was because of an integer overflow error. As far as we can tell, it seems like those $A$ and $B$ actually generate an infinitely large semigroup, though I haven't rigorously proven it.
In this section, the semigroup generated by $A$ and $B$ is NOT finite.
Then we plugged in the following $A$ and $B$ into a python program that calculated the size of the semigroup generated by them:
$$
A = \left[\begin{matrix}
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & -1 & 0 & -1 & 0 \\
0 & 0 & 1 & -1 & 1 \\
0 & 0 & 0 & 0 & 0
\end{matrix}\right]\quad B = \left[\begin{matrix}
0 & -1 & 0 & -1 & 0 \\
-1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & -1 \\
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0
\end{matrix}\right]
$$
I'm not sure how he came up with these bad boys, he didn't really have a theory for why he chose them, but apparently they generate a semigroup with 12427 elements.
Now, we can observe a few things about these matrices:
- $A^4 = A$
- $B^3 = B^4$ (so $B^3 = B^4 = B^5 = \cdots$)
- $(AB)^3 = 0$
- $(BA)^4 = 0$
You can keep going generating interesting properties of these two matrices, but bottom line we're not sure why in general there are only a finite number of products of $A$ and $B$. It seems like you'd have to check a bunch of different edge cases. For example, we may know the nilpotency/idempotency of $A^i B^j$ for $i < 4, j < 3$, but how would you determine that
$$
f(i_1, j_1, i_2, j_2, i_3, j_3, …)
$$
where $(i_k, j_k)_{k=1}^\infty \in \{1, 2, 3\}\times\{1, 2\}$ is an arbitrary sequence, has a finite range? I suppose you could check something how, if you restrict the sequences $(i_k, j_k)$ such that a specific pair $(i_{k'}, j_{k'})$ doesn't repeat more than the nilpotency/idempotency of $A^{i_{k'}}B^{j_{k'}}$, then there's only a finite number of sequences you can choose, but this seems like a really difficult/roundabout way of proving this. Also, this doesn't give any insight into how you choose $A$ and $B$.
Can anyone provide any insight into this? Why do the matrices $A$ and $B$ work, and how would you choose other $A$ and $B$ in general?
EDIT 2: I've determined the following identity involving $A$ and $B$. Let $Z = B^2A^2BA$, and $C = B^3A^2$. Then $ZC^k$ is zero except the middle row (third row) is
$$
\text{Row}_3(ZC^k) = \left[\begin{matrix}-(-2)^{k+1} & (-2)^k & -(-2)^{k+1} & -(-2)^k & -(-2)^{k+1}\end{matrix}\right]
$$
which is unbounded. Of course, there are probably other simpler relationships, this is just the first one we found via computer.
EDIT 3: Another friend showed us a different approach. We can fairly easily brute force search for $A, B\in \mathbb{M}_{2\times 2}(\{0, 1, -1\})$ (there are only 6561 = (3^4)^2 choices) such that the semigroup generated by $A$ and $B$ is finite, then extend these to $5\times 5$ matrices in block format:
$$
A_{5\times 5} = \left[\begin{matrix}A & O \\ O & I\end{matrix}\right],\qquad B_{5\times 5} = \left[\begin{matrix}B & O \\ O & I\end{matrix}\right]
$$
Though this works to generate such a semigroup, my problem with it is that it doesn't give us any insight into the choice of $A$ and $B$ either; it still requires us to brute force search. If, for example, we were forced to find $A$ and $B$, $5\times 5$, that generate a semigroup with order greater than any finite semigroup of $2\times 2$ or $3\times 3$ matrices, we would still be lost. Hence, I'm still curious about the theory behind choosing $A$ and $B$.
Best Answer
Let me give a partial answer to your very interesting question. One can effectively decide whether the semigroup generated by a finite set of matrices with coefficients in $\mathbb{Z}$ (or even in $\mathbb{Q}$) is finite or not. The reference is [1] (or [2]) and this is a nontrivial result.
It is also known that the semigroup is finite if and only if every of its elements generate a finite semigroup (that is, have finitely many distinct powers), see [4]. Note that this condition does not suffice to decide whether the semigroup is finite.
You will also find some detailed information on the corresponding problem for groups of matrices in [3].
[1] Jacob, Gérard. Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. (French) Theoret. Comput. Sci. 5 (1977/78), no. 2, 183--204.
Abstract: Let $S$ be a finite set of matrices over a commutative field $K$. We give here an algorithm which decides whether the matrix semigroup $H$ generated by $S$ is finite; and in that case, our algorithm computes the cardinality of $H$.
[2] Jacob, Gérard. La finitude des représentations linéaires des semi-groupes est décidable. (French) J. Algebra 52 (1978), no. 2, 437--459.
[3] Kuzmanovich, James and Pavlichenkov, Andrey, Finite Groups of Matrices Whose Entries Are Integers, The American Mathematical Monthly, 109, No. 2 (Feb., 2002), 173--186.
[4] McNaughton, Robert; Zalcstein, Yechezkel. The Burnside problem for semigroups. J. Algebra 34 (1975), 292--299.