Revisiting Finiteness of Matrix Monoids

Ait El Manssour, Rida; Guttenberg, Roland; Lhote, Nathan; Shirmohammadi, Mahsa; Worrell, James Ben

doi:10.4230/LIPIcs.ICALP.2026.158

Revisiting Finiteness of Matrix Monoids

Rida Ait El Manssour

University of Oxford, UK Roland Guttenberg

University of Warsaw, Poland Nathan Lhote

Aix-Marseille Université, LIS, France Mahsa Shirmohammadi

CNRS & IRIF, Paris, France James Ben Worrell

University of Oxford, UK

Abstract

This paper concerns decision problems related to finite monoids of rational matrices. We show that determining finiteness of a given finitely presented monoid is in PSpace, improving the known $\textsc{coNExp}^{\textsc{NP}}$ bound. We also show that the membership problem for finite matrix monoids is PSpace-complete, improving the known NExp-upper bound. Our two complexity results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids. This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras and of matrix monoids. Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices.

Keywords and phrases:

Matrix Semigroups, Finiteness, Integrality, Bitsize Bound

Category:

Track B: Automata, Logic, Semantics, and Theory of Programming

Funding:

Rida Ait El Manssour: Supported by the EPSRC Fellowship (EP/X033813/1).

Roland Guttenberg: Supported by the ERC grant INFSYS, agreement No. 950398.

Mahsa Shirmohammadi: Supported by the ERC Synergy Grant VePaSS (agreement No. 101224640) and the grant VeSyAM (ANR-22-CE48-0005).

James Ben Worrell: Supported by the EPSRC Fellowship (EP/X033813/1).

Copyright and License:

© Rida Ait El Manssour, Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi,
and James Ben Worrell; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Automata over infinite objects

DOI:

10.4230/LIPIcs.ICALP.2026.158

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

1.1 Main Results

The study of decision problems for matrix monoids – and their connections with automata theory – has a long history, spanning more than sixty years; see [13, 3] for a comprehensive survey. The connection between automata and monoids arises from the fact that the transition maps of automata give rise to matrix monoids with entries in a semiring. A particularly important instance is weighted automata over the field $\mathbb{Q}$ of rational numbers. In this setting, questions about the support and the growth of the formal series recognised by weighted automata reduce to questions about finitely generated matrix monoids over $\mathbb{Q}$ . In this paper we revisit several classical decision problems for monoids of rational matrices and obtain new complexity results.

We consider the following three problems, in which the input monoid is specified with a positive integer $d$ and a finite set of matrices $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ generating a monoid $X^{*}$ .

1.

Finiteness Problem: given $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , determine whether $X^{*}$ is finite.
2.

Finite Membership Problem: given $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ and a target matrix $a$ , determine whether $a\in X^{*}$ , under the promise that $X^{*}$ is finite.
3.

Integrality Problem: given $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , determine whether $X^{*}$ is conjugate to a matrix monoid with integer entries.

Our first main result shows that the Finiteness Problem is in PSpace, improving the $\textsc{coNExp}^{\textsc{NP}}$ upper bound of [4, Theorem 13]. Our second main result establishes that the Finite Membership Problem is PSpace-complete. The PSpace upper bound improves the NExp bound of [4, Theorem 14], and we provide a matching PSpace lower bound. A key technical ingredient underlying both upper bounds is a polynomial bound (in the input size of the generators) on the bitsize of matrix entries appearing in finite monoids. Using tools developed for these two results, we further show that both the decision and function versions of the Integrality Problem can be solved in polynomial time.

1.2 Context and Related Work

Finiteness is decidable in polynomial time for subgroups of the group $\mathrm{GL}_{d}(\mathbb{Q})$ of invertible matrices in $\mathrm{M}_{d}(\mathbb{Q})$ . If a finite subgroup has generators with integer entries of absolute value at most $M$ , the entries of every matrix in the group have absolute value at most $M^{d^{2}}d^{3d^{2}+3}$ [2, Theorem 1.1]. Finiteness is also decidable in polynomial time for finitely generated submonoids of $\mathrm{M}_{d}(\mathbb{N})$ . If such a monoid is finite then it consists of matrices whose entries are at most $M^{d-1}5{d/2}d^{d}$ [18, Theorem A.2], where $M$ is the maximum entry of a generator of the monoid.

The decidability of the Finiteness Problem for matrix monoids over the rationals was first shown by McNaughton and Zalcstein [12], who proved that a finitely generated matrix monoid is infinite if and only if it contains an element of infinite order. This characterization implies that infiniteness is recursively enumerable and hence that finiteness is decidable (since finiteness is also recursively enumerable). Subsequently, Mandel and Simon [11] and Jacob [8] gave effective, albeit non-elementary, bounds on the cardinality of a finitely generated submonoid of $\mathrm{M}_{d}(\mathbb{Q})$ in terms of the dimension $d$ and the number of generators.

The first elementary bound was obtained only recently, in [4], which shows that the cardinality is bounded by $m^{2^{O(d^{2}\log d)}}$ , where $d$ is the dimension and $m$ is the number of generators. This cardinality bound was obtained from a diameter bound [4, Theorem 1]: every element of a finite monoid can be expressed as a product of generators of length at most $2^{d(2d+3)}g(d)^{d+1}$ , where $g(d)\leq 2^{d}d!$ is the maximum order of a finite subgroup of $\mathrm{GL}_{d}(\mathbb{Q})$ . This bound is obtained using multilinear algebra and a graph construction, previously used to compute the Zariski closure of a finitely generated matrix monoid [7]. In this paper we reformulate the main technical result of [4] in terms of factorisation forests, from which the diameter bound follows directly.

On the other hand, the non-elementary cardinality bounds of [8, 11] proceed by reducing the general case to that of irreducible monoids. Recall that a matrix monoid $M\subseteq\mathrm{M}_{d}(\mathbb{Q})$ is irreducible if the only subspaces of $\mathbb{Q}^{d}$ invariant under all matrices in $M$ are $\left\{0\right\}$ and $\mathbb{Q}^{d}$ . Schützenberger showed that such a monoid, if finite, has cardinality at most $(2d+1)^{d^{2}}$ [15]. This bound has very recently been improved to $3^{d^{2}}$ , with an almost matching lower bound of $2^{\lfloor{d^{2}}/4\rfloor}$ [10, 17]. To lift bounds from irreducible monoids to general monoids, Berstel and Reutenauer use a change of basis that simultaneously puts all matrices in upper block triangular form, with square diagonal blocks, such that the monoid generated by the matrices appearing in each diagonal block is irreducible [3, Chapter 9, Theorem 1.1]. This lifting argument depends only on the existence of such a change of basis, not on its effective computation. Indeed, Berstel and Reutenauer [3] posed as an open problem the decidability of irreducibility, i.e. whether the above normal form consists of a single block. In fact, a procedure for determining irreducibility had already been given by [14]. Nevertheless, determining irreducibility and computing the above-mentioned upper block triangular form is still not known to be doable in polynomial time.

The improved cardinality bounds and complexity results in this paper exploit a combination of a suitable variant of the approach of [3] with the diameter bound of [4]. We observe that the explicit bounds for irreducible finite matrix monoids extend to the broader class of monoids whose enveloping algebra is semisimple. We then lift these bounds to general matrix monoids by combining (i) an upper block triangular form based on the Wedderburn–Malcev decomposition of the enveloping algebra as a direct sum of a semisimple algebra and a nilpotent ideal with (ii) the diameter bound of [4]. In contrast to the reduction to upper block triangular form with irreducible blocks on the diagonal, as used in [3], the polynomial-time computability of the Wedderburn–Malcev decomposition is straightforward. For our approach it is essential that this decomposition admit a polynomial-size representation.

2 Preliminaries

We write $\mathrm{M}_{d,e}(R)$ for the set of $d\times e$ matrices with entries in a ring $R$ and denote by $\mathrm{M}_{d}(R):=\mathrm{M}_{d,d}(R)$ the set of square matrices of dimension $d$ . We denote the $d\times d$ identity matrix by $\mathrm{id}_{d}$ . Given $X,Y\subseteq\mathrm{M}_{d}(R)$ , we write $XY\subseteq\mathrm{M}_{d}(R)$ for the element-wise product and, for $r\in\mathbb{N}$ , we write $X^{r}$ for the $r$ -fold product of $X$ with itself. Note that $X^{0}=\{\mathrm{id}_{d}\}$ . We also write $X^{\leq r}:=\bigcup_{i=0}^{r}X^{i}$ and $X^{<r}:=\bigcup_{i=0}^{r-1}X^{i}$ . The submonoid of $\mathrm{M}_{d}(R)$ generated by $X$ is $X^{*}:=\bigcup_{i=0}^{\infty}X^{i}$ , while the subsemigroup generated by $X$ is $X^{+}:=\bigcup_{i=1}^{\infty}X^{i}$ .

For an invertible matrix $b$ , we denote by $\mathrm{cof}(b)$ the cofactor matrix of $b$ , that is, the $(i,j)$ -entry of $\mathrm{cof}(b)$ is $(-1)^{i+j}\det(c(i,j))$ where $c(i,j)$ denotes the matrix obtained from $b$ by deleting row $j$ and column $i$ . Then Cramer’s rule gives $b^{-1}=\frac{1}{\det(b)}\mathrm{cof}(b)^{T}$ .

2.1 Height of Matrices

Given a finite set of matrices $X\subseteq\mathrm{M}_{m,n}(\mathbb{Q})$ , and an integer $q$ , we say that $q$ is a common denominator of $X$ if $q\cdot X\subseteq\mathrm{M}_{m,n}(\mathbb{Z})$ . The height of $X$ is defined as:

\llbracket X\rrbracket=\max(m,n)\cdot q\cdot p

where $q$ is the least common denominator of $X$ and $p$ is the maximum absolute value of entries of elements of $q X$ .

In particular, for a reduced fraction $\frac{p}{q}$ seen as an element of $\mathrm{M}_{1}(\mathbb{Q})$ we have $\llbracket\frac{p}{q}\rrbracket=|pq|$ . The main idea is that the log of the height corresponds to (an upper bound of) the number of bits needed to represent entries of a matrix.

