# A convex set with a rich difference

,  Oliver Roche-Newton  Institute for Algebra, Johannes Kepler Universität
Linz, Austria<EMAIL_ADDRESS>and  Audie Warren  Johann Radon
Institute for Computational and Applied Mathematics
Linz, Austria<EMAIL_ADDRESS>
###### Abstract.

We construct a convex set $A$ with cardinality $2n$ and with the property that
an element of the difference set $A-A$ can be represented in $n$ different
ways. We also show that this construction is optimal by proving that for any
convex set $A$, the maximum possible number of representations an element of
$A-A$ can have is $\lfloor|A|/2\rfloor$.

## Introduction

A finite set $A\subset\mathbb{R}$ is said to be convex if the consecutive
differences are strictly increasing. That is, if we write
$A=\\{a_{1}<a_{2}<\dots<a_{n}\\}$, $A$ is convex if

$a_{i}-a_{i-1}<a_{i+1}-a_{i}$

holds for all $2\leq i\leq n-1$. One can also use the equivalent formulation
that a set $A$ is convex if we can write $A=f(\\{1,2,\dots,n\\})$ for some
strictly convex function $f$. The convexity of $f$ disrupts the additive
structure of the pre-image $\\{1,2,\dots,n\\}$, and this leads us to expect
that a convex set cannot have much additive structure.

This principle can be quantified in different ways, and one such way is to
prove that the difference set

$A-A:=\\{a-b:a,b\in A\\}$

is large. The current state of the art for this problem is a result of Schoen
and Shkredov [6], proving that the bound111Throughout this note, the notation
$X\gg Y$ and $Y\ll X,$ are equivalent and mean that $X\geq cY$ for some
absolute constant $c>0$.

$|A-A|\gg|A|^{8/5-o(1)}$

holds for any convex set $A$.

Another approach is to consider the additive energy

$E(A):=|\\{(a,b,c,d)\in A^{4}:a-b=c-d\\}|,$

which can also be expressed as

$E(A)=\sum_{x}r^{2}_{A-A}$

where $r_{A-A}(x):=|\\{(a,b)\in A\times A:a-b=x\\}|$. The bound

(1) $E(A)\ll|A|^{5/2}$

was proven using incidence theory by Konyagin [3] and using elementary methods
by Garaev [2]. See also [4] for an alternative presentation of a proof of (1).
A further improvement was later given by Shkredov [7], using additional higher
energy tools from additive combinatorics.

One might even expect that a qualitatively stronger statement than (1) holds;
namely that $r_{A-A}(x)$ is guaranteed to be small for all $x\neq 0$. Indeed,
if one knew, for instance, that $r_{A-A}(x)\leq|A|^{1-c}$ holds for all $x\neq
0$, this immediately implies the non-trivial bound $E(A)\ll|A|^{3-c}$, which
in turn implies the non-trivial bound $|A-A|\gg|A|^{1+c}$.

However, a construction of Schoen [5] shows that such a uniform upper bound
for the representation function $r_{A-A}(x)$ is not possible. Schoen
constructed a convex set with $n$ elements and some $x\neq 0$ with
$r_{A-A}(x)\geq n/4$.

The main purpose of this note is to give a construction of a convex set with a
rich difference which improves the construction of Schoen. We prove the
following result.

######  Theorem 1.

For every $m\in\mathbb{N}$, there exists a convex set $A\subseteq\mathbb{R}$
of size $2m$ and a non-zero element $d\in A-A$ such that $r_{A-A}(d)\geq m$.

We also show that this construction is optimal, proving that, for any convex
set with cardinality $n$ and any $d\neq 0$,

$r_{A-A}(d)\leq\left\lfloor\frac{n}{2}\right\rfloor.$

## The construction

###### Proof of Theorem 1.

We give a concrete construction of the set

$A=\\{a_{1}<a_{2}<\dots<a_{2m}\\},$

which is made up of two halves. The set $A$ begins with $0$, and then has gaps
$1+(i-1)\delta$, for some very small $\delta>0$ which will be specified later.
The first half of $A$ is filled like this. That is, for $1\leq k\leq m+1$, we
define

$a_{k}:=(k-1)+\delta\frac{(k-2)(k-1)}{2},$

and so the first $m+1$ elements of $A$ are the elements of the set

$A_{1}:=\left\\{0,1,2+\delta,3+3\delta,...,m+\delta\frac{m(m-1)}{2}\right\\}.$

Fix

$d:=m+\delta\frac{m(m-1)}{2}=a_{m+1}.$

The rest of $A$ is defined iteratively. For $1\leq i\leq m-1$, we set

$a_{m+1+i}:=a_{1+2i}+d.$

This immediately gives rise to the system of equations

(2) $d=a_{m+1}-a_{1}=a_{m+2}-a_{3}=\dots=a_{2m}-a_{2m-1}.$

We therefore have $r_{A-A}(d)\geq m$.

It remains to check that this set is convex. Note that the first part of $A$,
namely $A_{1}=\\{a_{1},\dots,a_{m+1}\\}$, is convex, since the consecutive
difference increase by $\delta$ at each step.

We will prove by induction on $i$ that the set

$\\{a_{1},a_{2},\dots,a_{m+2+i}\\}$

is convex for $0\leq i\leq m-2$.

We first check the base case $i=0$. We need to verify that the difference
$a_{m+2}-a_{m+1}$ is sufficiently large, which will give a condition on
$\delta$. We must have

$a_{m+2}-a_{m+1}>a_{m+1}-a_{m},$

which upon plugging in the definitions yields

$2+\delta>1+\frac{\delta m(m-1)}{2}-\frac{\delta(m-2)(m-1)}{2}.$

After simplification, this gives the condition $\delta<\frac{1}{m-2}$.

Now let $1\leq i\leq m-2$. We must verify that

$\\{a_{1},a_{2},\dots,a_{m+2+i}\\}$

is convex, given the induction hypothesis that
$\\{a_{1},a_{2},\dots,a_{m+1+i}\\}$ is convex. All that remains is to check
that

$a_{m+2+i}-a_{m+1+i}>a_{m+1+i}-a_{m+i}.$

We use equations (2) to rewrite each side, as

$a_{m+2+i}-a_{m+1+i}=a_{1+2(i+1)}-a_{1+2i}$
$a_{m+1+i}-a_{m+i}=a_{1+2i}-a_{1+2(i-1)}.$

Note that, since the differences on the right hand side above are then
consecutive differences of length two within a convex set, we have

$\displaystyle a_{m+2+i}-a_{m+1+i}$ $\displaystyle=a_{1+2(i+1)}-a_{1+2i}$
$\displaystyle>a_{1+2i}-a_{1+2(i-1)}$ $\displaystyle=a_{m+1+i}-a_{m+i}$

as needed. Here we have used the inductive hypothesis that
$\\{a_{1},a_{2},\dots,a_{m+1+i}\\}$ is convex as well as the fact that
$1+2(i+1)\leq m+1+i$. The latter inequality follows from the condition that
$i\leq m-2$. ∎

Note that by taking $\delta$ to be a sufficiently small rational number, and
dilating the set $A$ through by common denominators, we can find
$A\subseteq\mathbb{Z}$ satisfying Theorem 1.

## A matching upper bound for the representation function

The next result shows that the construction of Theorem 1 is optimal.

######  Theorem 2.

For a convex set $A\subset\mathbb{R}$ and any
$d\in\mathbb{R}\setminus\\{0\\}$,

$r_{A-A}(d)\leq\left\lfloor\frac{|A|}{2}\right\rfloor.$

###### Proof.

Write the elements of $A$ in increasing order so that
$A=\\{a_{1}<a_{2}<\dots<a_{n}\\}$. Suppose that $d$ can be represented in $t$
different ways as an element of $A-A$. We can write

$\displaystyle d=$ $\displaystyle a_{j_{1}+k_{1}}-a_{j_{1}}$ $\displaystyle=$
$\displaystyle a_{j_{2}+k_{2}}-a_{j_{2}}$ $\displaystyle\vdots$ (3)
$\displaystyle=$ $\displaystyle a_{j_{t}+k_{t}}-a_{j_{t}}$

such that the $k$ indices satisfy

(4) $k_{1}>k_{2}>\dots>k_{t}.$

Indeed, because $A$ is convex, we cannot have two of the $k$ indices repeating
in the list (Proof.). This follows from the fact that, for fixed $k$, the
sequence

(5) $(a_{j+k}-a_{j})_{j\in\mathbb{N}}$

is strictly increasing. Note also that, for fixed $j$, the sequence

(6) $(a_{j+k}-a_{j})_{k\in\mathbb{N}}$

is strictly increasing. This follows immediately from the fact that the
$a_{i}$ are increasing.

######  Claim 1.

For all $1\leq i\leq t-1$

$j_{i+1}\geq j_{i}+2$

###### Proof of Claim.

Suppose for a contradiction that $j_{i+1}\leq j_{i}+1$. We also have
$k_{i+1}\leq k_{i}-1$, and so $j_{i+1}+k_{i+1}\leq j_{i}+k_{i}$. Therefore

$a_{j_{i+1}+k_{i+1}}\leq a_{j_{i}+k_{i}}.$

But then it follows from (Proof.) that

$0\leq a_{j_{i}+k_{i}}-a_{j_{i+1}+k_{i+1}}=a_{j_{i}}-a_{j_{i+1}},$

and so

(7) $j_{i}\geq j_{i+1}.$

However, since the sequences (5) and (6) are strictly increasing, it follows
that

$\displaystyle a_{j_{i+1}+k_{i+1}}-a_{j_{i+1}}$ $\displaystyle\leq
a_{j_{i}+k_{i+1}}-a_{j_{i}}$ $\displaystyle<a_{j_{i}+k_{i}}-a_{j_{i}}.$

This contradicts (Proof.).

∎

Applying the claim iteratively yields

(8) $j_{t}\geq j_{t-1}+2\geq j_{t-2}+4\geq\dots\geq j_{1}+2(t-1)\geq
1+2(t-1)=2t-1.$

