11institutetext: Keele University, UK
11email<EMAIL_ADDRESS>
22institutetext: Liverpool John Moores University, UK
22email<EMAIL_ADDRESS>33institutetext: University of
Liverpool, UK
33email<EMAIL_ADDRESS>
# On the Identity and Group Problems for Complex Heisenberg Matrices

Paul C. Bell 11 Reino Niskanen 22 Igor Potapov 33 Pavel Semukhin 22

###### Abstract

We study the Identity Problem, the problem of determining if a finitely
generated semigroup of matrices contains the identity matrix; see Problem 3
(Chapter 10.3) in “Unsolved Problems in Mathematical Systems and Control
Theory” by Blondel and Megretski (2004). This fundamental problem is known to
be undecidable for $\mathbb{Z}^{4\times 4}$ and decidable for
$\mathbb{Z}^{2\times 2}$. The Identity Problem has been recently shown to be
in polynomial time by Dong for the Heisenberg group over complex numbers in
any fixed dimension with the use of Lie algebra and the Baker-Campbell-
Hausdorff formula. We develop alternative proof techniques for the problem
making a step forward towards more general problems such as the Membership
Problem. We extend our techniques to show that the fundamental problem of
determining if a given set of Heisenberg matrices generates a group, can also
be decided in polynomial time.

##  1 Introduction

Matrices and matrix products can represent dynamics in many systems, from
computational applications in linear algebra and engineering to natural
science applications in quantum mechanics, population dynamics and statistics,
among others [4, 3, 9, 10, 14, 18, 23, 27, 28]. The analysis of various
evolving systems requires solutions of reachability questions in linear
systems, which form the essential part of verification procedures, control
theory questions, biological systems predictability, security analysis etc.

Reachability problems for matrix products are challenging due to the
complexity of this mathematical object and a lack of effective algorithmic
techniques. The significant challenge in the analysis of matrix semigroups was
initially illustrated by Markov(1947), [26] and later highlighted by Patterson
(1970) [29], Blondel and Megretski (2004) [4], and Harju (2009) [20]. The
central reachability question is the Membership Problem: Decide whether or not
a given matrix $M$ belongs to the matrix semigroup $S$ generated by a set of
square matrices $G$. By restricting $M$ to be the identity matrix, the problem
is known as the Identity Problem.

######  Problem 1 (Identity Problem)

Let $S$ be a matrix semigroup generated by a finite set of $n{\times}n$
matrices over
$\mathbb{K}=\mathbb{Z},\mathbb{Q},\mathbb{A},\mathbb{Q}(\mathrm{i}),\ldots$ Is
the identity matrix $\bm{I}$ in the semigroup, i.e., does $\bm{I}\in S$ hold?

The Membership Problem is known to be undecidable for integer matrices from
dimension three, but the decidability status of the Identity Problem was
unknown for a long time for matrix semigroups of any dimension, see Problem
10.3 in “Unsolved Problems in Mathematical Systems and Control Theory” [4].
The Identity Problem was shown to be undecidable for $48$ matrices from
$\mathbb{Z}^{4\times 4}$ in [2] and for a generator of eight matrices in [22].
This implies that the _Group Problem_ (decide whether a finitely generated
semigroup is a group) is also undecidable. The Identity Problem and the Group
Problem are open for $\mathbb{Z}^{3\times 3}$.

The Identity Problem for a semigroup generated by $2\times 2$ matrices was
shown to be $\EXPSPACE$ decidable in [8] and later improved by showing to be
$\NP$-complete in [1]. The only decidability beyond integer $2{\times}2$
matrices were shown in [13] for flat rational subsets of GL$(2,\mathbb{Q})$.

Similarly to [7], the work [22] initiated consideration of matrix decision
problems in the Special Linear Group SL$(3,\mathbb{Z})$, by showing that there
is no embedding from pairs of words into matrices from SL$(3,\mathbb{Z})$.
Beyond the $2{\times}2$ case, the Identity Problem was shown to be decidable
for the discrete Heisenberg group ${\rm H}(3,\mathbb{Z})$ which is a subgroup
of SL$(3,\mathbb{Z})$.

The Heisenberg group is widely used in mathematics and physics. This is in
some sense the simplest non-commutative group, and has close connections to
quantum mechanical systems [5, 19, 24], harmonic analysis, and number theory
[6, 12]. It also makes appearances in complexity theory, e.g., the analysis
and geometry of the Heiseberg group have been used to disprove the Goemans-
Linial conjecture in complexity theory [25]. Matrices in physics and
engineering are ordinarily defined with values over $\mathbb{R}$ or
$\mathbb{C}$. In this context, we formulate our decision problems and
algorithmic solutions over the field of complex numbers with a finite
representation, Gaussian rationals $\mathbb{Q}(\mathrm{i})$.

The Identity Problem was recently shown to be decidable in polynomial time for
complex Heisenberg matrices in a paper by Dong [17]. They first prove the
result for upper-triangular matrices with rational entries and ones on the
main diagonal, $\mathrm{UT}(\mathbb{Q})$ and then use a known embedding of the
Heisenberg group over algebraic numbers into $\mathrm{UT}(\mathbb{Q})$. Their
approach is different from our techniques; the main difference being that [17]
uses tools from Lie algebra, and in particular, matrix logarithms and the
Baker-Campbell-Hausdorff formula, to reason about matrix products and their
properties. In contrast, our approach first characterises matrices which are
‘close to’ the identity matrix, which we denote $\Omega$-matrices. Such
matrices are close to the identity matrix in that they differ only in a single
position in the top-right corner. We then argue about the commutator angle of
matrices within this set in order to determine whether zero can be reached, in
which case the identity matrix is reachable. We believe that these techniques
take a step towards proving the decidability of the more general _membership
problem_ , which we discuss towards the end of the paper. A careful analysis
then follows to ensure that all steps require only Polynomial time, and we
extend our techniques to show that determining if a given set of matrices
forms a group (the _group problem_) is also decidable in $\P$ (this result is
shown in [15] using different techniques). We thus present polynomial time
algorithms for both these problems for Heisenberg matrices over
$\mathbb{Q}$(i) in any dimension $n$.

These new techniques allow us to extend previous results for the discrete
Heisenberg group H($n,\mathbb{Z}$) and H($n,\mathbb{Q}$) [22, 11, 23, 16] and
make a step forward towards proving the decidability of the membership problem
for complex Heisenberg matrices.

##  2 Roadmap

We will give a brief overview of our approach here. Given a Heisenberg matrix
$M=\begin{pmatrix}1&\bm{m}_{1}^{T}&m_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\
0&\bm{0}^{T}&1\end{pmatrix}\in{\rm H}(n,\mathbb{Q}(\mathrm{i}))$, denote by
$\psi(M)$ the triple
$(\bm{m}_{1},\bm{m}_{2},m_{3})\in\mathbb{Q}(\mathrm{i})^{2n-3}$. We define the
set $\Omega\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ as those matrices where
$\bm{m}_{1}$ and $\bm{m}_{2}$ are zero vectors, i.e., matrices in $\Omega$
look like $\bm{I}_{n}$ except allowing any element of $\mathbb{Q}(\mathrm{i})$
in the top right element. Such matrices play a crucial role in our analysis.

In particular, given a set of matrices
$G=\\{G_{1},\ldots,G_{t}\\}\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$
generating a semigroup $\langle G\rangle$, we can find a description of
$\Omega_{\langle G\rangle}=\langle G\rangle\cap\Omega$. Since
$\bm{I}\in\Omega$, the Identity Problem reduces to determining if
$\bm{I}\in\Omega_{\langle G\rangle}$.

Several problems present themselves, particularly if we wish to solve the
problem in Polynomial time ($\P$). The set $\Omega_{\langle G\rangle}$ is
described by a linear set $\mathcal{S}\subseteq\mathbb{N}^{t}$, which is the
solution set of a homogeneous system of linear Diophantine equations induced
by matrices in $G$. This is due to the observation that the elements
$(\bm{m}_{1},\bm{m}_{2})\in\mathbb{Q}(\mathrm{i})^{2n-4}$ behave in an
additive fashion under multiplication of Heisenberg matrices. The main issue
is that the size of the basis of $\mathcal{S}$ is exponential in the
description size of $G$. Nevertheless, we can determine _if a solution exists_
to such a system in $\P$ (1), and this proves sufficient.

The second issue is that reasoning about the element
$m_{3}\in\mathbb{Q}(\mathrm{i})$ (i.e., the top right element) in a product of
Heisenberg matrices is much more involved than for elements
$(\bm{m}_{1},\bm{m}_{2})\in\mathbb{Q}(\mathrm{i})^{2n-4}$. Techniques to
determine if $m_{3}=0$ for an $\Omega$-matrix within $\Omega_{\langle
G\rangle}$ take up the bulk of this paper.

The key to our approach is to consider _commutators_ of pairs of matrices
within $G$, which in our case can be described by a single complex number.
After removing all _redundant matrices_ (those never reaching an
$\Omega$-matrix), we have two cases to consider. Either every pair of matrices
from $G$ has the same _angle_ of the commutator or else there are at least two
commutators with different angles.

The latter case is used in 5. It states that the identity matrix can always be
constructed using a solution that contains four particular matrices. Let
$M_{1}$, $M_{2}$, $M_{3}$ and $M_{4}$ be such that
$[M_{1},M_{2}]=r\exp(\mathrm{i}\gamma)$ and
$[M_{3},M_{4}]=r^{\prime}\exp(\mathrm{i}\gamma^{\prime})$, where
$\gamma\neq\gamma^{\prime}$ so that pairs $M_{1},M_{2}$ and $M_{3},M_{4}$ have
different commutator angles. We may then define four matrix products using the
same generators but matrices $M_{1}$, $M_{2}$, $M_{3}$ and $M_{4}$ are in a
different order. This difference in order and the commutator angles being
different, ensures that we can control the top right corner elements in order
to construct the identity matrix. 3 provides details on how to calculate the
top right element in these products. We then prove that these top right
elements in the four matrices are not contained in an open half-plane and this
is sufficient for us to construct the identity matrix.

The above construction does not work when all commutators have the same angle,
and indeed in this case the identity may or may not be present. Hence, we need
to consider various possible shuffles of matrices in these products. To this
end, we extend the result of 3 to derive a formula for the top right element
for any shuffle and prove it as 4. We observe that there is a _shuffle
invariant_ part of the product that does not depend on the shuffle, and that
shuffles add or subtract commutators. Furthermore, this shuffle invariant
component can be calculated from the generators used in the product. As we
assume that all commutators have the same angle, $\gamma$, different shuffles
move the value along the line in the complex plane defined by the common
commutator angle which we call the _$\gamma$ -line_.

It is straightforward to see that if it is not possible to reach the
$\gamma$-line using using the additive semigroup of shuffle invariants, then
the identity cannot be generated. Indeed, since different shuffles move the
value along the $\gamma$-line but the shuffle invariant part never reaches it,
then the possible values are never on the $\gamma$-line, which includes the
origin.

We show that if it _is_ possible to reach the $\gamma$-line using shuffle
invariants and there are at least two non-commuting matrices in the used
solution, then we can show that the identity matrix is in the semigroup (6).
Testing this property requires determining the solvability of a polynomially-
sized set of non-homogeneous systems of linear Diophantine equations, which
can be done in polynomial time by 1.

If the $\gamma$-line can be reached only using commuting matrices, we can
construct another system of linear Diophantine equations since the top right
element has an explicit formula in terms of generators used (see 6).

##  3 Preliminaries

The sets of rational numbers, real numbers and complex numbers are denoted by
$\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$. The set of rational complex
numbers is denoted by $\mathbb{Q}(\mathrm{i})=\\{a+b\mathrm{i}\mid
a,b\in\mathbb{Q}\\}$. The set $\mathbb{Q}(\mathrm{i})$ is often called the
Gaussian rationals in the literature. A complex number can be written in polar
form $a+b\mathrm{i}=r\exp(\mathrm{i}\varphi)$, where $r\in\mathbb{R}$ and
$\varphi\in[0,\pi)$. We denote the _angle_ of the polar form $\varphi$ by
$\operatorname{arg}(a+b\mathrm{i})$. We also denote
$\operatorname{Re}(a+b\mathrm{i})=a$ and $\operatorname{Im}(a+b\mathrm{i})=b$.
It is worth highlighting that commonly the polar form is defined for a
positive real $r$ and an angle between $[0,2\pi)$. These two definitions are
obviously equivalent.

