1 Introduction↩︎

Given a finite set \(\mathcal{A}\) of \(n \times n\) matrices, the semigroup generated by \(\mathcal{A}\) is the set of all products of matrices from \(\mathcal{A}\). Matrix semigroups appear naturally in many areas of computer science, such as automata theory, dynamical systems, program analysis and formal verification. Let us illustrate that with the following two examples.

Two examples.

Consider the linear loop in 1 (left), where the conditions for both exiting the loop and choosing one of the two conditional branches are abstracted out and denoted by \(*\). We assume that, in each iteration, one of the two linear operators is nondeterministically applied to the vector \(\big(\begin{smallmatrix} x \\ y \end{smallmatrix}\big)\) 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 \(\mathcal{A}_\ell\) in 1 (centre). This semigroup 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 (\(\mathcal{A}_r\) in the example in 1 (centre)) 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 extends the variety of applicable techniques [1].

General motivation.

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 [2]. For such problems, the known decidable special cases are usually obtained by restricting the dimension [3]–[5] or considering only matrices with nonnegative entries [6].

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 are precisely the transition semigroups of minimal weighted automata over \(\mathbb{Q}\) with a finite image set [7], a rich generalisation of unambiguous and deterministic NFAs. Finite matrix semigroups are also building blocks of noncommutative power series of polynomial growth [8]. We remark that both \(\mathcal{A}_\ell\) and \(\mathcal{A}_r\) from 1 generate finite semigroups.

The setting of the paper.

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 analysing 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 \(S_m \mathrel{\vcenter{:}}= \left\{ \big(\begin{smallmatrix} 0 & i \\ 0 & 0 \end{smallmatrix}\big) \mid 0 \le i < m \right\}\) 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 [9] and can be viewed as a generalisation of the concept of strongly connected finite automata to the case of weighted automata. Indeed, it is easy to see that a matrix semigroup is irreducible if and only if the weighted automaton corresponding to this matrix semigroup under every change of basis defined by a rational matrix is strongly connected. In some applications, such as matrix mortality, a matrix semigroup can be directly analysed by decomposing it into irreducible semigroups of smaller dimension, see e.g. [10] and the proof of 3 in the appendix.

2 Existing results and our contributions↩︎

As usual, we denote by \(\mathbb{N}\), \(\mathbb{Z}\) and \(\mathbb{Q}\) the sets of natural, integer and rational numbers, respectively. We write \(\mathrm{GL}_n(\mathbb{Q})\) and \(\mathrm{GL}_n(\mathbb{Z})\) for the multiplicative group of all invertible \(n \times n\) matrices over \(\mathbb{Q}\) and \(\mathbb{Z}\), respectively. We denote by \(\vec{v}\) a column vector of appropriate dimension, by \(\vec{0}\) a zero column vector, by \(A^\top\) the transpose of a matrix \(A\), and by \(O_n\) and \(I_n\) the \(n\times n\) zero and identity matrix, respectively. We assume that all vector spaces are over the field \(\mathbb{Q}\) and in particular that all matrices have rational entries, unless explicitly stated otherwise.

The maximal size of finite matrix groups.

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 size of rational finite matrix groups is well understood. By a folklore result (see, e.g., [11]), 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 size of any finite subgroup of \(\mathrm{GL}_n(\mathbb{Z})\) divides \((2 n)!\); see, e.g., [12]. Thus, denoting the size of the largest finite subgroup of \(\mathrm{GL}_n(\mathbb{Q})\) by \(g(n)\), we have \(g(n) \le (2 n)!\). It is shown in a paper by Friedland [13] 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 [14] which in turn is based on the classification of finite simple groups. Feit showed in an unpublished manuscript [15] 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 [16] for a list of the maximal-size 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 [17] (also based on the classification of finite simple groups), which Weisfeiler left behind before his tragic disappearance.

The maximal size of finite rational matrix semigroups.

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., [18], [19]) or an irreducibility assumption. A semigroup \(S \subseteq \mathbb{Q}^{n \times n}\) is called irreducible if the only vector spaces \(\mathcal{V}\subseteq \mathbb{Q}^n\) such that \(X \mathcal{V}\subseteq \mathcal{V}\) for all \(X \in S\) are \(\mathcal{V}= \mathbb{Q}^n\) and \(\mathcal{V}= \{\vec{0}\}\). The semigroup \(S_m\) from above is not irreducible because for the vector space \(\mathcal{V}= \{\big(\begin{smallmatrix} x \\ 0 \end{smallmatrix}\big) \mid x \in \mathbb{Q}\}\) we have \(X \mathcal{V}= \{\big(\begin{smallmatrix} 0 \\ 0 \end{smallmatrix}\big)\} \subseteq \mathcal{V}\) for all \(X \in S_m\).