We also know that $j_{t}+k_{t}\leq n$ and $k_{t}\geq 1$. Therefore,

$j_{t}\leq n-1.$

Combining this with (8) gives

$t\leq n/2.$

Finally, since $t$ is an integer, this is equivalent to the bound

$t\leq\lfloor n/2\rfloor.$

∎

## Concluding remarks

Interestingly, the construction cannot be modified to give a rich sum in a
convex set. For $x\in\mathbb{R}$, we use the notation

$r_{A+A}(x):=|\\{(a,b)\in A\times A:a+b=x\\}|.$

In sharp contrast with Theorem 1, the bound

(9) $r_{A+A}(C)\ll|A|^{2/3}.$

holds for any convex set $A$ and $C\in\mathbb{R}$. The inequality (9) was also
observed by Schoen [5], and can be proved using the Szemerédi-Trotter Theorem.

Another interesting direction is to determine how many $k$-rich
representations can occur. A well-known application of the Szemerédi-Trotter
Theorem (see for instance [4]) gives the bound

(10) $|\\{d:r_{A-A}(d)\geq t\\}|\ll\frac{n^{3}}{t^{3}}$

for any convex set $A$ with cardinality $n$. On the other hand, one can glue
together $n/t$ copies of the construction in Theorem 1 with $t$ elements in
order to obtain a convex set $A$ with $n$ elements and

(11) $|\\{d:r_{A-A}(d)\geq t\\}|\gg\frac{n}{t}.$

There is a considerable gap between the upper and lower bounds of (10) and
(11) respectively, although the bounds converge as $t$ gets close to $n$.

## Acknowledgements

The authors were supported by the Austrian Science Fund FWF Project P 34180.
We are grateful to Brandon Hanson, Misha Rudnev and Dmitrii Zhelezov for
helpfully sharing their insights. We are particularly grateful to Ilya
Shkredov for informing us about the reference [5].

## References

  * [1] G. Elekes, M. Nathanson and I. Ruzsa, Convexity and sumsets, J Number Theory. 83 (1999), 194-201.
  * [2] M. Z. Garaev, ‘On lower bounds for the $L_{1}$-norm of some exponential sums’, Mat. Zametki 68 (2000), no. 6, 842-850.
  * [3] S. V. Konyagin, ‘An estimate for the $L_{1}$-norm of an exponential sums’, (in Russian) In The Theory of Approximations of Functions and Operators, Abstracts of Papers of the International Conference, Dedicated to Stechkin’s 80th Anniversary, Ekaterinbourg (2000), 88-89.
  * [4] O. Raz, O. Roche-Newton and M. Sharir, ‘Sets with few distinct distances do not have heavy lines’, Discrete Math. 338 (2015), no. 8, 1484–1492.
  * [5] T. Schoen, ‘On Convolutions of Convex Sets and Related Problems’, Canad. Math. Bull. 57 (2014), no. 4, 877-883.
  * [6] T. Schoen and I. Shkredov, ‘On sumsets of convex sets’, Combin. Probab. Comput. 20 (2011), no. 5, 793-798.
  * [7] I. Shkredov, ‘Some new results on higher energies’, Trans. Moscow Math. Soc. (2013), 31-63.


[name=Theorem,style=plain,sibling=theorem]ourtheorem
[name=Corollary,sibling=theorem]ourcorollary
[name=Lemma,Refname=Lemma,Lemmas,sibling=theorem]ourlemma
[name=Proposition,Refname=Proposition,Propositions,sibling=theorem]ourproposition
[name=Remark,Refname=Remark,style=plain,sibling=theorem]ourremark University
of Oxford, UKWork supported by St John’s College, Oxford. University College
London, UKhttps://orcid.org/0000-0002-5452-936X University of Oxford, UKWork
supported by a Royal Society University Research Fellowship.University of
Oxford, UKWork supported by St John’s College, Oxford. University of Oxford,
UKWork supported by St John’s College, Oxford. Georgina Bumpus and Georgina
Bumpus and Stefan Kiefer and Paul-Ioan Stoienescu and Jonathan
Tanner[500]Mathematics of computing Discrete mathematics [300]Theory of
computation Algebraic language theory [300]Theory of computation Quantitative
automata This work is part of a project that has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant agreement No. 852769, ARiAT).

###### Acknowledgements.

The authors thank James Worrell for discussing [17] with them. Artur Czumaj,
Anuj Dawar, and Emanuela Merelli 3 47th International Colloquium on Automata,
Languages, and Programming (ICALP 2020) ICALP 2020 ICALP 2020 July 8–11, 2020
Saarbrücken, Germany (virtual conference) 168 115

# On the Size of Finite Rational Matrix Semigroups

Georgina Bumpus  Christoph Haase  Stefan Kiefer  Paul-Ioan Stoienescu
Jonathan Tanner

###### Abstract

Let $n$ be a positive integer and $\mathcal{M}$ a set of rational $n\times
n$-matrices such that $\mathcal{M}$ generates a finite multiplicative
semigroup. We show that any matrix in the semigroup is a product of matrices
in $\mathcal{M}$ whose length is at most $2^{n(2n+3)}g(n)^{n+1}\in
2^{O(n^{2}\log n)}$, where $g(n)$ is the maximum order of finite groups over
rational $n\times n$-matrices. This result implies algorithms with an
elementary running time for deciding finiteness of weighted automata over the
rationals and for deciding reachability in affine integer vector addition
systems with states with the finite monoid property.

###### keywords:

Matrix semigroups, Burnside problem, weighted automata, vector addition
systems

###### category:

##  1 Introduction

#### The Burnside Problem

An element $g$ of a semigroup $G$ is called _torsion_ if $g^{i}=g^{j}$ holds
for some naturals $i<j$, and $G$ _torsion_ if all its elements are torsion.
Burnside [6] asked in 1902 a question which became known as the _Burnside
problem_ for groups: is every finitely generated torsion group finite? Schur
[28] showed in 1911 that this holds true for groups of invertible complex
matrices, i.e., any finitely generated torsion subgroup of
$\mathit{GL}(n,\mathbb{C})$ is finite. This was generalised by Kaplansky [21,
p. 105] to matrices over arbitrary fields. The Burnside problem for groups has
a negative answer in general: in 1964 Golod and Shafarevich exhibited a
finitely generated infinite torsion group [13, 14].

#### The Maximal Order of Finite Matrix Groups

Schur’s result [28] assures that finitely generated torsion matrix groups are
finite, but does not bound the group order. Indeed, it is easy to see that any
finite cyclic group is isomorphic to a group generated by a matrix in
$\mathit{GL}(2,\mathbb{R})$. The same is not true for
$\mathit{GL}(n,\mathbb{Q})$: An elementary proof (which we reproduce in the
appendix following [23]) shows that any finite subgroup of
$\mathit{GL}(n,\mathbb{Q})$ is conjugate to a finite subgroup of
$\mathit{GL}(n,\mathbb{Z})$. Another elementary proof shows that the order of
any finite subgroup of $\mathit{GL}(n,\mathbb{Z})$ divides $(2n)!$; see, e.g.,
[27, Chapter IX]. Thus, denoting the order of the largest finite subgroup of
$\mathit{GL}(n,\mathbb{Q})$ by $g(n)$, we have $g(n)\leq(2n)!$. It is shown in
a paper by Friedland [12] that $g(n)=2^{n}n!$ holds for all sufficiently large
$n$. This bound is attained by the group of signed permutation matrices.
Friedland’s proof rests on an article by Weisfeiler [34] which in turn is
based on the classification of finite simple groups. Feit showed in an
unpublished manuscript [9] that $g(n)=2^{n}n!$ holds if and only if
$n\in\mathbb{N}\setminus\\{2,4,6,7,8,9,10\\}$.111A list of the maximal-order
finite subgroups of $\mathit{GL}(n,\mathbb{Q})$ for $n\in\\{2,4,6,7,8,9,10\\}$
can be found in [3, Table 1]. Feit’s proof relies on an unpublished manuscript
[33], also based on the classification of finite simple groups, which
Weisfeiler left behind before his tragic disappearance.

#### Deciding Finiteness of Matrix Groups

Bounds on group orders give a straightforward, albeit inefficient, way of
deciding whether a given set of matrices generates a finite group: starting
from the set of generators, enlarge it with products of matrices in the set,
until either it is closed under product or the bound on the order has been
exceeded. One can do substantially better: it is shown in [2] that, using
computations on quadratic forms, one can decide in polynomial time if a given
finite set of rational matrices generates a finite group.

#### Deciding Finiteness of Matrix Semigroups

The Burnside problem has a natural analogue for semigroups. In 1975,
McNaughton and Zalcstein [26] positively solved the Burnside problem for
matrix semigroups, i.e., they showed, for any field $\mathbb{F}$, that any
finitely generated torsion subsemigroup of $\mathbb{F}^{n\times n}$ is finite,
using the result for groups by Schur and Kaplansky as a building block. From a
computational point of view, McNaughton and Zalcstein’s result suggests an
approach for deciding finiteness of the semigroup generated by a given set of
rational matrices: finiteness is recursively enumerable, by closing the set of
generators under product, as described above for groups. On the other hand,
infiniteness is recursively enumerable by enumerating elements in the
generated semigroup and checking each element whether it is torsion. By the
contrapositive of McNaughton and Zalcstein’s result, if the generated matrix
semigroup is infinite, it has a non-torsion element, witnessing infiniteness.
However, deciding whether a given matrix has finite order is nontrivial. Only
in 1980 did Kannan and Lipton [19, 20] show that the so-called _orbit problem_
is decidable (in polynomial time), implying an algorithm for checking whether
a matrix has finite order.

Avoiding this problem, Mandel and Simon [25] showed in 1977 that there exists
a function $f:\mathbb{N}^{3}\to\mathbb{N}$ such that if $S$ is a finite
subsemigroup of $\mathbb{F}^{n\times n}$, generated by $m$ of its elements,
and the subgroups of $S$ have order at most $g$, then $S$ has size
(cardinality) at most $f(n,m,g)$. For rational matrices, one may use the
function $g(n)$ from above for $g$. By making, in a sense, McNaughton and
Zalcstein’s proof quantitative, Mandel and Simon explicitly construct such a
function $f$, which implies an algorithm, with bounded runtime, for deciding
finiteness of a finitely generated rational matrix semigroup. A similar result
about the decidability of this problem was obtained independently and
concurrently by Jacob [18].