The height is submultiplicative with respect to matrix multiplication and satisfies a form of triangle inequality. Let $X\subseteq\mathrm{M}_{m,n}(\mathbb{Q})$ and $Y\subseteq\mathrm{M}_{n,\ell}(\mathbb{Q})$ be finite sets of matrices. Then:

\displaystyle\llbracket XY\rrbracket\leq\llbracket X\rrbracket\llbracket Y% \rrbracket\qquad\text{and}\qquad\llbracket\Sigma_{i=1}^{k}X\rrbracket\leq k% \llbracket X\rrbracket.

(1)

Indeed, observe that given $x_{1},\ldots,x_{k}\in X$ , the least common denominator of $(x_{1}+\ldots+x_{k})$ divides the one of $X$ . The triangle inequality for $|\cdot|$ then gives the property.

We relate below the height of a matrix with its inverse, which will prove useful:

Claim 1.

Let $d\geq 1$ and let $a\in\mathrm{GL}_{d}(\mathbb{Q})$ , then $\llbracket a^{-1}\rrbracket\leq\llbracket a\rrbracket^{2d}$ .

Proof.

Let $q$ be the least common denominator of $a$ and let $p$ be the maximum absolute value of entries of $b=qa$ . By Cramer’s rule, $b^{-1}=\frac{1}{\det(b)}\mathrm{cof}(b)^{T}$ . From the Hadamard bound, $\det(b)\leq d^{\frac{d}{2}}p^{d}$ . For the same reason, we have $\llbracket\mathrm{cof}(b)\rrbracket\leq dd^{\frac{d}{2}}p^{d}$ . Thus

\llbracket b^{-1}\rrbracket\,\leq\,\det(b)\,\llbracket\mathrm{cof}(b)% \rrbracket\,\leq\,dd^{d}p^{2d}\,.

Finally since $a^{-1}=qb^{-1}$ , we have by the scalar submultiplicative property that

\llbracket a^{-1}\rrbracket\,\leq\,q\llbracket b^{-1}\rrbracket\,\leq\,qd^{d+1% }p^{2d}\,\leq\,\llbracket a\rrbracket^{2d}\,.\

$\hfill\vartriangleleft$

2.2 Semisimplicity and the Jacobson Radical

A vector space $A\subseteq\mathrm{M}_{d}(\mathbb{Q})$ containing $\mathrm{id}_{d}$ is called an algebra if $A$ is closed under matrix multiplication. Given $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , the vector space spanned by $X^{\ast}$ , or equivalently the smallest algebra $E$ containing $X$ is called the enveloping algebra $\mathrm{Env}(X)$ . For example, let

a:=\begin{pmatrix}1&1\\ 0&0\end{pmatrix},\qquad b:=\begin{pmatrix}0&1\\ 0&1\end{pmatrix},\qquad X:=\{a,b\}.

Recall that $X^{*}$ denotes the submonoid generated by $X$ , which contains the identity matrix $\mathrm{id}_{2}$ . Direct computation gives

a^{2}=a,\qquad b^{2}=b,\qquad ab=\begin{pmatrix}0&2\\ 0&0\end{pmatrix},\qquad ba=0.

Hence $X^{*}=\left\{\mathrm{id}_{2},\,0,\,a,\,b,\,ab\right\}$ . Moreover, $ab=a+b-\mathrm{id}_{2}$ , and therefore

\mathrm{Env}(X)=\mathrm{Span}_{\mathbb{Q}}\left\{a,b,\mathrm{id}_{2}\right\}=% \left\{\begin{pmatrix}x&y\\ 0&z\end{pmatrix}\;\middle|\;x,y,z\in\mathbb{Q}\right\}.

A key notion when studying algebras is that of (nilpotent) ideals. A vector subspace $I\subseteq E$ is called an ideal if $E\cdot I=I=I\cdot E$ . An ideal $I$ is called nilpotent if there exists $d\in\mathbb{N}$ such that $I^{d}=\{0\}$ ; the smallest such exponent $d$ is called the nilpotency index of $I$ . In the above example, the sets

\displaystyle I_{1}=\left\{\begin{pmatrix}x&y\\ 0&0\end{pmatrix}\mid x,y\in\mathbb{Q}\right\}

\displaystyle I_{2}=\left\{\begin{pmatrix}0&y\\ 0&z\end{pmatrix}\mid y,z\in\mathbb{Q}\right\}

\displaystyle I_{3}=\left\{\begin{pmatrix}0&y\\ 0&0\end{pmatrix}\mid y\in\mathbb{Q}\right\}

are ideals, with $I_{3}$ being a nilpotent ideal of nilpotency index $2$ . Nilpotent ideals are a cause of complexity, but thankfully sets of strictly upper block triangular matrices like $I_{3}$ are (up to conjugation) the only examples of nilpotent ideals. In the following we repeat a proof of this fact, as it will be crucial in our size bounds for finite monoids, but we require some development first.

The trace $\mathrm{tr}(a)$ of $a\in\mathrm{M}_{d}(\mathbb{Q})$ is the sum of the diagonal entries of $a$ . An algebra $E\subseteq\mathrm{M}_{d}(\mathbb{Q})$ is called semisimple if $\{0\}$ is its only nilpotent ideal. We define $J(E):=\{a\in E\mid\forall b\in E\colon\mathrm{tr}(ab)=0\}$ and have the following classical theorem of Dickson [6].

Theorem 2.

The set $J(E)$ is a nilpotent ideal and the quotient $E/J(E)$ is semisimple.

Theorem 2 implies that $J(E)$ is the largest nilpotent ideal, that is, $J(E)$ is identical to the Jacobson radical of $E$ . In Section 2.3 and Section 3.1 we will recall a proof of the fact that $J(E)$ can be effectively conjugated to strictly upper block triangular matrices, hence establishing that indeed nilpotent ideals are strictly upper block triangular. To this end, we have to compute a basis of $J(E)$ as follows. Let $B=\{b_{1},\ldots,b_{k}\}\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , with $k\leq d^{2}$ , be a basis of $E$ . Define the $\mathbb{Q}$ -linear trace map $\mathrm{Tr}_{B}\colon E\to\mathbb{Q}^{k}$ by

\mathrm{Tr}_{B}(a):=(\mathrm{tr}(ab_{1}),\ldots,\mathrm{tr}(ab_{k}))\,.

With respect to the basis $B$ on $E$ this map is represented by the trace matrix

T_{B}=(\mathrm{tr}(b_{i}b_{j}))_{1\leq i,j\leq k}

(2)

We have $ker(\mathrm{Tr}_{B})=J(E)$ : Indeed, since the trace $\mathrm{tr}$ is a linear map, $\mathrm{tr}(ab_{1})=\dots=\mathrm{tr}(ab_{k})=0$ implies for all $b=\sum_{i=1}^{k}\lambda_{i}b_{i}\in E$ that

\mathrm{tr}(ab)=\mathrm{tr}\left(a\sum_{i=1}^{k}\lambda_{i}b_{i}\right)=\sum_{% i=1}^{k}\lambda_{i}\mathrm{tr}(ab_{i})=0.

2.3 Block Decompositions of Matrices

A filtration of the vector space $\mathbb{Q}^{d}$ is a strictly increasing sequence of subspaces

\displaystyle\{0\}=W_{0}\subset W_{1}\subset\cdots\subset W_{k}=\mathbb{Q}^{d}\,.

(3)

We say that a basis $B=\{v_{1},\ldots,v_{d}\}$ of $\mathbb{Q}^{d}$ is adapted to the filtration (3) if it arises as the disjoint union of bases of subspaces $V_{1},\ldots,V_{k}\subseteq\mathbb{Q}^{d}$ such that $W_{i}=V_{1}\oplus\cdots\oplus V_{i}$ for $i\in\{0,\ldots,k\}$ . Such an adapted basis can be constructed by first choosing a basis of $W_{1}$ , and then successively extending a basis of $W_{i}$ to a basis of $W_{i+1}$ , for $i=1,\ldots,k-1$ . An algebra $E\subseteq\mathrm{M}_{d}(\mathbb{Q})$ is said to preserve the filtration (3) if $E\cdot W_{i}\subseteq W_{i}$ for all $i\in\{0,\ldots,k\}$ . In such a case, let $p\in\mathrm{M}_{d}(\mathbb{Q})$ be the matrix whose columns are given by $B$ . Then for all $b\in E$ the matrix $a:=p^{-1}bp$ has the upper block triangular form

a=\begin{pmatrix}a_{1,1}&a_{1,2}&\dots&a_{1,k}\\ 0&a_{2,2}&\dots&a_{2,k}\\ \vdots&0&\ddots&\vdots\\ 0&\dots&0&a_{k,k}\end{pmatrix},

where $a_{i,j}$ has dimension $d_{i}\times d_{j}$ for $j\geq i$ , where $d_{i}=\dim(V_{i})$ and $d_{j}=\dim(V_{j})$ . Here we say that $(d_{1},\ldots,d_{k})$ is the signature of the block decomposition of $a$ .

Note that if $E=\mathrm{Env}(X)$ is the enveloping algebra of a set of matrices $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , then for an invertible matrix $p\in\mathrm{M}_{d}(\mathbb{Q})$ , the conjugated algebra $p^{-1}Ep$ is in upper block triangular form if and only if $p^{-1}Xp$ is upper block triangular.

3 Structure Theory of Matrix Monoids and Algebras

In this section we give convenient formulations of known results concerning, respectively, the structure of matrix monoids and their enveloping algebras, that are key ingredients of the main results of this paper.

3.1 Wedderburn–Malcev Form

We say that an algebra $E\subseteq\mathrm{M}_{d}(\mathbb{Q})$ is in Wedderburn–Malcev form if, with respect to some signature, $E$ consists of upper block triangular matrices and the Jacobson radical $J(E)$ consists of strictly upper block triangular matrices. In this case we have that $\operatorname{BlockDiag}(E)\cong E/J(E)$ is semisimple, where $\operatorname{BlockDiag}(\cdot)$ is the projection onto the set of block diagonal matrices.