The _identity matrix_ is denoted by $\bm{I}_{n}$ or, if the dimension $n$ is
clear from the context, by $\bm{I}$. The _Heisenberg group_ H$(n,\mathbb{K})$
is formed by $n\times n$ matrices of the form
$M=\begin{pmatrix}1&\bm{m}_{1}^{T}&m_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{m_{2}}\\\
0&\bm{0}^{T}&1\end{pmatrix}$, where
$\bm{m}_{1},\bm{m}_{2}\in\mathbb{K}^{n-2}$, $m_{3}\in\mathbb{K}$ and
$\bm{0}=(0,0,\ldots,0)^{T}\in\mathbb{Q}(\mathrm{i})^{n-2}$ is the zero vector.
It is easy to see that the Heisenberg group is a non-commutative subgroup of
${\rm SL}(n,\mathbb{K})=\\{M\in\mathbb{K}^{n\times n}\mid\det(M)=1\\}$.

We will be interested in subsemigroups of H$(n,\mathbb{Q}(\mathrm{i}))$ which
are finitely generated. Given a set of matrices
$G=\\{G_{1},\ldots,G_{t}\\}\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$, we
denote the matrix semigroup generated by $G$ as $\langle G\rangle$.

Let $M=\begin{pmatrix}1&\bm{m}_{1}^{T}&m_{3}\\\
\bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\ 0&\bm{0}^{T}&1\end{pmatrix}$, then
$(M)_{1,n}=m_{3}$ is the top right element. To improve readability, by
$\psi(M)$ we denote the triple
$(\bm{m}_{1},\bm{m}_{2},m_{3})\in\mathbb{Q}(\mathrm{i})^{2n-3}$.

The vectors $\bm{m}_{1},\bm{m}_{2}$ play a crucial role in our considerations.
We define the set $\Omega\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ as those
matrices where $\bm{m}_{1}$ and $\bm{m}_{2}$ are zero vectors, i.e., matrices
in $\Omega$ look like $\bm{I}_{n}$ except allowing any element of
$\mathbb{Q}(\mathrm{i})$ in the top right element. That is,
$\Omega=\left\\{\begin{pmatrix}1&\bm{0}^{T}&m_{3}\\\
\bm{0}&\bm{I}_{n-2}&\bm{0}\\\ 0&\bm{0}^{T}&1\end{pmatrix}\mid
m_{3}\in\mathbb{Q}(\mathrm{i})\right\\}$, where
$\bm{0}=(0,0,\ldots,0)^{T}\in\mathbb{Q}(\mathrm{i})^{n-2}$ is the zero vector.

Let us define a shuffling of a product of matrices. Let $M_{1},\ldots,M_{k}\in
G$. The set of permutations of a product of these matrices is denoted by
$\textsf{shuffle}(M_{1},\ldots,M_{k})=\\{M_{\sigma(1)}\cdots
M_{\sigma(k)}\mid\sigma\in\mathcal{S}_{k}\\}$, where $\mathcal{S}_{k}$ is the
set of permutations on $k$ elements. If some matrix appears multiple times in
the list, say $M_{1}$ appears $x$ times, we write
$\mathsf{shuffle}(M_{1}^{x},M_{2},\ldots,M_{k})$ instead of
$\mathsf{shuffle}(\underbrace{M_{1},\ldots,M_{1}}_{x\text{
times}},M_{2},\ldots,M_{k})$. We further extend this notion and for a matrix
$M=M_{1}M_{2}\cdots M_{k}\in\langle G\rangle$,
$\mathsf{shuffle}(M)=\mathsf{shuffle}(M_{1}M_{2}\cdots M_{k})$ and
$\mathsf{shuffle}(M_{1},M_{2},\ldots,M_{k})$ denote the same set.

Let $M_{1}=\begin{pmatrix}1&\bm{a}_{1}^{T}&c_{1}\\\
\bm{0}&\bm{I}_{n-2}&\bm{b}_{1}\\\ 0&\bm{0}^{T}&1\end{pmatrix}$ and
$M_{2}=\begin{pmatrix}1&\bm{a}_{2}^{T}&c_{2}\\\
\bm{0}&\bm{I}_{n-2}&\bm{b}_{2}\\\ 0&\bm{0}^{T}&1\end{pmatrix}$. By an abuse of
notation, we define the _commutator_ $[M_{1},M_{2}]$ of $M_{1}$ and $M_{2}$ by
$[M_{1},M_{2}]=\bm{a}_{1}^{T}\bm{b}_{2}-\bm{a}_{2}^{T}\bm{b}_{1}\in\mathbb{Q}(\mathrm{i})$.
Note that the commutator of two arbitrary matrices $A,B$ is ordinarily defined
as $[A,B]=AB-BA$, i.e., a matrix. However, for matrices $M_{1},M_{2}\in{\rm
H}(n,\mathbb{Q}(\mathrm{i}))$, it is clear that
$M_{1}M_{2}-M_{2}M_{1}=\begin{pmatrix}0&\bm{0}^{T}&\bm{a}_{1}^{T}\bm{b}_{2}-\bm{a}_{2}^{T}\bm{b}_{1}\\\
\bm{0}&O&\bm{0}\\\ 0&\bm{0}^{T}&0\end{pmatrix}$, where $O$ is the
$(n-2)\times(n-2)$ zero matrix, thus justifying our notation which will be
used extensively. Observe that the matrices $M_{1},M_{2}$ commute if and only
if $[M_{1},M_{2}]=0$.

Note that the commutator is antisymmetric, i.e.,
$[M_{1},M_{2}]=-[M_{2},M_{1}]$. We further say that $\gamma$ is the _angle of
the commutator_ if $[M_{1},M_{2}]=r\exp(\mathrm{i}\gamma)$ for some
$r\in\mathbb{R}$ and $\gamma\in[0,\pi)$. If two commutators $[M_{1},M_{2}]$,
$[M_{3},M_{4}]$ have the same angles, that is,
$[M_{1},M_{2}]=r\exp(\mathrm{i}\gamma)$ and
$[M_{3},M_{4}]=r^{\prime}\exp(\mathrm{i}\gamma)$ for some
$r,r^{\prime}\in\mathbb{R}$, then we denote this property by
$[M_{1},M_{2}]\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{3},M_{4}]$.
If they have different angles, then we write
$[M_{1},M_{2}]\not\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{3},M_{4}]$.
By convention, if $[M_{1},M_{2}]=0$, then
$[M_{1},M_{2}]\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{3},M_{4}]$
for every $M_{3},M_{4}\in{\rm H}(n,\mathbb{Q}(\mathrm{i}))$.

To show that our algorithms run in polynomial time, we will need the following
lemma.

###### Lemma 1

  1. (i)

Let $A\in\mathbb{Q}^{n\times m}$ be a rational matrix, and
$\bm{b}\in\mathbb{Q}^{n}$ be an $n$-dimensional rational vector with non-
negative coefficients. Then we can decide in polynomial time whether the
system of inequalities $A\bm{x}\geq\bm{b}$ has an integer solution
$\bm{x}\in\mathbb{Z}^{m}$.

  2. (ii)

Let $A_{1}\in\mathbb{Q}^{n_{1}\times m}$ and $A_{2}\in\mathbb{Q}^{n_{2}\times
m}$ be a rational matrices. Then we can decide in polynomial time whether the
system of inequalities $A_{1}\bm{x}\geq\bm{0}^{n_{1}}$ and
$A_{2}\bm{x}>\bm{0}^{n_{2}}$ has an integer solution
$\bm{x}\in\mathbb{Z}^{m}$.

###### Proof

_(i)_ We will show that the system $A\bm{x}\geq\bm{b}$ has an integer solution
$\bm{x}\in\mathbb{Z}^{m}$ if and only if it has a rational solution
$\bm{x}\in\mathbb{Q}^{m}$. One direction is obvious. So, suppose there is a
rational vector $\bm{x}\in\mathbb{Q}^{m}$ such that $A\bm{x}\geq\bm{b}$. Let
$r\geq 1$ be the least common multiple of the denominators of all the
coefficients of $\bm{x}$. Let $\bm{x^{\prime}}=r\bm{x}\in\mathbb{Z}^{m}$.
Hence we have

$A\bm{x^{\prime}}=A(r\bm{x})=r(A\bm{x})\geq r\bm{b}\geq\bm{b},$

where the last two inequalities hold because $\bm{b}$ has non-negative
coefficients and $r\geq 1$. The finish the proof, note that we can decide in
polynomial time whether a system of linear inequalities has a rational
solution using linear programming, see [30].

_(ii)_ Since the system of inequalities is homogeneous, we can assume without
loss of generality that matrices $A_{1}$, $A_{2}$ have integer coefficients.
Hence the condition $A_{2}\bm{x}>\bm{0}^{n_{2}}$ is equivalent to
$A_{2}\bm{x}\geq\bm{1}^{n_{2}}$ for any integer vector
$\bm{x}\in\mathbb{Z}^{m}$, where $\bm{1}^{n_{2}}$ is a vector of dimension
$n_{2}$ with coordinates $1$. By the first part, we can decide in polynomial
time whether the system of inequalities $A_{1}\bm{x}\geq\bm{0}^{n_{1}}$ and
$A_{2}\bm{x}\geq\bm{1}^{n_{2}}$ has an integer solution
$\bm{x}\in\mathbb{Z}^{m}$. ∎

##  4 Properties of $\Omega$-matrices

To solve the Identity Problem for subsemigroups of ${\rm
H}(n,\mathbb{Q}(\mathrm{i}))$ (Problem 1), we will be analysing matrices in
$\Omega$ (matrices with all zero elements, except possibly the top-right
corner value). Let us first discuss how to construct $\Omega$-matrices from a
given set of generators $G\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$.

As observed earlier, when multiplying Heisenberg matrices of the form
$\begin{pmatrix}1&\bm{m}_{1}^{T}&m_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\
0&\bm{0}^{T}&1\end{pmatrix}$, elements $\bm{m}_{1}$ and $\bm{m}_{2}$ are
_additive_. We can thus construct a homogeneous system of linear Diophantine
equations (SLDEs) induced by matrices in $G$. Each $\Omega$-matrix then
corresponds to a solution to this system.

