3
$\begingroup$

I was working on a problem with a friend where we were given two 5x5 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$.

$\endgroup$
  • $\begingroup$ Just to be sure: (a) Should the entry "-" in $A$ be $-1$? (b) Do your matrices have entries in $\mathbb{Z}$? (c) What is exactly your question: are you looking for very large finite semigroups of this form and do you want to decide whether the semigroup generated by $A$ and $B$ is finite (given $A$ and $B$ as input)? $\endgroup$ – J.-E. Pin Nov 6 '18 at 17:38
  • $\begingroup$ @J.-E.Pin (a) yes thank you. (b) the elements in the semigroup can have elements in $\mathbb{Z}$, I'll edit that too. (c) I'm curious how to choose $A$ and $B$ to produce large semigroups. What properties of $A$ and $B$ can we exploit to get a semigroup of order $>800$ for example. $\endgroup$ – user3002473 Nov 6 '18 at 17:51
  • $\begingroup$ @J.-E.Pin Also we've determined that the code terminates due to an issue with integer overflow, so the semigroup generated by said $A$ and $B$ might not actually be finite, but it seems like the choice of $A$ and $B$ to satisfy a number of nilpotency/idempotency relations is the right direction to go in. $\endgroup$ – user3002473 Nov 6 '18 at 17:52
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesing works! I guess I'll have to find someone who speaks French. The origin of this question is a bonus question from a computer science assignment, so considering that the general case presented in that first paper is nontrivial, I suppose the expected solution is indeed the far less interesting "restricted brute-force" solution. I'll continue looking into the problem in the literature, however. Thank you! $\endgroup$ – user3002473 Nov 6 '18 at 18:59
  • $\begingroup$ can you clarify the seeming contradiction of saying that "the semigroup is finite if and only if every of its elements generate a finite semigroup" along with "this condition does not suffice to decide whether the semigroup is finite"; is this a necessary and sufficient condition or not? $\endgroup$ – Morgan Rodgers Nov 6 '18 at 19:05
  • $\begingroup$ @morgan-rodgers It is a necessary and sufficient condition, but in order to use it in an algorithm, you need to inspect all the elements of the semigroup, so it does not really help if you don't know how to bound the length of the products. This is however a strong property, related to the Burnside problem. $\endgroup$ – J.-E. Pin Nov 6 '18 at 19:18
  • $\begingroup$ Ah okay, so the condition does suffice to decide whether the semigroup is finite, it is just not the most practical to implement and test. Thank you for the clarification. $\endgroup$ – Morgan Rodgers Nov 6 '18 at 19:20
  • $\begingroup$ @morgan-rodgers No, because if the semigroup is infinite, you will never conclude. You just have a semi-algorithm. $\endgroup$ – J.-E. Pin Nov 6 '18 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.