Proposition 3.

Let $E$ be a sub-algebra of $\mathrm{M}_{d}(\mathbb{Q})$ and let $J$ be a nilpotent ideal in $E$ . Given a basis $B$ of $J$ , one can compute in polynomial time an invertible matrix $p\in\mathrm{M}_{d}(\mathbb{Q})$ such that

(i)

the conjugated algebra $p^{-1}Ep$ and conjugated ideal $p^{-1}Jp$ consist of upper block triangular and strictly upper block triangular matrices, respectively;
(ii)

$\llbracket p\rrbracket\leq\llbracket B\rrbracket^{d}$ and $\llbracket p^{-1}\rrbracket\leq\llbracket B\rrbracket^{2d^{2}}$ .

Proof.

We first show Item (i). Let $k\leq d$ be the nilpotency index of $J$ and write $W_{i}:=J^{k-i}\mathbb{Q}^{d}$ . Then we obtain the following filtration:

\displaystyle\{0\}=W_{0}\subset W_{1}\subset\cdots\subset W_{k}=\mathbb{Q}^{d}\,.

(4)

The above chain of inclusions is strict. Indeed, if the sequence were not strict then we would have $W_{0}=W_{i}$ for some $i<k$ . But this contradicts the fact that $W_{0}=\{0\}$ and $W_{i}\neq\{0\}$ by minimality of $k$ . Note, moreover, that $E$ preserves the filtration (4). Indeed, since $J$ is an ideal, we have $E\cdot W_{i}=E\cdot J^{k-i}\mathbb{Q}^{d}\subseteq J^{k-i}\mathbb{Q}^{d}=W_{i}\,$ .

Let $\{v_{1},\ldots,v_{d}\}$ be a basis adapted to the filtration in (4), as defined in Section 2.3, and let $p$ be the matrix whose $i$ -th column is $v_{i}$ , for $i\in\left\{1,\ldots,d\right\}$ . Since $E$ preserves the filtration, it follows that the conjugated algebra $p^{-1}Ep$ consists of upper block triangular matrices. We claim furthermore that the conjugated ideal $p^{-1}Jp$ consists of strictly upper block triangular matrices. To see this, let $a\in J$ and $i\geq 1$ . Then the inclusion $a\,W_{i}\subseteq J\,W_{i}=W_{i-1}$ holds, meaning that multiplication by $a$ strictly lowers the index in the filtration. This implies that $p^{-1}ap$ is strictly upper block triangular in the adapted basis.

Height analysis: We next establish Item (ii). We start by computing bases $B_{i}$ of the $W_{i}s$ . We take $B_{k}$ to be the canonical basis of $W_{k}$ . For $i\in\left\{1,\dots,k\right\}$ , $B_{i}B$ spans $W_{i-1}$ . By submultiplicativity of the height we obtain bases such that $\llbracket B_{i}\rrbracket\leq\llbracket B\rrbracket^{d}$ for any $i\in\left\{1,\ldots,k\right\}$ . From these bases we can select a basis adapted to the filtration in (4): first select a basis of $W_{1}$ . Then for $i\in\left\{1,\ldots,k-1\right\}$ , given a basis adapted to the filtration $W_{0}\subset\ldots\subset W_{i}$ , we can extend it to a basis adapted to $W_{0}\subset\ldots\subset W_{i+1}$ by adding vectors from $B_{i+1}$ .

Let $p$ be the change of basis matrix obtained from these vectors, then $\llbracket p\rrbracket\leq\llbracket B\rrbracket^{d}$ . Using Claim 1, above, we obtain $\llbracket p^{-1}\rrbracket\leq\llbracket B\rrbracket^{2d^{2}}$ . $\hfill\blacktriangleleft$

Theorem 4.

There is a polynomial-time algorithm that, given a basis $B$ of an algebra $E\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , determines an invertible matrix $p\in\mathrm{M}_{d}(\mathbb{Q})$ such that $p^{-1}Ep$ is in Wedderburn–Malcev form. Moreover we have $\llbracket\left\{p,p^{-1}\right\}\rrbracket=\llbracket B\rrbracket^{O(d^{4})}$ .

Proof.

By bilinearity of the trace, the Jacobson radical $J(E)$ is defined by the following system of linear equations:

J(E)=\{a\in E\mid\forall b\in B\colon\mathrm{tr}(ab)=0\}\,.

Thus we can compute a basis $B^{\prime}$ of $J(E)$ from $B$ in polynomial time.

Applying Proposition 3 to $E$ and $J:=J(E)$ , given in terms of the basis $B^{\prime}$ , we can compute in polynomial time an invertible matrix $p\in\mathrm{M}_{d}(\mathbb{Q})$ such that $p^{-1}Ep$ is upper block triangular and $p^{-1}Jp$ is strictly upper block triangular.

Height analysis. Using the Bareiss algorithm, the Hadamard bound gives us a bound on the height of elements of $B^{\prime}$ . This is similar to the result of Claim 1, except that here the dimension is bounded by $d^{2}$ : $\llbracket B^{\prime}\rrbracket\leq\llbracket B\rrbracket^{O(d^{2})}$ .

Applying Proposition 3, we obtain $\llbracket\left\{p,p^{-1}\right\}\rrbracket=\llbracket B\rrbracket^{O(d^{4})}$ . $\hfill\blacktriangleleft$

3.2 Diameter Bound for Finite Monoids via Factorisation Forests

Recall that a finitely generated monoid has diameter $D$ if every element of the monoid can be written as the product of a list of generators of length at most $D$ . The diameter bound for finitely generated matrix monoids in [4] is proved using a graph construction that was introduced in [7] for computing the Zariski closure of matrix monoids. Below, we reformulate their main technical contribution in terms of factorisation forests, extracting a result that we think is of independent interest.

Given a morphism $\varphi:\Sigma^{+}\rightarrow\mathrm{M}_{d}(\mathbb{Q})$ , a Ramseyan factorisation forest of a word $w\in\Sigma^{+}$ is a finite unranked plane tree whose nodes are labelled with elements of $\Sigma^{+}$ . The root is labelled $w$ , the children have labels in $\Sigma$ , and an internal node with label $x$ whose children are labelled $x_{0},\ldots,x_{s-1}$ , satisfies

(i): $\varphi(x)=\varphi(x_{0}x_{1}\cdots x_{s-1})$ , and
(ii): if $s\geq 3$ then $\varphi(x_{0}),\ldots,\varphi(x_{s-1})$ generate a subgroup of $\mathrm{M}_{d}(\mathbb{Q})$ .

The height of such a tree is the maximum number of non-leaves on a root-to-leaf path and the reduced height is the maximum number of nodes of arity at least 3 on a root-to-leaf path.

The above notion of factorisation forest differs from the classical notion, due to Simon [16], which involves the stronger condition that for every node with 3 or more children, that node and all its children should be the same idempotent element of the monoid. The payoff is that we obtain a factorisation forest whose height depends only on the dimension of the matrices, not the cardinality of the monoid (as is the case for the classical formulation).

Theorem 5.

If $\varphi$ has finite image then every word $w\in\Sigma^{+}$ has a Ramseyan factorisation forest of height at most $2d(d+3)$ and reduced height at most $d$ .

We first show that Theorem 5 implies the claimed diameter bound, before proceeding to its proof.

Corollary 6 ([4, Theorem 1]).

Let $d$ be a positive integer and let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ . If $X^{*}$ is finite, then its diameter is at most $2^{2d(d+3)}g(d)^{d}$ , where $g(d)$ is the maximum cardinality of a subgroup of $\mathrm{M}_{d}(\mathbb{Q})$ .

Proof.

Let $\varphi:\Sigma^{+}\rightarrow\mathrm{M}_{d}(\mathbb{Q})$ be a morphism such that $\varphi(\Sigma)=X$ . With respect to $\varphi$ , every word $w\in\Sigma^{+}$ has a Ramseyan factorisation forest of height at most $2d(d+3)$ and reduced height at most $d$ . We can moreover assume that the non-binary nodes of such a tree have arity at most $g(d)$ . Such a tree thus has at most $2^{2d(d+3)}g(d)^{d}$ leaves. The result follows. $\hfill\blacktriangleleft$

The starting point for proving Theorem 5 is a factorisation forest theorem for general matrix monoids (both finite and infinite) in [1, Proposition 2]. We then transform such a factorisation forest into a Ramseyan factorisation forest, using a construction similar to [4, Lemma 11]. Given a morphism $\varphi:\Sigma^{+}\rightarrow\mathrm{M}_{d}(\mathbb{Q})$ , a weak factorisation forest of a word $w\in\Sigma^{+}$ is a finite unranked plane tree whose nodes are labelled with elements of $\Sigma^{+}$ . The root is labelled $w$ , the children have labels in $\Sigma$ , and a node with label $x$ whose children are labelled $x_{0},\ldots,x_{s-1}$ , satisfies

(i): $\varphi(x)=\varphi(x_{0}x_{1}\cdots x_{s-1})$ , and
(ii): if $|s|\geq 3$ then $\operatorname{rk}(\varphi(x_{0}))=\cdots=\operatorname{rk}(\varphi(x_{s-1}))=% \operatorname{rk}(\varphi(x))=\operatorname{rk}(\varphi(x)^{2})$ .

The height and reduced height of a weak factorisation forest are defined exactly as in the Ramseyan case. The following result gives bounds on the height and reduced height of weak factorisation forests in arbitrary matrix monoids.

Theorem 7 ([1], Proposition 3).

Let $\varphi:\Sigma^{+}\to\mathrm{M}_{d}(\mathbb{Q})$ be a semigroup morphism. Then every word has a weak factorisation forest of height $\leq d(d+3)$ and reduced height $\leq d$ .