Let $G=\\{G_{1},\ldots,G_{t}\\}$, where
$\psi(G_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$. For a vector
$\bm{a}\in\mathbb{Q}(\mathrm{i})^{n-2}$, define
$\operatorname{Re}(\bm{a})=(\operatorname{Re}(\bm{a}(1)),\ldots,\operatorname{Re}(\bm{a}(n-2))$
(similarly for $\operatorname{Im}(\bm{a})$). We consider system
$A\bm{x}=\bm{0}$, where

$A=\begin{pmatrix}\operatorname{Re}(\bm{a}_{1})&\operatorname{Re}(\bm{a}_{2})&\cdots&\operatorname{Re}(\bm{a}_{t})\\\
\operatorname{Im}(\bm{a}_{1})&\operatorname{Im}(\bm{a}_{2})&\cdots&\operatorname{Im}(\bm{a}_{t})\\\
\operatorname{Re}(\bm{b}_{1})&\operatorname{Re}(\bm{b}_{2})&\cdots&\operatorname{Re}(\bm{b}_{t})\\\
\operatorname{Im}(\bm{b}_{1})&\operatorname{Im}(\bm{b}_{2})&\cdots&\operatorname{Im}(\bm{b}_{t})\end{pmatrix},$
(1)

$\bm{x}\in\mathbb{N}^{t}$ and $\bm{0}$ is the $4(n-2)$-dimensional zero
vector; noting that $A\in\mathbb{Q}^{4(n-2)\times t}$. Let
$\mathcal{S}=\\{\bm{s}_{1},\ldots,\bm{s}_{p}\\}$ be the set of minimal
solutions to the system. Recall that elements of $\mathcal{S}$ are
irreducible. That is, a minimal solution cannot be written as a sum of two
nonzero solutions. The set $\mathcal{S}$ is always finite and constructable
[30].

A matrix $M_{i}\in G$ is _redundant_ if the $i$th component is 0 in every
minimal solution $\bm{s}\in\mathcal{S}$. Non-redundant matrices can be
recognized by checking whether a non-homogeneous SLDE has a solution. More
precisely, to check whether $M_{i}$ is non-redundant, we consider the system
$A\bm{x}=\bm{0}$ together with the constraint that $\bm{x}(i)\geq 1$, where
$\bm{x}(i)$ is the $i$th component of $\bm{x}$. Using 1, we can determine in
polynomial time whether such a system has an integer solution.

For the remainder of the paper, we assume that $G$ is the set of non-redundant
matrices. This implicitly assumes that for this $G$, the set
$\mathcal{S}\neq\emptyset$. Indeed, if there are no solutions to the
corresponding SLDEs, then all matrices are redundant. Hence $G=\emptyset$ and
$\bm{I}\not\in\langle G\rangle$ holds trivially.

Let $M_{1},\ldots,M_{k}\in G$ be such that $X=M_{1}\cdots M_{k}\in\Omega$. The
Parikh vector of occurrences of each matrix from $G$ in product $X$ may be
written as $\bm{x}=(m_{1},\ldots,m_{t})\in\mathbb{N}^{t}$. This Parikh vector
$\bm{x}$ is a linear combination of elements of $\mathcal{S}$, i.e.,
$\bm{x}=\sum_{j=1}^{p}y_{j}\bm{s}_{j}$, with $y_{j}\in\mathbb{N}$, because
$\bm{x}$ is a solution to the SLDEs. Each element of
$\mathsf{shuffle}(M_{1},\ldots,M_{k})$ has the same Parikh vector, but their
product is not necessarily the same matrix; potentially differing in the top
right element.

Let us state some properties of $\Omega$-matrices.

###### Lemma 2

The $\Omega$-matrices are closed under matrix product; the top right element
is additive under the product of two matrices; and $\Omega$-matrices commute
with Heisenberg matrices. In other words, let $A,B\in\Omega$ and $M\in{\rm
H}(n,\mathbb{Q}(\mathrm{i}))$, then

  1. (i)

$AB\in\Omega$;

  2. (ii)

$(AB)_{1,n}=A_{1,n}+B_{1,n}$;

  3. (iii)

$AM=MA$.

Furthermore, if $N=M_{1}M_{2}\cdots M_{k-1}M_{k}\in\Omega$ for some
$M_{1},\ldots,M_{k}\in{\rm H}(n,\mathbb{Q}(\mathrm{i}))$, then every cyclic
permutation of matrices results in $N$. That is,

$N=M_{2}M_{3}\cdots M_{k}M_{1}=\cdots=M_{k}M_{1}\cdots M_{k-2}M_{k-1}$

###### Proof

The first three claims follow from the definition of $\Omega$-matrices. Let us
present the proofs for the sake of completeness. Let
$A=\begin{pmatrix}1&\bm{0}^{T}&a_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{0}\\\
0&\bm{0}^{T}&1\end{pmatrix}$ and $B=\begin{pmatrix}1&\bm{0}^{T}&b_{3}\\\
\bm{0}&\bm{I}_{n-2}&\bm{0}\\\ 0&\bm{0}^{T}&1\end{pmatrix}$. Now,
$AB=\begin{pmatrix}1&\bm{0}^{T}&a_{3}+b_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{0}\\\
0&\bm{0}&1\end{pmatrix}$ as was claimed in (i) and (ii). Let then
$M=\begin{pmatrix}1&\bm{m}_{1}^{T}&m_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\
0&\bm{0}^{T}&1\end{pmatrix}$. Now

$\displaystyle AM=\begin{pmatrix}1&\bm{m}_{1}^{T}&a_{3}+m_{3}\\\
\bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\ 0&\bm{0}^{T}&1\end{pmatrix}\text{ and
}MA=\begin{pmatrix}1&\bm{m}_{1}^{T}&m_{3}+a_{3}\\\
\bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\ 0&\bm{0}^{T}&1\end{pmatrix}.$

Let us proof the final claim. We will prove that $M_{1}M_{2}\cdots
M_{k-1}M_{k}=M_{2}M_{3}\cdots M_{k}M_{1}$. The other cyclic permutations are
proven analogously. Denote $\psi(M_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$ for
$i=1,\ldots,k$. Now by a direct computation,

$\displaystyle\psi(M_{1}M_{2}\cdots M_{k-1}M_{k})$
$\displaystyle=(\sum_{i=1}^{k}\bm{a}_{i},\sum_{i=1}^{k}\bm{b}_{i},\sum_{i=1}^{k}c_{i}+\sum_{1\leq
i<j\leq k}\bm{a}_{i}^{T}\bm{b}_{j})\text{ and}$
$\displaystyle\psi(M_{2}M_{3}\cdots M_{k}M_{1})$
$\displaystyle=(\sum_{i=1}^{k}\bm{a}_{i},\sum_{i=1}^{k}\bm{b}_{i},\sum_{i=1}^{k}c_{i}+\sum_{2\leq
i<j\leq k}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=2}^{k}\bm{a}_{i}^{T}\bm{b}_{1}).$

As the resulting matrices are in $\Omega$,
$\sum_{i=1}^{k}\bm{a}_{i}=\sum_{i=1}^{k}\bm{b}_{i}=\bm{0}$. Hence, we only
need to prove that the third components are equal. Observe that
$-\bm{a}_{1}=\sum_{i=2}^{k}\bm{a}_{i}$ and
$\bm{b}_{1}=-\sum_{i=2}^{k}\bm{b}_{i}$. Now

$\sum_{i=2}^{k}(\bm{a}_{i}^{T}\cdot\bm{b}_{1})=(\sum_{i=2}^{k}\bm{a}_{i}^{T})\cdot\bm{b}_{1}=(-\bm{a}_{1}^{T})\cdot(-\sum_{i=2}^{k}\bm{b}_{i})=\sum_{i=2}^{k}(\bm{a}_{1}^{T}\cdot\bm{b}_{i}).$

This allows us to rewrite $\sum_{2\leq i<j\leq
k}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=2}^{k}\bm{a}_{i}^{T}\bm{b}_{1}$ as

$\sum_{2\leq i<j\leq
k}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=2}^{k}\bm{a}_{1}^{T}\bm{b}_{i}=\sum_{1\leq
i<j\leq k}\bm{a}_{i}^{T}\bm{b}_{j},$

which is the third component of the first product. ∎

We require the following technical lemma that allows us to calculate the value
in top right corner for particular products. The claim is proven by a direct
computation.

###### Lemma 3

