The Asymptotic Size of Finite Irreducible Semigroups of Rational Matrices

Consider the linear loop in Figure 1 (left), where the conditions for both exiting the loop and choosing one of the two conditional branches are abstracted out and denoted by $\ast$. We assume that, in each iteration, one of the two linear operators is nondeterministically applied to the vector $\left(\begin{array}{c}x\\ y\end{array}\right)$ of variables. The overall set of linear operators that can be applied to this vector during the execution of the loop is thus the matrix semigroup generated by ${𝒜}_{\mathrm{\ell }}$. This can be seen as the set of all behaviours of the loop.

Similarly, the set of all possible behaviours of a nondeterministic finite automaton (NFA) is represented by its transition monoid. Note that the transition monoid does not depend on initial and final states. In this context, an NFA is called unambiguous if for every pair $p,q$ of states, each word labels at most one path from $p$ to $q$ in it. Clearly, every deterministic NFA is unambiguous. The transition monoid of an unambiguous NFA can be seen as the monoid generated by the set of transition matrices of the letters (${𝒜}_r$ in the example in Figure 1 (right)) with the usual addition and multiplication of the integers. This fact allows us to consider unambiguous NFAs as automata with multiplicities (or, more generally, weighted automata), which significantly extend the variety of applicable techniques [13].

In algorithmic applications, there is always a trade-off between the expressiveness of a model and the tractability of deciding its properties. This is especially important for matrix semigroups: for example, the question whether the semigroup generated by a given set of matrices contains the zero matrix is undecidable already for $3\times 3$ integer matrices [20]. For such problems, the known decidable special cases are usually obtained by restricting the dimension [8, 3, 9] or considering only matrices with nonnegative entries [22].

In this paper, we consider a different restriction: finiteness of the generated semigroup. It constitutes a “middle ground” between the two applications above. From the loop analysis point of view, it describes loops that have a finite set of behaviours regardless of the initial values of the variables. On the other hand, finite rational matrix semigroups closely correspond to weighted automata over $\mathbb{Q}$ that have a finite image set (see, e.g., [7, Section 4.1]), a rich generalization of unambiguous and deterministic NFAs. Finite matrix semigroups are also building blocks of noncommutative power series of polynomial growth [5, Section 9.2]. We remark that both ${𝒜}_{\mathrm{\ell }}$ and ${𝒜}_r$ from Figure 1 generate finite semigroups.

The general motivation behind the paper is to shed light on the structure of finite semigroups of $n\times n$ rational matrices and to develop new tools for analyzing them. The concrete question we pursue here is about the maximum size of such semigroups in terms of $n$. In general, there is no upper bound because for each $m\in \mathbb{N}$ the set forms a semigroup of size $m$. However, intuitively, this example is in a sense degenerate, since only the same one-dimensional subspace is affected by the corresponding linear operators. Matrix semigroups where such degenerate behaviour does not occur are called irreducible (see the next section for the formal definition). They are actively studied in representation theory of finite monoids [25, Chapter 5] and can be viewed as a generalization of the concept of strongly connected finite automata to the case of weighted automata, as argued in [16].

In some applications, such as matrix mortality, a matrix semigroup can be directly analyzed by decomposing it into irreducible semigroups of smaller dimension, see e.g. [2, Section 5] and the proof of Theorem 29 in the appendix of [14]. More generally, it is announced in [16] that every rational matrix semigroup can be decomposed into irreducible parts, resembling a simultaneous Jordan normal form (which does not always exist for multiple matrices), and that irreducibility can be decided in polynomial time. We note that the results announced in [16] do not improve the old bound of Schützenberger [24, 5] on the size of irreducible finite matrix semigroups, and thus do not overlap with the present paper.

Let us first highlight the importance of rational entries in our setting. Indeed, every cyclic group is isomorphic to a group generated by a $2\times 2$ real rotation matrix, so there is no hope of bounding the size of finite matrix groups with real entries. The case of rational entries is however very different, and the maximal order of rational finite matrix groups is well understood. By a folklore result (see, e.g., [15, Theorem 1.6]), any finite subgroup of ${\mathrm{GL}}_n(\mathbb{Q})$ is conjugate to a finite subgroup of ${\mathrm{GL}}_n(\mathbb{Z})$. An elementary proof shows that the order of any finite subgroup of ${\mathrm{GL}}_n(\mathbb{Z})$ divides $(2n)!$; see, e.g., [18, Chapter IX]. Thus, denoting the order of the largest finite subgroup of ${\mathrm{GL}}_n(\mathbb{Q})$ by $g(n)$, we have $g(n)\le (2n)!$. It is shown in a paper by Friedland [11] that $g(n)=2^{n}n!$ holds for all sufficiently large $n$. This bound is attained by the group of signed permutation matrices (that is, matrices with entries in $\{-1,0,1\}$ with exactly one nonzero entry in each row and each column). Friedland’s proof rests on an article by Weisfeiler [27] which in turn is based on the classification of finite simple groups. Feit showed in an unpublished manuscript [10] that $g(n)=2^{n}n!$ holds if and only if $n\in \mathbb{N}\setminus \{2,4,6,7,8,9,10\}$; see also [4, Table 1] for a list of the maximal-order finite subgroups of ${\mathrm{GL}}_n(\mathbb{Q})$ for $n\in \{2,4,6,7,8,9,10\}$. Feit’s proof relies on an unpublished manuscript [26] (also based on the classification of finite simple groups), which Weisfeiler left behind before his tragic disappearance.