Recall that the notion of Ramseyan factorisation forest strengthens Condition (ii) to the requirement that $\varphi(x_{0}),\ldots,\varphi(x_{s-1})$ generate a subgroup of $\mathrm{M}_{d}(\mathbb{Q}).$ We next show how to transform a weak factorisation forest to a Ramseyan factorisation forest in case the morphism $\varphi$ has finite image. To this end, we use the following result, a direct consequence of [7, Proposition 9] and [4, Lemma 7].

Lemma 8.

Let $a_{1},\ldots,a_{\ell}\in\mathrm{M}_{d}(\mathbb{Q})$ and $a:=a_{1}\cdots a_{\ell}$ . Assume that

\operatorname{rk}(a_{1})=\cdots=\operatorname{rk}(a_{\ell})=\operatorname{rk}(a)

(5)

Then there exist $1=i_{1}<i_{2}<\cdots<i_{t}=\ell$ , where $t\leq 2^{d}+1$ , such that $\ker(a)=\ker(a_{i_{1}}\cdots a_{i_{t}})$ and $\operatorname{im}(a)=\operatorname{im}(a_{i_{1}}\cdots a_{i_{t}})$ .

The following is a version of [4, Lemma 11].

Proposition 9.

Assume $\varphi$ has a finite image. Let $s\geq 3$ and $w,w_{0},\ldots,w_{s-1}\in\Sigma^{+}$ such that:

$\blacksquare$

$\varphi(w)=\varphi(w_{0}w_{1}\cdots w_{s-1})$ ,
$\blacksquare$

$\operatorname{rk}(\varphi(w_{0}))=\cdots=\operatorname{rk}(\varphi(w_{s-1}))=% \operatorname{rk}(\varphi(w))=\operatorname{rk}(\varphi(w)^{2})$ .

Then there exist $u_{0},\ldots,u_{t-1}\in\{w_{0},\ldots,w_{s-1}\}^{\leq 2^{d+2}}$ such that $\varphi(w)=\varphi(u_{0}\cdots u_{t-1})$ and, moreover, $\varphi(u_{0}),\ldots,\varphi(u_{t-1})$ generate a subgroup of $\mathrm{M}_{d}(\mathbb{Q}).$

Proof.

For $i\in\{0,\ldots,s-2\}$ , we apply Lemma 8 to $\varphi(w_{i+1})\varphi(w_{i+2})\cdots\varphi(w_{s-1})$ and $\varphi(w_{0})\varphi(w_{1})\cdots\varphi(w_{i})$ respectively to obtain $x_{i},y_{i}\in\{w_{0},\ldots,w_{s-1}\}^{\leq 2^{d}+1}$ such that

$\blacksquare$

$\operatorname{im}(\varphi(x_{i}))=\operatorname{im}(\varphi(w_{i+1})),\quad% \ker(\varphi(x_{i}))=\ker(\varphi(w_{s-1}))$ .
$\blacksquare$

$\operatorname{im}(\varphi(y_{i}))=\operatorname{im}(\varphi(w_{0})),\quad\ker(% \varphi(y_{i}))=\ker(\varphi(w_{i})).$

From the rank condition $\operatorname{rk}(\varphi(w_{0}))=\cdots=\operatorname{rk}(\varphi(w_{s-1}))=% \operatorname{rk}(\varphi(w))=\operatorname{rk}(\varphi(w)^{2}),$ we obtain that $\ker(\varphi(y_{i}))\cap\operatorname{im}(\varphi(x_{i}))=\{0\}$ , which implies that

\ker(\varphi(y_{i}x_{i}))=\ker(\varphi(x_{i}))=\ker(\varphi(w_{s-1})),\quad% \operatorname{im}(\varphi(y_{i}x_{i}))=\operatorname{im}(\varphi(y_{i}))=% \operatorname{im}(\varphi(w_{0})).

Let $p$ be the smallest integer such that $\varphi(y_{i}x_{i})^{p}=\varphi(y_{i}x_{i})^{2p}$ for all $i$ . Such an integer $p$ exists since $\varphi$ has a finite image. Moreover, $\varphi(y_{i}x_{i})^{p}$ acts as the identity on $\operatorname{im}(\varphi(y_{i}x_{i}))=\operatorname{im}(\varphi(w_{0}))$ . We then rewrite $\varphi(w)$ as

\varphi(w)=\varphi(w_{0}x_{0})\,\varphi(y_{0}x_{0})^{p-1}\,\varphi(y_{0}w_{1}x% _{1})\,\varphi(y_{1}x_{1})^{p-1}\cdots\varphi(y_{s-2}x_{s-2})^{p-1}\,\varphi(y% _{s-2}w_{s-1}).

Let $(u_{j})_{j=0}^{t-1}$ be the finite sequence obtained by listing the factors $(u_{j})_{j=0}^{t-1}:=$

\Big(w_{0}x_{0},\;\underbrace{y_{0}x_{0},\ldots,y_{0}x_{0}}_{p-1\text{ times}}% ,\;y_{0}w_{1}x_{1},\;\underbrace{y_{1}x_{1},\ldots,y_{1}x_{1}}_{p-1\text{ % times}},\;\ldots,\;\underbrace{y_{s-2}x_{s-2},\ldots,y_{s-2}x_{s-2}}_{p-1\text% { times}},\;y_{s-2}w_{s-1}\Big).

Then each $u_{j}$ belongs to $\{w_{0},\ldots,w_{s-1}\}^{\leq 2^{d+2}},$ and $\varphi(w)=\varphi(u_{0}\cdots u_{t-1})$ .

Let $G=\{\varphi(u_{0}),\ldots,\varphi(u_{t-1})\}^{*}\subseteq M_{d}(\mathbb{Q})$ . Note that for every $0\leq i\leq t-1$ , $u_{i}$ has one of the forms $w_{0}x_{0},y_{j}x_{j},y_{j}w_{j+1}x_{j+1},y_{s-2}w_{s-1}$ . Therefore, for every $0\leq i\leq t-1$ , $\ker(\varphi(u_{i}))=\ker(\varphi(w_{s-1}))$ , $\operatorname{im}(\varphi(u_{i}))=\operatorname{im}(\varphi(w_{0}))$ , and moreover, $\ker(\varphi(u_{i}))\cap\operatorname{im}(\varphi(u_{i}))=\{0\}$ . Since the $\varphi(u_{i})$ all have the same kernel $U$ and image $V$ such that moreover $U\cap V=\{0\}$ , $G$ is isomorphic to a finite monoid of invertible linear endomorphisms of $V$ , i.e. is a group. $\hfill\blacktriangleleft$

Proof of Theorem 5.

We will show that every $v\in\Sigma^{+}$ has a Ramseyan factorisation forest of height at most $2d(d+3)$ , and reduced height at most $d$ . Fix $v\in\Sigma^{+}$ . The construction of the Ramseyan factorisation forest of $v$ relies on the weak factorisation forest given in Theorem 7. Let $T$ be the weak factorisation forest of $v$ , with height at most $d(d+3)$ and reduced height at most $d$ . We modify $T$ as follows. Process the nodes with more than two children level by level, starting from the leaves and moving upward. Whenever a node labelled by $w$ has more than two children labelled $w_{0},\ldots,w_{s-1}$ , apply Proposition 9 to that node, and replace that node by the corresponding subtree as in Figure 1.

Figure 1: A schematic Ramseyan factorisation tree for

w

with leaves among

w_{i}

of height

\leq d+3

. The root

w

is decomposed into

u_{0},u_{1},\ldots,u_{t-1}

. We display

u_{0}=w_{0}x_{0},u_{1}=y_{0}x_{0},\ldots,u_{t-1}=y_{s-1}w_{s-1}

. Each factor

x_{i}

,

y_{i}

, is further refined by a binary subtree down to leaves among the

w_{j}

.

Each application of Proposition 9 increases the height below that node by at most $d+3$ , and does not increase the reduced height. Since, for each path from the root to leaf we can pass through at most $d$ nodes that have more than two children, on every such path we can apply Proposition 9 at most $d$ times. Therefore, the total height increases by at most $d(d+3),$ and the reduced height remains unchanged. Hence, the resulting tree has height at most $2d(d+3)$ , reduced height at most $d$ , and satisfies the Ramseyan factorisation forest conditions. $\hfill\blacktriangleleft$

4 Height Bound for Finite Monoids

In this section we prove a bound on the bitsize of the matrices in a finite matrix monoid that is polynomial in the bitsize of the generators and the dimension $d$ . We first obtain a bitsize bound in the case that the enveloping algebra of the monoid is semisimple. This bound combines the fact that an element of such a monoid is determined by its image under the trace map (see Section 2.2) together with the fact that the image of the trace map is confined to a small range, due to the monoid being finite. We then lift the bitsize bound from the semisimple case to the general case using the Wedderburn–Malcev-form computation in Theorem 4 and the diameter bound in Corollary 6. We remark that similar arguments are used in [2] in the group case.

Lemma 10.

Let $X^{*}\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be a finite monoid. Then $\mathrm{tr}(a)\in\{-d,\dots,d\}$ for all $a\in X^{*}$ .

Proof.

Consider a matrix $a\in X^{*}$ . Since $X^{*}$ is finite, there exists $m>n$ such that $a^{m}=a^{n}$ . It follows that the minimal polynomial of $a$ divides $x^{n}-x^{m}$ , i.e. every eigenvalue of $a$ is either $0$ or a root of unity. In particular, $|\lambda|\leq 1$ for all eigenvalues $\lambda$ of $a$ and hence $|\mathrm{tr}(a)|=|\sum_{i=1}^{d}\lambda_{i}|\leq d$ . As a sum of algebraic integers, $\mathrm{tr}(a)$ is itself an algebraic integer. Since $\mathrm{tr}(a)$ is moreover rational and $\mathbb{Z}$ integrally closed in $\mathbb{Q}$ , we obtain $\mathrm{tr}(a)\in\mathbb{Z}$ . The lemma immediately follows. $\hfill\blacktriangleleft$

Theorem 11.

Let $X^{*}\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be a finite monoid such that $\mathrm{Env}(X)$ is semisimple, with a basis $B\subseteq X^{*}$ . Then $\llbracket X^{*}\rrbracket=d^{O(d^{2})}\llbracket B\rrbracket$ .