Let $M_{1},M_{2},\ldots,M_{k}\in{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ such that
$M_{1}M_{2}\cdots\ M_{k}\in\Omega$ and let $\ell\geq 1$. Then,
$(M_{1}^{\ell}M_{2}^{\ell}\cdots\
M_{k}^{\ell})_{1,n}=\ell\sum_{i=1}^{k}\left(c_{i}-\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}\right)+\frac{\ell^{2}}{2}\sum_{1\leq
i<j\leq k-1}[M_{i},M_{j}],$ where $\psi(M_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$
for each $i=1,\ldots,k$.

###### Proof

Denote $\psi(M_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$. A direct calculation shows
that the element in the top right corner is

$\sum_{i=1}^{k}\ell
c_{i}+\sum_{i=1}^{k}\frac{\ell(\ell-1)}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\ell^{2}\sum_{1\leq
i<j\leq k}\bm{a}_{i}^{T}\bm{b}_{j}.$

That is, the coefficient of $\ell$ is already in the desired form. Let us
rewrite the coefficient of $\ell^{2}$ as follows:

$\displaystyle\sum_{i=1}^{k-1}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\frac{1}{2}\bm{a}_{k}^{T}\bm{b}_{k}+\sum_{1\leq
i<j\leq k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=1}^{k-1}\bm{a}_{i}^{T}\bm{b}_{k}$
$\displaystyle=\sum_{i=1}^{k-1}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\sum_{1\leq
i<j\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=1}^{k-1}\bm{a}_{i}^{T}\bm{b}_{k}+\bm{a}_{k}^{T}\bm{b}_{k}-\frac{1}{2}\bm{a}_{k}^{T}\bm{b}_{k}$
$\displaystyle=\sum_{i=1}^{k-1}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\sum_{1\leq
i<j\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=1}^{k}\bm{a}_{i}^{T}\bm{b}_{k}-\frac{1}{2}\bm{a}_{k}^{T}\bm{b}_{k}$
$\displaystyle=\sum_{i=1}^{k-1}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\sum_{1\leq
i<j\leq k-1}\bm{a}_{i}^{T}\bm{b}_{j}-\frac{1}{2}\bm{a}_{k}^{T}\bm{b}_{k},$

where the first equality was obtained by taking terms with subindex $k$ out of
the sums, the second by adding
$\frac{1}{2}\bm{a}_{k}^{T}\bm{b}_{k}-\frac{1}{2}\bm{a}_{k}^{T}\bm{b}_{k}$, and
the final two by observing that $\sum_{i=1}^{k}\bm{a}_{i}=\bm{0}$. Now,
$\bm{a}_{k}^{T}\bm{b}_{k}$ can be rewritten as

$\bm{a}_{k}^{T}\bm{b}_{k}=\left(\sum_{i=1}^{k-1}\bm{a}_{i}\right)^{T}\cdot\sum_{j=1}^{k-1}\bm{b}_{j}=\sum_{1\leq
i<j\leq k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{1\leq j<i\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=1}^{k-1}\bm{a}_{i}^{T}\bm{b}_{i}.$

Combining this with the previous equation, we finally obtain that the
coefficient of $\ell^{2}$ is

$\displaystyle\sum_{i=1}^{k-1}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\sum_{1\leq
i<j\leq k-1}\bm{a}_{i}^{T}\bm{b}_{j}-\frac{1}{2}\left(\sum_{1\leq i<j\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{1\leq j<i\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{i=1}^{k-1}\bm{a}_{i}^{T}\bm{b}_{i}\right)$
$\displaystyle=\frac{1}{2}\left(\sum_{1\leq i<j\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}-\sum_{1\leq j<i\leq
k-1}\bm{a}_{i}^{T}\bm{b}_{j}\right)$ $\displaystyle=\frac{1}{2}\sum_{1\leq
i<j\leq k-1}[M_{i},M_{j}].$

Thus completing the proof. ∎

If we further assume that the matrices from the previous lemma commute, then
for every
$M\in\mathsf{shuffle}(M_{1}^{\ell},M_{2}^{\ell},\ldots,M_{k}^{\ell})$:

$M_{1,n}=\ell\sum_{i=1}^{k}\left(c_{i}-\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}\right)+\frac{\ell^{2}}{2}\sum_{1\leq
i<j\leq
k-1}[M_{i},M_{j}]=\ell\sum_{i=1}^{k}\left(c_{i}-\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}\right),$
(2)

noting that $[M_{i},M_{j}]=0$ when matrices $M_{i}$ and $M_{j}$ commute.

In Lemma 3, the matrix product has an ordering which yielded a simple
presentation of the value in the top right corner. In the next lemma, we
consider an arbitrary shuffle of the product and show that the commutators are
important when expressing the top right corner element.

###### Lemma 4

Let $M_{1},M_{2},\ldots,M_{k}\in{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ such that
$M_{1}M_{2}\cdots\ M_{k}\in\Omega$ and let $\ell\geq 1$. Let $M$ be a shuffle
of the product $M_{1}^{\ell}M_{2}^{\ell}\cdots M_{k}^{\ell}$ by a permutation
$\sigma$ that acts on $k\ell$ elements. Then

$(M)_{1,n}=\ell\sum_{i=1}^{k}\left(c_{i}-\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}\right)+\frac{\ell^{2}}{2}\sum_{1\leq
i<j\leq k-1}[M_{i},M_{j}]-\sum_{1\leq i<j\leq k}z_{ji}[M_{i},M_{j}],$

where $\psi(M_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$ for $i=1,\ldots,k$, and
$z_{ji}$ is the number of times $M_{j}$ appears before $M_{i}$ in the product;
so $z_{ji}$ is the number of inversions of $i,j$ in $\sigma$.

###### Proof

As in 3, we proceed by a direct calculation. Denote
$\psi(M_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$. First, let us denote by $z_{ij}$
the number of times matrix $M_{i}$ is to the left of matrix $M_{j}$ in $M$.
Note, that $z_{ij}+z_{ji}=\ell^{2}$ as there are in total $\ell^{2}$
multiplications of $M_{i}$ and $M_{j}$. Now, the direct calculation of the top
right element in $M$ is

$\sum_{i=1}^{k}\ell
c_{i}+\sum_{i=1}^{k}\frac{\ell(\ell-1)}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\sum_{1\leq
i<j\leq k}z_{ij}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{1\leq j<i\leq
k}z_{ij}\bm{a}_{i}^{T}\bm{b}_{j}.$

As in the proof of 3, the $\ell$ terms are as in the claim. Let us focus on
the $\ell^{2}$ term. We add $\sum_{1\leq i<j\leq
k}z_{ji}\bm{a}_{i}^{T}\bm{b}_{j}-\sum_{1\leq i<j\leq
k}z_{ji}\bm{a}_{i}^{T}\bm{b}_{j}=0$ to the term, resulting in

$\displaystyle\ell^{2}\sum_{i=1}^{k}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\sum_{1\leq
i<j\leq k}z_{ij}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{1\leq j<i\leq
k}z_{ij}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{1\leq i<j\leq
k}z_{ji}\bm{a}_{i}^{T}\bm{b}_{j}-\sum_{1\leq i<j\leq
k}z_{ji}\bm{a}_{i}^{T}\bm{b}_{j}$
$\displaystyle=\ell^{2}\sum_{i=1}^{k}\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i}+\ell^{2}\sum_{1\leq
i<j\leq k}\bm{a}_{i}^{T}\bm{b}_{j}+\sum_{1\leq j<i\leq
k}z_{ij}(\bm{a}_{i}^{T}\bm{b}_{j}-\bm{a}_{j}^{T}\bm{b}_{i})$
$\displaystyle=\frac{\ell^{2}}{2}\sum_{1\leq i<j\leq
k-1}[M_{i},M_{j}]-\sum_{1\leq i<j\leq k}z_{ji}[M_{i},M_{j}].$

In the above equation the first equality follows from the fact that
$z_{ij}+z_{ji}=\ell^{2}$ and the second equality can be obtained via analogous
calculation as in the proof of 3. ∎

The crucial observation is that regardless of the shuffle, the top right
corner element has a common term, namely
$\sum_{i=1}^{k}(c_{i}-\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i})$, plus some linear
combination of commutators. We call the common term the _shuffle invariant_.
Note that the previous lemmas apply to any Heisenberg matrices, even those in
${\rm H}(n,\mathbb{C})$. For the remainder of the section, we restrict
considerations to matrices in $G$.

######  Definition 1 (Shuffle Invariant)

Let $M_{1},\ldots,M_{k}\in G$ be such that $X=M_{1}\cdots\ M_{k}\in\Omega$.
The Parikh vector of occurrences of each matrix from $G$ in product $X$ may be
written as $\bm{x}=(m_{1},\ldots,m_{t})\in\mathbb{N}^{t}$ where $t=|G|$ as
before. Define
$\Lambda_{\bm{x}}=\sum_{i=1}^{t}m_{i}(c_{i}-\frac{1}{2}\bm{a}_{i}^{T}\bm{b}_{i})$
as the shuffle invariant of Parikh vector $\bm{x}$.

Note that the shuffle invariant is dependant only on the generators used in
the product and the Parikh vector $\bm{x}$.

Let $\mathcal{S}=\\{\bm{s}_{1},\ldots,\bm{s}_{p}\\}\subseteq\mathbb{N}^{k}$ be
the set of minimal solutions to the system of linear Diophantine equations for
$G$ giving an $\Omega$-matrix, as described in the beginning of the section.
Each $\bm{s}_{j}$ thus induces a shuffle invariant that we denote
$\Lambda_{\bm{s}_{j}}\in\mathbb{Q}(\mathrm{i})$ as shown in Definition 1. The
Parikh vector of any $X=M_{1}M_{2}\cdots\ M_{k}$ with $X\in\Omega$, denoted
$\bm{x}$, is a linear combination of elements of $\mathcal{S}$, i.e.,
$\bm{x}=\sum_{j=1}^{p}y_{j}\bm{s}_{j}$. We then note that the shuffle
invariant $\Lambda_{\bm{x}}$ of $\bm{x}$ is
$\Lambda_{\bm{x}}=\sum_{j=1}^{p}y_{j}\Lambda_{\bm{s}_{j}}$, i.e., a linear
combination of shuffle invariants of $\mathcal{S}$.

Finally, it follows from Lemma 4 that for any
$X\in\mathsf{shuffle}(M_{1},M_{2},\ldots,M_{k})$, where as before
$M_{1}M_{2}\cdots M_{k}\in\Omega$ and whose Parikh vector is
$\bm{x}=\sum_{j=1}^{p}y_{j}\bm{s}_{j}$, the top right entry of $X$ is equal to

$\displaystyle X_{1,n}$ $\displaystyle=$
$\displaystyle\Lambda_{\bm{x}}+\sum_{1\leq i<j\leq k}\alpha_{ij}[M_{i},M_{j}]\
=\ \sum_{j=1}^{p}y_{j}\Lambda_{\bm{s}_{j}}+\sum_{1\leq i<j\leq
k}\alpha_{ij}[M_{i},M_{j}],$ (3)

where each $\alpha_{ij}\in\mathbb{Q}$ depends on the shuffle.

Furthermore, if a product of Heisenberg matrices is an $\Omega$-matrix and all
matrix pairs share a common angle $\gamma$ for their commutators, then
shuffling the matrix product only modifies the top right element of the matrix
by a real multiple of $\exp(\mathrm{i}\gamma)$. This drastically simplifies
our later analysis.

##  5 The Identity Problem for subsemigroups of ${\rm
H}(n,\mathbb{Q}(\mathrm{i}))$

In this section, we prove our main result.

###### Theorem 5.1

Let $G\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ be a finite set of matrices.
Then it is decidable in polynomial time if $\bm{I}\in\langle G\rangle$.

The proof relies on analysing generators used in a product that results in an
$\Omega$-matrix. There are two distinct cases to consider: either there is a
pair of commutators with distinct angles, or else all commutators have the
same angle. The former case is considered in 5 and the latter in 6. More
precisely, we will prove that in the former case, the identity matrix is
always in the generated semigroup and that the latter case reduces to deciding
whether shuffle invariants reach the line defined by the angle of the
commutator.

The two cases are illustrated in Figure 1. On the left, is a depiction of the
case where there are at least two commutators with different angles,
$\gamma_{1}$ and $\gamma_{2}$. We will construct a sequence of products where
the top right element tends to $r_{1}\exp(\mathrm{i}\gamma_{1})$ with positive
$r_{1}$ and another product that tends to $r_{2}\exp(\mathrm{i}\gamma_{1})$
with negative $r_{2}$. This is achieved by changing the order of matrices
whose commutator has angle $\gamma_{1}$. Similarly, we construct two sequences
of products where the top right elements tend to
$r_{3}\exp(\mathrm{i}\gamma_{2})$ and $r_{4}\exp(\mathrm{i}\gamma_{2})$, where
$r_{3}$ and $r_{4}$ have the opposite signs. Together these sequences ensure,
that eventually, the top right elements do not lie in the same open half-
planes. On the right, is a depiction of the other case, where all commutators
lie on $\gamma$-line. In this case, the shuffle invariants of products need to
be used to reach the line.

$\operatorname{Im}$$\operatorname{Re}$$\gamma$$\gamma+\Lambda_{1}$$\gamma+2\Lambda_{1}$$\Lambda_{1}$$\Lambda_{2}$$\Lambda_{1}+\Lambda_{2}$$r_{1}$$r_{2}$$r_{3}$$H_{1}$$H_{2}$$\operatorname{Im}$$\operatorname{Re}$$\gamma_{1}$$\gamma_{2}$$r_{1,1}$$r_{1,2}$$r_{1,3}$$r_{2,1}$$r_{2,2}$$r_{2,3}$$r_{3,1}$$r_{3,2}$$r_{3,3}$

Figure 1:  Illustrations of 5 and 6. Left shows two lines defined by two
different commutators and how the values $r_{1,\ell}$ and $r_{2,\ell}$ tend to
$\gamma_{1}$-line in opposite directions, while $r_{3,\ell}$ tends to
$\gamma_{2}$-line ($r_{4,\ell}$ is omitted for clarity). Eventually, they are
not all within the same closed half-plane. Right shows that if there is only
one shuffle invariant, say $\Lambda_{1}$, then all reachable values are on
lines parallel to the $\gamma$-line, namely, $\gamma+k\Lambda_{1}$ for $k>0$.
But if there exists $\Lambda_{2}$ in the opposite half-plane, then the
$\gamma$-line itself is reachable.

###### Lemma 5

Let $G=\\{G_{1},\ldots,G_{t}\\}\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$,
where each $G_{i}$ is non-redundant. Suppose there exist
$M_{1},M_{2},M_{3},M_{4}\in G$ such that
$[M_{1},M_{2}]\not\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{3},M_{4}]$.
Then $\bm{I}\in\langle G\rangle$.

###### Proof

Since all $M_{i}$’s are non-redundant, there exists a product
$M_{1}M_{2}M_{3}M_{4}\cdots M_{k}\in\Omega$, where $k\geq 4$ and every $M_{i}$
is in $G$. We prove the lemma by considering four products
$M_{1}^{\ell}M_{2}^{\ell}(M_{3}M_{4}X)^{\ell}$,
$M_{2}^{\ell}M_{1}^{\ell}(M_{3}M_{4}X)^{\ell}$,
$M_{3}^{\ell}M_{4}^{\ell}(M_{1}M_{2}X)^{\ell}$ and
$M_{4}^{\ell}M_{3}^{\ell}(M_{1}M_{2}X)^{\ell}$, where
$X=\prod_{i=5}^{k}M_{i}$. Denote
$\psi(M_{i})=\left(\bm{a}_{i},\bm{b}_{i},c_{i}\right)$ for $i=1,\ldots,4$ and
$\psi(X)=\left(\bm{x}_{1},\bm{x}_{2},x_{3}\right)$.

Note that our assumption on the matrices $M_{1},M_{2},M_{3},M_{4}$ implies
that there are at least four distinct matrices in the product
$M_{1}M_{2}\cdots\ M_{k}\in\Omega$ justifying the above notation. Indeed, if
there were at most three, the assumption would not hold. Assume that $X$
defined as above is the empty product and $M_{i}=M_{j}$ for some $i,j=1,2,3,4$
and $i\neq j$. For the sake of clarity, we will assume that $i=1$ and $j=3$.
The other cases are analogous. Now,
$[M_{1},M_{2}]=\bm{a}_{1}^{T}\bm{b}_{2}-\bm{a}_{2}^{T}\bm{b}_{1}$ and
$[M_{1},M_{4}]=\bm{a}_{1}^{T}\bm{b}_{4}-\bm{a}_{4}^{T}\bm{b}_{1}$, and since
$M_{1}M_{2}M_{1}M_{4}\in\Omega$, we also have
$2\bm{a}_{1}+\bm{a}_{2}+\bm{a}_{4}=\bm{0}$ and
$2\bm{b}_{1}+\bm{b}_{2}+\bm{b}_{4}=\bm{0}$. That is, now

$[M_{1},M_{4}]=\bm{a}_{1}^{T}\bm{b}_{4}-\bm{a}_{4}^{T}\bm{b}_{1}=-\bm{a}_{1}^{T}(2\bm{b}_{1}+\bm{b}_{2})+(2{\bm{a}_{1}+\bm{a}_{2}})^{T}\bm{b}_{1}=\bm{a}_{2}^{T}\bm{b}_{1}-\bm{a}_{1}^{T}\bm{b}_{2}=-[M_{1},M_{2}],$

which implies
$[M_{1},M_{4}]\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{1},M_{2}]$
contrary to our assumption.

Let $\gamma_{1}$ and $\gamma_{2}$ be the angles of $[M_{1},M_{2}]$ and
$[M_{3},M_{4}]$, respectively, where $\gamma_{1}\neq\gamma_{2}$ by assumption.
We show that, in the limit as $\ell$ tends to infinity, the angles of the top-
right entries in the first two products tend to $\gamma_{1}$, but they
approach $\gamma_{1}$-line (that is, the line defined by the vector
$r\exp(\mathrm{i}\gamma_{1})$, where $r$ is a positive real number) from
opposite direction, i.e., one approaches $r\exp(\mathrm{i}\gamma_{1})$ and the
other $-r\exp(\mathrm{i}\gamma_{1})$. The same holds for the last two products
and the angle $\gamma_{2}$. See the left half of Figure 1 for illustration.

Let us consider the product $M_{1}^{\ell}M_{2}^{\ell}(M_{3}M_{4}X)^{\ell}$ for
some $\ell\in\mathbb{N}$. By 3,