Let us mention that the notion of irreducible matrices from nonnegative matrix theory, as in, e.g., [20], is weaker. Following [20], a square matrix with nonnegative entries is called irreducible if permuting its rows and columns cannot result in a matrix of the shape \(\big(\begin{smallmatrix}A & B \\ 0 & C\end{smallmatrix}\big)\), where \(A\) and \(C\) are square matrices. In terms of digraphs, 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 [20], but the converse is not always true.

In the book by Berstel and Reutenauer [8] it is shown that if a semigroup \(S \subseteq \mathbb{Q}^{n \times n}\) is finite and irreducible then \(|S| \le (2 n + 1)^{n^2} \in 2^{\mathcal{O}(n^2 \log n)}\). The technique, due to Schützenberger [21], 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 \(2 n + 1\) in the bound \((2 n + 1)^{n^2}\) corresponds to the possible traces in the set \(\{-n, -n+1, \ldots, n\}\).

The diameter and the mortality threshold.

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. [18], without assuming that \(S\) is irreducible, that the diameter of \(S\) with respect to any generating set is at most \(2^{n (2 n + 3)} g(n)^{n+1} \in 2^{\mathcal{O}(n^2 \log n)}\), where \(g\) is the above-mentioned group-bound function with \(g(n) \le (2 n)!\). The technique used in [18] is not based on traces but on exterior algebra. Nevertheless, their bound of \(2^{\mathcal{O}(n^2 \log n)}\) is strikingly similar to the aforementioned bound on semigroup cardinality. Panteleev [22] showed that for every \(n\) there exists a semigroup of diameter \(2^{n + \Theta(\sqrt{n \log n})}\) with respect to some generating set. This semigroup is actually constructed as the transition 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 [8], [21], Almeida and Steinberg [10] showed that the mortality threshold of any finite rational matrix semigroup containing the zero matrix is at most \((2 n - 1)^{n^2}\) for \(n \ge 2\). This bound is once again \(2^{\mathcal{O}(n^2 \log n)}\), as in [8], [18], [21]. The best known lower bound of \(\Omega(n^2)\) on the mortality threshold of finite semigroups of rational matrices is due to Rystsov [23]. He conjectured that \(\mathcal{O}(n^2)\) is also the upper bound [24], 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 contributions and organization of the paper.

Our main result, 2, is that any finite irreducible semigroup \(S \subseteq \mathbb{Q}^{n \times n}\) has at most \(3^{n^2}\) elements, thus “breaking” the \(2^{\mathcal{O}(n^2 \log n)}\) barrier in previous results about both the cardinality and the diameter [8], [10], [18], [21]. This is in a sense tight: as we show in 1, 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}\) (1). This result follows already from the proof of [10], which used a different technique. We also provide a lower bound of \(2^{\lfloor n^2/4 \rfloor}\) for the aperiodic case (1). There are also finite irreducible matrix semigroups (over \(\{-1,0,+1\}\)) that do not contain the zero matrix but still have \(2^{\Omega(n^2)}\) elements (1).¹ 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}\) (3). This improves the result by Almeida and Steinberg [10].

After the conference version [25] of this manuscript was accepted, Steinberg [26] provided a shorter proof of the upper bound \(3^{n^2}\), based on representation theory of finite semigroups. While his proof is more concise, we believe that our explicit linear-algebraic approach might have its own advantages. In particular, it might help with establishing stronger upper bounds on the values of the entries of matrices in irreducible finite semigroups, providing an improvement for the irreducible case of such a bound from [19].

The paper is structured as follows. In 3 we establish basic facts about finite irreducible matrix semigroups and their (0-)minimal ideals. In 4 we explain the construction of a group “at” (i.e., corresponding to) an idempotent from the (0-)minimal ideal. The results of [sec:irreducible,sub:G] are mostly known. [sec:upper-one,sec:upper-two] 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 in 7. In 8 we provide lower bounds. We conclude the paper by highlighting some open problems in 9. Some proofs have been moved to an appendix for better readability of the manuscript.

Technique.

In contrast to [10], [18], [21], 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 10 for the background we need) describes a finite subgroup \(G\) of \(\mathrm{GL}_r(\mathbb{Q})\) (often, e.g., in [27], called the maximal subgroup at \(E\)), which reflects the symmetries in \(T\) ([sec:irreducible,sub:G]). As discussed above, the asymptotic size of such matrix groups is well understood.

