betaFeedback

WorksComputer Science

Revisiting Finiteness of Matrix Monoids

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 co−NEXPNP\text{co}{-}\text{NEXP}^{\text{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.

2012 ACM Subject Classification Theory of computation →\to Automata over infinite objects

Keywords and phrases Matrix Semigroups, Finiteness, Integrality, Bitsize Bound

Digital Object Identifier 10.4230/LIPIcs.ICALP.2026.170

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).

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

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

Editors: Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis; Article No. 170; pp. 170:1–170:17

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Introduction

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 Q\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 Q\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 dd and a finite set of matrices X⊆Md(Q)X \subseteq M_d(\mathbb{Q}) generating a monoid X∗X^*.

  1. Finiteness Problem: given X⊆Md(Q)X \subseteq M_d(\mathbb{Q}), determine whether X∗X^* is finite.

  2. Finite Membership Problem: given X⊆Md(Q)X \subseteq M_d(\mathbb{Q}) and a target matrix aa, determine whether a∈X∗a \in X^*, under the promise that X∗X^* is finite.

  3. Integrality Problem: given X⊆Md(Q)X \subseteq M_d(\mathbb{Q}), determine whether X∗X^* is conjugate to a matrix monoid with integer entries.

Our first main result shows that the Finiteness Problem is in PSPACE, improving the coNEXP^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.

Context and Related Work

Finiteness is decidable in polynomial time for subgroups of the group GLd(Q)\mathrm{GL}_d(\mathbb{Q}) of invertible matrices in Md(Q)M_d(\mathbb{Q}). If a finite subgroup has generators with integer entries of absolute value at most MM, the entries of every matrix in the group have absolute value at most Md23dd2+3M^{d^2 3d^{d^2+3}} [2 Theorem 1.1]. Finiteness is also decidable in polynomial time for finitely generated submonoids of Md(N)M_d(\mathbb{N}). If such a monoid is finite then it consists of matrices whose entries are at most Mdd−15d/2dM^{d^d-1}5d/2^d [18 Theorem A.2], where MM 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 Md(Q)M_d(\mathbb{Q}) in terms of the dimension dd and the number of generators.

The first elementary bound was obtained only recently, in [4], which shows that the cardinality is bounded by m2O(d2log⁡d)m^{2^{O(d^2 \log d)}}, where dd is the dimension and mm 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 2d(2d+3)g(d)d+12^{d(2d+3)}g(d)^{d+1}, where g(d)≤2dd!g(d) \leq2^d d! is the maximum order of a finite subgroup of GLd(Q)\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⊆Md(Q)M \subseteq M_d(\mathbb{Q}) is irreducible if the only subspaces of Qd\mathbb{Q}^d invariant under all matrices in MM are {0}\{0\} and Qd\mathbb{Q}^d. Schützenberger showed that such a monoid, if finite, has cardinality at most (2d+1)d2(2d+1)^{d^2} [15]. This bound has very recently been improved to 3d23^{d^2}, with an almost matching lower bound of 2⌊d2/4⌋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.

Preliminaries

We write Md,e(R)M_{d,e}(R) for the set of d×ed \times e matrices with entries in a ring RR and denote by Md(R):=Md,d(R)M_d(R) := M_{d,d}(R) the set of square matrices of dimension dd. We denote the d×dd \times d identity matrix by idd\mathrm{id}_d. Given X,Y⊆Md(R)X,Y \subseteq M_d(R), we write XY⊆Md(R)XY \subseteq M_d(R) for the element-wise product and, for r∈Nr \in\mathbb{N}, we write XrX^r for the rr-fold product of XX with itself. Note that X0={idd}X^0 = \{\mathrm{id}_d\}. We also write X≤r:=⋃i=0rXiX^{\leq r} := \bigcup_{i=0}^{r} X^i and X<r:=⋃i=0r−1XiX^{<r} := \bigcup_{i=0}^{r-1} X^i. The submonoid of Md(R)M_d(R) generated by XX is X∗:=⋃i=0∞XiX^* := \bigcup_{i=0}^{\infty} X^i, while the subsemigroup generated by XX is X+:=⋃i=0∞XiX^+ := \bigcup_{i=0}^{\infty} X^i.

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

Height of Matrices

Given a finite set of matrices X⊆Mm,n(Q)X \subseteq M_{m,n}(\mathbb{Q}), and an integer qq, we say that qq is a common denominator of XX if q⋅X⊆Mm,n(Z)q \cdot X \subseteq M_{m,n}(\mathbb{Z}). The height of XX is defined as:

⟦X⟧=max⁡(m,n)⋅q⋅p\llbracket X \rrbracket= \max(m,n) \cdot q \cdot p

where qq is the least common denominator of XX and pp is the maximum absolute value of entries of elements of qXqX.

In particular, for a reduced fraction pq\frac{p}{q} seen as an element of M1(Q)\mathrm{M}_1(\mathbb{Q}) we have ⟦pq⟧=∣pq∣\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⊆Mm,n(Q)X \subseteq\mathrm{M}_{m,n}(\mathbb{Q}) and Y⊆Mn,ℓ(Q)Y \subseteq\mathrm{M}_{n,\ell}(\mathbb{Q}) be finite sets of matrices. Then:

⟦XY⟧≤⟦X⟧⟦Y⟧and⟦∑i=1kX⟧≤k⟦X⟧.(1)\llbracket XY\rrbracket\leq\llbracket X\rrbracket\llbracket Y\rrbracket \qquad\text{and}\qquad \llbracket\sum_{i=1}^{k}X\rrbracket\leq k\llbracket X\rrbracket. \tag*{(1)}

Indeed, observe that given x1,…,xk∈Xx_1,\ldots,x_k \in X, the least common denominator of (x1+…+xk)(x_1+\ldots+x_k) divides the one of XX. 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≥1d \geq1 and let a∈GLd(Q)a \in\mathrm{GL}_d(\mathbb{Q}), then ⟦a−1⟧≤⟦a⟧2d\llbracket a^{-1}\rrbracket\leq\llbracket a\rrbracket^{2d}.

Proof. Let qq be the least common denominator of aa and let pp be the maximum absolute value of entries of b=qab=qa. By Cramer’s rule, b−1=1det⁡(b)cof⁡(b)Tb^{-1} = \frac{1}{\det(b)}\operatorname{cof}(b)^{\mathsf{T}}. From the Hadamard bound,

det⁡(b)≤dd2pd.\det(b) \leq d^{\frac{d}{2}}p^d.

For the same reason, we have ⟦cof⁡(b)⟧≤ddd2pd\llbracket\operatorname{cof}(b)\rrbracket\leq d d^{\frac{d}{2}}p^d. Thus

⟦b−1⟧≤det⁡(b)⟦cof⁡(b)⟧≤ddd2dp2d.\llbracket b^{-1}\rrbracket\leq\det(b)\llbracket\operatorname{cof}(b)\rrbracket\leq d^{d}d^{2d}p^{2d}.

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

⟦a−1⟧≤q⟦b−1⟧≤qdd+1p2d≤⟦a⟧2d.\llbracket a^{-1}\rrbracket\leq q\llbracket b^{-1}\rrbracket\leq qd^{d+1}p^{2d} \leq\llbracket a\rrbracket^{2d}.

Semisimplicity and the Jacobson Radical

A vector space A⊆Md(Q)A \subseteq\mathrm{M}_d(\mathbb{Q}) containing id⁡d\operatorname{id}_d is called an algebra if AA is closed under matrix multiplication. Given X⊆Md(Q)X \subseteq\mathrm{M}_d(\mathbb{Q}), the vector space spanned by X∗X^*, or equivalently the smallest algebra EE containing XX is called the enveloping algebra Env⁡(X)\operatorname{Env}(X). For example, let

a:=(1100),b:=(0101),X:={a,b}.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∗X^* denotes the submonoid generated by XX, which contains the identity matrix id⁡2\operatorname{id}_2. Direct computation gives

a2=a,b2=b,ab=(0200),ba=0.a^2=a,\qquad b^2=b,\qquad ab=\begin{pmatrix}0 & 2 \\ 0 & 0\end{pmatrix},\qquad ba=0.

Hence X∗={id⁡2,0,a,b,ab}X^*=\{\operatorname{id}_2,0,a,b,ab\}. Moreover, ab=a+b−id⁡2ab=a+b-\operatorname{id}_2, and therefore

Env⁡(X)=Span⁡Q{a,b,id⁡2}={(xy0z)∣x,y,z∈Q}.\operatorname{Env}(X)=\operatorname{Span}_{\mathbb{Q}}\{a,b,\operatorname{id}_2\} =\left\{ \begin{pmatrix}x & y\\0 & z\end{pmatrix} \mathrel{\Big|} x,y,z\in\mathbb{Q} \right\}.

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

I1={(xy00)∣x,y∈Q}I2={(0y0z)∣y,z∈Q}I3={(0y00)∣y∈Q}I_1=\left\{ \begin{pmatrix}x & y\\0 & 0\end{pmatrix} \mathrel{\Big|}x,y\in\mathbb{Q} \right\} \qquad I_2=\left\{ \begin{pmatrix}0 & y\\0 & z\end{pmatrix} \mathrel{\Big|}y,z\in\mathbb{Q} \right\} \qquad I_3=\left\{ \begin{pmatrix}0 & y\\0 & 0\end{pmatrix} \mathrel{\Big|}y\in\mathbb{Q} \right\}

are ideals, with I3I_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 I3I_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 tr⁡(a)\operatorname{tr}(a) of a∈Md(Q)a \in M_d(\mathbb{Q}) is the sum of the diagonal entries of aa. An algebra E⊆Md(Q)E \subseteq M_d(\mathbb{Q}) is called semisimple if {0}\{0\} is its only nilpotent ideal. We define J(E):={a∈E∣∀b∈E:tr⁡(ab)=0}J(E) := \{a \in E \mid\forall b \in E : \operatorname{tr}(ab) = 0\} and have the following classical theorem of Dickson [6].

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

Theorem 2 implies that J(E)J(E) is the largest nilpotent ideal, that is, J(E)J(E) is identical to the Jacobson radical of EE. In Section 2.3 and Section 3.1 we will recall a proof of the fact that J(E)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)J(E) as follows. Let B={b1,…,bk}⊆Md(Q)B = \{b_1,\ldots,b_k\} \subseteq M_d(\mathbb{Q}), with k≤d2k \le d^2, be a basis of EE. Define the Q\mathbb{Q}-linear trace map Tr⁡B:E→Qk\operatorname{Tr}_B : E \to\mathbb{Q}^k by