$(M_{1}^{\ell}M_{2}^{\ell}(M_{3}M_{4}X)^{\ell})_{1,n}=\\\
\ell\left(\sum_{i=1}^{4}c_{i}+x_{3}-\frac{1}{2}(\bm{a}_{1}^{T}\bm{b}_{1}+\bm{a}_{2}^{T}\bm{b}_{2}+(\bm{a}_{3}+\bm{a}_{4}+\bm{x}_{1})^{T}(\bm{b}_{3}+\bm{b}_{4}+\bm{x}_{2})\right)+\frac{\ell^{2}}{2}[M_{1},M_{2}].$

That is, the coefficient of $\ell^{2}$ is $\frac{1}{2}[M_{1},M_{2}]$.
Similarly by 3, the coefficients of $\ell^{2}$ in the top right elements of
$M_{2}^{\ell}M_{1}^{\ell}(M_{3}M_{4}X)^{\ell}$,
$M_{3}^{\ell}M_{4}^{\ell}(M_{1}M_{2}X)^{\ell}$ and
$M_{4}^{\ell}M_{3}^{\ell}(M_{1}M_{2}X)^{\ell}$ are $\frac{1}{2}[M_{2},M_{1}]$,
$\frac{1}{2}[M_{3},M_{4}]$, $\frac{1}{2}[M_{4},M_{3}]$, respectively. Let
$[M_{1},M_{2}]=r_{1}\exp(\mathrm{i}\gamma_{1})$,
$[M_{2},M_{1}]=r_{2}\exp(\mathrm{i}\gamma_{2})$,
$[M_{3},M_{4}]=r_{3}\exp(\mathrm{i}\gamma_{3})$, and
$[M_{4},M_{3}]=r_{4}\exp(\mathrm{i}\gamma_{4})$. It is convenient to consider
these complex numbers as two-dimensional vectors. Recall that commutator is
antisymmetric and hence $r_{1}=-r_{2}$, $\gamma_{1}=\gamma_{2}$ and
$r_{3}=-r_{4}$, $\gamma_{3}=\gamma_{4}$. By our assumption,
$[M_{1},M_{2}]\not\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{3},M_{4}]$
and thus $\gamma_{1}\neq\gamma_{3}$. It follows that the four vectors are not
contained in any _closed_ half-plane. Indeed,
$r_{1}\exp(\mathrm{i}\gamma_{1})$ and $-r_{1}\exp(\mathrm{i}\gamma_{1})$
define two closed half-planes, say $H_{1}$ and $H_{2}$. Any _closed_ half-
plane that contains both $r_{1}\exp(\mathrm{i}\gamma_{1})$ and
$-r_{1}\exp(\mathrm{i}\gamma_{1})$ must be equal to either $H_{1}$ or $H_{2}$.
As $r_{3}=-r_{4}$, either $r_{3}\exp(\mathrm{i}\gamma_{3})$ or
$-r_{3}\exp(\mathrm{i}\gamma_{3})$ is _not_ in that half-plane.

Let us express the top right elements as functions of power $\ell$:

$\displaystyle(M_{1}^{\ell}M_{2}^{\ell}(M_{3}M_{4}X)^{\ell})_{1,n}=r_{1,\ell}\exp(\mathrm{i}\gamma_{1,\ell}),$
$\displaystyle(M_{2}^{\ell}M_{1}^{\ell}(M_{3}M_{4}X)^{\ell})_{1,n}=r_{2,\ell}\exp(\mathrm{i}\gamma_{2,\ell}),$
$\displaystyle(M_{3}^{\ell}M_{4}^{\ell}(M_{1}M_{2}X)^{\ell})_{1,n}=r_{3,\ell}\exp(\mathrm{i}\gamma_{3,\ell}),$
$\displaystyle(M_{4}^{\ell}M_{3}^{\ell}(M_{1}M_{2}X)^{\ell})_{1,n}=r_{4,\ell}\exp(\mathrm{i}\gamma_{4,\ell}),$

where $r_{1,\ell},r_{2,\ell},r_{3,\ell},r_{4,\ell}\in\mathbb{R}$ and
$\gamma_{1,\ell},\gamma_{2,\ell},\gamma_{3,\ell},\gamma_{4,\ell}\in[0,\pi)$.

Since $r_{1}\exp(\mathrm{i}\gamma_{1})$, $r_{2}\exp(\mathrm{i}\gamma_{1})$,
$r_{3}\exp(\mathrm{i}\gamma_{3})$, and $r_{4}\exp(\mathrm{i}\gamma_{3})$ are
the coefficients that multiply $\frac{1}{2}\ell^{2}$ in the formula for the
top-right entry in the above products, and $\ell^{2}$ is the highest power
that appears there, we conclude that

$\lim_{\ell\to\infty}\gamma_{1,\ell}=\lim_{\ell\to\infty}\gamma_{2,\ell}=\gamma_{1}\qquad\text{and}\qquad\lim_{\ell\to\infty}\gamma_{3,\ell}=\lim_{\ell\to\infty}\gamma_{4,\ell}=\gamma_{3}.$

Moreover, for sufficiently large $\ell$, $r_{i,\ell}$ and $r_{i+1,\ell}$ have
opposite signs, where $i=1,3$.

Recall that $r_{1}\exp(\mathrm{i}\gamma_{1})$,
$r_{2}\exp(\mathrm{i}\gamma_{2})$, $r_{3}\exp(\mathrm{i}\gamma_{3})$, and
$r_{4}\exp(\mathrm{i}\gamma_{4})$ do not lie in the same closed half-plane. It
follows that, for sufficiently large $\ell$, the vectors
$r_{1,\ell}\exp(\mathrm{i}\gamma_{1,\ell})$,
$r_{2,\ell}\exp(\mathrm{i}\gamma_{2,\ell})$,
$r_{3,\ell}\exp(\mathrm{i}\gamma_{3,\ell})$, and
$r_{4,\ell}\exp(\mathrm{i}\gamma_{4,\ell})$ also do not lie in the same closed
half-plane. See the left half of Figure 1 for illustration.

Since they are not in the same closed half-plane, their positive linear
combinations span the whole plane $\mathbb{Q}(\mathrm{i})$. In particular, for
some $\ell\geq 1$ and some $x_{1},x_{2},x_{3},x_{4}\in\mathbb{N}$, not all of
which are zero, we have

$x_{1}r_{1,\ell}\exp(\mathrm{i}\gamma_{1,\ell})+x_{2}r_{2,\ell}\exp(\mathrm{i}\gamma_{2,\ell})+x_{3}r_{3,\ell}\exp(\mathrm{i}\gamma_{3,\ell})+x_{4}r_{4,\ell}\exp(\mathrm{i}\gamma_{4,\ell})=0.$

This implies that

$\left(M_{1}^{\ell}M_{2}^{\ell}(M_{3}M_{4}X)^{\ell}\right)^{x_{1}}\left(M_{2}^{\ell}M_{1}^{\ell}(M_{3}M_{4}X)^{\ell}\right)^{x_{2}}\left(M_{3}^{\ell}M_{4}^{\ell}(M_{1}M_{2}X)^{\ell}\right)^{x_{3}}\left(M_{4}^{\ell}M_{3}^{\ell}(M_{1}M_{2}X)^{\ell}\right)^{x_{4}}$

equals the identity matrix $\bm{I}$, finishing the proof. ∎

It remains to consider the case when the angles of commutators coincide for
each pair of non-redundant matrices. Our aim is to prove that, under this
condition, it is decidable whether the identity matrix is in the generated
semigroup.

###### Lemma 6

Let $G=\\{G_{1},\ldots,G_{t}\\}\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ be
a set of non-redundant matrices such that the angle of commutator
$[G_{i},G_{i^{\prime}}]$ is $\gamma$ for all $1\leq i,i^{\prime}\leq t$, then
we can determine in polynomial time if $\bm{I}\in\langle G\rangle$.

###### Proof

Let $\\{\bm{s}_{1},\ldots,\bm{s}_{p}\\}\subseteq\mathbb{N}^{t}$ be the set of
minimal solutions to the SLDEs for $G$ giving zeros in $\bm{a}$ and $\bm{b}$
elements. Each $\bm{s}_{j}$ induces a shuffle invariant
$\Lambda_{\bm{s}_{j}}\in\mathbb{Q}(\mathrm{i})$ as explained in Definition 1.

Consider a product $X=M_{1}\cdots M_{k}\in\Omega$, where each $M_{i}\in G$.
Let $\bm{x}=(m_{1},m_{2},\ldots,m_{t})\in\mathbb{N}^{t}$ be the Parikh vector
of the number of occurrences of each matrix from $G$ in product $X$. Since
$X\in\Omega$, we have $\bm{x}=\sum_{j=1}^{p}y_{j}\bm{s}_{j}$, where each
$y_{j}\in\mathbb{N}$. Notice that
$X\in\mathsf{shuffle}(G_{1}^{m_{1}},\ldots,G_{t}^{m_{t}})$. Hence, by Equation
(3), we have

$X_{1,n}=\Lambda_{\bm{x}}+\sum_{1\leq i<j\leq
k}\alpha_{ij}[M_{i},M_{j}]=\sum_{j=1}^{p}y_{j}\Lambda_{\bm{s}_{j}}+r\exp(\mathrm{i}\gamma),$
(4)

where $\alpha_{ij}\in\mathbb{Q}$ and $r\in\mathbb{R}$ depend on the shuffle.
In other words, any shuffle of the product $X$ will change the top right entry
$X_{1,n}$ by a real multiple of $\exp(\mathrm{i}\gamma)$.

Let $H_{1},H_{2}$ be the two _open_ half-planes of the complex plane induced
by $\exp(\mathrm{i}\gamma)$, that is, the union $H_{1}\cup H_{2}$ is the
complement of the $\gamma$-line; thus $0\not\in H_{1}\cup H_{2}$. We now prove
that if $\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}\subseteq
H_{1}$ or $\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}\subseteq
H_{2}$ then we cannot reach the identity matrix.

Assume that $\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}\subseteq
H_{1}$, renaming $H_{1},H_{2}$ if necessary. Assume that there exists some
product $X=X_{1}X_{2}\cdots X_{k}$ equal to the identity matrix, where $k>0$
and $X_{j}\in G$. Then since $X\in\Omega$, we see from Equation (4) that
$X_{1,n}=\sum_{j=1}^{p}y_{j}\Lambda_{\bm{s}_{j}}+r\exp(\mathrm{i}\gamma)$,
where $r\in\mathbb{R}$.

Clearly, $\sum_{j=1}^{p}y_{j}\Lambda_{\bm{s}_{j}}\in H_{1}$, and since
$y_{j}\neq 0$ for at least one $i$, we have
$\sum_{j=1}^{p}y_{j}\Lambda_{\bm{s}_{j}}\neq 0$. Now, since
$r\exp(\mathrm{i}\gamma)$ is on the $\gamma$-line, which is the boundary of
$H_{1}$, the value $X_{1,n}$ belongs to $H_{1}$ and cannot equal zero. This
contradicts the assumption that $X$ is the identity matrix.

If $\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}$ is not fully
contained in either $H_{1}$ or $H_{2}$, then there are two possibilities.
Either there exists some $\Lambda_{\bm{s}_{j}}\in\mathbb{Q}(\mathrm{i})$ such
that the angle of $\Lambda_{\bm{s}_{j}}$ is equal to $\gamma$ (in which case
such a $\Lambda_{\bm{s}_{j}}$ lies on the line defined by
$\exp(\mathrm{i}\gamma)$), or else there exist
$\Lambda_{\bm{s}_{i}},\Lambda_{\bm{s}_{j}}$ such that $1\leq i<j\leq p$ and
$\Lambda_{\bm{s}_{i}}$ and $\Lambda_{\bm{s}_{j}}$ lie in different open half-
planes, say $\Lambda_{\bm{s}_{i}}\in H_{1}$ and $\Lambda_{\bm{s}_{j}}\in
H_{2}$.

In the latter case, note that there exists $x,y\in\mathbb{N}$ such that
$x\Lambda_{\bm{s}_{i}}+y\Lambda_{\bm{s}_{j}}=r\exp(\mathrm{i}\gamma)$ for some
$r\in\mathbb{R}$ since $\Lambda_{\bm{s}_{i}},\Lambda_{\bm{s}_{j}}$ and the
commutators that define the $\gamma$-line have rational components. It means
that in both cases there exist $z_{1},\ldots,z_{p}\in\mathbb{N}$ such that
$\sum_{j=1}^{p}z_{j}\Lambda_{\bm{s}_{j}}=r\exp(\mathrm{i}\gamma)$ for some
$r\in\mathbb{R}$.