#### Size Bounds

Unlike the function $g$ for rational matrix groups, Mandel and Simon’s
function $f(n,m,g)$ depends on $m$, the number of generators. This is
unavoidable: the semigroup generated by the set
$\mathcal{M}_{m}:=\left\\{\begin{pmatrix}0&i\\\
0&0\end{pmatrix}:i\in\\{0,\ldots,m-1\\}\\}\right\\}$ is the set
$\mathcal{M}_{m}$ itself, with $|\mathcal{M}_{m}|=m$ for any $m\in\mathbb{N}$.
Further, the growth in $n$ of Mandel and Simon’s $f$ is, roughly, a tower of
exponentials of height $n$. They write in [25, Section 3]: “However, it is
likely that our upper bound [$f(n,m,g)$] can be significantly improved.”

In [4, Chapter VI], Berstel and Reutenauer also show, for the rational case,
the existence of a function in $n$ and $m$ that bounds the semigroup size.
They write: “As we shall see, the function […] grows extremely rapidly.” An
analysis of their proof shows that the growth of their function is comparable
with the growth of Mandel and Simon’s function. A related approach is taken in
[31]. Further proofs of McNaughton and Zalcstein’s result can be found, e.g.,
in [24, 11, 8, 30], but they do not lead to better size bounds.

#### Length Bounds

In 1991, Weber and Seidl [32] considered semigroups over _nonnegative_ integer
matrices. Using combinatorial and automata-theoretic techniques, they showed
that if a finite set $\mathcal{M}\subseteq\mathbb{N}^{n\times n}$ generates a
finite monoid, then for any matrix $M$ of that monoid there are
$M_{1},\ldots,M_{\ell}\in\mathcal{M}$ with $\ell\leq\lceil e^{2}n!\rceil-2$
such that $M=M_{1}\cdots M_{\ell}$; i.e., any matrix in the monoid is a
product of matrices in $\mathcal{M}$ whose _length_ is at most $\lceil
e^{2}n!\rceil-2$. Note that this bound does not depend on the number of
generators. Weber and Seidl also give an example that shows that such a length
bound cannot be smaller than $2^{n-2}$.

Almeida and Steinberg [1] proved in 2009 a length bound for rational matrices
and expressing the zero matrix: if a finite set
$\mathcal{M}\subseteq\mathbb{Q}^{n\times n}$ (with $n>1$) generates a _finite_
semigroup that includes the zero matrix $0$, then there are
$M_{1},\ldots,M_{\ell}\in\mathcal{M}$ with $\ell\leq(2n-1)^{n^{2}}-1$ such
that $0=M_{1}\cdots M_{\ell}$. A length bound of $n^{5}$ for expressing the
zero matrix was recently given in the nonnegative integer case [22]. It is
open whether there is a polynomial length bound for expressing the zero matrix
in the rational case.

#### Our Contribution

We prove a $2^{O(n^{2}\log n)}$ length bound for the rational case: Let
$\mathcal{M}\subseteq\mathbb{Q}^{n\times n}$ be a finite set of rational
matrices such that $\mathcal{M}$ generates a finite semigroup
$\overline{\mathcal{M}}$. Then for any $M\in\overline{\mathcal{M}}$ there are
$M_{1},\ldots,M_{\ell}\in\mathcal{M}$ with $\ell\leq 2^{n(2n+3)}g(n)^{n+1}\in
2^{O(n^{2}\log n)}$ such that $M=M_{1}\cdots M_{\ell}$. (Here $g(n)\leq(2n)!$
denotes the order of the largest finite subgroup of
$\mathit{GL}(n,\mathbb{Q})$.) The example by Weber and Seidl mentioned above
shows that any such length bound must be at least $2^{n-2}$. A length bound
trivially implies a size bound, and section 1 allows us to obtain the first
significant improvement over the fast-growing function of Mandel and Simon.
Let $\mathcal{M}\subseteq\mathbb{Q}^{n\times n}$ be a finite set of $m$
rational matrices that generate a finite semigroup $\overline{\mathcal{M}}$.
Then $|\overline{\mathcal{M}}|\leq m^{2^{O(n^{2}\log n)}}$.

The proof of section 1 is largely based on linear-algebra arguments,
specifically on the structure of a certain graph of vector spaces obtained
from $\mathcal{M}$. This graph was introduced and analysed by Hrushovski et
al. [17] for the computation of the _Zariski closure_ of the generated matrix
semigroup.

After the preliminaries (section 2) and the proof of section 1 (section 3), we
discuss applications in automata theory (section 4). In particular we show
that our result implies the first elementary-time algorithm for deciding
finiteness of weighted automata over the rationals.

##  2 Preliminaries

We write $\mathbb{N}=\\{0,1,2,\ldots\\}$. For a finite alphabet $\Sigma$, we
write $\Sigma^{*}=\\{a_{1}\cdots a_{k}:k\geq 0,\ a_{i}\in\Sigma\\}$ and
$\Sigma^{+}=\\{a_{1}\cdots a_{k}:k\geq 1,\ a_{i}\in\Sigma\\}$ for the free
monoid and the free semigroup generated by $\Sigma$. The elements of
$\Sigma^{*}$ are called _words_. For a word $w=a_{1}\cdots a_{k}$, its
_length_ $|w|$ is $k$. We denote by $\varepsilon$ the empty word, i.e., the
word of length $0$. For $L\subseteq\Sigma^{*}$, we also write
$L^{*}=\\{w_{1}\cdots w_{k}:k\geq 0,\ w_{i}\in L\\}\subseteq\Sigma^{*}$ and
$L^{+}=\\{w_{1}\cdots w_{k}:k\geq 1,\ w_{i}\in L\\}\subseteq\Sigma^{*}$.

We denote by $I_{n}$ the $n\times n$-identity matrix, and by $\vec{0}$ the
zero vector. For vectors $v_{1},\ldots,v_{k}$ from a vector space, we denote
their span by $\left<v_{1},\ldots,v_{k}\right>$. In this article, we view
elements of $\mathbb{Q}^{n}$ as _row_ vectors.

For some $n\in\mathbb{N}\setminus\\{0\\}$, let
$\mathcal{M}\subseteq\mathbb{Q}^{n\times n}$ be a finite set of rational
matrices, generating a finite semigroup $\overline{\mathcal{M}}$. For
notational convenience, throughout the paper, we associate to $\mathcal{M}$ an
alphabet $\Sigma$ with $|\mathcal{M}|=|\Sigma|$, and a bijection
$M:\Sigma\to\mathcal{M}$ which we extend to the monoid morphism
$M:\Sigma^{*}\to\overline{\mathcal{M}}\cup\\{I_{n}\\}$. Thus we may write
$M(\Sigma)$ and $M(\Sigma^{*})$ for $\mathcal{M}$ and
$\overline{\mathcal{M}}\cup\\{I_{n}\\}$, respectively.

We often identify a matrix $A\in\mathbb{Q}^{n\times n}$ with its linear
transformation $A:\mathbb{Q}^{n}\to\mathbb{Q}^{n}$ such that $x\mapsto xA$ for
row vectors $x\in\mathbb{Q}^{n}$. To avoid clutter, we extend linear-algebra
notions from matrices to words, i.e., we may write $\operatorname{im}w$, $\ker
w$, $\operatorname{rk}w$ for the image
$\operatorname{im}(M(w))=\mathbb{Q}^{n}M(w)$, the kernel
$\ker(M(w))=\\{x\in\mathbb{Q}^{n}:xM(w)=\vec{0}\\}$, and the rank of $M(w)$.

If all matrices in $M(\Sigma)$ are invertible and $M(\Sigma^{*})$ is finite,
then $M(\Sigma^{*})$ is a finite subgroup of $\mathit{GL}(n,\mathbb{Q})$. For
$n\in\mathbb{N}$, let us write $g(n)$ for the size of the largest finite
subgroup of $\mathit{GL}(n,\mathbb{Q})$. As discussed in the introduction, a
non-trivial but elementary proof shows $g(n)\leq(2n)!$, and it is known that
$g(n)=2^{n}n!$ holds for sufficiently large $n$.

#### Exterior Algebra

This brief introduction is borrowed and slightly extended from [17, Section
3]. Let $V$ be an $n$-dimensional vector space over a field $\mathbb{F}$. (We
will only consider $V=\mathbb{Q}^{n}$.) For any $r\in\mathbb{N}$, let
$\mathcal{A}_{r}$ denote the set of maps $B:V^{r}\to\mathbb{F}$ so that $B$ is
linear in each argument and further $B(v_{1},\ldots,v_{r})=0$ holds whenever
$v_{i}=v_{i+1}$ holds for some $i\in\\{1,\ldots,r-1\\}$. These conditions
imply that swapping two adjacent arguments changes the sign, i.e.,

$B(v_{1},\ldots,v_{i-2},v_{i-1},v_{i+1},v_{i},v_{i+2},v_{i+3},\ldots,v_{r})\
=\ -B(v_{1},\ldots,v_{r})\,.$

These properties of $\mathcal{A}_{r}$ imply that, given an arbitrary basis
$\\{e_{1},\ldots,e_{n}\\}$ of $V$, any $B\in\mathcal{A}_{r}$ is uniquely
determined by all $B(e_{i_{1}},\ldots,e_{i_{r}})$ where $1\leq
i_{1}<i_{2}<\ldots<i_{r}\leq n$. For any $v_{1},\ldots,v_{r}\in V$, define the
_wedge product_

$v_{1}\wedge\cdots\wedge
v_{r}:\mathcal{A}_{r}\to\mathbb{F}\quad\text{by}\quad(v_{1}\wedge\cdots\wedge
v_{r})(B)=B(v_{1},\ldots,v_{r})\,.$