We then construct an injective map \(\Psi\) from \(S\) to tuples of elements of \(G \cup \{O_r\}\) (5.1). Thus, we have \(|S| = |\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^{\mathcal{O}(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 (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 ([sub:width] [sub:Hb] [sub:row-prefix]) 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 \(\Psi(X)\) within a two-dimensional grid (6.4).

3 Irreducible matrix semigroups↩︎

Let \(n \in \mathbb{N}\) and let \(S \subseteq \mathbb{Q}^{n \times n}\) be a semigroup. A vector space \(\mathcal{V}\subseteq \mathbb{Q}^n\) is called \(S\)-invariant if \(S \mathcal{V}\subseteq \mathcal{V}\), i.e., \(X \mathcal{V}\subseteq \mathcal{V}\) for all \(X \in S\). The semigroup \(S\) is called irreducible if the only \(S\)-invariant subspaces of \(\mathbb{Q}^n\) are \(\mathbb{Q}^n\) and \(\{\vec{0}\}\). The definition of irreducibility means that there are only trivial \(S\)-invariant “column” subspaces. But it implies that there are also only trivial \(S\)-invariant “row” subspaces:

In the following we assume that \(S\) is finite, irreducible and nonzero, i.e., \(S \ne \{O_n\}\). We write \(S^1 \mathrel{\vcenter{:}}= S \cup \{I_n\}\).

3.1 The (0-)minimal ideal↩︎

A minimal ideal of a semigroup is an ideal that is minimal within the set of all ideals. A 0-minimal ideal of a semigroup with zero is an ideal that is minimal within the set of all nonzero ideals. Every finite semigroup has a minimal ideal, and every non-trivial finite semigroup with zero also has a 0-minimal ideal. Hence, \(S\) has a (0-)minimal ideal, say \(T \ne \{O_n\}\). We show the following two lemmas.

For the remainder, let us write \(r\) for this common rank, i.e., \(\operatorname{rk}X = r\) for all \(X \in T \setminus \{O_n\}\).

4 The idempotent \(E\) and its group \(G\)↩︎

Using machinery from basic semigroup theory (see 10), one can obtain the following lemmas.

Fix the idempotent \(E \in T \setminus \{O_n\}\) from 3. The following lemma follows from the idempotence of \(E\).

The factorization \(E = D C\) from 5 allows us to put the group from 4 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 5, so that \(D C = E\) and \(C D = I_r\). Define \[G \;\mathrel{\vcenter{:}}= \;C S D \setminus \{O_r\} \;\subseteq \;\mathbb{Q}^{r \times r}\,.\] We have the following lemma.

5 Upper bound: setting the stage↩︎

5.1 The injective map \(\Psi\)↩︎

To explain our general approach, consider for the moment a map \(\mu: S \to G \cup \{O_r\}\) with \(\mu(X) = C X D\), a generalization of the map \(\phi\) from 6. We can use bounds on the group size mentioned in 2 to estimate \(|G|\). But since \(\mu\) is not in general injective, \(|\mu(S)|\) does not bound \(|S|\). Nevertheless, in the following we define a map \(\Psi\) with multiple components \(\psi_{i j}\), each of which is a variant of \(\mu\). More concretely, we have \(\psi_{i j}: S \to G \cup \{O_r\}\) with \(\psi_{i j}(X) = C U_i X V_j D\) for some matrices \(U_i, V_j \in S^{1}\). The matrices \(U_i, V_j\) are chosen so that \(\Psi : X \mapsto (\psi_{i j}(X))_{i j}\) is injective. Intuitively, the different \(\psi_{i j}\) exhibit different “group aspects” of a semigroup element \(X\). Since \(\Psi\) is injective, we have \(|S| = |\Psi(S)|\). The known group bounds then help to estimate \(|\Psi(S)|\). We provide further intuition of our approach at the end of this subsection. Since \(\sum_{X \in S^1} \mathop{\mathrm{im}}(X D)\) is \(S\)-invariant and nonzero (it contains \(\mathop{\mathrm{im}}D\)) and \(S\) is irreducible, we have \(\sum_{X \in S^1} \mathop{\mathrm{im}}(X D) = \mathbb{Q}^n\). Thus, there exist \(V_1, \ldots, V_v \in S^1\) (\(v \ge 1\)) such that \[\mathop{\mathrm{im}}(V_1 D) + \cdots + \mathop{\mathrm{im}}(V_v D) \;= \;\mathbb{Q}^n\,.\] As we will see later, this sum need not be direct.

Dually (cf.1), there exist \(U_1, \ldots, U_u \in S^1\) (\(u \ge 1\)) such that \[\mathop{\mathrm{row}}(C U_1) + \cdots + \mathop{\mathrm{row}}(C U_u) \;= \;\mathbb{Q}^{1 \times n}\,.\] For \(0 \le a \le u\) and \(0 \le b \le v\) define the vector spaces \[\begin{align} \mathcal{U}_{a} \;&\mathrel{\vcenter{:}}= \;\mathop{\mathrm{row}}(C U_1) + \cdots + \mathop{\mathrm{row}}(C U_{a}) \;\subseteq \;\mathbb{Q}^{1 \times n} \qquad \text{and} \\ \mathcal{V}_{b} \;&\mathrel{\vcenter{:}}= \;\mathop{\mathrm{im}}(V_1 D) + \cdots + \mathop{\mathrm{im}}(V_{b} D) \;\subseteq \;\mathbb{Q}^n\,. \end{align}\] By convention, \(\mathcal{U}_0 = \{\vec{0}^\top\}\) and \(\mathcal{V}_0 = \{\vec{0}\}\). Without loss of generality, we can assume for all \(1 \le a \le u\) that \(\mathop{\mathrm{row}}(C U_a) \not\subseteq \mathcal{U}_{a-1}\). Similarly, we also assume for all \(1 \le b \le v\) that \(\mathop{\mathrm{im}}(V_b D) \not\subseteq \mathcal{V}_{b-1}\). Thus, the vector space inclusions \(\{\vec{0}\} = \mathcal{U}_0 \subset \mathcal{U}_1 \subset \ldots \subset \mathcal{U}_u = \mathbb{Q}^{1 \times n}\) are strict, and similarly for the \(\mathcal{V}_j\). It follows that \(u, v \le n\). We note the following lemma.

For \(1 \le i \le u\) and \(1 \le j \le v\) and \(X \in S\) define \[\psi_{i j}(X) \;\mathrel{\vcenter{:}}= \;C U_i X V_j D \;\in \;G \cup \{O_r\}\,.\] Also define \[\Psi(X) \;\mathrel{\vcenter{:}}= \;\begin{pmatrix} \psi_{1 1}(X) & \cdots & \psi_{1 v}(X) \\ \vdots & \ddots & \vdots\\ \psi_{u 1}(X) & \cdots & \psi_{u v}(X) \end{pmatrix} \;= \; \begin{pmatrix} C U_1 X V_1 D & \cdots & C U_1 X V_v D \\ \vdots & \ddots & \vdots\\ C U_u X V_1 D & \cdots & C U_u X V_v D \end{pmatrix} \;\in \;\mathbb{Q}^{u r \times v r}\,.\] We will primarily view \(\Psi(X)\) not as a large matrix, but as a grid (or array) of smaller \(\mathbb{Q}^{r \times r}\) matrices.

In the following we will be interested in \(|S|\). By 8, we have \(|S| = |\Psi(S)|\); i.e., it suffices to estimate the number of different \(\Psi(X)\) for \(X \in S\). Taking this further, we have \[\begin{align} |S| \;&= \;|\Psi(S)| \;\le \;\prod_{i=1}^u \prod_{j=1}^v |\psi_{i j}(S)| \;= \;\prod_{i=1}^u \prod_{j=1}^v |C U_i S V_j D| \;\le \;\prod_{i=1}^u \prod_{j=1}^v (|G|+1) \;\\ &= \;(|G|+1)^{u v} \;\le \;3^{r^2 u v} \qquad \text{using \ref{lem:group-G} \ref{lem:bound-on-group-size}.} \end{align}\] Suppose for a moment that the vector spaces \((\mathop{\mathrm{row}}(C U_i))_i\) were independent and the vector spaces \((\mathop{\mathrm{im}}(V_j D))_j\) were independent, i.e., suppose that \(\bigoplus_{i=1}^u \mathop{\mathrm{row}}(C U_i) = \mathbb{Q}^{1 \times n}\) and \(\bigoplus_{j=1}^v \mathop{\mathrm{im}}(V_j D) = \mathbb{Q}^{n}\). Then \(u r = n\) and \(v r = n\) (in particular, \(r \mid n\) and \(u = v = n/r\)), and using the inequality above we would obtain \(|S| \le 3^{n^2}\). However, in general this independence does not hold and we have to estimate \(u,v \le n\), giving only a weaker bound \(|S| \le 3^{r^2 n^2}\). Therefore, we pursue a different avenue, based on the idea that if, say, \(\mathop{\mathrm{im}}(V_1 D)\) and \(\mathop{\mathrm{im}}(V_2 D)\) overlap nontrivially then \(\psi_{i 1}(X)\) and \(\psi_{i 2}(X)\) are “coupled” across \(X \in S\), i.e., \(\psi_{i 1}(X)\) and \(\psi_{i 2}(X)\) do not vary independently. Formalizing this idea and making it work is the key technical contribution of this paper. Before doing that, we treat a much easier case of aperiodic semigroups.

5.2 The aperiodic case↩︎

A semigroup is called aperiodic if every subsemigroup which is also a group is trivial, i.e., has only one element. In this subsection we analyze the size of \(S\), assuming it is aperiodic. Showcasing the use of our injective map \(\Psi\), 1 below recovers a result from [10].

Using the injective map \(\Psi\) we obtain the following result, which essentially follows from the proof of [10]. This is already a good illustration how our approach differs from the approach of [8], [10], [21]: instead of bounding the possible values that the traces of matrices in \(S\) can take, we consider a family \(\Psi\) of “linear” maps from \(S\) to the group \(G\).

6 Upper bound: doing the main work↩︎

6.1 The width \(w_b\) of a column↩︎

For this and the next two subsections, we fix an arbitrary column index \(b \in \{1, \ldots, v\}\). Define the width \(w_b\) of block column \(b\): \[w_b \;\mathrel{\vcenter{:}}= \;\dim \mathcal{V}_b - \dim \mathcal{V}_{b-1} \;= \;\dim(\mathcal{V}_{b-1} + \mathop{\mathrm{im}}(V_b D)) - \dim \mathcal{V}_{b-1}\,.\] Intuitively, \(\mathop{\mathrm{im}}(V_b D)\) adds \(w_b \le r\) independent dimensions to \(\mathcal{V}_{b-1}\). We note that \[\label{eq:wj} \begin{align} w_1 \;&= \;\dim \mathcal{V}_1 \;= \;\operatorname{rk}(V_1 D) \;= \;r && \text{by \ref{lem:rk-VjD}\quad and}\\ w_1 + \cdots + w_v \;&= \;\dim \mathcal{V}_v \;= \;n && \text{from the definition of the \mathcal{V}_j.} \end{align}\tag{1}\] The following picture illustrates these widths.

Also define \[\mathcal{L}_b \;\mathrel{\vcenter{:}}= \;\{\vec{y} \in \mathbb{Q}^r \mid V_b D \vec{y} \in \mathcal{V}_{b-1}\} \qquad \text{and} \qquad \ell_b \;\mathrel{\vcenter{:}}= \;\dim \mathcal{L}_b\,.\] In words, \(\mathcal{L}_b\) is the vector space consisting of the vectors \(\vec{y} \in \mathbb{Q}^{r}\) that the matrix \(V_b D\) maps into the intersection of \(\mathcal{V}_{b-1}\) and \(\mathop{\mathrm{im}}(V_b D)\); i.e., we have \(V_b D \mathcal{L}_b = \mathcal{V}_{b-1} \cap \mathop{\mathrm{im}}(V_b D)\). The following lemma connects \(w_b\) and \(\ell_b\).

6.2 The coupling group \(H_b\)↩︎

In this subsection we introduce \(H_b\), a subgroup of \(G\). Later we will see that this “coupling group” \(H_b\) restricts the possibilities for \(\psi_{a b}(X)\) (for some block row \(a\)) once the “prefix” \(\psi_{a 1}(X), \ldots, \psi_{a (b-1)}(X)\) has been fixed. The smaller the width \(w_b\), the smaller \(H_b\) becomes and the fewer possibilities are there for \(\psi_{a b}(X)\). Define \[H_b \;\mathrel{\vcenter{:}}= \;\{g \in G \mid g \vec{y} = \vec{y} \text{ for all } \vec{y} \in \mathcal{L}_b\}\,;\] i.e., \(H_b\) consists of those matrices \(g \in G\) that fix \(\mathcal{L}_b\).

Our analysis of the semigroup size is based on known bounds on the size of finite matrix groups. Concretely, we will use the following lemma. Its proof follows classical lines; see, e.g., [11]. For completeness, we provide a proof in the appendix.

6.3 A block row prefix↩︎

For this subsection, we fix an arbitrary block row index \(a \in \{1, \ldots, u\}\). We consider the (number of) possible first \(b\) blocks of the \(a\)th block row of \(\Psi(X)\) when \(X\) ranges over \(S\), i.e., the possible \[\begin{pmatrix} \psi_{a 1}(X) & \cdots & \psi_{a b}(X) \end{pmatrix} \qquad \text{where X \in S.}\] The following lemma states in particular that the action of \(\psi_{a b}(X)\) on \(\mathcal{L}_b\) is determined by the actions of \(\psi_{a 1}(X), \ldots, \psi_{a (b-1)}(X)\) on \(\mathcal{L}_b\).

The following lemma says that if two matrices \(\widehat{X}, X \in S\) have the same \(\Psi\)-values in the first \(b-1\) blocks of block row \(a\), then their \(\psi_{a b}\)-values are related by an element of the group \(H_b\). This lemma motivates our term “coupling group” for \(H_b\).

The following lemma bounds the number of different \(\psi_{a b}(X)\) when the \(\psi_{a j}(X)\) for \(j < b\) have been fixed.

Here is an illustration of the lemma.

The following proposition bounds the number of length-\(b\) prefixes of the \(a\)th block row of \(\Psi\). It will not be used later; it serves as “warm-up” for the “2-dimensional” 18 in 6.4 below.

Using 1, we can improve the bound \(|S| \le 3^{r^2 n^2}\) obtained at the end of 5.1. Let us write \(Y_{a b} \mathrel{\vcenter{:}}= Y_b\) for the set \(Y_b\) from 1, to make its implicit dependence on \(a \in \{1, \ldots, u\}\) (fixed at the beginning of the subsection) explicit. Since \(w_j \le r\) and \(w_1 + \cdots + w_v = n\) by 1 , we have \(w_1^2 + \cdots + w_v^2 \le r n\). Then 1 gives \(|Y_{a v}| \le 3^{r n}\), and we obtain, using \(u \le n\), \[|S| \;= \;|\Psi(S)| \;\le \;\prod_{a=1}^{u} |Y_{a v}| \;\le \;\prod_{a=1}^{u} 3^{r n} \;= \;3^{r n u} \;\le \;3^{r n^2}\,,\] improving on the earlier bound by a factor of \(r\) in the exponent.

In order to improve this bound down to \(|S| \le 3^{n^2}\), we need to exploit dependencies between the block rows, in addition to the dependencies within block row \(a\) explored thus far. Column dependencies are, of course, completely analogous to row dependencies; the remaining challenge is to find a way to couple each block \((a,b)\) both within its row and its column.

6.4 The overall count↩︎

In the previous subsection we considered the length-\(b\) prefix of the \(a\)th block row of \(\Psi\) \[\begin{pmatrix} \psi_{a 1}(X) & \cdots & \psi_{a b}(X) \end{pmatrix} \qquad \text{where X \in S.}\] Next we wish to formulate the column analogue of 15. Analogously to the width \(w_b\) of block column \(b\), we define the height, \(h_a\), of block row \(a\), i.e., \[h_a \;\mathrel{\vcenter{:}}= \;\dim \mathcal{U}_a - \dim \mathcal{U}_{a-1} \qquad \text{where 1 \le a \le u.}\] We have \(h_a > 0\), analogously to \(w_b > 0\) from 10. The following equalities are exactly analogous to 1 for \(w_b\) in 6.1: \[\label{eq:hi} \begin{align} h_1 \;&= \;\dim \mathcal{U}_1 \;= \;\operatorname{rk}(C U_1) \;= \;r \\ h_1 + \cdots + h_u \;&= \;\dim \mathcal{U}_u \;= \;n \,. \end{align}\tag{2}\] In particular, \(h_1 = \operatorname{rk}(C U_1) = r\) follows from the analogue of 7. The following lemma considers a length-\(a\) prefix of the \(b\)th block column of \(\Psi\).

The proof follows from transposing the row argument from the last two subsections; we omit the proof, as it is fully analogous to the proof of 15.

Towards the overall count, define the grid \[\Gamma \;\mathrel{\vcenter{:}}= \;\{1, \ldots, u\} \times \{1, \ldots, v\}\,.\] Let \(\mathord{\prec}\) be the row-major order on \(\Gamma\), i.e., \[(i,j) \prec (i',j') \quad \Longleftrightarrow \quad i < i'\quad\text{or}\quad (i = i' \text{ and } j < j').\]

2 (a) visualizes the order \(\mathord{\prec}\).

The following lemma is a grid analogue to 15 16; in fact, the proof is based on these lemmas.

The following lemma is the grid analogue to 1.

Now the main theorem follows.

7 Mortality threshold and minimum-rank diameter↩︎

In this section we prove the following theorem.

Roughly speaking, 3 is proved by decomposing \(S\) into irreducible “parts” and using 2.

Below we prove a result that is slightly stronger than 3. To state it, we define the minimum-rank diameter of \(S\) as the minimum depth among the minimum-rank (possibly zero) matrices \(X \in S\). First we note the following simple fact.

If the zero matrix is in the semigroup, then the zero matrix is the unique minimum-rank matrix and, thus, the mortality threshold equals the minimum-rank diameter. Therefore, the following proposition implies 3.

8 Lower bound↩︎

Fix \(n \ge 2\) and write \(n = p+q\) with \[p \;\mathrel{\vcenter{:}}= \;\left\lfloor \tfrac{n}{2} \right\rfloor, \qquad q \;\mathrel{\vcenter{:}}= \;\big\lceil \tfrac{n}{2} \big\rceil, \qquad P \;\mathrel{\vcenter{:}}= \;\{1,\ldots,p\}, \qquad Q \;\mathrel{\vcenter{:}}= \;\{p+1,\ldots,n\}\,.\] We view \(P\) as the “north-west” index set and \(Q\) as the “south-east” one; note \(P \cap Q = \emptyset\). For \(X \in \mathbb{Z}^{n\times n}\) we write \[\mathop{\mathrm{supp}}X \;\mathrel{\vcenter{:}}= \;\{(i,j)\in\{1,\dots,n\}^2 \mid X_{ij}\neq 0\}\] for the support of \(X\). We define four families of matrices with entries in \(\{-1, 0, 1\}\): \[\begin{align} \mathsf{NE}\;&\mathrel{\vcenter{:}}=\;\{X \in \{-1,0,1\}^{n\times n} \mid \mathop{\mathrm{supp}}X \subseteq P\times Q\}\,,\\ \mathsf{COL}\;&\mathrel{\vcenter{:}}=\;\{X \in \{-1,0,1\}^{n\times n} \mid \exists\, b \in P:\;\mathop{\mathrm{supp}}X \subseteq P \times \{b\}\}\,,\\ \mathsf{ROW}\;&\mathrel{\vcenter{:}}=\;\{X \in \{-1,0,1\}^{n\times n} \mid \exists\, a \in Q:\;\mathop{\mathrm{supp}}X \subseteq \{a\} \times Q\}\,,\\ \mathsf{UNIT}\;&\mathrel{\vcenter{:}}=\;\{X \in \{-1,0,1\}^{n\times n} \mid |\mathop{\mathrm{supp}}X| \le 1\}\,. \end{align}\] In words, \(\mathsf{NE}\) consists of the north-east-supported matrices; \(\mathsf{COL}\) consists of the north-west-supported matrices with at most one nonzero column; \(\mathsf{ROW}\) consists of the south-east-supported matrices with at most one nonzero row; and \(\mathsf{UNIT}\) consists of the signed matrix units and \(0\). Each family includes the zero matrix. Define \(S\;\mathrel{\vcenter{:}}= \;\mathsf{NE}\;\cup\; \mathsf{COL}\;\cup\; \mathsf{ROW}\;\cup\; \mathsf{UNIT}\,.\) The following proposition complements 2.

The following proposition complements 1.

8.1 Zero-free irreducible semigroups↩︎

The examples from the previous lower-bound constructions all contain the zero matrix. In fact, most matrices in these semigroups are nilpotent, so the presence of the zero matrix might seem essential. We now show that one can still obtain zero-free irreducible semigroups of size \(2^{\Omega(n^2)}\).

The argument has two ingredients. We first construct a large zero-free strongly connected semigroup of \(0\)-\(1\) matrices by a block-based construction. We then pass to signed matrices and use strong connectivity to obtain irreducibility.

For a semigroup \(S \subseteq \{0,1\}^{n \times n}\), let us write \(\Gamma(S)\) for the directed graph on \(\{1,\ldots,n\}\) with an edge \(p \to q\) if there exists \(X \in S\) with \(X_{q p} = 1\). We call \(S\) strongly connected if \(\Gamma(S)\) is strongly connected. Since \(S\) is a semigroup of \(0\)-\(1\) matrices, this is equivalent to requiring that for every \(p,q \in \{1,\ldots,n\}\) there exists \(X \in S\) with \(X_{q p} = 1\).

We now describe the block construction informally. Fix a partition of \(\{1,\ldots,n\}\) into blocks \(B_1,\ldots,B_m\). A matrix in our family is obtained by considering each row block \(B_i\) separately and choosing a single column block \(B_{\sigma(i)}\) from which this row block receives its nonzero entries. Once \(B_{\sigma(i)}\) has been chosen, every column in \(B_{\sigma(i)}\) carries exactly one nonzero entry inside the rows indexed by \(B_i\), whereas columns outside \(B_{\sigma(i)}\) contribute nothing to that row block. The row inside \(B_i\) where this nonzero entry is placed may depend on the column, so each row block is controlled by a function from its chosen column block into \(B_i\). Under multiplication, the active column block for \(B_i\) in the left factor is followed through the right factor, and the corresponding functions compose. This keeps the family closed under multiplication, while the freedom in choosing the blockwise maps yields exponentially many matrices and still allows one to connect any position to any other.

The next proposition shows that the same block construction remains closed after one freely chooses signs on all nonzero entries.

For \(X \in \{0,1\}^{n \times n}\), let \[\Sigma(X) \;\mathrel{\vcenter{:}}= \; \{Y \in \{-1,0,1\}^{n \times n} \mid \mathop{\mathrm{supp}}Y = \mathop{\mathrm{supp}}X\}\] denote the set of all signings of \(X\). For a semigroup \(S \subseteq \{0,1\}^{n \times n}\), we call the semigroup generated by \(\bigcup_{X \in S} \Sigma(X)\) the signed version of \(S\).

The relevance of signed versions is that strong connectivity forces irreducibility.

We can now combine the previous propositions.

9 Conclusions and open problems↩︎

Our \(3^{n^2}\) bound on the cardinality of finite irreducible rational matrix semigroups (2) breaks the barrier of \(2^{\mathcal{O}(n^2 \log n)}\) suggested in previous works [8], [10], [18], [21]. Up to a constant in the exponent our bound is tight (1). As discussed in the introduction, the largest finite rational \(n \times n\) matrix groups are known explicitly, using the classification of finite simple groups. It would be similarly intriguing to identify the largest finite irreducible rational \(n \times n\) matrix semigroups. By our results, they have \(2^{\Theta(n^2)}\) elements.

While we now have a good understanding of the maximal cardinality of finite irreducible matrix semigroups, for their diameter there is still a gap between the best known lower bound of \(2^{n + \Theta(\sqrt{n \log n})}\)  [22] and the upper bound of \(2^{\Theta(n^2)}\) implied by our work. As mentioned in the introduction, the gap for the mortality threshold is even bigger, since only polynomial lower bounds are known.

It would be also interesting to understand if the upper bound from 2 can be made more precise if it is also allowed to depend on the number of generators. The examples from our lower bounds have exponentially many generators. For transformation semigroups (equivalently, semigroups of matrices with entries in \(\{0, 1\}\) with exactly one nonzero entry in every row) this question was studied in [28]. The diameter of transformation semigroups with a bounded number of generators was studied in [29]. The cardinality of aperiodic transformation semigroups was studied in [30].

10 Semigroup Theory↩︎

We draw on some background from semigroup theory, and follow [31]. We denote the zero of a semigroup by \(0\). A semigroup without zero is called simple if it has no proper ideals. A semigroup \(S\) with zero is called 0-simple if

1. its only ideals are the zero ideal \(\{0\}\) and \(S\);

2. \(S^2 \ne \{0\}\).

A minimal ideal of a semigroup is an ideal that is minimal within the set of all ideals. A 0-minimal ideal of a semigroup with zero is an ideal that is minimal within the set of all nonzero ideals. Every finite semigroup has a minimal ideal. Every finite semigroup with zero \(S \ne \{0\}\) also has a 0-minimal ideal. We have the following proposition.

An idempotent \(e \ne 0\) is called primitive if for every idempotent \(f\) \[e f = f e = f \ne 0 \quad \text{implies} \quad e = f\,.\] A semigroup is called completely (0-)simple if it is (0-)simple and has a primitive idempotent. We have the following proposition.

In particular, every finite (0-)simple semigroup has a primitive nonzero idempotent.

A Rees 0-matrix semigroup \(M^0[G; I, \Lambda; P]\) is a semigroup with zero \((I \times G \times \Lambda) \cup \{0\}\), where \(G\) is a group, \(I, \Lambda\) are nonempty index sets, and the “sandwich” matrix \(P = (p_{\lambda i})\) is a \(\Lambda \times I\) matrix with entries in the 0-group \(G^0 (= G \cup \{0\})\) such that no row or column of \(P\) consists entirely of zeros. Multiplication is defined by \[\begin{align} (i, a, \lambda) (j, b, \mu) \;&= \;\begin{cases} (i,a p_{\lambda j} b, \mu) & \text{ if } p_{\lambda j} \ne 0, \\ 0 & \text{ if } p_{\lambda j} = 0, \end{cases} \\ (i,a,\lambda) 0 \;&= \;0 (i,a,\lambda) \;= \;0 0 \;= \;0\,. \end{align}\] A Rees matrix semigroup \(M[G; I, \Lambda; P]\) is analogously defined without zero. The following theorem is an important result of semigroup theory: one can represent completely (0-)simple semigroups as Rees (0-)matrix semigroups.

We use the Rees-Suschkewitsch theorem to derive the following lemma.

11 Proofs from 6↩︎

The following lemma, which is basic group theory, will be used twice.

References↩︎

---

1. This result was not contained in the conference version [25] of this manuscript.↩︎