Consider a product $T=T_{1}\cdots T_{k}\in\Omega$, where each $T_{j}\in G$ and
whose Parikh vector is equal to $\sum_{j=1}^{p}z_{j}\bm{s}_{j}$, where
$z_{1},\ldots,z_{p}\in\mathbb{N}$ are as above. It follows from Equation (4)
that
$T_{1,n}=\sum_{j=1}^{p}z_{j}\Lambda_{\bm{s}_{j}}+r^{\prime}\exp(\mathrm{i}\gamma)=r\exp(\mathrm{i}\gamma)+r^{\prime}\exp(\mathrm{i}\gamma),$
where $r,r^{\prime}\in\mathbb{R}$ and shuffles of such a product change only
$r^{\prime}$.

We have two possibilities. Either $T=T_{1}\cdots T_{k}$ is a product only
consisting of commuting matrices from $G$, or else two of the matrices in the
product of $T$ do not commute. In the latter case, let us write
$T^{\prime}=N_{1}N_{2}X^{\prime}\in\mathsf{shuffle}(T_{1},\ldots,T_{k})$,
where $N_{1}\in G$ and $N_{2}\in G$ do not commute and $X^{\prime}$ is the
product of the remaining matrices in any order. We observe that Lemma 3
implies

$\displaystyle(N_{1}^{\ell_{1}}N_{2}^{\ell_{1}}X^{\prime\ell_{1}})_{1,n}$
$\displaystyle=\ell_{1}r\exp(\mathrm{i}\gamma)+\frac{\ell_{1}^{2}}{2}[N_{1},N_{2}]=\ell_{1}r\exp(\mathrm{i}\gamma)+\frac{\ell_{1}^{2}}{2}r^{\prime}\exp(\mathrm{i}\gamma)\quad\text{and}$
$\displaystyle(N_{2}^{\ell_{2}}N_{1}^{\ell_{2}}X^{\prime\ell_{2}})_{1,n}$
$\displaystyle=\ell_{2}r\exp(\mathrm{i}\gamma)+\frac{\ell_{2}^{2}}{2}[N_{2},N_{1}]=\ell_{2}r\exp(\mathrm{i}\gamma)-\frac{\ell_{2}^{2}}{2}r^{\prime}\exp(\mathrm{i}\gamma),$

for some $0\neq r^{\prime}\in\mathbb{R}$. We then notice that
$\left((N_{1}^{\ell_{1}}N_{2}^{\ell_{1}}X^{\prime\ell_{1}})^{d_{1}}(N_{2}^{\ell_{2}}N_{1}^{\ell_{2}}X^{\prime\ell_{2}})^{d_{2}}\right)_{1,n}=d_{1}\left(\ell_{1}r\exp(\mathrm{i}\gamma)+\frac{\ell_{1}^{2}}{2}r^{\prime}\exp(\mathrm{i}\gamma)\right)+d_{2}\left(\ell_{2}r\exp(\mathrm{i}\gamma)-\frac{\ell_{2}^{2}}{2}r^{\prime}\exp(\mathrm{i}\gamma)\right)$.
Now,

$\displaystyle
d_{1}\left(\ell_{1}r\exp(\mathrm{i}\gamma)+\frac{\ell_{1}^{2}}{2}r^{\prime}\exp(\mathrm{i}\gamma)\right)+d_{2}\left(\ell_{2}r\exp(\mathrm{i}\gamma)-\frac{\ell_{2}^{2}}{2}r^{\prime}\exp(\mathrm{i}\gamma)\right)$
$\displaystyle=0$ $\displaystyle\Longleftrightarrow
d_{1}(2\ell_{1}r+\ell_{1}^{2}r^{\prime})+d_{2}(2\ell_{2}r-\ell_{2}^{2}r^{\prime})$
$\displaystyle=0$ $\displaystyle\Longleftrightarrow
d_{1}(2\frac{r}{r^{\prime}}\ell_{1}+\ell_{1}^{2})+d_{2}(2\frac{r}{r^{\prime}}\ell_{2}-\ell_{2}^{2})$
$\displaystyle=0.$

By our assumption, the vectors $r\exp(\mathrm{i}\gamma)$ and
$r^{\prime}\exp(\mathrm{i}\gamma)$ have rational coordinates and the same
angle $\gamma$. It follows that $\frac{r}{r^{\prime}}\in\mathbb{Q}$. Hence we
may choose sufficiently large $\ell_{1},\ell_{2}>1$ such that
$2\frac{r}{r^{\prime}}\ell_{1}+\ell_{1}^{2}$ and
$2\frac{r}{r^{\prime}}\ell_{2}-\ell_{2}^{2}$ have different signs, and then
integers $d_{1},d_{2}>1$ can be chosen that satisfy the above equation. This
choice of $\ell_{1},\ell_{2},d_{1},d_{2}$ is then such that
$(N_{1}^{\ell_{1}}N_{2}^{\ell_{1}}X^{\prime\ell_{1}})^{d_{1}}(N_{2}^{\ell_{2}}N_{1}^{\ell_{2}}X^{\prime\ell_{2}})^{d_{2}}=\bm{I}$
as required. Thus if such non-commuting matrices are present, we can reach the
identity.

We now show how to decide in polynomial time whether the $\gamma$-line can be
reached by a pair of non-commuting matrices from $G$. We can compute a vector
$v$ with rational components that lies on the the $\gamma$-line in polynomial
time, e.g., it can be any non-zero commutator. We must now determine if there
exist a shuffle invariant that lies on the $\gamma$-line and which uses a pair
on non-commuting matrices. This may be determined by deciding the solvability
of a polynomially sized set of Non-homogeneous Systems of Linear Diophantine
Equations (NSLDEs), as explained below. We will show that determining if such
a NSLDE has a solution can be done in polynomial time, and therefore the above
property can be decided in $\P$. We now outline the process.

Let $v\in\mathbb{Q}(\mathrm{i})$ be a complex number on the $\gamma$-line with
rational components. We define its _vectorization_ as
$\textrm{vec}(v)=(\operatorname{Re}(v),\operatorname{Im}(v))$, i.e., splitting
into real and imaginary components. The value
$v^{\perp}\in\mathbb{Q}(\mathrm{i})$ whose vectorization
$\textrm{vec}(v^{\perp})$ is perpendicular to $\textrm{vec}(v)$ in the complex
plane is defined as $v^{\perp}=\exp(\frac{i\pi}{2})v$ noting that
$\textrm{vec}(v^{\perp})$ has rational components such that
$\textrm{vec}(v^{\perp})=(-\operatorname{Im}(v)),\operatorname{Re}(v))$. Now,
if all shuffle invariants are _not_ contained within $H_{1}$ (or else $H_{2}$)
then there exists two shuffle invariants, say
$\Lambda_{\bm{s}_{1}},\Lambda_{\bm{s}_{2}}\in\mathbb{Q}(\mathrm{i})$ such that
$\textrm{vec}(\Lambda_{\bm{s}_{1}})\cdot\textrm{vec}(v^{\perp})>0$ and
$\textrm{vec}(\Lambda_{\bm{s}_{2}})\cdot\textrm{vec}(v^{\perp})<0$, where
$\cdot$ denotes the dot product, or else there exists a shuffle invariant
$\Lambda_{\bm{s}_{3}}\in\mathbb{Q}(\mathrm{i})$ such that
$\textrm{vec}(\Lambda_{\bm{s}_{1}})\cdot\textrm{vec}(v^{\perp})=0$, thus
$\Lambda_{\bm{s}_{3}}$ is on the $\gamma$-line.

Recall that $G=\\{G_{1},\ldots,G_{t}\\}$ and define
$\bm{y}=(c_{1}-\frac{1}{2}\bm{a}_{1}^{T}\bm{b}_{1},\ldots,c_{t}-\frac{1}{2}\bm{a}_{t}^{T}\bm{b}_{t})\in\mathbb{Q}(\mathrm{i})^{t}$.
Consider the vector
$\bm{z}=\operatorname{Re}(v^{\perp})\operatorname{Re}(\bm{y})+\operatorname{Im}(v^{\perp})\operatorname{Im}(\bm{y})\in\mathbb{Q}^{t}$.
Now, let $\bm{x}$ be the Parikh vector of some product of matrices from $G$
that gives an $\Omega$-matrix. Then for $\bm{x}$ and its shuffle invariant
$\Lambda_{x}\in\mathbb{Q}(\mathrm{i})$, we have that
$\bm{z}^{T}\bm{x}=\textrm{vec}(\Lambda_{\bm{x}})\cdot\textrm{vec}(v^{\perp})$.

We will now derive a set of NSLDEs, to allow us to determine if it is possible
to find a product of matrices, not all of which commute, whose shuffle
invariant lies on the $\gamma$-line. We require a non-homogeneous system in
order to enforce that the solution is non-commuting.

We thus consider the following system of linear Diophantine equations
$A\bm{x}\geq\bm{b}$, which we will now define. We may assume that not all
matrices in generator set $G=\\{G_{1},\ldots,G_{t}\\}$ commute, since we will
deal with this subcase later. Let us therefore consider a pair of non-
commuting matrices $G_{i},G_{j}\in G$. In the construction of our NSLDE,
submatrices $A_{1}$ and $-A_{1}$ are used to enforce that $\bm{x}$ is the
Parikh vector of an $\Omega$-matrix $M_{\bm{x}}=M_{1}M_{2}\cdots M_{k}$,
submatrices $A_{2},-A_{2}$ are used to determine that the shuffle invariant
$\Lambda_{\bm{x}}$ is on the $\gamma$-line, and $A_{i,j}$ is used to ensure
that there exists two non-commuting matrices in the product $M_{1}M_{2}\cdots
M_{k}$, namely matrices $G_{i}$ and $G_{j}$. We will formulate such an NSLDE
for each pair of non-commuting matrices. Let us define
$T_{i,j}\bm{x}\geq\bm{b}$ for every pair of non-commuting matrices
$G_{i},G_{j}$ as follows:

$T_{i,j}=\begin{pmatrix}A_{1}\\\ -A_{1}\\\ A_{2}\\\ -A_{2}\\\
A_{i,j}\end{pmatrix},A_{1}=\begin{pmatrix}\operatorname{Re}(\bm{a}_{1})&\operatorname{Re}(\bm{a}_{2})&\cdots&\operatorname{Re}(\bm{a}_{t})\\\
\operatorname{Im}(\bm{a}_{1})&\operatorname{Im}(\bm{a}_{2})&\cdots&\operatorname{Im}(\bm{a}_{t})\\\
\operatorname{Re}(\bm{b}_{1})&\operatorname{Re}(\bm{b}_{2})&\cdots&\operatorname{Re}(\bm{b}_{t})\\\
\operatorname{Im}(\bm{b}_{1})&\operatorname{Im}(\bm{b}_{2})&\cdots&\operatorname{Im}(\bm{b}_{t})\\\
\end{pmatrix},A_{2}=\begin{pmatrix}\bm{z}(1)\\\ \bm{z}(2)\\\ \vdots\\\
\bm{z}(t)\end{pmatrix}^{T},A_{i,j}=\begin{pmatrix}\bm{e}_{i}^{T}\\\
\bm{e}_{j}^{T}\end{pmatrix},$ (5)