Tr⁡B(a):=(tr⁡(ab1),…,tr⁡(abk)).\operatorname{Tr}_B(a) := \left(\operatorname{tr}(ab_1),\ldots,\operatorname{tr}(ab_k)\right).

With respect to the basis BB on EE this map is represented by the trace matrix

TB=(tr⁡(bibj))1≤i,j≤k(2)T_B = \left(\operatorname{tr}(b_i b_j)\right)_{1 \le i,j \le k} \tag*{(2)}

We have ker⁡(Tr⁡B)=J(E)\ker(\operatorname{Tr}_B) = J(E). Indeed, since the trace tr⁡\operatorname{tr} is a linear map, tr⁡(ab1)=⋯=tr⁡(abk)=0\operatorname{tr}(ab_1) = \cdots= \operatorname{tr}(ab_k) = 0 implies for all b=∑i=1kλibi∈Eb = \sum_{i=1}^{k} \lambda_i b_i \in E that

tr⁡(ab)=tr⁡(a∑i=1kλibi)=∑i=1kλitr⁡(abi)=0.\operatorname{tr}(ab) = \operatorname{tr}\left(a \sum_{i=1}^{k} \lambda_i b_i\right) = \sum_{i=1}^{k} \lambda_i \operatorname{tr}(ab_i) = 0.

Block Decompositions of Matrices

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

{0}=W0⊂W1⊂⋯⊂Wk=Qd.(3)\{0\} = W_0 \subset W_1 \subset\cdots\subset W_k = \mathbb{Q}^d . \tag*{(3)}

We say that a basis B={v1,…,vd}B = \{v_1,\ldots,v_d\} of Qd\mathbb{Q}^d is adapted to the filtration (3) if it arises as the disjoint union of bases of subspaces V1,…,Vk⊆QdV_1,\ldots,V_k \subseteq\mathbb{Q}^d such that Wi=V1⊕⋯⊕ViW_i = V_1 \oplus\cdots\oplus V_i for i∈{0,…,k}i \in\{0,\ldots,k\}. Such an adapted basis can be constructed by first choosing a basis of W1W_1, and then successively extending a basis of WiW_i to a basis of Wi+1W_{i+1}, for i=1,…,k−1i = 1,\ldots,k-1. An algebra E⊆Md(Q)E \subseteq M_d(\mathbb{Q}) is said to preserve the filtration (3) if E⋅Wi⊆WiE \cdot W_i \subseteq W_i for all i∈{0,…,k}i \in\{0,\ldots,k\}. In such a case, let p∈Md(Q)p \in M_d(\mathbb{Q}) be the matrix whose columns are given by BB. Then for all b∈Eb \in E the matrix a:=p−1bpa := p^{-1}bp has the upper block triangular form

a=(a1,1a1,2⋯a1,k0a2,2⋯a2,k⋮0⋱⋮0⋯0ak,k).a = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots& a_{1,k} \\ 0 & a_{2,2} & \cdots& a_{2,k} \\ \vdots& 0 & \ddots& \vdots\\ 0 & \cdots& 0 & a_{k,k} \end{pmatrix}.

where ai,ja_{i,j} has dimension di×djd_i \times d_j for j≥ij \ge i, where di=dim⁡(Vi)d_i = \dim(V_i) and dj=dim⁡(Vj)d_j = \dim(V_j). Here we say that (d1,…,dk)(d_1,\ldots,d_k) is the signature of the block decomposition of aa.

Note that if E=Env⁡(X)E = \operatorname{Env}(X) is the enveloping algebra of a set of matrices X⊆Md(Q)X \subseteq M_d(\mathbb{Q}), then for an invertible matrix p∈Md(Q)p \in M_d(\mathbb{Q}), the conjugated algebra p−1Epp^{-1}Ep is in upper block triangular form if and only if p−1Xpp^{-1}Xp is upper block triangular.

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.

Wedderburn–Malcev Form

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

Proposition 3. Let EE be a sub-algebra of Md(Q)M_d(\mathbb{Q}) and let JJ be a nilpotent ideal in EE. Given a basis BB of JJ, one can compute in polynomial time an invertible matrix p∈Md(Q)p \in M_d(\mathbb{Q}) such that

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

(ii) ⟦p⟧≤⟦B⟧d\llbracket p\rrbracket\le\llbracket B\rrbracket^d and ⟦p−1⟧≤⟦B⟧2d2\llbracket p^{-1}\rrbracket\le\llbracket B\rrbracket^{2d^2}.

Proof. We first show Item (i). Let k≤dk \le d be the nilpotency index of JJ and write Wi:=Jk−iQdW_i := J^{k-i}\mathbb{Q}^d. Then we obtain the following filtration:

{0}=W0⊂W1⊂⋯⊂Wk=Qd.(4)\{0\}=W_0 \subset W_1 \subset\cdots\subset W_k=\mathbb{Q}^d . \tag*{(4)}

The above chain of inclusions is strict. Indeed, if the sequence were not strict then we would have W0=WiW_0=W_i for some i<ki<k. But this contradicts the fact that W0={0}W_0=\{0\} and Wi≠{0}W_i\ne\{0\} by minimality of kk. Note, moreover, that EE preserves the filtration (4). Indeed, since JJ is an ideal, we have E⋅Wi=E⋅Jk−iQd⊆Jk−iQd=WiE\cdot W_i=E\cdot J^{k-i}\mathbb{Q}^d\subseteq J^{k-i}\mathbb{Q}^d=W_i.