Proof.

Let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be such that $X^{*}$ is finite and $\mathrm{Env}(X)$ semisimple. One can choose $B$ a basis of $\mathrm{Env}(X)$ within $X^{\leq d^{2}-1}$ since $\mathrm{Env}(X)$ has dimension at most $d^{2}$ (and $\mathrm{id}_{d}\in X^{*})$ . From Equation (1), $\llbracket B\rrbracket\leq\llbracket X\rrbracket^{d^{2}}$ .

By Lemma 10, the matrix $T_{B}$ , defined in Equation (2), is an integer matrix with entries in $\left\{-d,\ldots,d\right\}$ . We have by Claim 1 that $\llbracket T_{B}^{-1}\rrbracket\leq(d^{3})^{2d^{2}}$ .

Let $a\in X^{*}$ and let $\alpha=(\alpha_{b})_{b\in B}\in\mathbb{Q}^{B}$ be such that $a=\sum_{b\in B}\alpha_{b}b$ . Then for any $c\in B$ , $\mathrm{tr}(ca)=\sum_{b\in B}\alpha_{b}\mathrm{tr}(cb)=(T_{B}\alpha)_{c}$ . By Lemma 10, the vector $T_{B}\alpha$ has entries in $\left\{-d,\ldots,d\right\}$ , and thus has height at most $d^{3}$ . We write $a=\sum_{b\in B}(T_{B}^{-1}T_{B}\alpha)_{b}b$ . Let $A=T_{B}^{-1}\left\{-d,\ldots,d\right\}^{B}$ and let $C$ be the set of entries of elements of $A$ . Then $\llbracket C\rrbracket\leq\llbracket A\rrbracket\leq(d^{3})^{2d^{2}+1}$ . Then since $X^{*}\subseteq\sum_{b\in B}CB$ , we have by triangle inequality that:

\displaystyle\llbracket X^{*}\rrbracket

\displaystyle\leq d^{2}\llbracket C\rrbracket\llbracket B\rrbracket\,\leq\,d^{% 2}(d^{3})^{2d^{2}+1}\llbracket B\rrbracket\,=\,d^{O(d^{2})}\llbracket B\rrbracket\

$\hfill\blacktriangleleft$

Proposition 12.

Let $X^{*}\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be a finite monoid such that $\mathrm{Env}(X)$ is in Wedderburn–Malcev form, with a basis $B\subseteq X^{*}$ . Then $\llbracket X^{*}\rrbracket=d^{O(d^{3})}\llbracket X\rrbracket^{d}\llbracket B% \rrbracket^{d}$ .

Proof.

By assumption we can write the set of generators of $\mathrm{Env}(X)$ as $X=\{a_{1}+c_{1},\ldots,a_{m}+c_{m}\}\subseteq X^{*}$ , where each $a_{i}$ is block diagonal and each $c_{i}$ strictly upper triangular on blocks. Write $A:=\{a_{1},\ldots,a_{m}\}$ , $C:=\{c_{1},\ldots,c_{m}\}$ and $D:=\{a_{1},\ldots,a_{m},c_{1},\ldots c_{m}\}$ .

We first obtain a bound on the height of $D^{*}$ . By definition of Wedderburn–Malcev normal form, $\mathrm{Env}(A)=\operatorname{BlockDiag}(\mathrm{Env}(X))$ is semisimple. Hence, by Theorem 11, $\llbracket A^{*}\rrbracket=d^{O(d^{2})}\llbracket B\rrbracket$ . Moreover, since any matrix in $(A^{*}C)^{d}$ is zero, we get that a non-zero matrix in $D^{*}$ contains at most $d-1$ occurrences of elements of $C$ . Hence $\llbracket D^{*}\rrbracket\leq(\llbracket A^{*}\rrbracket\llbracket C% \rrbracket)^{d}=d^{O(d^{3})}\llbracket X\rrbracket^{d}\llbracket B\rrbracket^{d}$ .

Let $a\in X^{*}$ . By Corollary 6, $a$ can be written as a product of at most

L(d):=2^{2d(d+3)+d^{2}}(d!)^{d}=d^{O(d^{2})}

matrices from the generating set $X$ . By the distributive law we can write $a$ as the sum of elements of $D^{*}$ . Since any matrix in $(A^{*}C)^{d}$ is zero, most of these summands are zero, and the number of non-zero summands is bounded by $\sum_{i<d}\binom{L(d)}{i}\leq dL(d)^{d}=d^{O(d^{3})}$ . By Equation (1), summing $k$ elements of a set can at most multiply the height by $k$ . Thus

\llbracket X^{*}\rrbracket\,\leq\,dL(d)^{d}\llbracket D^{*}\rrbracket\,=\,d^{O% (d^{3})}\llbracket X\rrbracket^{d}\,\llbracket B\rrbracket^{d}\,.\

$\hfill\blacktriangleleft$

Relationship between height and bitsize. Before stating our main result on the height of a finite matrix monoid, we define $\operatorname{\mathrm{size}}(X)$ the bitsize of a finite set $X$ of matrices: $\operatorname{\mathrm{size}}(X)$ is defined as the maximal number of bits necessary to write (the absolute values of) numerators and denominators of entries of elements of $X$ . Thus any element of $X$ can be represented with $mn(\operatorname{\mathrm{size}}(X)+1)$ many bits. Observe that the least common denominator of $X$ is smaller than $2^{mn\operatorname{\mathrm{size}}(X)}$ . In particular, if $m=n=d$ , then the following relationships hold:

	$\displaystyle\operatorname{\mathrm{size}}(X)\leq\log(\llbracket X\rrbracket)% \leq(2d^{2}+1)\operatorname{\mathrm{size}}(X)+\log d$			(6)
	$\displaystyle\operatorname{\mathrm{size}}(X)\leq\log(\llbracket X\rrbracket)% \leq\operatorname{\mathrm{size}}(X)+\log d,$	$\displaystyle\text{if }X\text{ has integer entries.}$		(7)

Theorem 13.

Let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ such that $X^{*}$ is finite, then $\llbracket X^{\ast}\rrbracket=\llbracket X\rrbracket^{O(d^{7})}$ , where the constant in the big-oh notation is absolute¹¹1By an absolute constant we mean a fixed number, independent of any parameters. As a consequence $\operatorname{\mathrm{size}}(X^{*})=O(d^{9}\operatorname{\mathrm{size}}(X))$ . Note that if $X\subseteq\mathrm{M}_{d}(\mathbb{Z})$ , then $\operatorname{\mathrm{size}}(X^{*})=O(d^{7}(\log d+\operatorname{\mathrm{size}% }(X)))$ .

Proof.

The first step is to compute a basis $B$ of $\mathrm{Env}(X)$ . Since $\mathrm{Env}(X)$ has dimension at most $d^{2}$ , one can find a basis within $X^{d^{2}-1}$ , which gives $\llbracket B\rrbracket\leq\llbracket X\rrbracket^{d^{2}}$ . We then put the matrices in Wedderburn–Malcev normal form. Applying Theorem 4, we obtain a change of basis matrix $p$ such that $\llbracket p^{-1}(X\cup B)p\rrbracket=\llbracket X\rrbracket^{O(d^{6})}$ . Finally, by applying Proposition 12, we obtain that

\llbracket X^{*}\rrbracket\leq\llbracket p\rrbracket\llbracket p^{-1}X^{*}p% \rrbracket\llbracket p^{-1}\rrbracket=\llbracket X\rrbracket^{O(d^{7})}\,.

Combining this with Equation (6), we obtain the polynomial size bound. If $X$ contains only integer matrices then using Equation (7), we obtain the result. $\hfill\blacktriangleleft$

5 Finiteness and Membership

In this section, we derive complexity results for the Finiteness and Finite Membership Problems as corollaries of the polynomial bit-size bound on matrix entries in finite monoids, established in Theorem 13.

Proposition 14.

The Finiteness Problem is decidable in PSpace.

Proof.

PSpace membership is a consequence of the following nondeterministic polynomial-space algorithm for deciding infiniteness. The algorithm maintains a matrix $a\in X^{*}$ , that is initially the identity. At each step, the algorithm nondeterministically chooses $b\in X$ and makes the assignment $a:=ab$ . If the algorithm reaches a matrix whose bitsize exceeds the bound given by Theorem 13, it accepts. (We note that the constant in the big-oh notation in Theorem 13 is absolute.) $\hfill\blacktriangleleft$

Proposition 15.

The Finite Membership Problem is PSpace-complete.

Proof.

PSpace membership is a consequence of the following nondeterministic polynomial-space algorithm. The algorithm maintains a matrix $a\in X^{*}$ , that is initially the identity. At each step, it nondeterministically guesses a generator $b\in X$ and performs the update $a:=ab$ . By Theorem 13, the bitsize of $a$ remains polynomially bounded throughout the computation. The algorithm accepts if it reaches the target matrix $t$ .

Hardness is shown by a reduction from the intersection emptiness problem for DFA. More precisely, we prove that the Finite Membership problem over $\mathbb{N}$ is PSpace-hard in Section 6. We also extend PSpace-hardness to matrices over any semiring $R\neq\{0\}$ and to irreducible monoids. $\hfill\blacktriangleleft$

6 PSPACE-hardness in Proposition 15

Recall that the DFA intersection emptiness problem asks, given $n\in\mathbb{N}$ and DFAs $D_{1},\dots,D_{n}$ over a common alphabet $\Sigma$ , whether the intersection of their languages is nonempty.

For simplicity, we think of each DFA $D_{i}$ as a weighted $\mathbb{N}$ -automaton $(\alpha_{i},(M_{\sigma,i})_{\sigma\in\Sigma},\gamma_{i})$ with $d_{i}$ states, where $\alpha_{i}\in\{0,1\}^{1\times d_{i}}$ is the initial row vector, $M_{\sigma,i}\in\{0,1\}^{d_{i}\times d_{i}}$ is the transition matrix of $\sigma\in\Sigma$ and $\gamma_{i}\in\{0,1\}^{d_{i}\times 1}$ is the final column vector. By construction, the weighted automaton $(\alpha_{i},(M_{\sigma,i})_{\sigma\in\Sigma},\gamma_{i})$ counts the number of runs of $D_{i}$ on a given word. Since each $D_{i}$ is deterministic, the value of the weighted automaton on a word $w\in\Sigma^{*}$ is 1 if $D_{i}$ accepts $w$ and 0 otherwise.