It follows from the properties of $\mathcal{A}_{r}$ above that the wedge
product is linear in each argument: if $v_{i}=\lambda
u+\lambda^{\prime}u^{\prime}$ then

$\Big{(}\bigwedge_{1\leq i\leq
k}v_{i}\Big{)}(B)=\lambda\Big{(}\bigwedge_{1\leq j<i}v_{j}\wedge
u\wedge\bigwedge_{i<j\leq
k}v_{j}\Big{)}(B)+\lambda^{\prime}\Big{(}\bigwedge_{1\leq j<i}v_{j}\wedge
u^{\prime}\wedge\bigwedge_{i<j\leq k}v_{j}\Big{)}(B)$

Moreover, $(v_{1}\wedge\cdots\wedge v_{r})(B)=0$ if $v_{i}=v_{j}$ holds for
some $i,j$ with $i\neq j$.

For $r\in\mathbb{N}$ define $\Lambda^{r}V$ as the vector space generated by
the length-$r$ wedge products $v_{1}\wedge\cdots\wedge v_{r}$ with
$v_{1},\ldots,v_{r}\in V$. For any basis $\\{e_{1},\ldots,e_{n}\\}$ of $V$,
the set $\\{e_{i_{1}}\wedge\cdots\wedge e_{i_{r}}:1\leq i_{1}<\ldots<i_{r}\leq
n\\}$ is a basis of $\Lambda^{r}V$; hence $\dim\Lambda^{r}V=\binom{n}{r}$.
Note that $\Lambda^{1}V=V$ and $\binom{n}{r}=0$ for $r>n$. One can view the
wedge product as an associative operation
$\mathord{\wedge}:\Lambda^{r}V\times\Lambda^{\ell}V\to\Lambda^{r+\ell}V$.
Define the _exterior algebra of $V$_ as the direct sum $\Lambda
V=\Lambda^{0}V\oplus\Lambda^{1}V\oplus\cdots$. Then also
$\mathord{\wedge}:\Lambda V\times\Lambda V\to\Lambda V$.

It follows that for $u_{1},\ldots,u_{r}\in V$, we have
$u_{1}\wedge\cdots\wedge u_{r}\neq\vec{0}$ if and only if
$\\{u_{1},\ldots,u_{r}\\}$ is linearly independent. Furthermore, for
$u_{1},\ldots,u_{r},v_{1},\ldots,v_{r}\in V$ and $u=u_{1}\wedge\cdots\wedge
u_{r}\neq\vec{0}$ and $v=v_{1}\wedge\cdots\wedge v_{r}\neq\vec{0}$, we have
that $u,v$ are scalar multiples if and only if
$\left<u_{1},\ldots,u_{r}\right>=\left<v_{1},\ldots,v_{r}\right>$.

The Grassmannian $\mathrm{Gr}(n)$ is the set of subspaces of $\mathbb{Q}^{n}$.
By the above-stated properties of the wedge product there is an injective
function

$\iota:\mathrm{Gr}(n)\to\Lambda\,\mathbb{Q}^{n}$

such that, for all $W\in\mathrm{Gr}(n)$, we have
$\iota(W)=v_{1}\wedge\cdots\wedge v_{r}$ where $\\{v_{1},\ldots,v_{r}\\}$ is
an arbitrarily chosen basis of $W$. Note that the particular choice of a basis
for $W$ only changes the value of $\iota(W)$ up to a constant. Given subspaces
$W_{1},W_{2}\in\mathrm{Gr}(n)$, we moreover have $W_{1}\cap
W_{2}=\\{\vec{0}\\}$ if and only if
$\iota(W_{1})\wedge\iota(W_{2})\neq\vec{0}$.

##  3 Proof of section 1

It is convenient to state and prove our main result in terms of monoids rather
than semigroups: Let $M:\Sigma^{*}\to\mathbb{Q}^{n\times n}$ be a monoid
morphism whose image $M(\Sigma^{*})$ is finite. Then for any $w\in\Sigma^{*}$
there is $u\in\Sigma^{*}$ with $M(w)=M(u)$ and

$|u|\ \leq\ 2^{n(2n+3)}g(n)^{n+1}\in 2^{O(n^{2}\log n)}\,.$

With this theorem at hand, section 1 follows immediately:

###### Proof of section 1.

Let $M\in\overline{\mathcal{M}}$ be an element of the semigroup generated by
$\mathcal{M}$. If $M\neq I_{n}$, by section 3, $M$ can be written as a short
product. Otherwise, $M=I_{n}\in G$, where
$G=\overline{\mathcal{M}\cap\mathit{GL}(n,\mathbb{Q})}$ is a finite group of
order at most $g(n)$. For any product $M_{1}\cdots M_{\ell}$ with $\ell>g(n)$,
there are $1\leq i<j\leq\ell$ such that $M_{1}\cdots M_{i}=M_{1}\cdots M_{j}$,
and so $M_{1}\cdots M_{\ell}=M_{1}\cdots M_{i}M_{j+1}\cdots M_{\ell}$. Hence,
there are $\ell\in\\{1,\ldots,g(n)\\}$ and
$M_{1},\ldots,M_{\ell}\in\mathcal{M}$ such that $M=I_{n}=M_{1}\cdots
M_{\ell}$. ∎

The same argument as in the proof above shows that in a finite _monoid_
$(H,\mathord{\cdot})$, generated by $G\subseteq H$, for any $h\in H$ there are
$\ell\in\\{0,\ldots,|H|-1\\}$ and $g_{1},\ldots,g_{\ell}\in G$ with
$h=g_{1}\cdots g_{\ell}$.

In the remainder of this section, we prove section 3. We assume that
$M:\Sigma^{*}\to\mathbb{Q}^{n\times n}$ is a monoid morphism with finite image
$M(\Sigma^{*})$.

###  3.1 The Maximum-Rank Case

In this subsection we prove: Suppose that there is $r\leq n$ with
$\operatorname{rk}a=r$ for all $a\in\Sigma$. Let $w\in\Sigma^{*}$ with
$\operatorname{rk}w=r$. Then there is $u\in\Sigma^{*}$ with $M(w)=M(u)$ and

$|u|\ \leq\ 2^{2n+3}g(n)-1\ \in\ 2^{O(n\log n)}\,.$

In this subsection we assume that $\operatorname{rk}a=r$ holds for all
$a\in\Sigma$. For the proof of subsection 3.1, we define a directed labelled
graph $G$ whose vertices are the vector spaces $\operatorname{im}w$ for
$w\in\Sigma^{*}$ such that $\operatorname{rk}w=r$, and whose edges are triples
$(V_{1},a,V_{2})$ such that $a\in\Sigma$ and $V_{1}M(a)=V_{2}$. Let
$(V_{1},a,V_{2})$ be an edge; then $V_{2}\subseteq\operatorname{im}a$, but
$\dim V_{2}=r=\operatorname{rk}a=\dim\operatorname{im}a$, hence
$V_{2}=\operatorname{im}a$, i.e., the edge label determines the edge target.
We will implicitly use the fact that any path in $G$ is determined by its
start vertex and the sequence of its edge labels. Note that if $V_{1}$ is a
vertex and $a\in\Sigma$, the edge $(V_{1},a,\operatorname{im}a)$ is present in
$G$ if and only if $\operatorname{rk}V_{1}M(a)=r$ if and only if
$V_{1}\cap\ker a=\\{\vec{0}\\}$.

The following two lemmas, which are variants of lemmas in [17, Section 6], are
statements about the structure of $G$ in terms of its strongly connected
components (SCCs).

Let $w=w_{1}\cdots w_{k}$ for $w_{1},\ldots,w_{k}\in\Sigma^{+}$ with
$\operatorname{rk}w=r$ such that the $k$ vertices
$\operatorname{im}w_{1},\ldots,\operatorname{im}w_{k}$ are all in different
SCCs of $G$. Then $k\leq 2\binom{n}{r}$.

###### Proof.

Let $i\in\\{2,\ldots,k-1\\}$. Since
$\operatorname{rk}w_{i}=r=\operatorname{rk}(w_{i}w_{i+1})$, we have
$\operatorname{im}w_{i}\cap\ker w_{i+1}=\\{\vec{0}\\}$, thus
$\iota(\operatorname{im}w_{i})\wedge\iota(\ker w_{i+1})\neq\vec{0}$. On the
other hand, for any $j<i$, since
$\operatorname{im}w_{i},\operatorname{im}w_{j}$ are in different SCCs and
$\operatorname{im}w_{i}$ is reachable from $\operatorname{im}w_{j}$, the
vertex $\operatorname{im}w_{j}$ is not reachable from
$\operatorname{im}w_{i}$; therefore we have $\operatorname{im}w_{i}\cap\ker
w_{j}\neq\\{\vec{0}\\}$, thus $\iota(\operatorname{im}w_{i})\wedge\iota(\ker
w_{j})=\vec{0}$. It follows that $\iota(\ker w_{i+1})\not\in\left<\iota(\ker
w_{j}):j<i\right>$. Indeed, if $\iota(\ker
w_{i+1})=\sum_{j<i}\lambda_{j}\iota(\ker w_{j})$ for some
$\lambda_{1},\ldots,\lambda_{i-1}$ then, by linearity of the wedge product,
$\iota(\operatorname{im}w_{i})\wedge\iota(\ker
w_{i+1})=\sum_{j<i}\lambda_{j}(\iota(\operatorname{im}w_{i})\wedge\iota(\ker
w_{j}))=\vec{0}$, a contradiction.

We show by induction on $i$ that $\dim\left<\iota(\ker
w_{j}):j\in\\{1,\ldots,i\\}\right>\geq i/2$ for all $i\in\\{1,\ldots,k\\}$.
This is clear for $i=1,2$. For the induction step, we have
$\dim\left<\iota(\ker
w_{j}):j\in\\{1,\ldots,i+1\\}\right>\geq\dim\left<\iota(\ker
w_{i+1}),\iota(\ker w_{j}):j\in\\{1,\ldots,i-1\\}\right>\geq
1+(i-1)/2=(i+1)/2$. Hence $k/2\leq\dim\left<\iota(\ker
w_{j}):j\in\\{1,\ldots,k\\}\right>\leq\dim\Lambda^{n-r}\mathbb{Q}^{n}=\binom{n}{r}$.
∎