Let {v1,…,vd}\{v_1,\ldots,v_d\} be a basis adapted to the filtration in (4), as defined in Section 2.3, and let pp be the matrix whose ii-th column is viv_i, for i∈{1,…,d}i\in\{1,\ldots,d\}. Since EE preserves the filtration, it follows that the conjugated algebra p−1Epp^{-1}Ep consists of upper block triangular matrices. We claim furthermore that the conjugated ideal p−1Jpp^{-1}Jp consists of strictly upper block triangular matrices. To see this, let a∈Ja\in J and i≥1i\ge1. Then the inclusion aWi⊆JWi=Wi−1aW_i\subseteq JW_i=W_{i-1} holds, meaning that multiplication by aa strictly lowers the index in the filtration. This implies that p−1app^{-1}ap is strictly upper block triangular in the adapted basis.

Height analysis: We next establish Item (ii). We start by computing bases BiB_i of the WiW_is. We take BkB_k to be the canonical basis of WkW_k. For i∈{1,…,k}i\in\{1,\ldots,k\}, BiBB_iB spans Wi−1W_{i-1}. By submultiplicativity of the height we obtain bases such that ⟦Bi⟧≤⟦B⟧d\llbracket B_i\rrbracket\le\llbracket B\rrbracket^d for any i∈{1,…,k}i\in\{1,\ldots,k\}. From these bases we can select a basis adapted to the filtration in (4): first select a basis of W1W_1. Then for i∈{1,…,k−1}i\in\{1,\ldots,k-1\}, given a basis adapted to the filtration W0⊂⋯⊂WiW_0\subset\cdots\subset W_i, we can extend it to a basis adapted to W0⊂⋯⊂Wi+1W_0\subset\cdots\subset W_{i+1} by adding vectors from Bi+1B_{i+1}.

Let pp be the change of basis matrix obtained from these vectors, then ⟦p⟧≤⟦B⟧d\llbracket p\rrbracket\le\llbracket B\rrbracket^d. Using Claim 1, above, we obtain ⟦p−1⟧≤⟦B⟧2d2\llbracket p^{-1}\rrbracket\le\llbracket B\rrbracket^{2d^2}.

Theorem 4. There is a polynomial-time algorithm that, given a basis BB of an algebra E⊆Md(Q)E\subseteq M_d(\mathbb{Q}), determines an invertible matrix p∈Md(Q)p\in M_d(\mathbb{Q}) such that p−1Epp^{-1}Ep is in Wedderburn–Malcev form. Moreover we have ⟦p,p−1⟧=⟦B⟧O(d4)\llbracket p,p^{-1}\rrbracket=\llbracket B\rrbracket^{O(d^4)}.

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

J(E)={a∈E∣∀b∈B:tr⁡(ab)=0}.J(E)=\{a\in E\mid\forall b\in B:\operatorname{tr}(ab)=0\}.