The reduction constructs $3+|\Sigma|$ matrices of dimension $d:=2+\sum_{i=1}^{n}d_{i}$ , namely $M_{\mathrm{init}},M_{\mathrm{end}},M_{t}$ , and $M_{\sigma}$ for each $\sigma\in\Sigma$ . The matrix $M_{t}$ is the target matrix, and the question is to check whether $M_{t}$ lies in the monoid generated by the other matrices. Below, for simplicity of notation, we extend the map $\sigma\mapsto M_{\sigma,i}$ to a monoid homomorphism $\Sigma^{*}$ in a natural way (where for the empty word $\varepsilon$ the matrix $M_{\varepsilon,i}$ is the identity matrix for appropriate size). Analogously, we extend the maps $\sigma\mapsto M_{\sigma}$ to $\Sigma^{*}$ . The idea is to simulate the computation of all weighted automata $(\alpha_{i},(M_{\sigma,i})_{\sigma\in\Sigma},\gamma_{i})$ over words $w$ , that is by definition $\alpha_{i}M_{w,i}\gamma_{i}$ , simultaneously by the matrix product $M_{\mathrm{init}}M_{w}M_{\mathrm{end}}$ .

To this end, we define the matrix $M_{\mathrm{init}}$ which initializes all weighted automata simultaneously, and similarly the matrix $M_{\mathrm{end}}$ which accounts for the final column vectors:

M_{\mathrm{init}}:=\left(\begin{array}[]{cccccc}0&\alpha_{1}&\alpha_{2}&\cdots% &\alpha_{n}&0\\ \hline\cr\lx@intercol\hfil\boldsymbol{0}_{(d-1)\times d}\hfil\lx@intercol\end{% array}\right)\qquad\text{and}\qquad M_{\mathrm{end}}:=\left(\begin{array}[]{c|% c}\hbox{\multirowsetup$\boldsymbol{0}_{d\times(d-1)}$}&0\\ &\gamma_{1}\\ &\gamma_{2}\\ &\vdots\\ &\gamma_{n}\\ &0\\ \end{array}\right)

For $\sigma\in\Sigma$ , the matrix $M_{\sigma}$ simulates simultaneously applying the transition matrices $M_{\sigma,i}$ , relying on the block multiplication:

M_{\sigma}:=\left(\begin{array}[]{c|cccc|c}&&\boldsymbol{0}_{1\times d}&&&\\ \hline\cr&M_{\sigma,1}&\boldsymbol{0}_{d_{1}\times d_{2}}&\cdots&\boldsymbol{0% }_{d_{1}\times d_{n}}&\\ &\boldsymbol{0}_{d_{2}\times d_{1}}&M_{\sigma,2}&\cdots&\boldsymbol{0}_{d_{2}% \times d_{n}}&\\ \boldsymbol{0}_{d\times 1}&&\vdots&&&\boldsymbol{0}_{d\times 1}\\ &\boldsymbol{0}_{d_{n}\times d_{1}}&\boldsymbol{0}_{d_{n}\times d_{2}}&\cdots&% M_{\sigma,n}&\\ \hline\cr&&\boldsymbol{0}_{1\times d}&&&\end{array}\right)

The target matrix $M_{t}$ is zero everywhere except in its top-right entry, where it is $n$ .

We argue the correctness of the reduction as follows. Let $X:=\{M_{\mathrm{init}},M_{\mathrm{end}}\}\cup\{M_{\sigma}\mid\sigma\in\Sigma\}$ . By the block matrix multiplication, $X^{+}M_{\mathrm{init}}X^{\ast}=\{0\}$ and $X^{\ast}M_{\mathrm{end}}X^{+}=\{0\}$ . Hence we can restrict ourselves to products $M_{\mathrm{init}}^{\leq 1}M_{w}M_{\mathrm{end}}^{\leq 1}$ with $w\in\Sigma^{*}$ . Moreover, we can assume the form $M_{\mathrm{init}}M_{w}M_{\mathrm{end}}$ , otherwise the top-right entry is $0$ instead of $n$ .

By a simple induction, we can see that $M_{\mathrm{init}}M_{w}$ , with $w\in\Sigma^{*}$ , is in the following form:

M_{\mathrm{init}}M_{w}:=\left(\begin{array}[]{ccccc}0&\alpha_{1}M_{w,1}&\cdots% &\alpha_{n}M_{w,n}&0\\ \hline\cr\lx@intercol\hfil\boldsymbol{0}_{(d-1)\times d}\hfil\lx@intercol\end{% array}\right)

(8)

where the base of induction ( $w=\varepsilon$ ) holds by the definition of $M_{\mathrm{init}}$ , and the induction step follows by block multiplication. Given the form in (8), it follows that $M_{\mathrm{init}}M_{w}M_{\mathrm{end}}$ is a zero matrix, except in its top-right entry, where it stores $\sum_{i=1}^{n}\alpha_{i}M_{w,i}\gamma_{i}$ . The latter is $n$ if and only if $w$ is accepted by all $D_{i}$ . To conclude the proof, we note that entries of matrices in the monoid range over $\{0,\ldots,n\}$ , hence the monoid is finite.

Extension to semirings.

The proof extends for matrices over any semiring $R\neq\{0\}$ and irreducible monoids as follows. To extend to a semiring $R\neq\{0\}$ , we have to prevent addition $1+1$ from occurring, as its value would depend on the semiring. To this end, we adapt the above construction as follows: We set $d:=1+n+\sum_{i=1}^{n}d_{i}$ , where the extra dimensions are used as additional target states. The idea is that instead of accumulating all $n$ runs on the same target state, for every DFA $D_{i}$ we have a separate target state which checks whether the corresponding DFA accepts. Formally, we still use $3+|\Sigma|$ matrices $M_{\mathrm{init}},M_{\mathrm{end}},M_{\mathrm{t}}$ and $M_{\sigma}$ for every $\sigma$ . The matrices $M_{\mathrm{init}}$ and $M_{\sigma}$ are as defined above, extended with $n-1$ additional zero columns at the right. The matrices $M_{\mathrm{t}}$ and $M_{\mathrm{end}}$ are now defined as follows, the left matrix being $M_{\mathrm{t}}$ and the right matrix is $M_{\mathrm{end}}$ .

\displaystyle\left(\begin{array}[]{c|c}\hbox{\multirowsetup$\boldsymbol{0}_{d% \times(d-n)}$}&\boldsymbol{1}_{1\times n}\\ &\boldsymbol{0}_{(d-1)\times n}\end{array}\right)

\displaystyle\left(\begin{array}[]{c|ccccc}&0&0&\dots&0\\ &\gamma_{1}&0_{d_{1}\times 1}&\dots&0_{d_{1}\times 1}\\ \boldsymbol{0}_{(d-n)\times(d-n)}&0_{d_{2}\times 1}&\gamma_{2}&&\vdots\\ &\vdots&&\ddots&0_{d_{n-1}\times 1}\\ &0_{d_{n}\times 1}&\dots&0_{d_{n}\times 1}&\gamma_{n}\\ \hline\cr&&\boldsymbol{0}_{n\times d}&&\end{array}\right)

We argue correctness similarly to the above. Let $X:=\{M_{\mathrm{init}},M_{\mathrm{end}}\}\cup\{M_{\sigma}\mid\sigma\in\Sigma\}$ . Again, $X^{+}M_{\mathrm{init}}X^{\ast}=\{0\}$ and $X^{\ast}M_{\mathrm{end}}X^{+}=\{0\}$ . Hence we can restrict ourselves to products $M_{\mathrm{init}}^{\leq 1}M_{w}M_{\mathrm{end}}^{\leq 1}$ with $w\in\Sigma^{*}$ . Again, we can assume $M_{\mathrm{init}}M_{w}M_{\mathrm{end}}$ , as otherwise the top-right entries are $0$ instead of $1$ . With a similar induction as before, we observe that $M_{\mathrm{init}}M_{w}M_{\mathrm{end}}$ is a zero matrix, except in the top-right entries, where the $i$ -th entry stores $\alpha_{i}M_{w,i}\gamma_{i}$ , i.e. is equal to $1$ if and only if the DFA $D_{i}$ accepts $w$ . Hence all these entries are equal to $1$ as in $M_{\mathrm{t}}$ if and only if $w$ is accepted by all $D_{i}$ . Moreover, observe that every $a\in X^{\ast}$ fulfills $a\in\{0,1\}^{d\times d}$ , because the only operations performed are $0+0=0$ , $1+0=1$ , $1\cdot 0=0$ and $1\cdot 1=1$ which hold in every semiring $R$ .

Extension to Irreducible Finite Monoids.

A monoid $M\subseteq M_{d}(\mathbb{Q})$ is called irreducible if there is no vector space $0\subsetneq V\subsetneq\mathbb{Q}^{d}$ such that $V\cdot M\subseteq V$ ²²2Defining irreducible with left or right multiplication gives the same definition, but right multiplication is more natural in automata theory, i.e. no vector space stable under multiplication by $M$ . We will show that membership is PSpace-hard also for irreducible finite monoids $M$ .

Proposition 16.

Membership is PSpace-hard even under the promise that $X^{\ast}$ is an irreducible finite matrix monoid.

Proof.