In view of the set $S_m$ from the previous section, bounds on the size of finite rational matrix semigroups either need to involve the number of generators (see, e.g., [7] and the references therein, as well as its announced improvement in [16]) or an irreducibility assumption. A semigroup $S\subseteq {\mathbb{Q}}^{n\times n}$ is called irreducible if the only vector spaces $𝒱\subseteq {\mathbb{Q}}^n$ such that $X𝒱\subseteq 𝒱$ for all $X\in S$ are $𝒱={\mathbb{Q}}^n$ and $𝒱=\{\overrightarrow{0}\}$. The semigroup $S_m$ from above is not irreducible because for the vector space $𝒱=\{\left(\begin{array}{c}x\\ 0\end{array}\right)\mid x\in \mathbb{Q}\}$ we have $X𝒱=\{\left(\begin{array}{c}0\\ 0\end{array}\right)\}\subseteq 𝒱$ for all $X\in S_m$.

Let us mention that the notion of irreducible matrices from nonnegative matrix theory, as in, e.g., [17], is weaker. Following [17], a square matrix with nonnegative entries is called irreducible if permuting its rows and columns cannot result in a matrix of the shape , where $A$ and $C$ are square matrices. A digraph is strongly connected if and only if its adjacency matrix is irreducible in this sense. Clearly, a matrix generating an irreducible semigroup in our sense must be irreducible in the sense of [17], but the converse is not always true.

In the book by Berstel and Reutenauer [5, Lemma IX.1.2] it is shown that if a semigroup $S\subseteq {\mathbb{Q}}^{n\times n}$ is finite and irreducible then $|S|\le {(2n+1)}^{n^2}\in 2^{𝒪(n^2\log n)}$. The technique, due to Schützenberger [24], is based on the analysis of the coefficients of characteristic polynomials of the matrices in $S$, and in particular of their traces. In fact, the quantity $2n+1$ in the bound ${(2n+1)}^{n^2}$ corresponds to the possible traces in the set $\{-n,-n+1,\mathrm{\dots },n\}$.

Let $S\subseteq {\mathbb{Q}}^{n\times n}$ be a finite semigroup generated by a subset $S_0\subseteq S$. The length of a shortest product of elements from $S_0$ resulting in $X\in S$ is called the depth of $X$. The diameter of $S$ is the maximum depth among all $X\in S$. Both the depth and the diameter are implicitly defined with respect to the set $S_0$ of generators. Intuitively, the diameter indicates how fast one can reach any matrix. It is easy to see that the diameter of a finite semigroup cannot exceed its size.

In 2020 it was shown by Bumpus et al. [7], without assuming that $S$ is irreducible, that the diameter of $S$ with respect to any generating set is at most $2^{n(2n+3)}g{(n)}^{n+1}\in 2^{𝒪(n^2\log n)}$, where $g$ is the above-mentioned group-bound function with $g(n)\le (2n)!$. The technique used in [7] is not based on traces but on exterior algebra. Nevertheless, their bound of $2^{𝒪(n^2\log n)}$ is strikingly similar to the aforementioned bound on semigroup cardinality. Panteleev [19] showed that for every $n$ there exists a semigroup of diameter $2^{n+\mathrm{\Theta }(\sqrt{n\log n})}$ with respect to some generating set. This semigroup is actually constructed as the transformation monoid of a deterministic finite automaton, and thus consists of matrices with entries in $\{0,1\}$ and exactly one nonzero entry in every row. As far as the authors know, no better lower bound is known for the maximum diameter of finite rational matrix semigroups.