Thus we can compute a basis B′B' of J(E)J(E) from BB in polynomial time. Applying Proposition 3 to EE and J:=J(E)J := J(E), given in terms of the basis B′B', we can compute in polynomial time an invertible matrix p∈Md(Q)p \in M_d(\mathbb{Q}) such that p−1Epp^{-1}Ep is upper block triangular and p−1Jpp^{-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′B'. This is similar to the result of Claim 1, except that here the dimension is bounded by d2d^2: ∥B′∥≤∥B∥O(d2)\lVert B'\rVert\le\lVert B\rVert^{O(d^2)}. Applying Proposition 3, we obtain ∥{p,p−1}∥=∥B∥O(d4)\lVert\{p,p^{-1}\}\rVert= \lVert B\rVert^{O(d^4)}.

Diameter Bound for Finite Monoids via Factorisation Forests

Recall that a finitely generated monoid has diameter DD if every element of the monoid can be written as the product of a list of generators of length at most DD. 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 φ:Σ+→Md(Q)\varphi: \Sigma^+ \to M_d(\mathbb{Q}), a Ramseyan factorisation forest of a word w∈Σ+w \in\Sigma^+ is a finite unranked plane tree whose nodes are labelled with elements of Σ+\Sigma^+. The root is labelled ww, the children have labels in Σ\Sigma, and an internal node with label xx whose children are labelled x0,…,xs−1x_0,\ldots,x_{s-1}, satisfies

(i) φ(x)=φ(x0x1⋯xs−1)\varphi(x) = \varphi(x_0x_1\cdots x_{s-1}), and

(ii) if s≥3s \ge3 then φ(x0),…,φ(xs−1)\varphi(x_0),\ldots,\varphi(x_{s-1}) generate a subgroup of Md(Q)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∈Σ+w \in\Sigma^+ has a Ramseyan factorisation forest of height at most 2d(d+3)2d(d+3) and reduced height at most dd.

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

Corollary 6. [4 Theorem 1] Let dd be a positive integer and let X⊆Md(Q)X \subseteq M_d(\mathbb{Q}). If X∗X^* is finite, then its diameter is at most 22d(d+3)g(d)d2^{2d(d+3)}g(d)^d, where g(d)g(d) is the maximum cardinality of a subgroup of Md(Q)M_d(\mathbb{Q}).

Proof. Let φ:Σ+→Md(Q)\varphi: \Sigma^+ \to M_d(\mathbb{Q}) be a morphism such that φ(Σ)=X\varphi(\Sigma) = X. With respect to φ\varphi, every word w∈Σ+w \in\Sigma^+ has a Ramseyan factorisation forest of height at most 2d(d+3)2d(d+3) and reduced height at most dd. We can moreover assume that the non-binary nodes of such a tree have arity at most g(d)g(d). Such a tree thus has at most 22d(d+3)g(d)d2^{2d(d+3)}g(d)^d leaves. The result follows.

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 φ:Σ+→Md(Q)\varphi: \Sigma^+ \to M_d(\mathbb{Q}), a weak factorisation forest of a word w∈Σ+w \in\Sigma^+ is a finite unranked plane tree whose nodes are labelled with elements of Σ+\Sigma^+. root is labelled ww, the children have labels in Σ\Sigma, and a node with label xx whose children are labelled x0,…,xs−1x_0,\ldots,x_{s-1}, satisfies

(i) φ(x)=φ(x0x1⋯xs−1)\varphi(x)=\varphi(x_0x_1\cdots x_{s-1}), and

(ii) if ∣s∣≥3|s|\ge3 then rk⁡(φ(x0))=⋯=rk⁡(φ(xs−1))=rk⁡(φ(x))=rk⁡(φ(x)2)\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 φ:Σ+→Md(Q)\varphi:\Sigma^+\to M_d(\mathbb{Q}) be a semigroup morphism. Then every word has a weak factorisation forest of height ≤d(d+3)\le d(d+3) and reduced height ≤d\le d.

Recall that the notion of Ramseyan factorisation forest strengthens Condition (ii) to the requirement that φ(x0),…,φ(xs−1)\varphi(x_0),\ldots,\varphi(x_{s-1}) generate a subgroup of Md(Q)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 a1,…,aℓ∈Md(Q)a_1,\ldots,a_\ell\in M_d(\mathbb{Q}) and a:=a1⋯aℓa:=a_1\cdots a_\ell. Assume that

rk⁡(a1)=⋯=rk⁡(aℓ)=rk⁡(a)(5)\operatorname{rk}(a_1)=\cdots=\operatorname{rk}(a_\ell)=\operatorname{rk}(a) \tag*{(5)}

Then there exist 1=i1<i2<⋯<it=ℓ1=i_1<i_2<\cdots<i_t=\ell, where t≤2d+1t\le2^{d+1}, such that ker⁡(a)=ker⁡(ai1⋯ait)\operatorname{ker}(a)=\operatorname{ker}(a_{i_1}\cdots a_{i_t}) and im⁡(a)=im⁡(ai1⋯ait)\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≥3s\ge3 and w,w0,…,ws−1∈Σ+w,w_0,\ldots,w_{s-1}\in\Sigma^+ such that:

  • φ(w)=φ(w0w1⋯ws−1)\varphi(w)=\varphi(w_0w_1\cdots w_{s-1}).

  • rk⁡(φ(w0))=⋯=rk⁡(φ(ws−1))=rk⁡(φ(w))=rk⁡(φ(w)2)\operatorname{rk}(\varphi(w_0))=\cdots=\operatorname{rk}(\varphi(w_{s-1}))=\operatorname{rk}(\varphi(w))=\operatorname{rk}(\varphi(w)^2).

Then there exist u0,…,ut−1∈{w0,…,ws−1}≤2d+2u_0,\ldots,u_{t-1}\in\{w_0,\ldots,w_{s-1}\}^{\le2^{d+2}} such that φ(w)=φ(u0⋯ut−1)\varphi(w)=\varphi(u_0\cdots u_{t-1}) and, moreover, φ(u0),…,φ(ut−1)\varphi(u_0),\ldots,\varphi(u_{t-1}) generate a subgroup of Md(Q)M_d(\mathbb{Q}).

Proof. For i∈{0,…,s−2}i\in\{0,\ldots,s-2\}, we apply Lemma 8 to φ(wi+1)φ(wi+2)⋯φ(ws−1)\varphi(w_{i+1})\varphi(w_{i+2})\cdots\varphi(w_{s-1}) and φ(w0)φ(w1)⋯φ(wi)\varphi(w_0)\varphi(w_1)\cdots\varphi(w_i) respectively to obtain xi,yi∈{w0,…,ws−1}≤2d+1x_i,y_i\in\{w_0,\ldots,w_{s-1}\}^{\le2^{d+1}} such that

  • im⁡(φ(xi))=im⁡(φ(wi+1))\operatorname{im}(\varphi(x_i))=\operatorname{im}(\varphi(w_{i+1})), ker⁡(φ(xi))=ker⁡(φ(ws−1))\operatorname{ker}(\varphi(x_i))=\operatorname{ker}(\varphi(w_{s-1})).

  • im⁡(φ(yi))=im⁡(φ(w0))\operatorname{im}(\varphi(y_i))=\operatorname{im}(\varphi(w_0)), ker⁡(φ(yi))=ker⁡(φ(wi))\operatorname{ker}(\varphi(y_i))=\operatorname{ker}(\varphi(w_i)).

From the rank condition rk⁡(φ(w0))=⋯=rk⁡(φ(ws−1))=rk⁡(φ(w))=rk⁡(φ(w)2)\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⁡(φ(yi))∩im⁡(φ(xi))={0}\operatorname{ker}(\varphi(y_i))\cap\operatorname{im}(\varphi(x_i))=\{0\}, which implies that

ker⁡(φ(yixi))=ker⁡(φ(xi))=ker⁡(φ(ws−1)),im⁡(φ(yixi))=im⁡(φ(yi))=im⁡(φ(w0)).\operatorname{ker}(\varphi(y_ix_i))=\operatorname{ker}(\varphi(x_i))=\operatorname{ker}(\varphi(w_{s-1})),\qquad\operatorname{im}(\varphi(y_ix_i))=\operatorname{im}(\varphi(y_i))=\operatorname{im}(\varphi(w_0)).

Let pp be the smallest integer such that φ(yixi)p=φ(yixi)2p\varphi(y_ix_i)^p=\varphi(y_ix_i)^{2p} for all ii. Such an integer pp exists since φ\varphi has a finite image. Moreover, φ(yixi)p\varphi(y_ix_i)^p acts as the identity on im⁡(φ(yixi))=im⁡(φ(w0))\operatorname{im}(\varphi(y_ix_i))=\operatorname{im}(\varphi(w_0)). We then rewrite φ(w)\varphi(w) as

φ(w)=φ(w0x0)φ(y0x0)p−1φ(y0w1x1)φ(y1x1)p−1⋯φ(ys−2xs−2)p−1φ(ys−2ws−1).\varphi(w)=\varphi(w_0x_0)\varphi(y_0x_0)^{p-1}\varphi(y_0w_1x_1)\varphi(y_1x_1)^{p-1}\cdots\varphi(y_{s-2}x_{s-2})^{p-1}\varphi(y_{s-2}w_{s-1}).

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

(w0x0,y0x0,…,y0x0⏟p−1 times,y0w1x1,y1x1,…,y1x1⏟p−1 times,…,ys−2xs−2,…,ys−2xs−2⏟p−1 times,ys−2ws−1).\left(w_0x_0,\underbrace{y_0x_0,\ldots,y_0x_0}_{p-1\ \text{times}},y_0w_1x_1,\underbrace{y_1x_1,\ldots,y_1x_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}\right).

Then each uju_j belongs to {w0,…,ws−1}≤2d+2\{w_0,\ldots,w_{s-1}\}^{\leq2d+2}, and φ(w)=φ(u0⋯ut−1)\varphi(w)=\varphi(u_0\cdots u_{t-1}). Let G={φ(u0),…,φ(ut−1)}⊆Md(Q)G=\{\varphi(u_0),\ldots,\varphi(u_{t-1})\}\subseteq M_d(\mathbb{Q}). Note that for every 0≤i≤t−10\leq i\leq t-1, uiu_i has one of the forms w0x0w_0x_0, yjxjy_jx_j, yjwj+1xj+1y_jw_{j+1}x_{j+1}, ys−2ws−1y_{s-2}w_{s-1}. Therefore, for every 0≤i≤t−10\leq i\leq t-1, ker⁡(φ(ui))=ker⁡(φ(ws−1))\ker(\varphi(u_i))=\ker(\varphi(w_{s-1})), im⁡(φ(ui))=im⁡(φ(w0))\operatorname{im}(\varphi(u_i))=\operatorname{im}(\varphi(w_0)), and moreover, ker⁡(φ(ui))∩im⁡(φ(ui))={0}\ker(\varphi(u_i))\cap\operatorname{im}(\varphi(u_i))=\{0\}. Since the φ(ui)\varphi(u_i) all have the same kernel UU and image VV such that moreover U∩V={0}U\cap V=\{0\}, GG is isomorphic to a finite monoid of invertible linear endomorphisms of VV, i.e. is a group.

Proof of Theorem 5. We will show that every v∈Σ+v\in\Sigma^+ has a Ramseyan factorisation forest of height at most 2d(d+3)2d(d+3), and reduced height at most dd. Fix v∈Σ+v\in\Sigma^+. The construction of the Ramseyan factorisation forest of vv relies on the weak factorisation forest given in Theorem 7. Let TT be the weak factorisation forest of vv, with height at most d(d+3)d(d+3) and reduced height at most dd. We modify TT 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 ww has more than two children labelled w0,…,ws−1w_0,\ldots,w_{s-1}, apply Proposition 9 to that node, and replace that node by the corresponding subtree as in Figure 1. Each application of

A schematic Ramseyan factorisation tree

Figure 1. A schematic Ramseyan factorisation tree for ww with leaves among wiw_i of height ≤d+3\leq d+3. The root ww is decomposed into u0,u1,…,ut−1u_0,u_1,\ldots,u_{t-1}. We display u0=w0x0u_0=w_0x_0, u1=y0x0,…,ut−1=ys−1ws−1u_1=y_0x_0,\ldots,u_{t-1}=y_{s-1}w_{s-1}. Each factor xi,yix_i,y_i is further refined by a binary subtree down to leaves among the wjw_j.

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

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 dd. 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 § 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∗⊆Md(Q)X^*\subseteq M_d(\mathbb{Q}) be a finite monoid. Then tr⁡(a)∈{−d,…,d}\operatorname{tr}(a)\in\{-d,\ldots,d\} for all a∈X∗a\in X^*.

Proof. Consider a matrix a∈X∗a \in X^*. Since X∗X^* is finite, there exists m>nm>n such that am=ana^m=a^n. It follows that the minimal polynomial of aa divides xn−xmx^n-x^m, i.e. every eigenvalue of aa is either 00 or a root of unity. In particular, ∣λ∣≤1|\lambda|\leq1 for all eigenvalues λ\lambda of aa and hence ∣tr⁡(a)∣=∣∑i=1dλi∣≤d|\operatorname{tr}(a)|=\left|\sum_{i=1}^{d}\lambda_i\right|\leq d. As a sum of algebraic integers, tr⁡(a)\operatorname{tr}(a) is itself an algebraic integer. Since tr⁡(a)\operatorname{tr}(a) is moreover rational and Z\mathbb{Z} integrally closed in Q\mathbb{Q}, we obtain tr⁡(a)∈Z\operatorname{tr}(a)\in\mathbb{Z}. The lemma immediately follows.

Theorem 11. Let X∗⊆Md(Q)X^* \subseteq\mathrm{M}_d(\mathbb{Q}) be a finite monoid such that Env⁡(X)\operatorname{Env}(X) is semisimple, with a basis B⊆X∗B\subseteq X^*. Then \left\llbracket X^*\right\rrbracket=d^{O(d^2)}\left\llbracket B\right\rrbracket.

Proof. Let X⊆Md(Q)X\subseteq\mathrm{M}_d(\mathbb{Q}) be such that X∗X^* is finite and Env⁡(X)\operatorname{Env}(X) semisimple. One can choose BB a basis of Env⁡(X)\operatorname{Env}(X) within X≤d2−1X^{\leq d^2-1} since Env⁡(X)\operatorname{Env}(X) has dimension at most d2d^2 (and idd∈X∗\mathrm{id}_d\in X^*). From Equation (1), \left\llbracket B\right\rrbracket\leq\left\llbracket X\right\rrbracket^{d^2}.

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

Let a∈X∗a\in X^* and let α=(αb)b∈B∈QB\alpha=(\alpha_b)_{b\in B}\in\mathbb{Q}^B be such that a=∑b∈Bαbba=\sum_{b\in B}\alpha_b b. Then for any c∈Bc\in B, tr⁡(ca)=∑b∈Bαbtr⁡(cb)=(TBα)c\operatorname{tr}(ca)=\sum_{b\in B}\alpha_b\operatorname{tr}(cb)=(T_B\alpha)_c. By Lemma 10, the vector TBαT_B\alpha has entries in {−d,…,d}\{-d,\ldots,d\}, and thus has height at most d3d^3. We write a=∑b∈B(TB−1TBα)bba=\sum_{b\in B}(T_B^{-1}T_B\alpha)_b b. Let A=TB−1{−d,…,d}BA=T_B^{-1}\{-d,\ldots,d\}^B and let CC be the set of entries of elements of AA. Then \left\llbracket C\right\rrbracket\leq\left\llbracket A\right\rrbracket\leq(d^3)^{2d^2+1}. Then since X∗⊆∑b∈BCBX^*\subseteq\sum_{b\in B}CB, we have by triangle inequality that:

\left\llbracket X^*\right\rrbracket\leq d^2\left\llbracket C\right\rrbracket\left\llbracket B\right\rrbracket\leq d^2(d^3)^{2d^2+1}\left\llbracket B\right\rrbracket=d^{O(d^2)}\left\llbracket B\right\rrbracket

Proposition 12. Let X∗⊆Md(Q)X^*\subseteq\mathrm{M}_d(\mathbb{Q}) be a finite monoid such that Env⁡(X)\operatorname{Env}(X) is in Wedderburn–Malcev form, with a basis B⊆X∗B\subseteq X^*. Then \left\llbracket X^*\right\rrbracket=d^{O(d^3)}\left\llbracket X\right\rrbracket^d\left\llbracket B\right\rrbracket^d.

Proof. By assumption we can write the set of generators of Env⁡(X)\operatorname{Env}(X) as X={a1+c1,…,am+cm}⊆X∗X=\{a_1+c_1,\ldots,a_m+c_m\}\subseteq X^*, where each aia_i is block diagonal and each cic_i strictly upper triangular on blocks. Write A:={a1,…,am}A:=\{a_1,\ldots,a_m\}, C:={c1,…,cm}C:=\{c_1,\ldots,c_m\} and D:={a1,…,am,c1,…,cm}D:=\{a_1,\ldots,a_m,c_1,\ldots,c_m\}.

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

Let a∈X∗a\in X^*. By Corollary 6, aa can be written as a product of at most

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

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

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

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

size⁡(X)≤log⁡(⟦X⟧)≤(2d2+1)size⁡(X)+log⁡d(6)\operatorname{size}(X) \le\log(\llbracket X\rrbracket) \le(2d^{2}+1)\operatorname{size}(X) + \log d \tag*{(6)}
size⁡(X)≤log⁡(⟦X⟧)≤size⁡(X)+log⁡d,(7)\operatorname{size}(X) \le\log(\llbracket X\rrbracket) \le\operatorname{size}(X) + \log d, \tag*{(7)}

if XX has integer entries.

Theorem 13. Let X⊆Md(Q)X \subseteq\mathrm{M}_{d}(\mathbb{Q}) such that X∗X^{*} is finite, then ⟦X∗⟧=⟦X⟧O(d7)\llbracket X^{*}\rrbracket= \llbracket X\rrbracket^{O(d^{7})}, where the constant in the big-oh notation is absolute1. As a consequence size⁡(X∗)=O(d9size⁡(X))\operatorname{size}(X^{*}) = O(d^{9}\operatorname{size}(X)).

Note that if X⊆Md(Z)X \subseteq\mathrm{M}_{d}(\mathbb{Z}), then size⁡(X∗)=O(d7(log⁡d+size⁡(X)))\operatorname{size}(X^{*}) = O(d^{7}(\log d+\operatorname{size}(X))).

Proof. The first step is to compute a basis BB of Env⁡(X)\operatorname{Env}(X). Since Env⁡(X)\operatorname{Env}(X) has dimension at most d2d^{2}, one can find a basis within Xd2−1X^{d^{2}-1}, which gives ⟦B⟧≤⟦X⟧d2\llbracket B\rrbracket\le\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 pp such that ⟦p−1(X∪B)p⟧=⟦X⟧O(d6)\llbracket p^{-1}(X \cup B)p\rrbracket= \llbracket X\rrbracket^{O(d^{6})}. Finally, by applying Proposition 12, we obtain that

⟦X∗⟧≤⟦p⟧⟦p−1X∗p⟧⟦p−1⟧=⟦X⟧O(d7).\llbracket X^{*}\rrbracket\le\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 XX contains only integer matrices then using Equation (7), we obtain the result.

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\mathsf{PSPACE}.

Proof. PSPACE\mathsf{PSPACE} membership is a consequence of the following nondeterministic polynomial-space algorithm for deciding infiniteness. The algorithm maintains a matrix a∈X∗a \in X^{*}, that is initially the identity. At each step, the algorithm nondeterministically chooses b∈Xb \in X and makes the assignment a:=aba := 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.)