where $\bm{x}\in\mathbb{N}^{t}$,
$\bm{b}=(\bm{0}^{4(n-2)},\bm{0}^{4(n-2)},0,0,1,1)^{T}$; noting that
$T_{i,j}\in\mathbb{Q}^{(8(n-2)+4)\times t}$. Here,
$\bm{e}_{i}\in\\{0,1\\}^{t}$ denotes the $i$’th standard (column) basis
vector, i.e., the all zero vector except $\bm{e}_{i}(i)=1$, and similarly for
$\bm{e}_{j}$. A solution $\bm{x}\in\mathbb{N}^{t}$ to this NSLDE implies that
$A_{1}\bm{x}\geq\bm{0}^{4(n-2)}$ and $-A_{1}\bm{x}\geq\bm{0}^{4(n-2)}$, thus
$A_{1}\bm{x}=\bm{0}^{4(n-2)}$, and therefore $G_{1}^{\bm{x}(1)}\cdots
G_{t}^{\bm{x}(t)}\in\Omega$, which was the first property that we wished to
enforce. Secondly, we see that $A_{2}\bm{x}\geq 0$ and $-A_{2}\bm{x}\geq 0$
implies that $\Lambda_{\bm{x}}$ is orthogonal to $v^{\perp}$, i.e., the
corresponding shuffle invariant is on the $\gamma$-line. Finally,
$A_{i,j}\bm{x}\geq(1,1)^{T}$ implies that matrix $G_{i}$ was used at least
once, and matrix $G_{j}$ was used at least once. Therefore, if the above
system has a solution, then there is a product containing non-commuting
matrices $G_{i},G_{j}$ that gives an $\Omega$-matrix, and whose shuffle
invariant lies on the $\gamma$-line. By the previous reasoning, this implies
that the identity matrix belongs to $\langle G\rangle$.

Note that the vector $\bm{b}$ has non-negative coordinates, namely, $0$s and
$1$s. Therefore, by 1, we can determine in polynomial time whether the system
$T_{i,j}\bm{x}\geq\bm{b}$ has an integer solution. There are $t(t-1)/2$ many
pairs of $i,j$ that we need to check. Hence we can determine in polynomial
time if the $\gamma$-line can be reached by using a pair of non-commuting
matrices (which implies that $\bm{I}\in\langle G\rangle$ as explained above).

Finally, we consider the case when the above procedure gives us a negative
answer, that is, all matrices which can be used to reach the $\gamma$-line
commute. Since we assumed that
$\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}$ is not contained in
$H_{1}$ or $H_{2}$, there are two cases to consider. Either there exist some
$\Lambda_{\bm{s}_{i}}\in H_{1}$ and some $\Lambda_{\bm{s}_{j}}\in H_{2}$ or
$\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}\subseteq
H_{1}\cup\gamma\text{-line}$. (Actually, there is a third possibility that
$\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}\subseteq
H_{2}\cup\gamma\text{-line}$ but it is similar to the second case by
symmetry.)

Note that we can determine in polynomial time which of these cases hold.
Indeed, the first case holds if and only if there exist vectors
$\bm{x},\bm{y}\in\mathbb{N}^{t}$ such that $A_{1}\bm{x}=\bm{0}^{4(n-2)}$,
$A_{1}\bm{y}=\bm{0}^{4(n-2)}$, $A_{2}\bm{x}>0$, and $A_{2}\bm{y}<0$. To see
this, take $\bm{x}\in\mathbb{N}^{t}$ such that $A_{1}\bm{x}=\bm{0}^{4(n-2)}$
and $A_{2}\bm{x}>0$. Then $\bm{x}$ can be written as
$\bm{x}=\sum_{j=1}^{p}z_{j}\bm{s}_{j}$ for some tuple
$(z_{1},\ldots,z_{p})\in\mathbb{N}^{p}$. So we have
$A_{2}\bm{x}=\sum_{j=1}^{p}z_{j}A_{2}\bm{s}_{j}>0$, which implies that
$A_{2}\bm{s}_{i}>0$ for some $i$ since all $z_{j}$ are non-negative. Hence
$\Lambda_{\bm{s}_{i}}\in H_{1}$. All the other cases can be considered in a
similar way, and the existence of a solution to such system can be decided in
polynomial time by the second part of 1.

In the first case, all matrices from $G$ can be used in some product that is
equal to an $\Omega$-matrix whose top-right entry lies on the $\gamma$-line.
Indeed, since we assume that each matrix $M_{k}$ from $G$ is non-redundant,
there is some $\bm{s}_{i}$ with non-zero $k$th coordinate. Now, the shuffle
invariant $\Lambda_{\bm{s}_{i}}$ can be paired with some
$\Lambda_{\bm{s}_{j}}$ from the other open half-plane to reach the
$\gamma$-line. Namely, there exist $x,y\in\mathbb{N}$ such that
$x\Lambda_{\bm{s}_{i}}+y\Lambda_{\bm{s}_{j}}=r\exp(\mathrm{i}\gamma)$ for some
$r\in\mathbb{R}$. Hence we can find a tuple
$(z_{1},\ldots,z_{p})\in\mathbb{N}^{p}$ such that
$\sum_{j=1}^{p}z_{j}\Lambda_{\bm{s}_{j}}=r\exp(\mathrm{i}\gamma)$, for some
$r\in\mathbb{R}$, and the vector $\sum_{j=1}^{p}z_{j}\bm{s}_{j}$ has only non-
zero coordinates. This gives us a product with Parikh vector
$\sum_{j=1}^{p}z_{j}\bm{s}_{j}$ that uses all matrices from $G$ and reaches
the $\gamma$-line.

On the other hand, in the second case, a matrix $G_{k}\in G$ can be used in
some product that reaches the $\gamma$-line if and only if the $k$th
coordinate of some $\bm{s}_{i}$, for which $\Lambda_{\bm{s}_{i}}$ lines on the
$\gamma$-line, is non-zero. In other words, precisely the following matrices
can be used to reach the $\gamma$-line:

$\\{G_{k}\in G\ :\ \text{there is some }\bm{s}_{i}\text{ such that
}\bm{s}_{i}(k)>0\text{ and }\Lambda_{\bm{s}_{i}}=r\exp(\mathrm{i}\gamma)\text{
for some }r\in\mathbb{R}\\}.$ (6)

To show this, assume $G_{k}$ belongs to a product that reaches the
$\gamma$-line and let $\bm{x}\in\mathbb{N}^{t}$ be its Parikh vector. We can
write $\bm{x}=\sum_{j=1}^{p}z_{j}\bm{s}_{j}$, for some
$(z_{1},\ldots,z_{p})\in\mathbb{N}^{p}$. Note that
$\Lambda_{\bm{x}}=\sum_{j=1}^{p}z_{j}\Lambda_{\bm{s}_{j}}=r\exp(\mathrm{i}\gamma)$
for some $r\in\mathbb{R}$. Since we assumed
$\\{\Lambda_{\bm{s}_{1}},\ldots,\Lambda_{\bm{s}_{p}}\\}\subseteq
H_{1}\cup\gamma\text{-line}$, it follows that $z_{j}=0$ if
$\Lambda_{\bm{s}_{j}}\in H_{1}$. This means that only those
$\Lambda_{\bm{s}_{j}}$ that lie on the $\gamma$-line can appear in the linear
combination $\Lambda_{\bm{x}}=\sum_{j=1}^{p}z_{j}\Lambda_{\bm{s}_{j}}$. Since
$G_{k}$ appears in the product, we have
$\bm{x}(k)=\sum_{j=1}^{p}z_{j}\bm{s}_{j}(k)>0$. Thus $z_{j}\bm{s}_{j}(k)>0$
for some $j$. In particular, $\bm{s}_{j}(k)>0$ and $z_{j}>0$, which implies
that $\Lambda_{\bm{s}_{j}}$ is on the $\gamma$-line. Therefore, $G_{k}$
belongs to the set (6).

Conversely, consider all matrices $G_{k}\in G$ for which there is some
$\bm{s}_{i_{k}}$ with the property that $\bm{s}_{i_{k}}(k)>0$ and
$\Lambda_{\bm{s}_{i_{k}}}$ lies on the $\gamma$-line. Let $\bm{x}$ be the sum
of these $\bm{s}_{i_{k}}$. In this case, $\Lambda_{\bm{x}}$ is on the
$\gamma$-line, and we can construct a product with Parikh vector $\bm{x}$ that
reaches the $\gamma$-line and contains all matrices from the set (6), namely,
it suffices to take any product with Parikh vector $\bm{x}$.

Note that the condition “there is some $\bm{s}_{i}$ such that
$\bm{s}_{i}(k)>0$ and $\Lambda_{\bm{s}_{i}}$ is on the $\gamma$-line” is
equivalent to the following: there is some $\bm{x}\in\mathbb{N}^{t}$ with
$\bm{x}(k)>0$ such that $A_{1}\bm{x}=\bm{0}^{4(n-2)}$ and $\Lambda_{\bm{x}}$
is on the $\gamma$-line. The implication in one direction is obvious. Suppose
there is $\bm{x}\in\mathbb{N}^{t}$ with $\bm{x}(k)>0$ such that
$A_{1}\bm{x}=\bm{0}^{4(n-2)}$ and $\Lambda_{\bm{x}}$ is on the $\gamma$-line.
Then we can write $\bm{x}$ as a sum $\bm{x}=\sum_{j=1}^{p}z_{j}\bm{s}_{j}$,
where $(z_{1},\ldots,z_{p})\in\mathbb{N}^{p}$. Since $\bm{x}(k)>0$, there is
$j$ such that $\bm{s}_{j}(k)>0$. Also note that $\Lambda_{\bm{s}_{i}}$ must be
on the $\gamma$-line, otherwise $\Lambda_{\bm{x}}$ would not be on the
$\gamma$-line because $z_{j}>0$. Hence we can determine which matrices belong
to (6) by deciding if there is a solution to a system on linear equation
similar to (5), with the exception that matrix $A_{i,j}$ should be replaced
with $A_{k}=(\bm{e}_{k}^{T})$ and vector $\bm{b}$ has the form
$\bm{b}=(\bm{0}^{4(n-2)},\bm{0}^{4(n-2)},0,0,1)^{T}$. This can be done in
polynomial time by 1.

In both cases, the set $C=\\{G_{1},\ldots,G_{t^{\prime}}\\}\subseteq G$ of
commuting matrices that are used to reach the $\gamma$-line can be computed in
polynomial time. To finish the proof, note that by (2), the top-right corner
$M_{1,n}$ of any $M\in\langle C\rangle\cap\Omega$ can be expressed using the
Parikh vector of the generators from $C$. This allows us to construct a new
homogeneous system of linear Diophantine equations. Let
$A\in\mathbb{Q}^{4(n-2)\times t^{\prime}}$ be defined as in Equation (1) using
only matrices present in $C$, and let
$B=(c_{1}-\frac{1}{2}\bm{a}_{1}^{T}\bm{b}_{1},\ldots,c_{t^{\prime}}-\frac{1}{2}\bm{a}_{t^{\prime}}^{T}\bm{b}_{t^{\prime}})$.
We then construct a system $\begin{pmatrix}A\\\ B\end{pmatrix}\bm{x}=\bm{0}$,
where $\bm{x}\in\mathbb{N}^{t^{\prime}}$ and $\bm{0}$ is the
$t^{\prime}$-dimensional zero vector. It is straightforward to see that if
this system has a solution $\bm{x}$, then

$G_{1}^{x(1)}G_{2}^{x(2)}\cdots G_{t^{\prime}}^{x(t^{\prime})}=\bm{I}.$

By 1 (see also [21]), we can decide if such a system has a non-zero solution
in polynomial time. ∎

Lemmata 5 and 6 allow us to prove the main result, Theorem 5.1.

###### Proof

Let $G=\\{G_{1},\ldots,G_{t}\\}$. The first step is to remove all redundant
matrices from $G$. Recall that we can check if a matrix is non-redundant by
deciding if a system of non-homogeneous linear Diophantine equations, giving
an $\Omega$-matrix, has a solution. This was explain at the beginning of
Section 4. It is decidable in polynomial time if there exists a solution to
such a system.

It is obvious that if there is no solution to the system, then the identity
matrix is not in the generated semigroup. Indeed, there is no way to generate
a matrix with zeroes in the $\bm{a}$ and $\bm{b}$ elements and thus
$\bm{I}\not\in\langle G\rangle$.

If there is at least one solution, then we calculate commutators
$[G_{i},G_{j}]$ for every pair $G_{i},G_{j}$ of non-redundant matrices from
$G$. If there are at least two commutators with different angles, the identity
matrix is in the semigroup by 5. If all commutators have the same angle, we
apply 6 to decide in polynomial time whether the identity matrix is in the
semigroup.

Note that there are $O(t^{2})$ commutators to calculate. Hence the whole
procedure runs in polynomial time. ∎

The decidability of the Identity Problem implies that the Subgroup Problem is
also decidable. That is, whether the semigroup generated by the generators $G$
contains a non-trivial subgroup. However, the decidability of the Group
Problem, i.e., whether $\langle G\rangle$ is a group, does not immediately
follow. Our result can be extended to show decidability of the Group Problem.

###### Corollary 1