We again use $d:=1+n+\sum_{i=1}^{n}d_{i}$ and base this construction on the semiring reduction. As opposed to the above reductions though, we now use $3+|\Sigma|+2(d-1)$ many matrices. The first $3+|\Sigma|$ matrices are $M_{\mathrm{init}},M_{\mathrm{end}},M_{\mathrm{t}}$ and $M_{\sigma}$ for every $\sigma\in\Sigma$ as before, they even have exactly the same definition as in the semiring reduction. Again, $M_{\mathrm{t}}$ is the target matrix. The new matrices are $\{\delta_{1,j}\mid j\in\{2,\dots,d\}\}$ and $\{\delta_{j,1}\mid j\in\{2,\dots,d\}\}$ , where $\delta_{i,j}$ is the Kronecker delta, i.e. the matrix with every entry $0$ except a $1$ at the intersection of the $i$ -th row and $j$ -th column. These matrices are added purely to ensure irreducibility. Namely $\delta_{j,1}$ resets the $j$ -th state to the initial state, and is otherwise $0$ . The matrix $\delta_{1,j}$ on the other hand is a type of initialization matrix which only initializes one DFA. None of these matrices will be useful for reaching the target, but they will ensure that no vector space can be stable under the monoid.

Correctness.

First, observe that the monoid $X^{\ast}$ is still finite: In the semiring reduction we argued that $X^{\ast}\subseteq\{0,1\}^{d\times d}$ , the same property can be proven in the same way.

Next we observe that the $\delta$ ’s are not useful for reaching the target matrix. Namely, let $w^{\prime}\in X^{*_{concat}}$ be any word of generator matrices (we do not yet identify $w^{\prime}$ with an element of the monoid, hence we clarify that the $\ast$ is concatenation here) which evaluates to $M_{\mathrm{t}}$ . We claim that there is a word $w^{\prime\prime}$ without $\delta$ ’s which also evaluates to the target.

Proof of claim: If $w^{\prime}$ does not contain $\delta$ ’s we are done. Hence assume that $w^{\prime}[k]=\delta_{i,j}$ for some $i, j, k$ , i.e. that some matrix used is $\delta_{i,j}$ . Then the product $w^{\prime}[1]\cdot\dots\cdot w^{\prime}[k]$ , i.e. the product corresponding to a prefix of the word, has only one non-zero column. However, the target matrix has multiple non-zero columns. By the structure of our matrices, in order to produce multiple non-zero columns from a single one, we must have $w^{\prime}[k^{\prime}]=M_{\mathrm{init}}$ for some $k^{\prime}>k$ . In order for $M_{\mathrm{init}}$ to not lead to the $0$ matrix, the non-zero column must have been the first column. The only generators $x\in X$ where the first column is non-zero are $\delta_{j,1}$ for some $j$ . Hence we have $w^{\prime}[k^{\prime}-1]=\delta_{j,1}$ for some $j$ . But then the product $w^{\prime}[1]\cdot\dots\cdot w^{\prime}[k^{\prime}-1]$ is useless. Removing it from the product, we obtain a new word $w^{\prime\prime}=w^{\prime}[k^{\prime}]\dots w^{\prime}[|w^{\prime}|]$ with fewer $\delta$ ’s. Repeating the process, we eventually arrive at a word $w^{\prime\prime}$ without any $\delta$ ’s, which still evaluates to the target, proving the claim.

By the claim, correctness now follows from the semiring correctness argument.

Finally, we have to argue that the monoid $X^{\ast}$ is irreducible. Let $0\subsetneq V$ be a vector space such that $V\cdot X\subseteq V$ . We have to show that $V=\mathbb{Q}^{d}$ . Since $0\subsetneq V$ , there exists some $0\neq v\in V$ . Let $j$ be such that $v[j]\neq 0$ . By applying the matrix $\delta_{j,1}$ , we reach the vector $(v[j],0,\dots,0)\in V$ . Since $V$ is a vector space, i.e. closed under scalar multiplication, we have $e_{1}\in V$ where $e_{1}\in\mathbb{Q}^{d}$ is the first unit vector. By applying $\delta_{1,j}$ we obtain $e_{j}\in V$ also for the other unit vectors, i.e. $j=2,\dots,d$ , which finishes the proof that $V=\mathbb{Q}^{d}$ . $\hfill\blacktriangleleft$

7 Integrality

For a finite set $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , the decision version of the Integrality Problem asks whether $X$ is conjugate to a set of integral matrices, while the function version computes a conjugation matrix $p\in\mathrm{GL}_{d}(\mathbb{Q})$ such that $p^{-1}Xp\subseteq\mathrm{M}_{d}(\mathbb{Z})$ . Observe that a set $X$ is conjugate to a set of integral matrices if and only if this holds for the set $X^{*}$ .

Theorem 17.

The decision and function versions of the Integrality Problem lie in PTime.

To prove Theorem 17, we first extend [2, Proposition 2.3] from groups to semigroups following a similar argument.

Proposition 18.

Let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be finite, and consider the $\mathbb{Z}$ -module $L$ generated by the set of vectors $X^{\ast}\cdot\mathbb{Z}^{d}$ . Then the following are equivalent:

1.

$L$ is a free $\mathbb{Z}$ -module of rank $d$ ;
2.

there exists $p\in\mathrm{GL}_{d}(\mathbb{Q})$ such that $p^{-1}Xp\subseteq\mathrm{M}_{d}(\mathbb{Z})$ ;
3.

there exists a common denominator $q$ , i.e. $q\in\mathbb{Z}\setminus\{0\}$ such that $q\cdot X^{\ast}\subseteq\mathrm{M}_{d}(\mathbb{Z})$ .

Proof.

We first show that Item 1 implies Item 2. Let $v_{1},\ldots,v_{d}\in\mathbb{Q}^{d}$ be a $\mathbb{Z}$ -basis of $L$ and define $p\in\mathrm{GL}_{d}(\mathbb{Q})$ as the matrix whose $i$ -th column is $v_{i}$ , for $i\in\{1,\ldots,d\}$ . Given $a\in X$ , since $aL\subseteq L$ , for all $i\in\{1,\ldots,d\}$ there exists $b_{i}\in\mathbb{Z}^{d}$ such that $av_{i}=pb_{i}$ . Defining $b$ as the matrix with the columns $b_{i}$ we obtain $ap=pb$ . Hence, $p^{-1}ap=b\in\mathrm{M}_{d}(\mathbb{Z})$ .

We next show that Item 2 implies Item 3. Assume that there exists $p\in\mathrm{GL}_{d}(\mathbb{Q})$ such that $p^{-1}Xp\subseteq\mathrm{M}_{d}(\mathbb{Z})$ . Then $X^{\ast}\subseteq p\mathrm{M}_{d}(\mathbb{Z})p^{-1}$ . Hence $X^{\ast}\subseteq q^{2}\mathrm{M}_{d}(\mathbb{Z})$ where $q\in\mathbb{Z}\setminus\{0\}$ is chosen such that $q p$ and $qp^{-1}$ are integer matrices. This establishes (3).

Finally, we show that Item 3 implies Item 1. Let $q\in\mathbb{Z}\setminus\{0\}$ be such that $qX^{\ast}\subseteq\mathrm{M}_{d}(\mathbb{Z})$ . Then $\mathbb{Z}^{n}\subseteq L\subseteq\frac{1}{q}\mathbb{Z}^{n}$ . Since $L$ is a submodule of $\frac{1}{q}\mathbb{Z}^{n}$ , which is free of rank $n$ , it follows that $L$ is free of rank at most $n$ . Furthermore, since $L$ contains $\mathbb{Z}^{n}$ it has rank exactly $n$ . $\hfill\blacktriangleleft$

The idea behind the algorithm for integrality is to determine whether a given number is a common denominator of $X^{\ast}$ , extending [2, Lemma 3.1] from groups to semigroups.

Lemma 19 ([2, Lemma 3.1]).

There is a PTime algorithm which, given a finite set $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ and a number $q\in\mathbb{N}$ (in binary), decides whether $q$ is a common denominator of $X^{\ast}$ , and if so computes a conjugation matrix $p\in\mathrm{GL}_{d}(\mathbb{Q})$ such that $p^{-1}Xp\subseteq\mathrm{M}_{d}(\mathbb{Z})$ .

Proof.

Let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ , let $m:=\operatorname{\mathrm{size}}(X)$ and let $q$ be a common denominator. Let $L:=\mathrm{Span}_{\mathbb{Z}}(X^{\ast}\cdot\mathbb{Z}^{d})\subseteq\mathbb{Q}^% {d}$ be the $\mathbb{Z}$ -module generated by $X^{\ast}\cdot\mathbb{Z}^{d}$ . As shown in the proof of Item 1 implies Item 2 in Proposition 18, the columns of the required base change $p$ are a basis of $L$ .

Observe that $q\mathbb{Z}^{d}\subseteq qL\subseteq\mathbb{Z}^{d}$ . To compute $q L$ , we define a sequence of vectors $(v_{k})$ inductively as follows. First we choose $v_{1},\ldots,v_{d}$ to be any set of vectors spanning $q\mathbb{Z}^{d}$ . Assume that we have defined $v_{1},\ldots,v_{k}$ for some $k\in\mathbb{N}$ . If there exists $a\in X$ and $l\in\{1,\ldots,k\}$ such that $av_{l}$ does not lie in the $\mathbb{Z}$ -span of $\{v_{1},\ldots,v_{k}\}$ then we define $v_{k+1}:=av_{l}$ (the choice of $a$ and $v_{l}$ doesn’t matter). Otherwise we terminate the construction. This sequence terminates in at most $d(\log_{2}q)+\frac{d}{2}m$ steps by [5, Prop. 3.1] and upon termination the resulting sequence of vectors spans $q L$ . Computing the vector $v_{k+1}$ from $\{v_{1},\ldots,v_{k}\}$ involves solving linear equations over $\mathbb{Z}$ , which is well-known to be in polynomial time (by the Hermite Normal Form [9]). Having obtained a generating set of $q L$ , we can compute a basis thereof using the Smith Normal Form in polynomial time. $\hfill\blacktriangleleft$

Observe that Lemma 19 does not yet imply Theorem 17; we require a bound on the common denominator $q$ which we can write using polynomially many bits and input to the algorithm of Lemma 19. We proceed to prove such a bound.

Proposition 20.