Proposition 15. The Finite Membership Problem is PSPACE\mathsf{PSPACE}-complete.

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

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

PSPACE-hardness in Proposition 15

Recall that the DFA intersection emptiness problem asks, given n∈Nn \in\mathbb{N} and DFAs D1,…,DnD_1,\ldots,D_n over a common alphabet Σ\Sigma, whether the intersection of their languages is nonempty.

For simplicity, we think of each DFA DiD_i as a weighted N\mathbb{N}-automaton (αi,(Mσ,i)σ∈Σ,γi)(\alpha_i,(M_{\sigma,i})_{\sigma\in\Sigma},\gamma_i) with did_i states, where αi∈{0,1}1×di\alpha_i \in\{0,1\}^{1\times d_i} is the initial row vector, Mσ,i∈{0,1}di×diM_{\sigma,i} \in\{0,1\}^{d_i\times d_i} is the transition matrix of σ∈Σ\sigma\in\Sigma and γi∈{0,1}di×1\gamma_i \in\{0,1\}^{d_i\times1} is the final column vector. By construction, the weighted automaton (αi,(Mσ,i)σ∈Σ,γi)(\alpha_i,(M_{\sigma,i})_{\sigma\in\Sigma},\gamma_i) counts the number of runs of DiD_i on a given word. Since each DiD_i is deterministic, the value of the weighted automaton on a word w∈Σ∗w \in\Sigma^* is 1 if DiD_i accepts ww and 0 otherwise.

