The asymptotic size of finite irreducible semigroups of rational matrices

preprint2026arXivOpen access

Abstract

We study finite semigroups of n×nn \times n matrices with rational entries. Such semigroups provide a rich generalization of transition monoids of unambiguous (and, in particular, deterministic) finite automata. In this paper we determine the maximum size of finite semigroups of rational n×nn \times n matrices, with the goal of shedding more light on the structure of such matrix semigroups. While in general such semigroups can be arbitrarily large in terms of nn, a classical result of Schützenberger from 1962 implies an upper bound of 2O(n2log⁡n)2^{O(n^2 \log n)} for irreducible semigroups, i.e., the only subspaces of QnQ^n that are invariant for all matrices in the semigroup are QnQ^n and the subspace consisting only of the zero vector. Irreducible matrix semigroups can be viewed as the building blocks of general matrix semigroups, and as such play an important role in mathematics and computer science. From the point of view of automata theory, they generalize strongly connected automata. Using a very different technique from that of Schützenberger, we improve the upper bound on the cardinality to 3n23^{n^2}. This is the main result of the paper. The bound is in some sense tight, as we show that there exists, for every nn, a finite irreducible semigroup with 3⌊n2/4⌋3^{\lfloor n^2/4 \rfloor} rational matrices. Our main result also leads to an improvement of a bound, due to Almeida and Steinberg, on the mortality threshold. The mortality threshold is a number ℓ\ell such that if the zero matrix is in the semigroup, then the zero matrix can be written as a product of at most ℓ\ell matrices from any subset that generates the semigroup.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.