Let $a_{1}\cdots a_{k}\in\Sigma^{*}$ be (the edge labels of) a shortest path
in $G$ from a vertex $\operatorname{im}a_{0}$ to $\operatorname{im}a_{k}$.
Then $k\leq\binom{n}{r}$.

###### Proof.

Let $i\in\\{0,\ldots,k-2\\}$. We have $\operatorname{im}a_{i}\cap\ker
a_{i+1}=\\{\vec{0}\\}$, thus $\iota(\operatorname{im}a_{i})\wedge\iota(\ker
a_{i+1})\neq\vec{0}$. On the other hand, for any $j>i+1$, since $a_{i+1}\cdots
a_{j}$ is a shortest path from $\operatorname{im}a_{i}$ to
$\operatorname{im}a_{j}$, there is no edge from $\operatorname{im}a_{i}$ to
$\operatorname{im}a_{j}$; therefore we have $\operatorname{im}a_{i}\cap\ker
a_{j}\neq\\{\vec{0}\\}$, thus $\iota(\operatorname{im}a_{i})\wedge\iota(\ker
a_{j})=\vec{0}$. It follows that $\iota(\ker a_{i+1})\not\in\left<\iota(\ker
a_{j}):j>i+1\right>$.

By induction it follows that $\dim\left<\iota(\ker
a_{j}):j\in\\{i+1,\ldots,k\\}\right>\geq k-i$ holds for all
$i\in\\{0,\ldots,k-1\\}$. Hence $k\leq\dim\left<\iota(\ker
a_{j}):j\in\\{1,\ldots,k\\}\right>\leq\dim\Lambda^{n-r}\mathbb{Q}^{n}=\binom{n}{r}$.
∎

The next lemmas discuss _cycles_ $w\in\Sigma^{+}$ in $G$, i.e., (the edge
labels of) paths in $G$ such that $\operatorname{im}w\cap\ker
w=\\{\vec{0}\\}$. A cycle $w$ is said to be _around_ $\operatorname{im}w_{0}$
if $\operatorname{im}w=\operatorname{im}w_{0}$. The following lemma says,
loosely speaking, that cycles around a single vertex “generate a group”.

Let $w_{0}\in\Sigma^{+}$ with $\operatorname{rk}w_{0}=r$, and let
$P\in\mathbb{Q}^{r\times n}$ be a matrix with
$\operatorname{im}P=\operatorname{im}w_{0}$. Then for every cycle
$w\in\Sigma^{+}$ around $\operatorname{im}w_{0}$ there exists a unique
invertible matrix $M^{\prime}(w)\in\mathit{GL}(r,\mathbb{Q})$ such that
$PM(w)=M^{\prime}(w)P$. Moreover, for any nonempty set $C\subseteq\Sigma^{+}$
of cycles around $\operatorname{im}w_{0}$, $M^{\prime}(C^{+})$ is a finite
subgroup of $\mathit{GL}(r,\mathbb{Q})$.

###### Proof.

Let $w\in\Sigma^{+}$ be a cycle around $\operatorname{im}w_{0}$. Since
$\operatorname{im}P\cap\ker(M(w))=\\{\vec{0}\\}$, it follows that
$\operatorname{im}(PM(w))=\operatorname{im}w=\operatorname{im}P$. So the rows
of $PM(w)$ are linear combinations of rows of $P$, and vice versa, hence there
is a unique $M^{\prime}(w)\in\mathit{GL}(r,\mathbb{Q})$ with
$PM(w)=M^{\prime}(w)P$.

Let $C\subseteq\Sigma^{+}$ be a nonempty set of cycles around
$\operatorname{im}w_{0}$. For any $w_{1},w_{2}\in C$ we have
$M^{\prime}(w_{1}w_{2})P=PM(w_{1}w_{2})=PM(w_{1})M(w_{2})=M^{\prime}(w_{1})PM(w_{2})=M^{\prime}(w_{1})M^{\prime}(w_{2})P$,
and since the rows of $P$ are linearly independent, it follows that
$M^{\prime}(w_{1}w_{2})=M^{\prime}(w_{1})M^{\prime}(w_{2})$. Thus,
$M^{\prime}(C^{+})$ is a semigroup.

Towards a contradiction, suppose $M^{\prime}(C^{+})$ were infinite. Since the
rows of $P$ are linearly independent, it follows that $M^{\prime}(C^{+})P$ is
infinite, thus $PM(C^{+})$ is infinite. Since
$\operatorname{im}w_{0}=\operatorname{im}P$, there is a matrix
$B\in\mathbb{Q}^{n\times r}$ with $M(w_{0})=BP$. Since the columns of $B$ are
linearly independent, the set $BPM(C^{+})$ is infinite. But this set equals
$M(w_{0}C^{+})$, contradicting the finiteness of $M(\Sigma^{*})$. Thus the
semigroup $M^{\prime}(C^{+})$ is finite. As
$M^{\prime}(C^{+})\subseteq\mathit{GL}(r,\mathbb{Q})$, it follows that
$M^{\prime}(C^{+})$ is a finite group. ∎

The following lemma allows us, loosely speaking, to limit the number of cycles
in a word.

Let $w_{0},w_{1},\ldots,w_{k}\in\Sigma^{+}$ such that $w_{1},\ldots,w_{k}$ are
cycles around $\operatorname{im}w_{0}$. Then there exist $\ell\leq g(n)-1$ and
$\\{u_{1},\ldots,u_{\ell}\\}\subseteq\\{w_{1},\ldots,w_{k}\\}$ such that
$M(w_{0}w_{1}\cdots w_{k})=M(w_{0}u_{1}\cdots u_{\ell})$.

###### Proof.

We can assume $k\geq 1$. Let $C=\\{w_{1},\ldots,w_{k}\\}$. Let $P$ and
$M^{\prime}(w)$ for $w\in C$ as in subsection 3.1. By subsection 3.1, the set
$M^{\prime}(C^{+})$ is a finite subgroup of $\mathit{GL}(r,\mathbb{Q})$, so we
have $|M^{\prime}(C^{+})|\leq g(r)\leq g(n)$. By section 3, there are
$\ell\leq g(n)-1$ and $u_{1},\ldots,u_{\ell}\in C$ such that
$M^{\prime}(w_{1})\cdots M^{\prime}(w_{k})=M^{\prime}(u_{1})\cdots
M^{\prime}(u_{\ell})$. Since $\operatorname{im}w_{0}=\operatorname{im}P$,
there is a matrix $B\in\mathbb{Q}^{n\times r}$ with $M(w_{0})=BP$. Hence we
have $M(w_{0}w_{1}\cdots w_{k})=BPM(w_{1})\cdots
M(w_{k})=BM^{\prime}(w_{1})\cdots M^{\prime}(w_{k})P=BM^{\prime}(u_{1})\cdots
M^{\prime}(u_{\ell})P=BPM(u_{1})\cdots M(u_{\ell})=M(w_{0}u_{1}\cdots
u_{\ell})$. ∎

The following lemma allows us to add cycles to a word.

Let $w\in\Sigma^{+}$ be a cycle in $G$. Then there exists
$\rho(w)\in\mathbb{N}\setminus\\{0\\}$ such that
$M(w_{0})=M(w_{0}w^{\rho(w)})$ holds for all $w_{0}\in\Sigma^{+}$ with
$\operatorname{im}w_{0}=\operatorname{im}w$.

###### Proof.

Let $P\in\mathbb{Q}^{r\times n}$ be a matrix with
$\operatorname{im}P=\operatorname{im}w$. By subsection 3.1, there exists
$M^{\prime}(w)\in\mathit{GL}(r,\mathbb{Q})$ such that $PM(w)=M^{\prime}(w)P$
and $\\{M^{\prime}(w)^{i}:i\in\mathbb{N}\\}$ is a finite group. Define
$\rho(w)$ to be the order of this group, i.e.,
$M^{\prime}(w)^{\rho(w)}=I_{r}$. Let $w_{0}\in\Sigma^{+}$ with
$\operatorname{im}w_{0}=\operatorname{im}w$. Since
$\operatorname{im}w_{0}=\operatorname{im}P$, there is a matrix
$B\in\mathbb{Q}^{n\times r}$ with $M(w_{0})=BP$. Hence
$M(w_{0})=BP=BI_{r}P=BM^{\prime}(w)^{\rho(w)}P=BPM(w)^{\rho(w)}=M(w_{0})M(w)^{\rho(w)}=M(w_{0}w^{\rho(w)})$.
∎

$\ \ddots\ $$\ \cdots\ $$\ \ddots\
$$a$$a_{1}$$s(a,a_{1})$$s(a_{1},a)$$a_{2}$$s(a,a_{2})$$s(a_{2},a)$$a_{3}$$a_{k}$$s(a,a_{k})$$s(a_{k},a)$
Figure 1: Illustration of the paths $w$ and $w^{\prime}$ in subsection 3.1.
Edges are depicted as solid arrows, paths as dashed arrows.

The following lemma allows us to limit the length of paths within an SCC.

Let $a\in\Sigma$, and let $w\in\Sigma^{*}$ be a path in $G$ from
$\operatorname{im}a$ such that $\operatorname{im}a$ and $\operatorname{im}w$
are in the same SCC. Then there exists $u\in\Sigma^{*}$ with $M(aw)=M(au)$ and

$|u|\ \leq\ 2^{n+2}g(n)-2\ \in\ 2^{O(n\log n)}\,.$

###### Proof.

For any $b_{1},b_{2}\in\Sigma$ such that
$\operatorname{im}b_{1},\operatorname{im}b_{2}$ are in the SCC of
$\operatorname{im}a$, let $s(b_{1},b_{2})\in\Sigma^{*}$ be a shortest path
from $\operatorname{im}b_{1}$ to $\operatorname{im}b_{2}$. By subsection 3.1,
we have $|s(b_{1},b_{2})|\leq\binom{n}{r}$.