Let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be a finite set of matrices in Wedderburn-Malcev normal form. Let $q^{\prime}$ be a common denominator for the set $X$ of generators. Let $B\subseteq X^{\ast}$ be a basis of the enveloping algebra $\mathrm{Env}(X)$ . Assume the monoid $X^{\ast}$ has some common denominator $q\in\mathbb{N}$ , then also $q:=\det(T_{\operatorname{BlockDiag}(B)})^{d}\cdot(q^{\prime})^{d-1}$ is a common denominator for $X^{\ast}.$

Proof of Proposition 20.

Let $X\subseteq\mathrm{M}_{d}(\mathbb{Q})$ be a finite set of matrices in Wedderburn-Malcev normal form such that $X^{\ast}$ has a common denominator. Just as in Proposition 12, write $X=\{a_{1}+c_{1},\ldots,a_{m}+c_{m}\}\subseteq X^{*}$ , where each $a_{i}$ is block diagonal and each $c_{i}$ strictly upper block triangular. Write $A:=\{a_{1},\ldots,a_{m}\}$ , $C:=\{c_{1},\ldots,c_{m}\}$ and $D:=\{a_{1},\ldots,a_{m},c_{1},\ldots c_{m}\}$ . We first claim that $\det(T_{\operatorname{BlockDiag}(B)})$ is a common denominator for $A^{\ast}$ .

Proof of claim: We first show that $\mathrm{tr}(a)\in\mathbb{Z}$ for all $a\in X^{\ast}$ . Since $X^{\ast}$ has a common denominator $q$ , there exists a conjugation matrix $p\in\mathrm{GL}_{d}(\mathbb{Q})$ such that $p^{-1}X^{\ast}p\subseteq\mathrm{M}_{d}(\mathbb{Z})$ by Proposition 18. In particular, $p^{-1}ap\in\mathrm{M}_{d}(\mathbb{Z})$ . Therefore $tr(p^{-1}ap)\in\mathbb{Z}$ , and since the trace is invariant under base change, we obtain $tr(a)\in\mathbb{Z}$ . This in particular implies that $\mathrm{Tr}_{B}(a)\in\mathbb{Z}^{|B|}$ for all $a\in X^{\ast}$ .

By definition of Wedderburn-Malcev normal form the block diagonal part $a$ for $a+c\in X^{\ast}$ can be uniquely determined from $\mathrm{Tr}_{B}(a)$ . Since $\mathrm{Tr}_{B}(a)\in\mathbb{Z}^{|B|}$ , the denominator of $a$ hence divides the denominator of $\mathrm{Tr}_{B}^{-1}$ . By Cramer’s rule, since $T_{\operatorname{BlockDiag}(B)}$ is an integer matrix, $\det(T_{\operatorname{BlockDiag}(B)})$ is a common denominator for $T_{\operatorname{BlockDiag}(B)}^{-1}$ , finishing the claim.

Since any matrix in $(A^{*}C)^{d}$ is zero, we obtain that $q=(\det(T_{\operatorname{BlockDiag}(B)}))^{d}\cdot(q^{\prime})^{d-1}$ is a common denominator for $D^{\ast}$ . Since any matrix in $X^{\ast}$ is by the distributive law a sum of matrices in $D^{\ast}$ , we obtain that $q$ is also a common denominator for $X^{\ast}$ . $\hfill\blacktriangleleft$

We can now prove Theorem 17.

Proof of Theorem 17.

By Theorem 4 we can transform $X^{\ast}$ to Wedderburn-Malcev normal form with polynomial overhead. Henceforth assume that $X^{\ast}$ is in Wedderburn-Malcev normal form. Compute the number $q=\det(T_{\operatorname{BlockDiag}(B)})^{d}\cdot(q^{\prime})^{d-1}$ of Proposition 20, and output the result of applying Lemma 19 with $(X,q)$ as input. $\hfill\blacktriangleleft$

8 Discussion

While it has been known for over 30 years that determining finiteness of finitely generated matrix groups is in polynomial time, until [4] no elementary bound was known for the case of matrix monoids. The present paper brings the complexity down to polynomial space. It is an interesting question whether this can be further improved. A more fine-grained optimisation of our results would be to improve the exponent in the polynomial bitsize bound in Theorem 13. Another direction for further work concerns the complexity of computing the Zariski closure of a finitely generated matrix monoid. This is a generalisation of the problem of determining finiteness that has various applications in automata theory and program analysis [7]. Currently no elementary upper bounds are known for this problem.

References

[1] Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, and James Worrell. Algebraic closure of matrix sets recognized by 1-vass. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5211–5240. SIAM, 2026. doi:10.1137/1.9781611978971.189.
[2] László Babai, Robert Beals, and Daniel Rockmore. Deciding finiteness of matrix groups in deterministic polynomial time. In ISSAC93, pages 117–126. Association for Computing Machinery, 1993. doi:10.1145/164081.164104.
[3] Jean Berstel and Christophe Reutenauer. Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010.
[4] Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu, and Jonathan Tanner. On the size of finite rational matrix semigroups. In ICALP, volume 168 of LIPIcs, pages 115:1–115:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ICALP.2020.115.
[5] Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell. On learning polynomial recursive programs. Proc. ACM Program. Lang., 8(POPL):1001–1027, 2024. doi:10.1145/3632876.
[6] Leonard Eugene Dickson. Algebras and their Arithmetics. University of Chicago Press, 1924.
[7] Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. Polynomial invariants for affine programs. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 530–539. ACM, 2018. doi:10.1145/3209108.3209142.
[8] Gérard Jacob. Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoretical Computer Science, 5(2):183–204, 1977. doi:10.1016/0304-3975(77)90006-8.
[9] Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499–507, 1979. doi:10.1137/0208040.
[10] Stefan Kiefer and Andrew Ryzhikov. The asymptotic size of finite irreducible semigroups of rational matrices, 2026. doi:10.48550/arXiv.2601.01236.
[11] Arnaldo Mandel and Imre Simon. On finite semigroups of matrices. Theoretical Computer Science, 5(2):101–111, 1977. doi:10.1016/0304-3975(77)90001-9.
[12] Robert McNaughton and Yechezkel Zalcstein. The burnside problem for semigroups. Journal of Algebra, 34(2):292–299, 1975.
[13] Jean-Éric Pin. Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris, 7:73, 2010.
[14] Lajos Rónyai. Algorithmic properties of maximal orders in simple algebras over Q. Computational Complexity, 2(3):225–243, 1992. doi:10.1007/BF01272075.
[15] Marcel Paul Schützenberger. Finite counting automata. Information and Control, 5:91–107, 1962. doi:10.1016/S0019-9958(62)90244-9.
[16] Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72(1):65–94, 1990. doi:10.1016/0304-3975(90)90047-L.
[17] Benjamin Steinberg. A short proof of a bound on the size of finite irreducible semigroups of rational matrices, 2026. doi:10.48550/arXiv.2601.03206.
[18] Andreas Weber and Helmut Seidl. On finitely generated monoids of matrices with entries in N. RAIRO Theor. Informatics Appl., 25:19–38, 1991. doi:10.1051/ITA/1991250100191.

[bib.bib1] [1] Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, and James Worrell. Algebraic closure of matrix sets recognized by 1-vass. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5211–5240. SIAM, 2026. doi:10.1137/1.9781611978971.189.

[bib.bib2] [2] László Babai, Robert Beals, and Daniel Rockmore. Deciding finiteness of matrix groups in deterministic polynomial time. In ISSAC93, pages 117–126. Association for Computing Machinery, 1993. doi:10.1145/164081.164104.

[bib.bib3] [3] Jean Berstel and Christophe Reutenauer. Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010.

[bib.bib4] [4] Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu, and Jonathan Tanner. On the size of finite rational matrix semigroups. In ICALP, volume 168 of LIPIcs, pages 115:1–115:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ICALP.2020.115.

[bib.bib5] [5] Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell. On learning polynomial recursive programs. Proc. ACM Program. Lang., 8(POPL):1001–1027, 2024. doi:10.1145/3632876.

[bib.bib6] [6] Leonard Eugene Dickson. Algebras and their Arithmetics. University of Chicago Press, 1924.

[bib.bib7] [7] Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. Polynomial invariants for affine programs. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 530–539. ACM, 2018. doi:10.1145/3209108.3209142.

[bib.bib8] [8] Gérard Jacob. Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoretical Computer Science, 5(2):183–204, 1977. doi:10.1016/0304-3975(77)90006-8.

[bib.bib9] [9] Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499–507, 1979. doi:10.1137/0208040.

[bib.bib10] [10] Stefan Kiefer and Andrew Ryzhikov. The asymptotic size of finite irreducible semigroups of rational matrices, 2026. doi:10.48550/arXiv.2601.01236.

[bib.bib11] [11] Arnaldo Mandel and Imre Simon. On finite semigroups of matrices. Theoretical Computer Science, 5(2):101–111, 1977. doi:10.1016/0304-3975(77)90001-9.

[bib.bib12] [12] Robert McNaughton and Yechezkel Zalcstein. The burnside problem for semigroups. Journal of Algebra, 34(2):292–299, 1975.

[bib.bib13] [13] Jean-Éric Pin. Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris, 7:73, 2010.

[bib.bib14] [14] Lajos Rónyai. Algorithmic properties of maximal orders in simple algebras over Q. Computational Complexity, 2(3):225–243, 1992. doi:10.1007/BF01272075.

[bib.bib15] [15] Marcel Paul Schützenberger. Finite counting automata. Information and Control, 5:91–107, 1962. doi:10.1016/S0019-9958(62)90244-9.

[bib.bib16] [16] Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72(1):65–94, 1990. doi:10.1016/0304-3975(90)90047-L.

[bib.bib17] [17] Benjamin Steinberg. A short proof of a bound on the size of finite irreducible semigroups of rational matrices, 2026. doi:10.48550/arXiv.2601.03206.

[bib.bib18] [18] Andreas Weber and Helmut Seidl. On finitely generated monoids of matrices with entries in N. RAIRO Theor. Informatics Appl., 25:19–38, 1991. doi:10.1051/ITA/1991250100191.