The depth of the zero matrix (again, with respect to a set $S_0$ of generators) is called the mortality threshold of $S$. Intuitively, it indicates how fast one can reach the zero matrix. Using a variation of the aforementioned technique due to Schützenberger [24, 5], Almeida and Steinberg [2] showed that the mortality threshold of any finite rational matrix semigroup containing the zero matrix is at most ${(2n-1)}^{n^2}$ for $n\ge 2$. This bound is once again $2^{𝒪(n^2\log n)}$, as in [24, 5, 7]. The best known lower bound of $\mathrm{\Theta }(n^2)$ on the mortality threshold of finite semigroups of rational matrices is due to Rystsov [21]. He conjectured that $𝒪(n^2)$ is also the upper bound, which to the best of our knowledge has not been disproved. It is noteworthy that the lower bound again comes from the transition monoid of a DFA.

Our main result, Theorem 28, is that any finite irreducible semigroup $S\subseteq {\mathbb{Q}}^{n\times n}$ has at most $3^{n^2}$ elements, thus “breaking” the $2^{𝒪(n^2\log n)}$ barrier in previous results about both the cardinality and the diameter [24, 5, 2, 7]. This is in a sense tight: as we show in Proposition 30, any such bound needs to be at least $3^{\lfloor n^2/4\rfloor }$. Recall that $|S|$ cannot be bounded purely in $n$ without assuming irreducibility. To showcase our technique, early on we give a relatively direct proof of the fact that if $S$ is also aperiodic (i.e., every subgroup of $S$ has only one element), then $|S|\le 2^{n^2}$ (Theorem 13). This result follows already from the proof of [2, Theorem 5.8], which used a different technique. We also provide a lower bound of $2^{\lfloor n^2/4\rfloor }$ for the aperiodic case (Proposition 31). Finally, as an application we show that if a finite, not necessarily irreducible, matrix semigroup contains the zero matrix, then its mortality threshold is at most $3^{n^2}$ (Theorem 29). This improves the result by Almeida and Steinberg [2].

The paper is structured as follows. In Section 3 we establish basic facts about finite irreducible matrix semigroups and their (0-)minimal ideals. In Section 4 we explain the construction of a group “at” (i.e., corresponding to) an idempotent from the (0-)minimal ideal. The results of Sections 3 and 4 are mostly known. Sections 5 and 6 are dedicated to the proof of our main result (which we outline in the next paragraph below). Its application to matrix mortality can be found at the end of Section 6. In Section 7 we provide lower bounds. We conclude the paper by highlighting some open problems in Section 8. Missing proofs can be found in the appendix of [14].

In contrast to [24, 2, 7], our technique is based neither on traces nor on exterior algebra. In fact, although the overall proof is non-trivial, it does not use anything outside of basic (semi)group theory and linear algebra. We outline our approach in the following.

Let $S$ be a finite rational $n\times n$ matrix semigroup, and let $T$ be a (0-)minimal ideal of $S$. One can show that all matrices in $T\setminus \{O_n\}$ have the same rank, say $r$, which is the minimum nonzero rank in $S$. Given an idempotent $E\in T\setminus \{O_n\}$, fundamental semigroup theory (see [14, Appendix A] for the background we need) describes a finite subgroup $G$ of ${\mathrm{GL}}_r(\mathbb{Q})$ (often, e.g., in [1], called the maximal subgroup at $E$), which reflects the symmetries in $T$ (Sections 3 and 4). As discussed above, the asymptotic size of such matrix groups is well understood.

We then construct an injective map $\mathrm{\Psi }$ from $S$ to tuples of elements of $G\cup \{O_r\}$ (Section 5.1). Thus, we have $|S|=|\mathrm{\Psi }(S)|$ and so it suffices to bound the number of distinct tuples over $G\cup \{O_r\}$. This immediately leads to $|S|\le 3^{r^2{n}^2}$, a bound that does not improve on $2^{𝒪(n^2\log n)}$ unless the minimum rank $r$ is constant. However, in this way we already obtain a near-optimal bound on the cardinality of aperiodic semigroups (Section 5.2).

To strengthen the bound in the general case, we then show that the tuple elements are in a sense “coupled” via small matrix groups. This part (Sections 6.1, 6.2, and 6.3) is the technical core of the paper and the most delicate aspect of the proof, even though it uses only elementary linear algebra. Finally, the overall bound of $3^{n^2}$ is obtained by carefully counting the coupled tuples $\mathrm{\Psi }(X)$ within a two-dimensional grid (Section 6.4).