Suppose $w=a_{1}\cdots a_{k}$ for $a_{i}\in\Sigma$. For $i\in\\{1,\ldots,k\\}$
define the cycle $w_{i}:=s(a_{i},a)s(a,a_{i})$ around
$\operatorname{im}a_{i}$. By subsection 3.1, we have $M(aw)=M(aw^{\prime})$
for

$\displaystyle w^{\prime}\ :=\ $ $\displaystyle
a_{1}w_{1}^{\rho(w_{1})}a_{2}w_{2}^{\rho(w_{2})}\cdots
a_{k}w_{k}^{\rho(w_{k})}\,.$ For $i\in\\{1,\ldots,k\\}$ also define the cycle
$v_{i}:=s(a,a_{i})s(a_{i},a)$ around $\operatorname{im}a$. Then we have:
$\displaystyle w^{\prime}\ =\ $ $\displaystyle
a_{1}s(a_{1},a)v_{1}^{\rho(w_{1})-1}s(a,a_{1})a_{2}s(a_{2},a)v_{2}^{\rho(w_{2})-1}s(a,a_{2})\cdots
a_{k}s(a_{k},a)v_{k}^{\rho(w_{k})-1}s(a,a_{k})$

Figure 1 illustrates the paths $w$ and $w^{\prime}$. Define a set of cycles
$C\subseteq\Sigma^{*}$ around $\operatorname{im}a$ by

$C\ :=\
\\{a_{1}s(a_{1},a),v_{1},s(a,a_{1})a_{2}s(a_{2},a),v_{2},\ldots,s(a,a_{k-1})a_{k}s(a_{k},a),v_{k}\\}\,.$

Since $w^{\prime}\in C^{*}s(a,a_{k})$, by subsection 3.1, there exist
$\ell\leq g(n)-1$ and $u_{1},\ldots,u_{\ell}\in C$ such that
$M(aw)=M(aw^{\prime})=M(au_{1}u_{2}\cdots u_{\ell}s(a,a_{k}))$. For all $v\in
C$ we have $|v|\leq 2\binom{n}{r}+1\leq 2^{n+2}$, and
$|s(a,a_{k})|\leq\binom{n}{r}\leq 2^{n}$. Hence the lemma holds for
$u:=u_{1}u_{2}\cdots u_{\ell}s(a,a_{k})$, as $|u|\leq
2^{n+2}(g(n)-1)+2^{n}\leq 2^{n+2}g(n)-2$. ∎

We are ready to prove subsection 3.1.

###### Proof of subsection 3.1.

Decompose the word $w$ into $w=a_{1}w_{1}a_{2}w_{2}\cdots a_{k}w_{k}$ for
$a_{i}\in\Sigma$ so that for all $i\in\\{1,\ldots,k\\}$ the vertices
$\operatorname{im}a_{i},\operatorname{im}w_{i}$ are in the same SCC, and for
all $i\in\\{1,\ldots,k-1\\}$ the vertices
$\operatorname{im}w_{i},\operatorname{im}a_{i+1}$ are in different SCCs. By
subsection 3.1, we have $k\leq 2\binom{n}{r}\leq 2^{n+1}$. For all
$i\in\\{1,\ldots,k\\}$, by subsection 3.1, there is $u_{i}\in\Sigma^{*}$ with
$|u_{i}|\leq 2^{n+2}g(n)-2$ such that $M(a_{i}w_{i})=M(a_{i}u_{i})$. Hence the
proposition holds for $u:=a_{1}u_{1}a_{2}u_{2}\cdots a_{k}u_{k}$, as $|u|\leq
2^{n+1}(2^{n+2}g(n)-2+1)\leq 2^{2n+3}-1$. ∎

###  3.2 The General Case

In this subsection we prove section 3. For $r\in\\{0,\ldots,n\\}$ let
$d_{r}\in\mathbb{N}$ be the smallest number such that for any $w\in\Sigma^{*}$
with $\operatorname{rk}w\geq r$ there is $u\in\Sigma^{*}$ with $M(w)=M(u)$ and
$|u|\leq d_{r}$. Also write $h$ for the bound from subsection 3.1.

For any $r\in\\{0,\ldots,n-1\\}$ we have $d_{r}\leq d_{r+1}+(d_{r+1}+1)h$.

###### Proof.

Let $w\in\Sigma^{*}$ with $\operatorname{rk}w\geq r$. We need to show that
there is $u\in\Sigma^{*}$ with $M(w)=M(u)$ and $|u|\leq d_{r+1}+(d_{r+1}+1)h$.
Decompose $w$ into $w=w_{0}a_{1}w_{1}a_{2}w_{2}\cdots a_{k}w_{k}$ for
$a_{i}\in\Sigma$ such that $\operatorname{rk}w_{0}>r$ and for all
$i\in\\{1,\ldots,k\\}$ we have $\operatorname{rk}(a_{i}w_{i})=r$ and
$\operatorname{rk}w_{i}>r$. (This decomposition is unique; in particular,
$a_{k}w_{k}$ is the shortest suffix of $w$ with rank $r$.) By the definition
of $d_{r+1}$, for all $i\in\\{0,\ldots,k\\}$ there exists $u_{i}\in\Sigma^{*}$
with $M(w_{i})=M(u_{i})$ and $|u_{i}|\leq d_{r+1}$. Then
$M(w)=M(u_{0}a_{1}u_{1}a_{2}u_{2}\cdots a_{k}u_{k})$.

Define a new alphabet $\Sigma_{r}$ and a monoid morphism
$M_{r}:\Sigma_{r}^{*}\to\mathbb{Q}^{n\times n}$ with
$M_{r}(\Sigma_{r})=\\{M(a_{i}u_{i}):i\in\\{1,\ldots,k\\}\\}$, and note that
$\operatorname{rk}M_{r}(b)=r$ for all $b\in\Sigma_{r}$. Then there is a word
$y\in\Sigma_{r}^{*}$ such that $M_{r}(y)=M(a_{1}u_{1}\cdots a_{k}u_{k})$. By
subsection 3.1, there is $x\in\Sigma_{r}^{*}$ with $M_{r}(y)=M_{r}(x)$ and
$|x|\leq h$. Obtain the word $v\in\Sigma^{*}$ from $x$ by replacing each
letter $b\in\Sigma_{r}$ in $x$ by $a_{i}u_{i}$ for $i\in\\{1,\ldots,k\\}$ such
that $M_{r}(b)=M(a_{i}u_{i})$. Then $M_{r}(x)=M(v)$, and thus
$M(w)=M(u_{0}a_{1}u_{1}\cdots
a_{k}u_{k})=M(u_{0})M_{r}(y)=M(u_{0})M_{r}(x)=M(u_{0})M(v)=M(u_{0}v)$, where
$|u_{0}v|=|u_{0}|+|v|\leq d_{r+1}+(d_{r+1}+1)|x|\leq d_{r+1}+(d_{r+1}+1)h$. ∎

We can now prove our main result.

###### Proof of section 3.

We prove by induction that for all $r\in\\{0,\ldots,n\\}$ we have
$d_{r}\leq(h+1)^{n-r}d_{n}+(h+1)^{n-r}-1$. For the base case, $r=n$, this is
trivial. For the step, let $r<n$. We have:

$\displaystyle d_{r}\ $ $\displaystyle\leq\ h+(h+1)d_{r+1}$ (subsection 3.2)
$\displaystyle\leq\ h+(h+1)\left((h+1)^{n-r-1}d_{n}+(h+1)^{n-r-1}-1\right)$
(induction hypothesis) $\displaystyle=\ h+(h+1)^{n-r}d_{n}+(h+1)^{n-r}-h-1$

This completes the induction proof. Hence
$d_{0}\leq(h+1)^{n}(d_{n}+1)=2^{n(2n+3)}g(n)^{n}(d_{n}+1)$. The rank-$n$
matrices in $M(\Sigma)$ generate a finite subgroup of
$\mathit{GL}(n,\mathbb{Q})$. So it follows by section 3 that $d_{n}+1\leq
g(n)$. Thus $d_{0}\leq 2^{n(2n+3)}g(n)^{n+1}$. ∎

##  4 Algorithmic Applications

section 1 gives an exponential-space algorithm for deciding finiteness of a
finitely generated rational matrix semigroup. In fact, the following theorem
shows that deciding finiteness is in the second level of the weak EXP
hierarchy (see e.g. [16] for a definition). Given be a finite set
$\mathcal{M}\subseteq\mathbb{Q}^{n\times n}$ of rational matrices, the problem
of deciding finiteness of the generated semigroup $\overline{\mathcal{M}}$ is
in $\textup{coNEXP}^{\textup{NP}}$.

###### Proof.

For a $\textup{NEXP}^{\textup{NP}}$ algorithm deciding infiniteness, non-
deterministically guess in exponential time some $M=M_{1}\cdots M_{\ell}$,
$M_{i}\in\mathcal{M}$, with $\ell=2^{n(2n+3)}g(n)^{n+1}+1$ as a witness for
infiniteness. Then, using a call to an NP oracle, check whether there are
$M_{1}^{\prime},\ldots,M_{r}^{\prime}\in\mathcal{M}$ such that
$M=M_{1}^{\prime}\cdots M_{r}^{\prime}$ for some $0\leq r<\ell$. If the call
is successful then reject, otherwise accept.

Correctness of the algorithm immediately follows from section 1: if
$\overline{\mathcal{M}}$ is finite, then the
$M_{1}^{\prime},\ldots,M_{r}^{\prime}\in\mathcal{M}$ such that
$M=M_{1}^{\prime}\cdots M_{r}^{\prime}$ are guaranteed to exist. ∎

This is the first improvement of the non-elementary algorithm of Mandel and
Simon [25].

Another immediate consequence of section 1 is an upper bound on the complexity
of the membership problem for finite matrix semigroups: Given a finite set of
rational matrices $\mathcal{M}\subseteq\mathbb{Q}^{n\times n}$ such that
$\overline{\mathcal{M}}$ is finite and $A\in\mathbb{Q}^{n\times n}$, the
problem of deciding whether $A\in\overline{\mathcal{M}}$ is in NEXP.