It is decidable in polynomial time whether a finite set of matrices
$G\subseteq{\rm H}(n,\mathbb{Q}(\mathrm{i}))$ forms a group.

###### Proof

In order for $\langle G\rangle$ to be a group, each element of $G$ must have a
multiplicative inverse. If there exist any redundant matrices in $G$, then
$\langle G\rangle$ is not a group, since a redundant matrix cannot be part of
a product giving even an $\Omega$-matrix. Checking if a matrix is redundant
can be done in polynomial time (see Section 4).

Assuming then that all matrices are non-redundant, if there exist matrices
$M_{1},M_{2},M_{3},M_{4}\in G$ such that
$[M_{1},M_{2}]\not\stackrel{{\scriptstyle\mathclap{\gamma}}}{{=}}[M_{3},M_{4}]$,
then $\bm{I}\in\langle G\rangle$ by Lemma 5, and in fact we can find a product
of matrices equal to the identity matrix which contains each matrix from $G$
(since all matrices are non-redundant, thus $M_{1}\cdots M_{k}\in\Omega$ may
be chosen to contain all matrices). Thus each matrix of $G$ has a
multiplicative inverse as required.

Next, assume that all matrices in $G$ are non-redundant and share a common
commutator angle. As explained in the proof of 6, we can compute in polynomial
time a subset $C\subseteq G$ of matrices that can be used in a product which
is equal to an $\Omega$-matrix whose top-right element lies on the
$\gamma$-line. Clearly, if $C\neq G$, then $\langle G\rangle$ is not a group.
If $C=G$ and $G$ contains a pair of non-commuting matrices, then in the proof
of 6 we can choose a product $T=T_{1}\cdots T_{k}\in\Omega$ in such a way that
it includes all matrices from $G$. Using the same idea we can construct a
product that gives $\bm{I}$ and uses all matrices from $G$. Hence $\langle
G\rangle$ is a group.

Finally, we need to consider the case when $C=G$ contains only commuting
matrices. We can decide if there is a product that is equal to $\bm{I}$ and
uses all matrices from $G$ by solving a homogeneous system of linear
Diophantine equations. Let $A\in\mathbb{Q}^{4(n-2)\times t}$ be defined as in
Section 4, and let
$A_{2}=(c_{1}-\frac{1}{2}\bm{a}_{1}^{T}\bm{b}_{1},\ldots,c_{t}-\frac{1}{2}\bm{a}_{t}^{T}\bm{b}_{t})$.
Define system $\begin{pmatrix}A\\\
A_{2}\end{pmatrix}\bm{x}=\bm{0}^{4(n-2)+1}$, where $\bm{x}\in\mathbb{N}^{t}$
and $\bm{0}^{4(n-2)+1}=(0,\ldots,0)\in\mathbb{N}^{4(n-2)+1}$. Solvability of
this system implies that the identity matrix can be reached. Unfortunately,
this does not guarantee that all matrices from $G$ were used in such a product
reaching $\bm{I}$. We can however form the following non-homogeneous system of
linear Diophantine equations

$\begin{pmatrix}A\\\ -A\\\ A_{2}\\\ -A_{2}\\\
I_{t}\end{pmatrix}\bm{x}\geq\begin{pmatrix}\bm{0}^{4(n-2)}\\\
\bm{0}^{4(n-2)}\\\ 0\\\ 0\\\ \bm{1}^{t}\end{pmatrix},$

where $\bm{1}^{t}=(1,\ldots,1)\in\mathbb{N}^{t}$ and $\bm{I}_{t}$ is the
$t\times t$ identity matrix. Solvability of this system is equivalent to the
homogeneous system defined above, with the added constraint that
$\bm{I}_{t}\bm{x}\geq\bm{1}^{t}$ implying that all matrices must be used at
least once in such a solution, as required for $\langle G\rangle$ to be a
group. By 1, we can decide in polynomial time if the above system has a
solution. ∎

##  6 Future research

We believe that the techniques, and the general approach, presented in the
previous chapters can act as stepping stones for related problems. In
particular, consider the Membership Problem, i.e., where the target matrix can
be any matrix rather than the identity matrix. Let
$M=\begin{pmatrix}1&\bm{m}^{T}_{1}&m_{3}\\\ \bm{0}&\bm{I}_{n-2}&\bm{m}_{2}\\\
0&\bm{0}^{T}&1\end{pmatrix}$ be the target matrix and let
$G=\\{G_{1},\ldots,G_{t}\\}$, where
$\psi(G_{i})=(\bm{a}_{i},\bm{b}_{i},c_{i})$. Following the idea of Section 4,
we can consider system $A\bm{x}=(\bm{m}_{1},\bm{m}_{2})$, where
$\bm{x}\in\mathbb{N}^{t}$. This system is a non-homogeneous system of linear
Diophantine equations that can be solved in $\NP$. The solution set is a union
of two finite solution sets, $S_{0}$ and $S_{1}$. The set $S_{0}$ being the
solutions to the corresponding homogeneous system that can be repeated any
number of times as they add up to $\bm{0}$ on the right-hand side. The other
set, $S_{1}$, corresponds to reaching the vector $(\bm{m}_{1},\bm{m}_{2})$.
The matrices corresponding to the solutions in $S_{1}$ have to be used exactly
this number of times.

The techniques developed in Section 4 allow us to manipulate matrices
corresponding to solutions in $S_{0}$ in order to obtain the desired value in
the top right corner. However, this is not enough as the main technique relies
on repeated use of $\Omega$-matrices. These can be interspersed with matrices
corresponding to a solution in $S_{1}$ affecting the top right corner in
uncontrollable ways.

## References

  * [1] Paul C. Bell, Mika Hirvensalo, and Igor Potapov.  The identity problem for matrix semigroups in SL$(2,\mathbb{Z})$ is NP-complete.  In Proceedings of SODA 2017, pages 187–206. SIAM, 2017.  doi:10.1137/1.9781611974782.13.
  * [2] Paul C. Bell and Igor Potapov.  On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups.  International Journal of Foundations of Computer Science, 21(6):963–978, 2010.  doi:10.1142/S0129054110007660.
  * [3] Kenneth R. Blaney and Andrey Nikolaev.  A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups.  Groups Complexity Cryptology, 8(1):69–74, 2016.  doi:10.1515/gcc-2016-0003.
  * [4] Vincent D. Blondel and Alexandre Megretski, editors.  Unsolved problems in mathematical systems and control theory.  Princeton University Press, 2004.
  * [5] Jean-Luc Brylinski.  Loop spaces, characteristic classes, and geometric quantization.  Birkhäuser, 1993.
  * [6] Daniel Bump, Persi Diaconis, Angela Hicks, Laurent Miclo, and Harold Widom.  An exercise(?) in Fourier analysis on the Heisenberg group.  Ann. Fac. Sci. Toulouse Math. (6), 26(2):263–288, 2017.  URL: https://doi.org/10.5802/afst.1533.
  * [7] Julien Cassaigne, Tero Harju, and Juhani Karhumäki.  On the undecidability of freeness of matrix semigroups.  International Journal of Algebra and Computation, 9(03n04):295–305, 1999.  doi:10.1142/S0218196799000199.
  * [8] Christian Choffrut and Juhani Karhumäki.  Some decision problems on integer matrices.  RAIRO - Theoretical Informatics and Applications, 39(1):125–131, 2005.  doi:10.1051/ita:2005007.
  * [9] Ventsislav Chonev, Joël Ouaknine, and James Worrell.  The orbit problem in higher dimensions.  In Proceedings of STOC 2013, pages 941–950. ACM, 2013.  doi:10.1145/2488608.2488728.
  * [10] Ventsislav Chonev, Joël Ouaknine, and James Worrell.  On the complexity of the orbit problem.  Journal of the ACM, 63(3):23:1–23:18, 2016.  doi:10.1145/2857050.
  * [11] Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell.  On reachability problems for low-dimensional matrix semigroups.  In Proceedings of ICALP 2019, volume 132 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019\.  doi:10.4230/LIPIcs.ICALP.2019.44.
  * [12] Persi Diaconis and Maryanthe Malliaris.  Complexity and randomness in the heisenberg groups (and beyond), 2021\.  URL: https://arxiv.org/abs/2107.02923, doi:10.48550/ARXIV.2107.02923.
  * [13] Volker Diekert, Igor Potapov, and Pavel Semukhin.  Decidability of membership problems for flat rational subsets of GL(2, $\mathbb{Q}$) and singular matrices.  In Ioannis Z. Emiris and Lihong Zhi, editors, ISSAC ’20: International Symposium on Symbolic and Algebraic Computation, Kalamata, Greece, July 20-23, 2020, pages 122–129. ACM, 2020.  doi:10.1145/3373207.3404038.
  * [14] Jintai Ding, Alexei Miasnikov, and Alexander Ushakov.  A linear attack on a key exchange protocol using extensions of matrix semigroups.  IACR Cryptology ePrint Archive, 2015:18, 2015.
  * [15] Ruiwen Dong.  On the identity problem and the group problem for subsemigroups of unipotent matrix groups.  CoRR, abs/2208.02164, 2022.  arXiv:2208.02164, doi:10.48550/arXiv.2208.02164.
  * [16] Ruiwen Dong.  On the identity problem for unitriangular matrices of dimension four.  In Proceedings of MFCS 2022, volume 241 of LIPIcs, pages 43:1–43:14, 2022.  doi:10.4230/LIPIcs.MFCS.2022.43.
  * [17] Ruiwen Dong.  Semigroup Intersection Problems in the Heisenberg Groups.  In In Proceedings of STACS 2023, volume 254 of LIPIcs, pages 25:1–25:18, 2023.  doi:10.4230/LIPIcs.STACS.2023.25.
  * [18] Esther Galby, Joël Ouaknine, and James Worrell.  On matrix powering in low dimensions.  In Proceedings of STACS 2015, volume 30 of LIPIcs, pages 329–340, 2015.  doi:10.4230/LIPIcs.STACS.2015.329.
  * [19] Razvan Gelca and Alejandro Uribe.  From classical theta functions to topological quantum field theory.  In The influence of Solomon Lefschetz in geometry and topology, volume 621 of Contemprorary Mathematics, pages 35–68. American Mathematical Society, 2014.  doi:10.1090/conm/621.
  * [20] Tero Harju.  Post correspondence problem and small dimensional matrices.  In Proceedings of DLT 2009, volume 5583 of LNCS, pages 39–46. Springer, 2009.  doi:10.1007/978-3-642-02737-6\\_3.
  * [21] Leonid G. Khachiyan.  Polynomial algorithms in linear programming.  USSR Computational Mathematics and Mathematical Physics, 20(1):53–72, 1980.
  * [22] Sang-Ki Ko, Reino Niskanen, and Igor Potapov.  On the identity problem for the special linear group and the Heisenberg group.  In Proceedings of ICALP 2018, volume 107 of LIPIcs, pages 132:1–132:15, 2018.  doi:10.4230/lipics.icalp.2018.132.
  * [23] Daniel König, Markus Lohrey, and Georg Zetzsche.  Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups.  Algebra and Computer Science, 677:138–153, 2016.  doi:10.1090/conm/677/13625.
  * [24] Bertram Kostant.  Quantization and unitary representations.  In Lectures in Modern Analysis and Applications III, pages 87–208. Springer, 1970.  doi:10.1007/BFb0079068.
  * [25] James R. Lee and Assaf Naor.  Lp metrics on the heisenberg group and the Goemans-Linial conjecture.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 99–108, 2006.  doi:10.1109/FOCS.2006.47.
  * [26] Andrei A. Markov.  On certain insoluble problems concerning matrices.  Doklady Akademii Nauk SSSR, 57(6):539–542, 1947.
  * [27] Alexei Mishchenko and Alexander Treier.  Knapsack problem for nilpotent groups.  Groups Complexity Cryptology, 9(1):87–98, 2017.  doi:10.1515/gcc-2017-0006.
  * [28] Joël Ouaknine, João Sousa Pinto, and James Worrell.  On termination of integer linear loops.  In Proceedings of SODA 2015, pages 957–969. SIAM, 2015.  doi:10.1137/1.9781611973730.65.
  * [29] Michael S. Paterson.  Unsolvability in $3\times 3$ matrices.  Studies in Applied Mathematics, 49(1):105, 1970.  doi:10.1002/sapm1970491105.
  * [30] Alexander Schrijver.  Theory of Linear and Integer Programming.  Wiley, 1998.