Suppose that $𝒰\ne {\mathbb{Q}}^{1\times n}$, i.e., $𝒰$ is a proper subspace. Define ${𝒰}^{\circ }≔\{\overrightarrow{v}\in {\mathbb{Q}}^n\mid 𝒰\overrightarrow{v}=\{\overrightarrow{0}\}\}$. Then $dim𝒰+dim{𝒰}^{\circ }=n$. Since , we have $dim{𝒰}^{\circ }>0$, i.e., ${𝒰}^{\circ }\ne \{\overrightarrow{0}\}$. Let $X\in S$ and let $\overrightarrow{v}\in {𝒰}^{\circ }$. Since $𝒰X\subseteq 𝒰$, we have $𝒰X\overrightarrow{v}\subseteq 𝒰\overrightarrow{v}=\{\overrightarrow{0}\}$, as $\overrightarrow{v}\in {𝒰}^{\circ }$. Thus, $X\overrightarrow{v}\in {𝒰}^{\circ }$. Since $\overrightarrow{v}\in {𝒰}^{\circ }$ was arbitrary, it follows that $X{𝒰}^{\circ }\subseteq {𝒰}^{\circ }$. Since $X\in S$ was arbitrary, ${𝒰}^{\circ }$ is $S$-invariant. Since ${𝒰}^{\circ }\ne \{\overrightarrow{0}\}$ and $S$ is irreducible, we have ${𝒰}^{\circ }={\mathbb{Q}}^n$. Since $dim𝒰+dim{𝒰}^{\circ }=n$, it follows that $𝒰=\{{\overrightarrow{0}}^{\top }\}$. $◀$

In the following we assume that $S$ is finite, irreducible and nonzero, i.e., $S\ne \{O_n\}$. We write $S^1≔S\cup \{I_n\}$.

Since $E\in T$ and $T$ is an ideal, for all $X\in S$ we have $EX\in T$ and, hence, $EXE=EEXE\in ETE$. Thus, $ESE\subseteq ETE$. The converse inclusion is immediate from $T\subseteq S$. $◀$

Fix the idempotent $E\in T\setminus \{O_n\}$ from Lemma 4. The following lemma follows from the idempotence of $E$.

Let $D\in {\mathbb{Q}}^{n\times r}$ be a matrix consisting of columns of $E$ that form a basis of $\mathrm{im}E$. Since $EE=E$ and the columns of $D$ are columns of $E$, we have $ED=D$. By the rank-nullity theorem, we have $dim(\ker E)=n-r$. Let $W\in {\mathbb{Q}}^{n\times (n-r)}$ be a matrix whose columns form a basis of $\ker E$. Thus, $EW=0$. Since $EE=E$, we have $\mathrm{im}E\cap \ker E=\{\overrightarrow{0}\}$, so the columns of the matrix $Q\in {\mathbb{Q}}^{n\times n}$ with are linearly independent. Thus, $Q$ is invertible. We have

Hence,

Define and recall that $D=Q\left(\begin{array}{c}{I}_r\\ 0\end{array}\right)$. Then, as required, we have

$◀$

The factorization $E=DC$ from Lemma 6 allows us to put the group from Lemma 5 in a more succinct form, which will be useful when invoking bounds on the size of matrix groups. To this end, fix $D\in {\mathbb{Q}}^{n\times r}$ and $C\in {\mathbb{Q}}^{r\times n}$ from Lemma 6, so that $DC=E$ and $CD=I_r$. Define

We have the following lemma.

Let us first consider a generalization of $\varphi$, namely the map $\mathrm{\Phi }:E{\mathbb{Q}}^{n\times n}E\to {\mathbb{Q}}^{r\times r}$ with $\mathrm{\Phi }(X)≔CXD$. Note that $\mathrm{\Phi }$ is a linear map and that

The map $\mathrm{\Phi }$ has a trivial kernel, since if $CXD=\mathrm{\Phi }(EXE)=O_r$ then $EXE=DCXDC=O_n$. Thus, $\mathrm{\Phi }$ and hence $\varphi$ are injective. It also follows that $\varphi (ESE\setminus \{O_n\})\subseteq G$.

Towards surjectivity of $\varphi$, let $X\in S$ with $CXD\ne 0$. Then $\mathrm{\Phi }(EXE)=CXD$. If $EXE=O_n$ then $\mathrm{\Phi }(EXE)=\mathrm{\Phi }(O_n)=O_r\ne CXD$, a contradiction; hence $EXE\ne O_n$. Thus, we also have $\varphi (EXE)=\mathrm{\Phi }(EXE)=CXD$. It follows that $\varphi (ESE\setminus \{O_n\})=G$; i.e., $\varphi$ is surjective.

It remains to show that $\varphi$ is a homomorphism. Using $CE=CDC=C$ and $ED=DCD=D$, we obtain $\varphi (E)=CED=CDCD=I_r$ and

$◀$