In the remainder of this section, we discuss implications of section 4 to
decision problems in automata theory.

###  4.1 Weighted Automata

The motivation for Mandel and Simon to study the finiteness problem originated
from investigating the decidability of the finiteness problem (originally
called boundedness problem in [25]) for weighted automata. A _weighted
automaton over $\mathbb{Q}$_ is a quintuple
$\mathcal{A}=(n,\Sigma,M,\alpha,\eta)$ where $n\in\mathbb{N}$ is the number of
states, $\Sigma$ is the finite alphabet, $M:\Sigma\to\mathbb{Q}^{n\times n}$
maps letters to transition matrices, $\alpha\in\mathbb{Q}^{n}$ is the initial
state vector, and $\eta\in\mathbb{Q}^{n}$ is the final state vector. We extend
$M$ to the monoid morphism $M:\Sigma^{*}\to\mathbb{Q}^{n\times n}$ as before.
Such an automaton defines a function $|\mathcal{A}|:\Sigma^{*}\to\mathbb{Q}$
by defining $|\mathcal{A}|(w)=\alpha M(w)\eta^{T}$, where the superscript $T$
denotes transpose. We say, $\mathcal{A}$ is _finite_ if the image of
$|\mathcal{A}|$ is finite, i.e., if
$|\mathcal{A}|(\Sigma^{*})\subseteq\mathbb{Q}$ is a finite set. The
_finiteness problem_ asks whether a given automaton is finite.

It is clear that if $M(\Sigma^{*})$ is finite then $\mathcal{A}$ is finite.
The converse is not generally true: e.g., any automaton $\mathcal{A}$ whose
initial state vector is the zero vector satisfies
$|\mathcal{A}|(\Sigma^{*})=\\{0\\}$, hence is finite, regardless of
$M(\Sigma^{*})$. However, it is argued in the proof of Corollary 5.4 in [25]
that, given an automaton $\mathcal{A}$, one can compute, in exponential time,
a polynomial-size automaton $\mathcal{B}$ with monoid morphism
$M_{\mathcal{B}}$ such that (i) $|\mathcal{A}|=|\mathcal{B}|$, and (ii)
$\mathcal{A}$ (and hence $\mathcal{B}$) is finite if and only if
$M_{\mathcal{B}}(\Sigma^{*})$ is finite.222We remark that this automaton
$\mathcal{B}$ has the minimal number of states among the automata defining the
function $|\mathcal{A}|$. This minimal automaton goes back to [29] and has
been further studied in, e.g., [7, 10]. Mandel and Simon use this argument to
show that the finiteness problem for weighted automata over $\mathbb{Q}$ is
decidable. section 4 then immediately gives: The finiteness problem for
weighted automata over $\mathbb{Q}$ can be decided in
$\textup{coNEXP}^{\textup{NP}}$.

###  4.2 Affine Integer Vector Addition Systems with States

We show that section 1 together with section 1 imply an upper bound for the
reachability problem in affine integer vector addition systems with states
with the finite monoid property (afmp-$\mathbb{Z}$-VASS) studied in [5]. An
affine $\mathbb{Z}$-VASS in dimension $d\in\mathbb{N}$ is a tuple
$\mathcal{V}=(d,Q,T)$ such that $Q$ is a finite set of states and $T\subseteq
Q\times\mathbb{Z}^{d\times d}\times\mathbb{Z}^{d}\times Q$ is a finite
transition relation. Setting $\mathcal{M}:=\\{A\in\mathbb{Z}^{d\times
d}:(q,A,\vec{b},r)\in T\\}$, in afmp-$\mathbb{Z}$-VASS we additionally require
that $\overline{\mathcal{M}}$ is finite. A configuration of $\mathcal{V}$ is a
tuple $(q,\vec{v})\in Q\times\mathbb{Z}^{d}$ which we write as $q(\vec{v})$.
We define the step relation
${\rightarrow}\subseteq(Q\times\mathbb{Z}^{d})^{2}$ such that
$q(\vec{v})\rightarrow r(\vec{w})$ if and only if there is a transition
$(q,A,\vec{b},r)\in T$ such that $\vec{w}=A\cdot\vec{v}+\vec{b}$. Moreover, we
denote by $\rightarrow^{*}$ the reflexive transitive closure of $\rightarrow$.
For a configuration $q(\vec{v})$, we define the reachability set of
$q(\vec{v})$ as
$\mathcal{R}(q(\vec{v})):=\\{r(\vec{w}):q(\vec{v})\rightarrow^{*}r(\vec{w})\\}$.
Given configurations $q(\vec{v})$ and $r(\vec{w})$, reachability is the
problem of deciding whether $r(\vec{w})\in\mathcal{R}(q(\vec{v}))$. Note that
$\mathcal{R}(q(\vec{v}))$ is in general infinite despite
$\overline{\mathcal{M}}$ being finite.

The reachability problem for afmp-$\mathbb{Z}$-VASS was shown decidable in [5]
by a reduction to reachability in $\mathbb{Z}$-VASS. A $\mathbb{Z}$-VASS is an
afmp-$\mathbb{Z}$-VASS in which every transition is of the form
$(q,I_{d},\vec{b},r)$. The reachability problem for $\mathbb{Z}$-VASS is known
to be NP-complete, see e.g. [15]. The size of the $\mathbb{Z}$-VASS obtained
in the reduction given in [5] grows in $|\overline{\mathcal{M}}|$ and hence
leads to a non-elementary upper bound for reachability in
afmp-$\mathbb{Z}$-VASS assuming Mandel and Simon’s bound. The results of this
paper enable us to significantly improve this upper bound. The reachability
problem for afmp-$\mathbb{Z}$-VASS can be decided in EXPSPACE.

###### Proof.

Let $\mathcal{V}=(d,Q,T)$ be an afmp-$\mathbb{Z}$-VASS and let $\mathcal{M}$
be defined as above. Set $||\mathcal{M}||:=|\overline{\mathcal{M}}|\cdot
d^{2}\cdot\max\\{\log(||A||+1):A\in\overline{\mathcal{M}}\\}$, where $||A||$
is the largest absolute value of all entries of $A$. Since $||A_{1}\cdots
A_{n}||\leq d^{n}\cdot||A_{1}||\cdots||A_{n}||$ for all
$A_{1},\ldots,A_{n}\in\mathbb{Z}^{d\times d}$ and $n\in\mathbb{N}$, by section
1 and section 1 we have

$||\mathcal{M}||\leq|T|^{2^{O(d^{2}\cdot\log d)}}\cdot
d^{2}\cdot{2^{d(2d+3)}g(d)^{d+1}}\cdot(\log
d+||T||)\leq||T||^{2^{O(d^{2}\cdot\log d)}},$

where $||T||:=\sum_{(q,A,\vec{b},r)\in
T}d^{2}\cdot\lceil\log||A||+\log||\vec{b}||+1\rceil$. It can be deduced from
the proof of [5, Thm. 7] that reachability in $\mathcal{V}$ can be decided in
non-deterministic space that is polynomially bounded in the encoding of
$\mathcal{V}$ and poly-logarithmically in $||\mathcal{M}||$, from which the
desired exponential space upper bound follows. ∎

##  5 Conclusion

The main result of this paper has been to show that any element in the finite
multiplicative semigroup $\overline{\mathcal{M}}$ generated by a finite set
$\mathcal{M}$ of $m$ rational $n\times n$ matrices can be obtained as a
product of generators of length at most $2^{O(n^{2}\log n)}$. This length
bound immediately gives that $|\overline{\mathcal{M}}|$ is bounded by
$m^{2^{O(n^{2}\log n)}}$.

There remain two immediate questions that we did not answer in this article.
The first is whether the order of growth of $|\overline{\mathcal{M}}|$ we
obtained is tight. If $\overline{\mathcal{M}}$ is a group its order can be
bounded by $2^{n}n!$ for almost all $n$, and this bound is attained by the
group of signed permutation matrices. In contrast, in the semigroup case
$|\overline{\mathcal{M}}|$ also depends on $m$. We conjecture that our doubly
exponential upper bound is not optimal and that it is possible to establish an
exponential upper bound of $|\overline{\mathcal{M}}|$ in terms of $m$ and $n$.
The second open question concerns the precise complexity of deciding
finiteness of matrix semigroups. We have been unable to establish any non-
trivial lower bounds on this problem and conjecture that our
$\textup{coNEXP}^{\textup{NP}}$ upper bound can significantly be improved,
possibly by adapting techniques of Babai et al. [2].