The reduction constructs 3+∣Σ∣3+|\Sigma| matrices of dimension d:=2+∑i=1ndid := 2+\sum_{i=1}^{n}d_i, namely Minit,Mend,MtM_{\mathrm{init}},M_{\mathrm{end}},M_t, and MσM_\sigma for each σ∈Σ\sigma\in\Sigma. The matrix MtM_t is the target matrix, and the question is to check whether MtM_t lies in the monoid generated by the other matrices. Below, for simplicity of notation, we extend the map σ↦Mσ,i\sigma\mapsto M_{\sigma,i} to a monoid homomorphism Σ∗\Sigma^* in a natural way (where for the empty word ε\varepsilon the matrix Mε,iM_{\varepsilon,i} is the identity matrix for appropriate size). Analogously, we extend the maps σ↦Mσ\sigma\mapsto M_\sigma to Σ∗\Sigma^*. The idea is to simulate the computation of all weighted automata (αi,(Mσ,i)σ∈Σ,γi)(\alpha_i,(M_{\sigma,i})_{\sigma\in\Sigma},\gamma_i) over words ww, that is by definition αiMw,iγi\alpha_iM_{w,i}\gamma_i, simultaneously by the matrix product MinitMwMendM_{\mathrm{init}}M_wM_{\mathrm{end}}.

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

Minit:=(0α1α2⋯αn00(d−1)×d)andMend:=(0d×(d−1)0γ1γ2⋮γn0).\begin{aligned} M_{\mathrm{init}}&:=\begin{pmatrix}0&\alpha_1&\alpha_2&\cdots&\alpha_n&0\\0_{(d-1)\times d}\end{pmatrix} \quad\text{and}\quad M_{\mathrm{end}}:=\begin{pmatrix}0_{d\times(d-1)}\\0\\\gamma_1\\\gamma_2\\\vdots\\\gamma_n\\0\end{pmatrix}. \end{aligned}

For σ∈Σ\sigma\in\Sigma, the matrix MσM_\sigma simulates simultaneously applying the transition matrices Mσ,iM_{\sigma,i}, relying on the block multiplication:

Mσ:=(01×d01×d101×d2⋯01×dn01×d0d1×1Mσ,10d1×d2⋯0d1×dn0d1×10d2×10d2×d1Mσ,2⋯0d2×dn0d2×1⋮⋮⋮⋱⋮⋮0dn×10dn×d10dn×d2⋯Mσ,n0dn×101×d01×d101×d2⋯01×dn01×d).M_\sigma:= \begin{pmatrix} 0_{1\times d} & 0_{1\times d_1} & 0_{1\times d_2} & \cdots& 0_{1\times d_n} & 0_{1\times d}\\ 0_{d_1\times1} & M_{\sigma,1} & 0_{d_1\times d_2} & \cdots& 0_{d_1\times d_n} & 0_{d_1\times1}\\ 0_{d_2\times1} & 0_{d_2\times d_1} & M_{\sigma,2} & \cdots& 0_{d_2\times d_n} & 0_{d_2\times1}\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 0_{d_n\times1} & 0_{d_n\times d_1} & 0_{d_n\times d_2} & \cdots& M_{\sigma,n} & 0_{d_n\times1}\\ 0_{1\times d} & 0_{1\times d_1} & 0_{1\times d_2} & \cdots& 0_{1\times d_n} & 0_{1\times d} \end{pmatrix}.

The target matrix MtM_t is zero everywhere except in its top-right entry, where it is nn.

We argue the correctness of the reduction as follows. Let X:={Minit,Mend}∪{Mσ∣σ∈Σ}X := \{M_{\mathrm{init}},M_{\mathrm{end}}\}\cup\{M_\sigma\mid\sigma\in\Sigma\}. By the block matrix multiplication, X+MinitX∗={0}X^+M_{\mathrm{init}}X^*=\{0\} and X∗MendX+={0}X^*M_{\mathrm{end}}X^+=\{0\}. Hence we can restrict ourselves to products Minit≤1MwMend≤1M_{\mathrm{init}}^{\leq1}M_wM_{\mathrm{end}}^{\leq1} with w∈Σ∗w\in\Sigma^*. Moreover, we can assume the form MinitMwMendM_{\mathrm{init}}M_wM_{\mathrm{end}}, otherwise the top-right entry is 0 instead of nn.

By a simple induction, we can see that MinitMwM_{\mathrm{init}}M_w, with w∈Σ∗w\in\Sigma^*, is in the following form:

MinitMw:=(0α1Mw,1⋯αnMw,n00(d−1)×d)(8)M_{\mathrm{init}}M_w:= \begin{pmatrix} 0&\alpha_1M_{w,1}&\cdots&\alpha_nM_{w,n}&0\\ 0_{(d-1)\times d} \end{pmatrix} \tag*{(8)}

where the base of induction (w=εw=\varepsilon) holds by the definition of MinitM_{\mathrm{init}}, and the induction step follows by block multiplication. Given the form in (8), it follows that MinitMwMendM_{\mathrm{init}}M_wM_{\mathrm{end}} is a zero matrix, except in its top-right entry, where it stores ∑i=1nαiMw,iγi\sum_{i=1}^{n} \alpha_i M_{w,i}\gamma_i. The latter is nn if and only if ww is accepted by all DiD_i. To conclude the proof, we note that entries of matrices in the monoid range over {0,…,n}\{0,\ldots,n\}, hence the monoid is finite.

Extension to semirings: The proof extends for matrices over any semiring R≠{0}R \ne\{0\} and irreducible monoids as follows. To extend to a semiring R≠{0}R \ne\{0\}, we have to prevent addition 1+11+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+∑i=1ndid := 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 nn runs on the same target state, for every DFA DiD_i we have a separate target state which checks whether the corresponding DFA accepts. Formally, we still use 3+∣Σ∣3+|\Sigma| matrices MinitM_{\mathrm{init}}, MendM_{\mathrm{end}}, MtM_t and MσM_\sigma for every σ\sigma. The matrices MinitM_{\mathrm{init}} and MσM_\sigma are as defined above, extended with n−1n-1 additional zero columns at the right. The matrices MtM_t and MendM_{\mathrm{end}} are now defined as follows, the left matrix being MtM_t and the right matrix is MendM_{\mathrm{end}}.

(0d×(d−n)11×n0(d−1)×n)(0(d−n)×(d−n)00⋯0γ10d1×1⋯0d1×10d2×1γ2⋱⋮⋮⋱⋱0dn−1×10dn×1⋯0dn×1γn0n×d)\left( \begin{array}{c|c} 0_{d\times(d-n)} & 1_{1\times n}\\ \hline 0_{(d-1)\times n} & \end{array} \right) \qquad \left( \begin{array}{c|cccc} 0_{(d-n)\times(d-n)} & 0 & 0 & \cdots& 0\\ \hline & \gamma_1 & 0_{d_1\times1} & \cdots& 0_{d_1\times1}\\ & 0_{d_2\times1} & \gamma_2 & \ddots& \vdots\\ & \vdots& \ddots& \ddots& 0_{d_{n-1}\times1}\\ & 0_{d_n\times1} & \cdots& 0_{d_n\times1} & \gamma_n\\ \hline 0_{n\times d} & & & & \end{array} \right)