## References

  * [1] J. Almeida and B. Steinberg.  Matrix mortality and the Černý-Pin conjecture.  In Proceedings of Developments in Language Theory (DLT), pages 67–80, 2009.
  * [2] L. Babai, R. Beals, and D. Rockmore.  Deciding finiteness of matrix groups in deterministic polynomial time.  In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 117–126, 1993.
  * [3] N. Berry, A. Dubickas, N. D. Elkies, B. Poonen, and C. Smyth.  The conjugate dimension of algebraic numbers.  The Quarterly Journal of Mathematics, 55(3):237–252, 2004.
  * [4] J. Berstel and C. Reutenauer.  Rational Series and Their Languages, volume 12 of Monographs in Theoretical Computer Science. An EATCS Series.  Springer-Verlag, 1988.
  * [5] M. Blondin, C. Haase, and F. Mazowiecki.  Affine extensions of integer vector addition systems with states.  In Proceedings of the International Conference on Concurrency Theory (CONCUR), pages 14:1–14:17, 2018.
  * [6] W. Burnside.  On an unsettled question in the theory of discontinuous groups.  The Quarterly Journal of Pure and Applied Mathematics, 33:230–238, 1902.
  * [7] J.W. Carlyle and A. Paz.  Realizations by stochastic finite automata.  Journal of Computer and System Sciences, 5(1):26–40, 1971.
  * [8] A. de Luca and S. Varricchio.  Finiteness and Regularity in Semigroups and Formal Languages.  Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, 1999.
  * [9] W. Feit.  The orders of finite linear groups.  Unpublished preprint.
  * [10] M. Fliess.  Matrices de Hankel.  Journal de Mathématiques Pures et Appliquées, 53:197–222, 1974.
  * [11] A. Freedman, R. N. Gupta, and R. M. Guralnick.  Shirshov’s theorem and representations of semigroups.  Pacific Journal of Mathematics, 181(3):159–176, 1997.
  * [12] S. Friedland.  The maximal orders of finite subgroups in $\mathit{GL}_{n}(\mathbb{Q})$.  Proceedings of the American Mathematical Society, 125(12):3519–3526, 1997.
  * [13] E. S. Golod.  On nil-algebras and finitely approximable $p$-groups.  Izv. Akad. Nauk SSSR Ser. Mat., 28:273–276, 1964.
  * [14] E. S. Golod and I. R. Shafarevich.  On the class field tower.  Izv. Akad. Nauk SSSR Ser. Mat., 28:261–272, 1964.
  * [15] C. Haase and S. Halfon.  Integer vector addition systems with states.  In Proceedings of Reachability Problems (RP), pages 112–124, 2014\.
  * [16] L. A. Hemachandra.  The strong exponential hierarchy collapses.  Journal of Computer and System Sciences, 39(3):299–322, 1989.
  * [17] E. Hrushovski, J. Ouaknine, A. Pouly, and J. Worrell.  Polynomial invariants for affine programs.  In Proceedings of the Symposium on Logic in Computer Science (LICS), pages 530–539, 2018.
  * [18] G. Jacob.  Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices.  Theoretical Computer Science, 5(2):183–204, 1977.
  * [19] R. Kannan and R. J. Lipton.  The orbit problem is decidable.  In Proceedings of the Symposium on Theory of Computing (STOC), pages 252–261, 1980.
  * [20] R. Kannan and R. J. Lipton.  Polynomial-time algorithm for the orbit problem.  Journal of the ACM, 33(4):808–821, 1986.
  * [21] I. Kaplansky.  Fields and Rings.  University of Chicago Press, second edition, 1972.
  * [22] S. Kiefer and C. Mascle.  On finite monoids over nonnegative integer matrices and short killing words.  In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS), pages 43:1–43:13, 2019.
  * [23] J. Kuzmanovich and A. Pavlichenkov.  Finite groups of matrices whose entries are integers.  The American Mathematical Monthly, 109(2):173–186, 2002.
  * [24] G. Lallement.  Semigroups and combinatorial applications.  John Wiley & Sons, 1979.
  * [25] A. Mandel and I. Simon.  On finite semigroups of matrices.  Theoretical Computer Science, 5(2):101–111, 1977.
  * [26] R. McNaughton and Y. Zalcstein.  The Burnside problem for semigroups.  Journal of Algebra, 34:292–299, 1975.
  * [27] M. Newman.  Integral Matrices.  Academic Press, 1972.
  * [28] I. Schur.  Über Gruppen periodischer Substitutionen.  In Sitzungsbericht Preuss. Akad. Wiss., pages 619–627, 1911.
  * [29] M. P. Schützenberger.  On the definition of a family of automata.  Information and Control, 4(2–3):245–270, 1961.
  * [30] B. Steinberg.  Yet another solution to the Burnside problem for matrix semigroups.  Canadian Mathematical Bulletin, 55(1):188–192, 2012.
  * [31] H. Straubing.  The Burnside problem for semigroups of matrices.  In L. J. Cummings, editor, Combinatorics on Words, pages 279–295. Academic Press, 1983.
  * [32] A. Weber and H. Seidl.  On finitely generated monoids of matrices with entries in $\mathbb{N}$.  Informatique théorique et Applications/Theoretical Informaties and Applications, 25:19–38, 1991.
  * [33] B. Weisfeiler.  On the size and structure of finite linear groups.  Unpublished preprint, see https://arxiv.org/abs/1203.1960.
  * [34] B. Weisfeiler.  Post-classification version of Jordan’s theorem on finite linear groups.  Proceedings of the National Academy of Sciences of the United States of America, 81:5278–5279, 1984.

##  Appendix A Rational vs. Integer Matrix Groups

We show that any finite subgroup of $\mathit{GL}(n,\mathbb{Q})$ is conjugate
to a finite subgroup of $\mathit{GL}(n,\mathbb{Z})$. This implies that
rational matrix groups cannot be larger than integer matrix groups.

First we need a basic fact about finitely generated Abelian groups. Let $A$ be
an (additively written) Abelian (= commutative) group. The group $A$ is
isomorphic to $\mathbb{Z}^{n}$ (“ _free of rank $n$_”) if and only if there is
a set $\\{a_{1},\ldots,a_{n}\\}\subseteq A$, called _basis_ of $A$, such that
for each $g\in A$ there are unique coefficients
$k_{1},\ldots,k_{n}\in\mathbb{Z}$ such that $g=k_{1}a_{1}+\cdots+k_{n}a_{n}$.
For any $g_{1},\ldots,g_{m}\in A$ we write

$\left<g_{1},\ldots,g_{m}\right>\ :=\
\left\\{k_{1}g_{1}+\cdots+k_{m}g_{m}:k_{1},\ldots,k_{m}\in\mathbb{Z}\right\\}\,.$

Using elementary arguments, we prove the following proposition, which is
related to the Fundamental Theorem of Finitely Generated Abelian Groups.

######  Lemma A.1.

Let $A$ be isomorphic to $\mathbb{Z}^{n}$, and let $H$ be a subgroup of $A$.
Then $H$ is isomorphic to $\mathbb{Z}^{m}$ for some $m\leq n$.

######  Proof A.2.

We proceed by induction on $n$, the rank of $A$. For the base case, if $n=0$,
then $H=A=\\{0\\}$. For the induction step, suppose the theorem holds for
ranks less than $n$. Fix a basis $\\{a_{1},\dots,a_{n}\\}$ of $A$ and define
$\phi:H\rightarrow\mathbb{Z}$ by $\phi(k_{1}a_{1}+\dots+k_{n}a_{n}):=k_{1}$.

If $\phi(H)=\\{0\\}$ then $H\subseteq\left<a_{2},\dots,a_{n}\right>$, so $H$
is isomorphic to $\mathbb{Z}^{m}$ for some $m\leq n-1$ by the induction
hypothesis. So assume $\phi(H)\neq\\{0\\}$. Let
$m\in\mathbb{N}\setminus\\{0\\}$ be the smallest positive value in $\phi(H)$
and let $h_{1}\in H$ be such that $\phi(h_{1})=m$. Note that
$h_{1}\notin\ker(\phi)$.

Consider any $h\in H$. Let $\ell,j,k_{2},\ldots,k_{n}\in\mathbb{Z}$ with
$j\in\\{0,\ldots,m-1\\}$ such that $h=(\ell
m+j)a_{1}+k_{2}a_{2}+\dots+k_{n}a_{n}$. Then $\phi(h-\ell h_{1})=j<m$. By the
definition of $m$ it follows that $j=0$, and thus $h=\ell h_{1}+h_{2}$ with
$h_{2}\in\ker(\phi)$.

Let $H_{1}:=\left<h_{1}\right>$ and $H_{2}:=\ker(\phi)$. They are subgroups of
$H$. By the argument in the previous paragraph, we have $H=H_{1}+H_{2}$.
Further $H_{1}\cap H_{2}=\\{0\\}$, as $h_{1}\notin\ker(\phi)$. Since $H_{2}$
is a subgroup of $\left<a_{2},\ldots,a_{n}\right>$, by the induction
hypothesis, $H_{2}$ is isomorphic to $\mathbb{Z}^{m^{\prime}}$ for some
$m^{\prime}\leq n-1$. It follows that $H$ is isomorphic to
$H_{1}\times\mathbb{Z}^{m^{\prime}}$, and so to $\mathbb{Z}^{1+m^{\prime}}$.

For any group $G\subseteq\mathit{GL}(n,\mathbb{Q})$ and any
$C\in\mathit{GL}(n,\mathbb{Q})$, the set $CGC^{-1}$ is a group that is
conjugate, hence isomorphic, to $G$. Following [23] we show that any finite
rational matrix group is conjugate to an integer matrix group.

######  Proposition A.3.

Let $G\subseteq\mathit{GL}(n,\mathbb{Q})$ be finite. Then there is
$C\in\mathit{GL}(n,\mathbb{Q})$ such that
$CGC^{-1}\subseteq\mathit{GL}(n,\mathbb{Z})$.

######  Proof A.4.

Observe that for any $M\in G$, we have $GM=G$. Define $A:=\sum_{M\in
G}\mathbb{Z}^{n}M\subseteq\mathbb{Q}^{n}$. By the observation, $AM=A$ holds
for all $M\in G$.

The set $A$ forms a group with respect to vector addition. It is finitely
generated by the rows of the matrices in $G$, i.e., $A=\left<e_{i}M:M\in G,\
i\in\\{1,\ldots,n\\}\right>$, where
$\\{e_{1},\ldots,e_{n}\\}\subseteq\\{0,1\\}^{n}$ is the standard basis. Let
$d\in\mathbb{N}$ be a common denominator of all entries of all those
generators. Then $dA\subseteq\mathbb{Z}^{n}$, so by A.1 the group $A$ is
isomorphic to $\mathbb{Z}^{n^{\prime}}$ for some $n^{\prime}\leq n$. On the
other hand, since the identity matrix is in $G$, we have
$\mathbb{Z}^{n}\subseteq A$. Hence, $n\leq n^{\prime}$, and so $A$ is
isomorphic to $\mathbb{Z}^{n}$. Let $\gamma:\mathbb{Z}^{n}\to A$ be such an
isomorphism. Then there is a matrix $C\in\mathit{GL}(n,\mathbb{Q})$ such that
$vC=\gamma(v)$ holds for all $v\in\mathbb{Z}^{n}$.

Let $M\in G$. Since
$\mathbb{Z}^{n}CMC^{-1}=AMC^{-1}=AC^{-1}\subseteq\mathbb{Z}^{n}$, all entries
of $CMC^{-1}$ are integers.