We argue correctness similarly to the above. Let X:={Minit,Mend}∪{Mσ∣σ∈Σ}X := \{M_{\mathrm{init}},M_{\mathrm{end}}\}\cup\{M_\sigma\mid\sigma\in\Sigma\}. Again, X+MinitX∗={0}X^+M_{\mathrm{init}}X^*=\{0\} and X∗MendX+={0}X^*M_{\mathrm{end}}X^+=\{0\}. Hence we can restrict ourselves to products Minit≤1MwMend≤1M_{\mathrm{init}}^{\leq1}M_wM_{\mathrm{end}}^{\leq1} with w∈Σ∗w\in\Sigma^*. Again, we can assume MinitMwMendM_{\mathrm{init}}M_wM_{\mathrm{end}}, as otherwise the top-right entries are 0 instead of 1. With a similar induction as before, we observe that MinitMwMendM_{\mathrm{init}}M_wM_{\mathrm{end}} is a zero matrix, except in the top-right entries, where the ii-th entry stores αiMw,iγi\alpha_iM_{w,i}\gamma_i, i.e. is equal to 1 if and only if the DFA DiD_i accepts ww. Hence all these entries are equal to 1 as in MtM_t if and only if ww is accepted by all DiD_i. Moreover, observe that every a∈X∗a\in X^* fulfills a∈{0,1}d×da\in\{0,1\}^{d\times d}, because the only operations performed are 0+0=00+0=0, 1+0=11+0=1, 1⋅0=01\cdot0=0 and 1⋅1=11\cdot1=1 which hold in every semiring RR.

Extension to Irreducible Finite Monoids: A monoid M⊆Md(Q)M\subseteq M_d(\mathbb{Q}) is called irreducible if there is no vector space 0⊊V⊊Qd0\subsetneq V\subsetneq\mathbb{Q}^d such that V⋅M⊆VV\cdot M\subseteq V, i.e. no vector space stable under multiplication by MM. We will show that membership is PSPACE-hard also for irreducible finite monoids MM.

Proposition 16. Membership is PSPACE-hard even under the promise that X∗X^* is an irreducible finite matrix monoid.

Proof. We again use d:=1+n+∑i=1ndid:=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+∣Σ∣+2(d−1)3+|\Sigma|+2(d-1) many matrices. The first 3+∣Σ∣3+|\Sigma| matrices are MinitM_{\mathrm{init}}, MendM_{\mathrm{end}}, MtM_t and MσM_\sigma for every σ∈Σ\sigma\in\Sigma as before, they even have exactly the same definition as in the semiring reduction. Again, MtM_t is the target matrix. The new matrices are {δ1,j∣j∈{2,…,d}}\{\delta_{1,j}\mid j\in\{2,\ldots,d\}\} and {δi,1∣i∈{2,…,d}}\{\delta_{i,1}\mid i\in\{2,\ldots,d\}\}, where δi,j\delta_{i,j} is the Kronecker delta, i.e. the matrix with every entry 0 except a 1 at the intersection of the ii-th row and jj-th column. These matrices are added purely to ensure irreducibility. Namely δj,1\delta_{j,1} resets the jj-th state to the initial state, and is otherwise 0. The matrix δ1,j\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∗X^* is still finite: In the semiring reduction we argued that X∗⊆{0,1}d×dX^* \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′∈Xconcat∗w' \in X^*_{\mathrm{concat}} be any word of generator matrices (we do not yet identify w′w' with an element of the monoid, hence we clarify that the * is concatenation here) which evaluates to MtM_t. We claim that there is a word w′′w'' without δ\delta’s which also evaluates to the target.

Proof of claim: If w′w' does not contain δ\delta’s we are done. Hence assume that w′[k]=δi,jw'[k] = \delta_{i,j} for some i,j,ki,j,k, i.e. that some matrix used is δi,j\delta_{i,j}. Then the product w′[1]⋯w′[k]w'[1]\cdots w'[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′[k′]=Minitw'[k'] = M_{\mathrm{init}} for some k′>kk' > k. In order for MinitM_{\mathrm{init}} to not lead to the 0 matrix, the non-zero column must have been the first column. The only generators x∈Xx \in X where the first column is non-zero are δj,1\delta_{j,1} for some jj. Hence we have w′[k′−1]=δj,1w'[k'-1] = \delta_{j,1} for some jj. But then the product w′[1]⋯w′[k′−1]w'[1]\cdots w'[k'-1] is useless. Removing it from the product, we obtain a new word w′′=w′[k′]⋯w′[∣w′∣]w'' = w'[k']\cdots w'[|w'|] with fewer δ\delta’s. Repeating the process, we eventually arrive at a word w′′w'' 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∗X^* is irreducible. Let 0⊊V0 \subsetneq V be a vector space such that V⋅X⊆VV \cdot X \subseteq V. We have to show that V=QdV = \mathbb{Q}^d. Since 0⊊V0 \subsetneq V, there exists some 0≠v∈V0 \ne v \in V. Let jj be such that v[j]≠0v[j] \ne0. By applying the matrix δj,1\delta_{j,1}, we reach the vector (v[j],0,…,0)∈V(v[j],0,\ldots,0) \in V. Since VV is a vector space, i.e. closed under scalar multiplication, we have e1∈Ve_1 \in V where e1∈Qde_1 \in\mathbb{Q}^d is the first unit vector. By applying δ1,j\delta_{1,j} we obtain ej∈Ve_j \in V also for the other unit vectors, i.e. j=2,…,dj = 2,\ldots,d, which finishes the proof that V=QdV = \mathbb{Q}^d. ◀

Integrality

For a finite set X⊆Md(Q)X \subseteq M_d(\mathbb{Q}), the decision version of the Integrality Problem asks whether XX is conjugate to a set of integral matrices, while the function version computes a conjugation matrix p∈GLd(Q)p \in\mathrm{GL}_d(\mathbb{Q}) such that p−1Xp⊆Md(Z)p^{-1}Xp \subseteq M_d(\mathbb{Z}). Observe that a set XX is conjugate to a set of integral matrices if and only if this holds for the set X∗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⊆Md(Q)X \subseteq M_d(\mathbb{Q}) be finite, and consider the Z\mathbb{Z}-module LL generated by the set of vectors X∗⋅ZdX^* \cdot\mathbb{Z}^d. Then the following are equivalent:

  1. LL is a free Z\mathbb{Z}-module of rank dd;

  2. there exists p∈GLd(Q)p \in\mathrm{GL}_d(\mathbb{Q}) such that p−1Xp⊆Md(Z)p^{-1}Xp \subseteq M_d(\mathbb{Z});

  3. there exists a common denominator qq, i.e. q∈Z∖{0}q \in\mathbb{Z} \setminus\{0\} such that q⋅X∗⊆Md(Z)q \cdot X^* \subseteq M_d(\mathbb{Z}).

Proof. We first show that Item 1 implies Item 2. Let v1,…,vd∈Qdv_1,\ldots,v_d \in\mathbb{Q}^d be a Z\mathbb{Z}-basis of LL and define p∈GLd(Q)p \in\mathrm{GL}_d(\mathbb{Q}) as the matrix whose ii-th column is viv_i, for i∈{1,…,d}i \in\{1,\ldots,d\}. Given a∈Xa \in X, since aL⊆LaL \subseteq L, for all i∈{1,…,d}thereexistsi \in\{1,\ldots,d\} there existsb_i \in \mathbb{Z}^d$ such that avi=pbiav_i = pb_i. Defining bb as the matrix with the columns bib_i we obtain ap=pbap = pb. Hence, p−1ap=b∈Md(Z)p^{-1}ap = b \in M_d(\mathbb{Z}). We next show that Item 2 implies Item 3. Assume that there exists p∈GL⁡d(Q)p \in\operatorname{GL}_{d}(\mathbb{Q}) such that p−1Xp⊆Md(Z)p^{-1}Xp \subseteq M_{d}(\mathbb{Z}). Then X∗⊆pMd(Z)p−1X^{*} \subseteq pM_{d}(\mathbb{Z})p^{-1}. Hence X∗⊆q2Md(Z)X^{*} \subseteq q^{2}M_{d}(\mathbb{Z}) where q∈Z∖{0}q \in\mathbb{Z} \setminus\{0\} is chosen such that qpqp and qp−1qp^{-1} are integer matrices. This establishes (3).

Finally, we show that Item 3 implies Item 1. Let q∈Z∖{0}q \in\mathbb{Z} \setminus\{0\} be such that qX∗⊆Md(Z)qX^{*} \subseteq M_{d}(\mathbb{Z}). Then Zn⊆L⊆1qZn\mathbb{Z}^{n} \subseteq L \subseteq\frac{1}{q}\mathbb{Z}^{n}. Since LL is a submodule of 1qZn\frac{1}{q}\mathbb{Z}^{n}, which is free of rank nn, it follows that LL is free of rank at most nn. Furthermore, since LL contains Zn\mathbb{Z}^{n} it has rank exactly nn. ◀

The idea behind the algorithm for integrality is to determine whether a given number is a common denominator of X∗X^{*}, 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⊆Md(Q)X \subseteq M_{d}(\mathbb{Q}) and a number q∈Nq \in\mathbb{N} (in binary), decides whether qq is a common denominator of X∗X^{*}, and if so computes a conjugation matrix p∈GL⁡d(Q)p \in\operatorname{GL}_{d}(\mathbb{Q}) such that p−1Xp⊆Md(Z)p^{-1}Xp \subseteq M_{d}(\mathbb{Z}).

Proof. Let X⊆Md(Q)X \subseteq M_{d}(\mathbb{Q}), let m:=size⁡(X)m := \operatorname{size}(X) and let qq be a common denominator. Let L:=Span⁡Z(X∗⋅Zd)⊆QdL := \operatorname{Span}_{\mathbb{Z}}(X^{*} \cdot\mathbb{Z}^{d}) \subseteq\mathbb{Q}^{d} be the Z\mathbb{Z}-module generated by X∗⋅ZdX^{*} \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 pp are a basis of LL.

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

Observe that Lemma 19 does not yet imply Theorem 17; we require a bound on the common denominator qq 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⊆Md(Q)X \subseteq M_{d}(\mathbb{Q}) be a finite set of matrices in Wedderburn-Malcev normal form. Let q′q' be a common denominator for the set XX of generators. Let B⊆X∗B \subseteq X^{*} be a basis of the enveloping algebra Env⁡(X)\operatorname{Env}(X). Assume the monoid X∗X^{*} has some common denominator q∈Nq \in\mathbb{N}, then also q:=det⁡(TBlockDiag⁡(B))d⋅(q′)d−1q := \det(T_{\operatorname{BlockDiag}(B)})^{d} \cdot(q')^{d-1} is a common denominator for X∗X^{*}.

Proof of Proposition 20. Let X⊆Md(Q)X \subseteq M_{d}(\mathbb{Q}) be a finite set of matrices in Wedderburn-Malcev normal form such that X∗X^{*} has a common denominator. Just as in Proposition 12, write X={a1+c1,…,am+cm}⊆X∗X = \{a_{1} + c_{1}, \ldots, a_{m} + c_{m}\} \subseteq X^{*}, where each aia_{i} is block diagonal and each cic_{i} strictly upper block triangular. Write A:={a1,…,am}A := \{a_{1}, \ldots, a_{m}\}, C:={c1,…,cm}C := \{c_{1}, \ldots, c_{m}\} and D:={a1,…,am,c1,…,cm}D := \{a_{1}, \ldots, a_{m}, c_{1}, \ldots, c_{m}\}. We first claim that det⁡(TBlockDiag⁡(B))\det(T_{\operatorname{BlockDiag}(B)}) is a common denominator for A∗A^{*}.

Proof of claim: We first show that tr⁡(a)∈Z\operatorname{tr}(a) \in\mathbb{Z} for all a∈X∗a \in X^{*}. Since X∗X^{*} has a common denominator qq, there exists a conjugation matrix p∈GL⁡d(Q)p \in\operatorname{GL}_{d}(\mathbb{Q}) such that p−1X∗p⊆Md(Z)p^{-1}X^{*}p \subseteq M_{d}(\mathbb{Z}) by Proposition 18. In particular, p−1ap∈Md(Z)p^{-1}ap \in M_{d}(\mathbb{Z}). Therefore tr⁡(p−1ap)∈Z\operatorname{tr}(p^{-1}ap) \in\mathbb{Z}, and since the trace is invariant under a basis change, we obtain tr⁡(a)∈Z\operatorname{tr}(a) \in\mathbb{Z}. This in particular implies that Tr⁡B(a)∈Z∣B∣\operatorname{Tr}_{B}(a) \in\mathbb{Z}^{|B|} for all a∈X∗a \in X^{*}.

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

Since any matrix in (A∗C)d(A^{*}C)^d is zero, we obtain that q=(det⁡(TBlockDiag⁡(B)))d⋅(q′)d−1q=(\det(T_{\operatorname{BlockDiag}(B)}))^d\cdot(q')^{d-1} is a common denominator for D∗D^{*}. Since any matrix in X∗X^{*} is by the distributive law a sum of matrices in D∗D^{*}, we obtain that qq is also a common denominator for X∗X^{*}.

We can now prove Theorem 17.

Proof of Theorem 17. By Theorem 4 we can transform X∗X^{*} to Wedderburn-Malcev normal form with polynomial overhead. Henceforth assume that X∗X^{*} is in Wedderburn-Malcev normal form. Compute the number q=det⁡(TBlockDiag⁡(B))d⋅(q′)d−1q=\det(T_{\operatorname{BlockDiag}(B)})^d\cdot(q')^{d-1} of Proposition 20, and output the result of applying Lemma 19 with (X,q)(X,q) as input.

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. [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.arxiv.org/abs/2507.09373
  2. [2]László Babai, Robert Beals, and Daniel Rockmore. Deciding finiteness of matrix groups in deterministic polynomial time. In ISSAC’93, page 117–126. Association for Computing Machinery, 1993. doi:10.1145/164081.164104.DOI
  3. [3]Jean Berstel and Christophe Reutenauer. Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010.
  4. [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
  5. [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.
  6. [6]Leonard Eugene Dickson. Algebras and their Arithmetics. University of Chicago Press, 1924.
  7. [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.DOI
  8. [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.
  9. [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. arXiv:https://doi.org/10.1137/0208040, doi:10.1137/0208040.
  10. [10]Stefan Kiefer and Andrew Ryzhikov. The asymptotic size of finite irreducible semigroups of rational matrices, 2026. URL: https://arxiv.org/abs/2601.01236, arXiv:2601.01236.
  11. [11]Arnaldo Mandel and Imre Simon. On finite semigroups of matrices. Theoretical Computer Science, 5(2):101–111, 1977.DOI
  12. [12]Robert McNaughton and Yechzekel Zalcstein. The burnside problem for semigroups. Journal of Algebra, 34(2):292–299, 1975.DOI
  13. [13]Jean-Éric Pin. Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris, 7:73, 2010.
  14. [14]Lajos Rónyai. Algorithmic properties of maximal orders in simple algebras over q. Computational Complexity, 2(3):225–243, 1992.
  15. [15]Marcel-Paul Schützenberger. Finite counting automata. Information and control, 5:91–107, 1962.DOI
  16. [16]Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72(1):65–94, 1990. doi:10.1016/0304–3975(90)90047–L.DOI
  17. [17]Benjamin Steinberger. A short proof of a bound on the size of finite irreducible semigroups of rational matrices, 2026. URL: https://arxiv.org/abs/2601.03206, arXiv:2601.03206.
  18. [18]Andreas Weber and Helmut Seidl. On finitely generated monoids of matrices with entries in N. RAIRO Theor. Informatics Appl., 25:19–38, 1991. URL: https://doi.org/10.1051/ita/1991250100191, doi:10.1051/ITA/1991250100191.

Paper details

vlnc:W_vzhe3sfs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents