On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond
Paul C. Bell Igor Potapov Pavel Semukhin


Variational Inference to Measure Model Uncertainty in Deep Neural Networks The results presented in this article have been obtained as part of the master thesis of Konstantin Posch in 2017. The master thesis has been peer reviewed and accepted by the thesis committee according to common University guidelines and standards on October 29th, 2017. It has been made available through the library of the University of Klagenfurt since then.  The results of the Master thesis have been presented at the 23rd Int. Meeting of Young Statisticians in Balatonfüred (Hungary) on October 14, 2018. A version of this article has been submitted to Springer International Journal of Computer Vision on May 7th, 2018 and is currently still under review. We have since been notified about another article published on Arxiv on November 14th, 2018 (https://arxiv.org/pdf/1806.05978.pdfhttps://arxiv.org/pdf/1806.05978.pdf) using essentially the same approach as we did, i.e. with variances of the variational distribution specified as multiples of the corresponding squared expectation values. However in their approach, different multiplication factors for each network weight are assumed whereas we only use one factor for all weights of one particular layer.
    Konstantin Posch*  *both authors contributed equally to this work       Jan Steinbrener* Jürgen Pilz 

    Received: date / Accepted: date
============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


We consider the following variant of the Mortality Problem: given k× k
matrices A_1, A_2, …,A_t, does there exist nonnegative integers
m_1, m_2, …,m_t such that the product A_1^m_1 A_2^m_2⋯ A_t^m_t
is equal to the zero matrix? It is known that this problem is decidable when
t ≤ 2 for matrices over algebraic numbers but becomes undecidable for
sufficiently large t and k even for integral matrices.

In this paper, we prove the first decidability results for t>2. We show as one of our central
results that for t=3 this problem in any dimension is Turing equivalent to the well-known Skolem
problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for
matrices that was not used to show decidability results in matrix semigroups before. As a corollary
we obtain that the above problem is decidable for t=3 and k ≤ 3 for matrices over algebraic
numbers and for t=3 and k=4 for matrices over real algebraic numbers. Another consequence is
that the set of triples (m_1,m_2,m_3) for which the equation A_1^m_1 A_2^m_2 A_3^m_3
equals the zero matrix is equal to a finite union of direct products of semilinear sets.

For t=4 we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem
is still decidable for upper-triangular 2 × 2 rational matrices by
employing powerful tools from transcendence theory such as Baker's theorem and
S-unit equations.




§ INTRODUCTION

A large number of naturally defined matrix problems  are still unanswered,
despite the long history of matrix theory.  Some of these questions have recently
drawn renewed interest in the context of the analysis of digital processes, verification problems, and 
links with several  fundamental questions in mathematics <cit.>.

One of these challenging problems is the Mortality Problem of whether the zero matrix belongs to a finitely generated matrix semigroup. It plays a central role in many questions from 
control theory and software verification <cit.>. The mortality problem has been known to be undecidable for matrices in ^3 × 3 since 1970 <cit.> and the current undecidability bounds for the M(d, k × k) problem (i.e. the mortality problem for semigroups generated by d matrices of size k× k) are M(6, 3 × 3), M(4, 5 × 5), M(3, 9 × 9) and M(2, 15 × 15), see <cit.>.
It is also known that the problem is NP-hard
for 2 × 2 integer matrices <cit.> and is decidable for 2 × 2 integer matrices with determinant 0,±1 <cit.>. 
In the case of finite matrix semigroups of any dimension
the mortality problem is known to be PSPACE-complete <cit.>.


In this paper, we study a very natural variant of the mortality problem when matrices must appear in a fixed order (i.e. under bounded language constraint):
Given k× k matrices A_1, A_2, …,A_t over a ring , do there exist m_1, m_2, …,m_t∈ such that
A_1^m_1 A_2^m_2… A_t^m_t=_k, k, where _k, k is k× k zero matrix?



In general (i.e. replacing _k, k by other matrices) this problem is known as the solvability of multiplicative matrix equations 
and has been studied for many decades. In its simplest form, when k = 1, the problem was studied by
Harrison in 1969 <cit.> as a reformulation of the “accessibility problem” for linear sequential machines. The case t = 1 was solved in polynomial time in a celebrated paper by Kannan and Lipton
in 1980 <cit.>. The case t = 2,  i.e. A^xB^y=C where A, B and C are commuting matrices
was solved by Cai, Lipton and Zalcstein in 1994 <cit.>. Later, in 1996, the solvability of matrix equations
over commuting matrices was solved in polynomial time in <cit.> and in 2010 it was shown
in <cit.> that A^xB^y=C is decidable for non-commuting matrices 
of any dimension with algebraic coefficients by a reduction to the  
commutative case from <cit.>. However, it was also shown in <cit.>  that the solvability of multiplicative matrix equations for sufficiently large natural numbers t and k is in general undecidable 
by an encoding of Hilbert's tenth problem
 and in particular for the mortality problem with bounded language constraint.
In 2015 it was also shown that the undecidability result holds for such equations with unitriangluar matrices <cit.>
and also in the case of specific equations with nonnegative matrices <cit.>.

The decidability of matrix equations for non-commuting matrices is only known as corollaries of either 
recent decidability results for solving membership problem in 2 × 2 matrix semigroups  <cit.> or in the case of quite
restricted classes of matrices, e.g. matrices from the Heisenberg group <cit.> or row-monomial matrices over commutative semigroups <cit.>.
In the other direction, progress has been made for matrix-exponential equations, but again in the case of commuting matrices <cit.>.


In this paper, we prove the first decidability results for the above problem
when t=3 and t=4. We will call these problems the ABC-Z
and ABCD-Z problems, respectively. More
precisely, we will show that the ABC-Z problem in any dimension is Turing equivalent to the Skolem
problem (also known as Skolem-Pisot problem) which asks whether a given linear recurrence sequence
ever reaches zero. Our proof relies on the Primary Decomposition Theorem for
matrices (Theorem <ref>) that was not used to show decidability results in matrix semigroups
before.
As a corollary, we obtain that the ABC-Z problem is decidable for 2 × 2 and 3 × 3 matrices over algebraic numbers and also for 4 × 4 matrices over real algebraic numbers.
Another consequence of the above equivalence is that 
the set of triples (m,n,ℓ) that satisfy the equation
A^mB^nC^ℓ=_k× k can be expressed as a finite union of direct
products of semilinear sets.

In contrast to the ABC-Z problem, we show that the solution set of the ABCD-Z
problem can be non-semilinear. This indicates that the ABCD-Z problem is unlikely
to be related to the Skolem problem. However we will show that the ABCD-Z problem
is decidable for upper-triangular 2 × 2 rational matrices.  The proof of
this result relies on
powerful tools from transcendence theory such as Baker's theorem for linear forms in logarithms, 
S-unit equations from algebraic number theory and the Frobenius rank inequality
from matrix analysis. More precisely, we will reduce the ABCD-Z equation for
upper-triangular 2 × 2 rational matrices to an equation of the form
ax+by+cz=0, where x,y,z are S-units, and then use an upper bound on the
solutions of this equation (as in Theorem <ref>). On the other hand, if we try to
generalize this result to arbitrary 2× 2 rational matrices or to
upper-triangular matrices of higher dimension, then we end up with an equation that
contain a sum of four or more S-units, and for such equations no effective upper
bounds on their solutions are known. So, these generalizations seems to lie
beyond the reach of current mathematical knowledge.




§ PRELIMINARIES


We denote by , ,  and  the sets of natural, integer, rational and complex numbers, respectively. Further, we denote by  the set of algebraic numbers and by _ the set of real algebraic numbers.

For a prime number p we define a valuation v_p(x) for nonzero x∈ as follows: if x=p^km/n, where m,n∈ and p does not divide m or n, then v_p(x) = v_p(p^km/n)=k.

Throughout this paper  will denote either the ring of integers  or one
of the fields , , _ or . We will use the notation ^n
× m for the set of n × m matrices over .

We denote by 𝐞_i the i'th standard basis vector of some dimension
(which will be clear from the context). Let _n,m be the zero matrix of
size n× m, _n be the identity matrix of size n× n, and
0_n be the zero column vector of length n.
Given a finite set of matrices 𝒢⊆^n × n, we
denote by ⟨𝒢⟩ the multiplicative semigroup generated by 𝒢. 

If A ∈^m× m and B∈^n× n, then we define their direct sum as A⊕ B=
[[    A _m,n; _n,m    B ]].
Let C ∈^k × k be a square matrix. We write
(C) for the
determinant of C. We call C singular if (C)= 0, otherwise it is
said to be invertible (or non-singular). Matrices A and B from ^k ×
k are called similar if there exists an invertible k× k matrix
S (perhaps over a larger field containing ) such that A = SBS^-1. In
this case, S is said to be a similarity matrix transforming A to B.

We will also require the following inequality regarding ranks of matrices, known
as the Frobenius rank inequality, see <cit.> for further details.


Let A, B, C ∈^k × k. Then

    AB + BC≤ABC + B



In the proof of our first main result about the ABC-Z problem we will make use of the primary decomposition theorem for matrices.


  Let A be a matrix from ^n× n, where  is a field. Let m_A(x) be the minimal polynomial for A such that
  
    m_A(x)=p_1(x)^r_1⋯ p_k(x)^r_k,

  where the p_i(x) are distinct irreducible monic polynomials over  and the r_i are positive integers. Let W_i be the null space of p_i(A)^r_i and let S_i be a basis for W_i. Then
  
    
  * S_1∪⋯∪ S_k is a basis for ^n and ^n=W_1⊕⋯⊕ W_k,
    
  * each W_i is invariant under A, that is, A𝐱∈ W_i for any 𝐱∈ W_i,
    
  * let S be a matrix whose columns are equal to the basis vectors from S_1∪⋯∪ S_k; then
      
    S^-1AS=A_1⊕⋯⊕ A_k,

      where each A_i is a matrix over  of the size |S_i|× |S_i|, and the minimal polynomial of A_i is equal to p_i(x)^r_i.
  


We will also need the following two propositions.


  If p(x) is a polynomial over a field , where  is either ,  or _, then the primary decomposition of p(x) can be algorithmically computed.



  If =, then one can use an LLL algorithm <cit.> to find primary decomposition in polynomial time.

  If =, then one can use well-known algorithms to compute standard representations of the roots of p(x) in polynomial time <cit.>. Let λ_1,…,λ_k be distinct roots of p(x) with multiplicities m_1,…,m_k, respectively. In this case the primary decomposition of p(x) is equal to
  
    p(x) = (x-λ_1)^m_1⋯(x-λ_k)^m_k.


  If =_, then again one can compute in polynomial time standard representations of the roots of p(x) in . Let λ_1,…,λ_i be real roots of p(x) with multiplicities m_1,…,m_i and let μ_1,μ_1,…,μ_j,μ_j be pairs of complex conjugate roots of p(x) with multiplicities n_1,…,n_j, respectively. Then the primary decomposition of p(x) over _ is equal to
  
    p(x)=(x-λ_1)^m_1⋯(x-λ_i)^m_ip_1(x)^n_1⋯ p_j(x)^n_j,

  where p_s(x)=(x-μ_s)(x-μ_s) = x^2-2Re(μ_s)x + |μ_s|^2 for s=1,…,j.




  Let A∈^n× n and m_A(x) be the minimal polynomial of A. Then
  A is invertible if and only if m_A(x) has nonzero free coefficient, i.e.,
  m_A(x) is not divisible by x.



  Suppose that A is invertible but m_A(x)=xm'(x) for some polynomial m'(x). Then
  
    _n,n=m_A(A)=A· m'(A).

  Multiplying the above equation by A^-1 we obtain m'(A)=_n,n, which contradicts the assumption that m_A(x) is the minimal polynomial for A.

  On the other hand, it x does not divide m_A(x), then m_A(x)=xm'(x)+a for some m'(x) and a nonzero constant a. Then
  
    _n,n = m_A(A) = A· m'(A) + a_n.

  From this equation we conclude that A is invertible, and A^-1=-1/am'(A).



Our proof of the decidability of ABCD-Z problem for 2× 2 upper-triangular rational matrices
relies on the following result which is proved using Baker's theorem on linear forms in logarithms
(see Corollary 4 in <cit.> and also <cit.>).

  
  Let S={p_1,…,p_s} be a finite collection of prime numbers and let a,b,c be relatively
  prime nonzero integers, that is, (a,b,c)=1.
  
  If x,y,z are relatively prime nonzero integers composed of primes from
  S that satisfy the equation ax+by+cz=0, then
  
    max{|x|,|y|,|z|} < exp(s^Cs P^4/3log A)

  for some constant C, where P = max{p_1,…,p_s} and A=max{|a|,|b|,|c|,3}.



Rational numbers whose numerator and denominator are divisible only by the primes
from S are called S-units.




§ LINEAR RECURRENCE SEQUENCES AND SEMILINEAR SETS


There is a long history in computer science and mathematics of studying sequences of numbers defined by some recurrence relation, where the next value in the sequence depends upon some `finite memory' of previous values in the sequence. Possibly the simplest, and certainly the most well known of these, is the Fibonacci sequence, which may be defined by the recurrence F(n) = F(n-1) + F(n-2) with F(0) = F(1) = 1 being given as the initial conditions of the sequence. 
We may generalise the Fibonacci sequence to define a linear recurrence sequence, which find application in many areas of mathematics and other sciences and for which many questions remain open. Let  be a ring; a sequence (u_n)_n=0^∞ is called a linear recurrence sequence (1-LRS) if it satisfies a relation of the form:

    u_n = a_k-1u_n-1 + ⋯ +   a_1u_n-k+1 +  a_0u_n-k,

for any n ≥ k, where each a_0, a_1, …, a_k-1∈ are fixed coefficients[In the literature, such a sequence is ordinarily called an LRS; we use the nomenclature 1-LRS since we will study a multidimensional variant of this concept. Also, 1-LRS are usually considered over integers, but in the present paper we will consider such sequences over algebraic numbers.]. Such a sequence (u_n)_n=0^∞ is said to be of depth k if it satisfies no shorter linear recurrence relation (for any k' < k). We call the initial k values of the sequence u_0, u_1, …, u_k-1 the initial conditions of the 1-LRS. Given the initial conditions and coefficients of a 1-LRS, every element is uniquely determined.

The zero set of a 1-LRS is defined as follows: 𝒵(u_n) = {j
∈ | u_j = 0}.

There are various questions that one may ask regarding 𝒵(u_n). One notable example relates to the famous “Skolem's problem” which is stated in the following way:

[Skolem's Problem]
Given the coefficients and initial conditions of a depth k 1-LRS (u_n)_n=0^∞, determine if 𝒵(u_n) is the empty set.


Skolem's problem has a long and rich history, see <cit.> for a good survey. We note here that the problem remains open despite properties of zero sets having been studied even since 1934 <cit.>. It is known that the Skolem problem is at least NP-hard <cit.> and that it is decidable for depth 3 over  and for depth 4 over _, see <cit.> and <cit.>[A proof of decidability for depth 5 was claimed in <cit.>, although there is possibly a gap in the proof <cit.>.]. Other interesting questions are related to the structure of 𝒵(u_n). We remind the reader the definition of semilinear sets.


  A set S ⊆ is called semilinear if it is the union of a finite set and finitely many arithmetic progressions.


A seminal result regarding 1-LRSs is that there zero sets are semilinear.


  The zero set of a 1-LRS over  (or more generally over any field of characteristic 0) is semilinear.

In particular, if (u_n)_n=0^∞ is a 1-LRS whose coefficients and initial conditions are algebraic numbers, then one can algorithmically find a number L∈ such that for every i=0,…,L-1, if we let u^i_m=u_i+mL, then

  
  * the sequence (u^i_m)_m=0^∞ is a 1-LRS of the same depth as (u_n)_n=0^∞, and
  
  * either 𝒵(u^i_m)= or 𝒵(u^i_m) is finite.



Note that in the above theorem we can decide whether 𝒵(u^i_m) is finite or 𝒵(u^i_m)= because 𝒵(u^i_m)= if and only if u^i_0=⋯ =u^i_k-1=0, where k is the depth of (u^i_m)_m=0^∞.

We will also consider a stronger version of the Skolem problem.

[Strong Skolem's Problem]
  Given the coefficients and initial conditions of a 1-LRS (u_n)_n=0^∞ over , find a description of the set 𝒵(u_n). That is, find a finite set F such that 𝒵(u_n) = F if 𝒵(u_n) is finite or, if 𝒵(u_n) is infinite, find a finite set F, a constant L∈ and numbers i_1,…,i_t∈{0,…,L-1} such that
  
    𝒵(u_n) = F ∪{i_1+mL : m∈}∪⋯∪{i_t+mL : m∈}.



Using the Skolem-Mahler-Lech theorem we can prove an equivalence between the strong version of the
Skolem problem and the standard version[This result was announced in <cit.> without a
proof, probably with a similar construction in mind.].


  Skolem's problem of depth k over  is Turing equivalent to the strong Skolem's problem of the same depth.



  Obviously, Skolem's problem is reducible to the strong Skolem's problem. We now show a reduction in the other direction.

  Let (u_n)_n=0^∞ be a depth-k 1-LRS over . By Theorem <ref>, we can algorithmically find a number L such that, for every i=0,…,L-1, the sequence u^i_m=u_i+mL is a 1-LRS of depth k which is either everywhere zero, that is, 𝒵(u^i_m)= or 𝒵(u^i_m) is finite. Recall that we can decide whether 𝒵(u^i_m) is equal to  by considering the first k terms of (u^i_m)_m=0^∞.

  By definition, we have 𝒵(u_n) = ⋃_i=0^L-1{i+L·𝒵(u^i_m)}. So, if 𝒵(u^i_m)=, then {i+L·𝒵(u^i_m)} = {i+mL : m∈}, and if 𝒵(u^i_m) is finite, then so is {i+L·𝒵(u^i_m)}.

  To finish the proof we need to show how to compute 𝒵(u^i_m), and hence {i+L·𝒵(u^i_m)}, when it is finite. For this we will use an oracle for the Skolem problem. Let m' be the smallest number such that 𝒵(u^i_m+m') is empty. Such m' exists because 𝒵(u^i_m) is finite. Furthermore, (u_m+m')_m=0^∞ is a 1-LRS of depth k for any m'. So, we ask the oracle for the Skolem problem to decide whether 𝒵(u^i_m+m')=∅ for each m'∈ starting from 0 until we find one for which 𝒵(u^i_m+m') is empty. Note that we do not have any bound on m' because we do not even know the size of 𝒵(u^i_m). All we know is that 𝒵(u^i_m) is finite, and hence the above algorithm will eventually terminate.
  Since 𝒵(u^i_m) is a subset of {0,…,m'}, then we can compute it by checking whether u^i_m=0 for m=0,…,m'.


Linear recurrence sequences can also be represented using matrices <cit.>:


  Let  be a ring; for a sequence (u_n)_n=0^∞ over  the following are equivalent:


  * (u_n)_n=0^∞ is a 1-LRS of depth k.

  * There are vectors 𝐮,𝐯∈^k and a matrix M∈^k× k such that u_n = 𝐮^TM^n𝐯 for n∈.


Moreover, for any matrix M∈^k× k, the sequence u_n=
(M^n)_[1,k] is a 1-LRS of depth at most k. On the other hand, if (u_n)_n=0^∞ is a 1-LRS of depth k, then there is a matrix M∈^(k+1)× (k+1) such that u_n = (M^n)_[1,k+1] for all n∈.


Lemma <ref> motivates the following definition of n-dimensional Linear Recurrence Sequences (n-LRSs) which as we show later are related to the mortality problem for bounded languages.


A multidimensional sequence u_m_1, m_2, …, m_n is called an n-LRS of depth k over  if there exist two vectors 𝐮,𝐯∈^k and matrices M_1, M_2, …, M_n ∈^k × k such that 

    u_m_1, m_2, …, m_n = 𝐮^T M_1^m_1 M_2^m_2⋯ M_n^m_n𝐯.






§ THE MORTALITY PROBLEM FOR BOUNDED LANGUAGES


We remind the reader the definition of the mortality problem for bounded
languages.

[Mortality for bounded languages]
Given k× k matrices A_1,…,A_t over a ring , do there exist m_1, m_2, …,m_t∈ such that

    A_1^m_1 A_2^m_2… A_t^m_t=_k, k.



Recall that for t = 3 and t=4 this problem is called the ABC-Z and ABCD-Z problem,
respectively. 
Our first main result is that the ABC-Z problem is 
computationally equivalent to the
Skolem problem for 1-LRS. Our reduction holds in any dimension 
and over the same number field which means
that any new decidability results for the Skolem problem will automatically extend the decidability 
of ABC-Z equations and can immediately  lead to new decidability results for equations in dimensions 2, 3 and 4. 
For the proof we will need the following technical lemma.

 
  Let  be a field, and suppose A, B, C ∈^k × k are matrices of the form
  
    A=
        [[    A_s,s   _s,k-s;   _k-s,s _k-s,k-s ]],    B=
        [[     B_s,t   X_s,k-t;   Y_k-s,t Z_k-s,k-t ]],    C=
        [[    C_t,t   _t,k-t;   _k-t,t _k-t,k-t ]]

  for some s,t≤ k, where A_s,s, B_s,t, X_s,k-t, Y_k-s,t, Z_k-s,k-t and C_t,t are matrices over  whose dimensions are indicated by their subscripts (in particular, A=A_s,s⊕_k-s,k-s and C=C_t,t⊕_k-t,k-t). If A_s,s and C_t,t are invertible matrices, then the equation ABC=_k,k is equivalent to B_s,t = _s,t.



  It is not hard to check that
  
    AB=
        [[    A_s,s   _s,k-s;   _k-s,s _k-s,k-s ]]·[[     B_s,t   X_s,k-t;   Y_k-s,t Z_k-s,k-t ]]
        =
        [[   A_s,sB_s,t A_s,sX_s,k-t;       _k-s,t     _k-s,k-t ]],

  and hence
  
    (AB)C=
        [[   A_s,sB_s,t A_s,sX_s,k-t;       _k-s,t     _k-s,k-t ]]·[[    C_t,t   _t,k-t;   _k-t,t _k-t,k-t ]]
        =
        [[ A_s,sB_s,tC_t,t          _s,k-t;          _k-s,t        _k-s,k-t ]].

  So, if B_s,t=_s,t, then ABC=_k,k. Conversely, if ABC=_k,k, then A_s,sB_s,tC_t,t=_s,t. Using the fact that A_s,s and C_t,t are invertible matrices, we can multiply the equation A_s,sB_s,tC_t,t=_s,t by A^-1_s,s on the left and by C^-1_t,t on the right to obtain that B_s,t=_s,t.


The next lemma is similar to Lemma <ref> and can also be proved by directly multiplying
the matrices.

 
  (1) Suppose A, B∈^k × k are matrices of the following form
  
    A=
        [[    A_s,s   _s,k-s;   _k-s,s _k-s,k-s ]] = A_s,s⊕_k-s,k-s  and  
        B=
        [[   B_s,k; X_k-s,k ]],

  for some s≤ k. If A_s,s is invertible, then AB=_k,k is equivalent to B_s,k = _s,k.

  (2) Suppose A, B∈^k × k are matrices of the following form
  
    A=[ [   A_k,t Y_k,k-t ]]  and  
        B=
        [[    B_t,t   _t,k-t;   _k-t,t _k-t,k-t ]] = B_t,t⊕_k-t,k-t,

  for some t≤ k. If B_t,t is invertible, then AB=_k,k is equivalent to A_k,t = _k,t.

  As in Lemma <ref>, in the above equations A_s,s, B_s,k, X_k-s,k, A_k,t, Y_k,k-t and B_t,t are matrices over  whose dimensions are indicated by their subscripts.




  Let  be the ring of integers  or one of the fields ,  or _. Then the ABC-Z
  problem for matrices from ^k× k is Turing equivalent to the Skolem problem of depth k over .



  First, we show reduction from the ABC-Z problem to the Skolem problem.

  Clearly, the ABC-Z problem over  is equivalent to the ABC-Z problem over  (by multiplying the
  matrices A,B,C by a suitable integer number). It is also not hard to see that the Skolem problem
  for 1-LRS over  is equivalent to the Skolem problem over  for 1-LRS of the same depth.
  Indeed, by Lemma <ref> we can express any 1-LRS (u_n)_n=0^∞ over  as u_n =
  𝐮^TM^n𝐯 for some rational vectors 𝐮 and 𝐯 and a rational
  matrix M. If we multiply 𝐮, 𝐯 and M by a suitable natural number t,
  then (t^n+2u_n)_n=0^∞ will be an integer 1-LRS, which has the same zero set as
  (u_n)_n=0^∞. Hence, without loss of generality, we will assume that  is one of the
  fields ,  or _.

  Consider an instance of the ABC-Z problem: A^mB^nC^ℓ=_k,k, where A,B,C∈^k,k. Let χ_A(x) be the characteristic polynomial of A. By Proposition <ref>, we can find a primary decomposition χ_A(x)=p_1(x)^m_1⋯ p_t(x)^m_t, where p_1(x),…,p_t(x) are distinct irreducible monic polynomials. From this decomposition we can find the minimal polynomial m_A(x) of A because m_A(x) is a factor of χ_A(x), and we can check all divisors of χ_A(x) to find m_A(x).

  Let m_A(x)=p_1(x)^r_1⋯ p_u(x)^r_u, where p_1(x),…,p_u(x) are distinct irreducible
  monic polynomials. Now we apply the Primary Decomposition Theorem (Theorem <ref>) to A.
  Let S_i be a basis for the null space of p_i(A)^r_i, which can be found, e.g., using
  Gaussian elimination. Let S be a matrix whose columns are the vectors of the basis
  S_1∪⋯∪ S_u. Then
  
    S^-1AS = A_1⊕⋯⊕ A_u,

  where the minimal polynomial of A_i is p_i(A)^r_i for i=1,…,u. Similarly, we can compute a primary decomposition m_C(x)=q_1(x)^s_1⋯ q_v(x)^s_v of the minimal polynomial for C, where q_1(x),…,q_v(x) are distinct irreducible monic polynomials, and a matrix T such that
  
    T^-1CT = C_1⊕⋯⊕ C_v,

  where the minimal polynomial of C_i is q_i(C)^s_i for i=1,…,v.

  Note that if p(x) is an irreducible monic polynomial, then either p(x)=x or x does not divide p(x). So, among the polynomials p_1(x),…,p_u(x) in the primary decomposition of m_A(x) at most one is equal to x, and the same holds for the polynomials q_1(x),…,q_v(x) in the primary decomposition of m_C(x).

  Suppose, for example, that p_u(x)=x. In this case m_A(x)=p_1(x)^r_1⋯ p_u-1(x)^r_u-1x^r_u, and S^-1AS = A_1⊕⋯⊕ A_u-1⊕ A_u, where the minimal polynomial of A_u is x^r_u, and hence A_u is a nilpotent matrix of index r_u. Recall that, for i=1,…,u-1, the polynomial p_i(x) is not divisible by x, and so is p_i(x)^r_i, which is the minimal polynomial for A_i. Hence, by Proposition <ref>, A_i is invertible. Let A_inv = A_1⊕⋯⊕ A_u-1 and A_nil = A_u. Then we obtain
  
    S^-1AS = A_inv⊕ A_nil,

  where A_inv is invertible, and A_nil is nilpotent. If
p_i(x)=x for some i<u, then we need in addition to permute some rows and columns of matrix S to obtain one that gives us Equation (<ref>) above. If none of the p_i(x) is equal to x, then we assume that A_nil is the empty matrix of size 0× 0.

  The same reasoning can be applied to matrix C, that is,
we can compute an invertible matrix C_inv, a nilpotent (or empty) matrix C_nil, and an invertible matrix T such that
 
    T^-1CT = C_inv⊕ C_nil.

  Note that the indices of the nilpotent matrices A_nil and C_nil are at most k, and hence A^k_nil and C^k_nil are zero (or empty) matrices.

  Our goal is to find all triples (m,n,ℓ)∈^3 for which A^mB^nC^ℓ=_k,k. In order to do this we will consider four cases: (1) m≥ k and ℓ≥ k, (2) m<k and ℓ<k, (3) m≥ k and ℓ<k, and (4) m<k and ℓ≥ k.

  Before dealing with each of these cases, we note that the equation A^mB^nC^ℓ=_k,k is equivalent to
  
    S(A^m_inv⊕ A^m_nil)S^-1   B^nT(C^ℓ_inv⊕ C^ℓ_nil)T^-1 =_k,k  or to
    
        (A^m_inv⊕ A^m_nil)S^-1   B^nT(C^ℓ_inv⊕ C^ℓ_nil) =_k,k

  because S and T are invertible matrices.
  
  Now suppose A_inv has size s× s, and C_inv has size t× t for some s,t≤ k.
  
  Case 1: m≥ k and ℓ≥ k. Since m,ℓ≥ k, we have A^m_nil = _k-s,k-s and C^ℓ_nil = _k-t,k-t, and hence the equation A^mB^nC^ℓ=_k,k is equivalent to
  
    (A^m_inv⊕_k-s,k-s)S^-1B^nT(C^ℓ_inv⊕_k-t,k-t) =_k,k.

  Suppose the matrix S^-1B^nT has a form S^-1B^nT=
    [[     B_s,t   X_s,k-t;   Y_k-s,t Z_k-s,k-t ]]. Since A^m_inv and C^ℓ_inv are invertible matrices, Lemma <ref> implies that Equation (<ref>) is equivalent to B_s,t=_s,t. Therefore, we obtain the following equivalence: A^mB^nC^ℓ=_k,k if and only if
    
    s^i,j_n = (𝐞_i^⊤ S^-1)B^n(T𝐞_j) = 0  for all i=1,…,s and j=1,…,t.

  By Lemma <ref>, the sequence (s^i,j_n)_n=0^∞ is a 1-LRS of order k over . As in the proof of Theorem <ref>, we can use an oracle for the Skolem problem for 1-LRS of depth k over  to compute the descriptions of the semilinear sets 𝒵(s^i,j_n). Hence we can compute a description of the intersection Z_1=⋂_i=1,…,s
 j=1,…,t𝒵(s^i,j_n), which is also a semilinear set. An important observation is that the set Z_1 does not depend on m and ℓ.

  Case 2: m<k and ℓ<k. Fix some m<k and ℓ<k. For this particular choice of m and ℓ, the equation A^mB^nC^ℓ=_k,k is equivalent to
  
    s^i,j_n = (𝐞_i^⊤ A^m)B^n(C^ℓ𝐞_j) = 0  for all i=1,…,k and j=1,…,k.

  Again, by Lemma <ref>, the sequence (s^i,j_n)_n=0^∞ is a 1-LRS of order k over , and we can use an oracle for the Skolem problem for 1-LRS of depth k over  to compute the descriptions of the semilinear sets 𝒵(s^i,j_n). Therefore, we can compute a description of the intersection Z_2(m,ℓ)=⋂_i=1,…,k
 j=1,…,k𝒵(s^i,j_n) which is equal to all values of n for which A^mB^nC^ℓ=_k,k holds for fixed m,ℓ<k.

  Case 3: m≥ k and ℓ<k. To solve this case we will combine ideas from cases (1) and (2). Fix some ℓ<k and let m be any integer such that m≥ k. Then A^m_nil = _k-s,k-s, and the equation A^mB^nC^ℓ=_k,k is equivalent to
  
    (A^m_inv⊕_k-s,k-s)S^-1B^nC^ℓ =_k,k.

  Suppose the matrix S^-1B^nC^ℓ has a form S^-1B^nC^ℓ=
    [[   B_s,k; X_k-s,k ]]. Since A^m_inv is invertible, Lemma <ref> implies that Equation (<ref>) is equivalent to B_s,k=_s,k. Therefore, Equation (<ref>) is equivalent to
  
    s^i,j_n = (𝐞_i^⊤ S^-1)B^n(C^ℓ𝐞_j) = 0  for all i=1,…,s and j=1,…,k.

  As in the previous two cases, we can use an oracle for the Skolem problem for 1-LRS of depth k over  to compute the descriptions of the semilinear sets 𝒵(s^i,j_n) and of the intersection Z_3(ℓ)=⋂_i=1,…,s
 j=1,…,k𝒵(s^i,j_n). Z_3(ℓ) is the set of all n for which A^mB^nC^ℓ=_k,k holds for a fixed ℓ<k and for any m≥ k.

  Case 4: m<k and ℓ≥ k. Fix some m<k and let ℓ be any integer such that ℓ≥ k. Using the same ideas as in Case 3 we can use an oracle for the Skolem problem to compute a description of a semilinear set Z_4(m) which is equal to all values of n for which A^mB^nC^ℓ=_k,k holds for a fixed m<k and for any ℓ≥ k.

  Combining all the above cases together, we conclude that the set of all triples (m,n,ℓ)∈^3 that satisfy the equation A^mB^nC^ℓ=_k,k is equal to the following union
  
    {(m,n,ℓ) : n∈ Z_1  and  m,ℓ≥ k}   ⋃⋃_m,ℓ<k{(m,n,ℓ) : n∈ Z_2(m,ℓ)}⋃
    ⋃_ℓ<k{(m,n,ℓ) : n∈ Z_3(ℓ)  and  m≥ k}   ⋃⋃_m<k{(m,n,ℓ) : n∈ Z_4(m)  and ℓ≥ k}.


  Having a description for the above set, we can decide whether is it empty or not, that is, whether there exist m,n,ℓ∈ such that A^mB^nC^ℓ=_k,k.

  We now show the reduction in the other direction. Let (u_n)_n=0^∞ be a 1-LRS that satisfies a relation

    u_n = a_k-1u_n-1 + ⋯ +   a_1u_n-k+1 +  a_0u_n-k,

where a_0≠ 0. Let A, B and C be the following matrices of size k× k:

    A = [ u_k-1     ⋯   u_1   u_0;     0     ⋯     0     0;     0     ⋯     0     0;     ⋮     ⋱     ⋮     ⋮;     0     ⋯     0     0 ],B = [ a_k-1     1     ⋯     0     0;     ⋮     ⋮     ⋱     ⋮     ⋮;   a_2     0     ⋯     1     0;   a_1     0     ⋯     0     1;   a_0     0     ⋯     0     0 ],C = [ 0 0 ⋯ 0 0; 0 0 ⋯ 0 0; ⋮ ⋮ ⋱ ⋮ ⋮; 0 0 ⋯ 0 0; 0 0 ⋯ 0 1 ].

A straightforward computation shows that the product A^mB^nC^ℓ is equal to a matrix where all entries equal zero except for the entry in the upper-right corner which is equal to u_k-1^m-1u_n. So, if we assume that u_k-1≠ 0, then we have the following implications: (1) if A^mB^nC^ℓ = _k, k for some m,n,ℓ∈ with m,ℓ≥ 1, then u_n=0; and (2) if u_n=0, then the equation A^mB^nC^ℓ = _k, k holds for any m,ℓ≥ 1.

The assumption that u_k-1≠ 0 is not a serious restriction because we can shift the original
sequence by at most k positions to ensure that u_k-1≠ 0. In other words, instead of (u_n)_n=0^∞ we can consider a sequence (u_n+t)_n=0^∞ for some t>0. It is easy to check that a 1-LRS of depth k is identically zero if and only if it contains k consecutive zeros. Hence if (u_n)_n=0^∞ is not identically zero, then we can find t<k such that the sequence (u_n+t)_n=0^∞ satisfies the condition that u_k-1+t≠ 0.



  The set of triples (m,n,ℓ) that satisfy an equation A^mB^nC^ℓ=_k, k is equal to a finite union of direct products of semilinear sets.



  The corollary follows from Equation (<ref>) above that describes all triples (m,n,ℓ) that satisfy the equation A^mB^nC^ℓ=_k, k. By construction and the Skolem-Mahler-Lech theorem, the sets Z_1, Z_2(m,ℓ), Z_3(ℓ) and Z_4(m) are semilinear. In Equation (<ref>) we take direct product of these sets either with singleton sets or with sets of the form _k = {n∈ : n≥ k}, which are also semilinear sets, and then take a finite union of such products.
  In other words, Equation (<ref>) can be rewritten as follows
  
    _k × Z_1 ×_k ⋃⋃_m,ℓ<k{m}×
        Z_2(m,ℓ)×{ℓ} ⋃
       ⋃_ℓ<k_k×
        Z_3(ℓ)×{ℓ} ⋃⋃_m<k{m}× Z_4(m)×_k.

The main corollary of Theorem <ref> is the following result.



The ABC-Z problem is decidable for 3× 3 matrices over algebraic numbers and for 4× 4 matrices over real algebraic numbers.



  By Theorem <ref>, the ABC-Z problem for 3× 3 matrices over  is equivalent to the Skolem problem of depth 3 over , and the ABC-Z problem 4× 4 matrices over _ is equivalent to the Skolem problem of depth 4 over _.
  Now the corollary follows from the fact that the Skolem problem is decidable for linear recurrence sequences of depth 3 over  and of depth 4 over _ <cit.>.


The next theorem is a generalisation of Theorem <ref> to an arbitrary number of matrices.


  Let  be the ring of integers  or one of the fields ,  or _. Then the mortality problem for bounded languages (Problem <ref>) over  for t+2 matrices is reducible to the following problem: given matrices A_1,…,A_t from ^k× k and vectors 𝐮_i, 𝐯_i from ^k, where i=1,…,r ,do there exists m_1,…,m_t∈ such that s^i_m_1,…,m_t=0 for all i=1,…,r, where

    s^i_m_1,…,m_t=𝐮_i^⊤ A_1^m_1… A_t^m_t𝐯_i.




  Consider an instance  of the mortality problem for bounded languages for t+2 matrices:
  
    A_0^m_0A_1^m_1⋯ A_t^m_tA_t+1^m_t+1=_k, k.

  The proof of the reduction is similar to the proof of Theorem <ref> for the equation A^mB^nC^ℓ=_k, k. However note that in Theorem <ref> we proved a stronger result in the sense that in Equation (<ref>) we gave a description of all the triples (m,n,ℓ) that satisfy A^mB^nC^ℓ=_k, k. If we simply want to know whether there exists one such triple, then we only need to consider Case 1 from the proof of Theorem <ref>, because if the equation A^mB^nC^ℓ=_k, k has a solution, then it has one in which m≥ k and ℓ≥ k.
  
  So, we replicate the proof of Case 1 where in place of matrices A and C we consider A_0 and A_t+1. By doing this we obtain a system of equations similar to Equation (<ref>), where in place of B^n we will have the product A_1^m_1⋯ A_t^m_t. This gives us the desired reduction.
  
  The key difference between this theorem and Theorem <ref> is that for t=1 the system of equations (<ref>) for 1-LRSs s^i_n can be reduced to the Skolem problem using Theorem <ref> and the Skolem-Mahler-Lech theorem (Theorem <ref>). For t>1, the solution set of the equation
  
    𝐮^⊤ A_1^m_1… A_t^m_t𝐯=0

  is not semilinear (see, e.g., Proposition <ref>), and we do not have an analog of Theorem <ref> or the Skolem-Mahler-Lech theorem in this case. So, we cannot solve a system of such equations using an oracle for a single equation of this form.




§ THE ABCD-Z PROBLEM IN DIMENSION TWO

Recall that the ABCD-Z problem in dimension two asks whether there exist natural numbers k,m,n,ℓ∈ such that

    A^k B^m C^n D^ℓ = _2,2.

In this section we will show that this problem is decidable for 2 × 2 upper-triangular matrices with rational coefficients.
In the proof we will use the following simple lemmas which show how to diagonalise and compute powers of an upper-triangular 2 × 2 matrix.


  Given an upper triangular matrix [ a b; 0 c ] such that a≠ c then:

[ a b; 0 c ] = [      1 -b/a-c;      0      1 ][ a 0; 0 c ][     1 b/a-c;     0     1 ]



  For any matrices of the form [ a b; 0 c ] and
  [ a b; 0 a ], such that a≠ c, and any k∈ we
  have
[ a b; 0 c ]^k = [         a^k ba^k-c^ka-c;           0         c^k ] and [ a b; 0 a ]^k = [     a^k kba^k-1;       0     a^k ].



The ABCD-Z problem is decidable for 2 × 2 upper-triangular matrices over rational numbers.



  First, note that if one of the matrices A, B, C or D is nilpotent, then Equation (<ref>) obviously has a solution. So from now on we assume that none of A, B, C or D is nilpotent. Furthermore, if A or D is invertible, then the ABCD-Z problem reduces to the ABC-Z problem for rational matrices of dimension two that is decidable by Theorem <ref>. So, without loss of generality, we will assume that both A and D are singular matrices.
  
  Now suppose we are given an instance of the ABCD-Z problem which satisfies the above-mentioned requirements. We will show that if Equation (<ref>) has a solution, then it has a solution with k=ℓ=1. Indeed, assume Equation (<ref>) has a solution, and let (k,m,n,ℓ) be a solution of minimal length, where the length of a solution is the sum k+m+n+ℓ. Using Theorem <ref> we can exclude the case when k=0 or ℓ=0 since in this case our problem is just an instance of the ABC-Z for 2× 2 matrices. So we will assume that in the above solution k,ℓ≥ 1.

By the Frobenius rank inequality (Theorem <ref>), we have that:

    A^kB^mC^nD^ℓ-1 + A^k-1B^mC^nD^ℓ≤A^k-1B^mC^nD^ℓ-1.

This follows since A^kB^mC^nD^ℓ = _2,2 = 0. In the above inequality, notice that neither A^kB^mC^nD^ℓ-1 nor A^k-1B^mC^nD^ℓ is the zero matrix by the assumption that the solution has minimal length. Hence the ranks of the matrices on the left hand side are at least 1. Therefore, A^k-1B^mC^nD^ℓ-1 = 2. Since we assumed that A and D are singular, it is necessary that k = ℓ = 1. Also notice that if B=1 or C=1, then we must have m=0 or n=0, respectively. Again these cases can be excluded by Theorem <ref>.

Thus, using the Frobenius rank inequality and the assumption that the solution is of minimal length, we reduced the ABCD-Z problem to an equation of the form:

    AB^mC^nD = _2,2,

where A = D = 1 and B = C = 2.

We assumed that A and D have rank one but are not nilpotent. This means that they have one zero and one nonzero element on the diagonal, in particular, they satisfy the condition of Lemma <ref>. Hence we can find invertible rational matrices S_A and S_D such that

    A = S_A^-1[ a 0; 0 0 ]S_A  and  
      D = S_D^-1[ d 0; 0 0 ]S_D,

where a,d are nonzero rational numbers. Applying Lemma <ref> with
matrix S_A B^m C^n S_D^-1 in place of B, we conclude that AB^mC^nD =
_2,2 holds if and only if the (1,1)-entry of S_A B^m C^n S_D^-1 equals zero.
In other words, the equation AB^mC^nD = _2,2 is equivalent to s_m,n = 𝐮^⊤ B^m C^n 𝐯 = 0, where 𝐮^⊤ = 𝐞_1^⊤ S_A and 𝐯 = S_D^-1𝐞_1 are vectors with rational coefficients.

We will consider three cases: (1) both B and C have distinct eigenvalues, (2) both B and C have a single eigenvalue of multiplicity 2 and (3) one matrix has distinct eigenvalues and the other has a single eigenvalue of multiplicity 2.

Case (1): B and C have distinct eigenvalues, that is, B=[ b_1 b_3;   0 b_2 ] and C=[ c_1 c_3;   0 c_2 ], where b_1≠ b_2 and c_1≠ c_2. By Lemma <ref> we have

    B^m = [                 b_1^m b_3b_1^m-b_2^mb_1-b_2;                     0                 b_2^m ]  and   
      C^n = [                 c_1^n c_3c_1^n-c_2^nc_1-c_2;                     0                 c_2^n ]

Multiplying these matrices we obtain:  B^mC^n=

    = [                 b_1^m b_3b_1^m-b_2^mb_1-b_2;                     0                 b_2^m ][                 c_1^n c_3c_1^n-c_2^nc_1-c_2;                     0                 c_2^n ]
     = [                                                        b_1^mc_1^n b_3b_1^mc_2^n-b_2^mc_2^nb_1-b_2 + c_3b_1^mc_1^n-b_1^mc_2^nc_1-c_2;                                                                 0                                                        b_2^mc_2^n ]

From this formula one can see that the entries of B^mC^n are linear combinations of b_1^mc_1^n, b_1^mc_2^n and b_2^mc_2^n with rational coefficients. Notice that the term b_2^mc_1^n does not appear in the entries of B^mC^n. Since 𝐮 and 𝐯 are rational vectors we conclude that

    s_m,n = 𝐮^⊤ B^m C^n 𝐯 = α b_1^mc_1^n +β b_1^mc_2^n +γ b_2^mc_2^n,

where α,β,γ∈. Multiplying the equation s_m,n = α b_1^mc_1^n +β b_1^mc_2^n +γ b_2^mc_2^n=0 by the product of denominators of α,β,γ and b_1,b_2,c_1,c_2 we can rewrite it in the following form

    as^mr^n+bs^mt^n+cq^mt^n=0

where a,b,c,q,r,s,t are integers and a,b,c are relatively prime. Recall that we want to find out
if there exist m,n∈ that satisfy the above exponential Diophantine equation. If one of the
coefficients a,b,c is zero, then this problem is easy to solve. For instance, if b=0 then the
above equation is equivalent to as^mr^n = -cq^mt^n. This equality holds if and only if as^mr^n
and -cq^mt^n have the same sign and v_p(as^mr^n) = v_p(-cq^mt^n) for every prime divisor p of
a,c,s,r,q or t. Each of these conditions can be expressed as a linear Diophantine equation. For
instance, the sign of as^mr^n or -cq^mt^n depends on the parity of m and n. So, the
requirement that as^mr^n and -cq^mt^n have the same sign can be written as a linear congruence
equation in m and n modulo 2, which in turn can be expressed as a linear Diophantine equation.
Since a system of linear Diophantine equations can be effectively solved, we can find out whether
there exist m and n that satisfy as^mr^n = -cq^mt^n.

Now suppose that a,b,c are relatively prime nonzero integers. Let
T be all primes that appear in s,r,q or t. Theorem
<ref> gives an upper bound on nonzero relatively prime integers
x,y,z that are composed of the primes from T and satisfy the equation
ax+by+cz=0. Therefore, we can algorithmically compute the following set

    𝒰={(x,y,z) : ax+by+cz=0, x,y,z≠ 0  and (x,y,z)=1}.

Next for each triple (x,y,z)∈𝒰 we want to find out if there exist m,n∈ such that

    (s^mr^n,s^mt^n,q^mt^n)= (xg,yg,zg)

for some g∈ that is composed of the primes from T. It is not hard to see that Equation (<ref>) holds if and only if for every p∈ T

    v_p(s^mr^n)-v_p(x) = v_p(s^mt^n)-v_p(y) = v_p(q^mt^n)-v_p(z)

and s^mr^n,s^mt^n,q^mt^n have the same signs as x,y,z, respectively. Since these conditions can be expressed as a system of linear Diophantine equations, we can algorithmically find if there are m,n∈ that satisfy Equation (<ref>). If such m and n exist for at least one triple (x,y,z)∈𝒰, then the original equation s_m,n = 0 has a solution. Otherwise, the equation s_m,n = 0 does not have a solution.

Case (2): both B and C have a single eigenvalue of multiplicity 2, that is, B=[ b_1 b_2;   0 b_1 ] and C=[ c_1 c_2;   0 c_1 ]. By Lemma <ref> we have

    B^m = [       b_1^m mb_2b_1^m-1;           0       b_1^m ]  and   
      C^n = [       c_1^n nc_2c_1^n-1;           0       c_1^n ].

Multiplying these matrices we obtain:

    B^mC^n = [       b_1^m mb_2b_1^m-1;           0       b_1^m ][       c_1^n nc_2c_1^n-1;           0       c_1^n ]
      = [                          b_1^mc_1^n mb_2b_1^m-1c_1^n + nc_2b_1^mc_1^n-1;                                   0                          b_1^mc_1^n ].

Note that the entries of B^mC^n are equal to linear combinations of b_1^mc_1^n, mb_1^m-1c_1^n and nb_1^mc_1^n-1 with rational coefficients. Therefore,

    s_m,n = 𝐮^⊤ B^m C^n 𝐯 = α b_1^mc_1^n +β mb_1^m-1c_1^n +γ nb_1^mc_1^n-1 = b_1^m-1c_1^n-1(α b_1c_1 +mβ c_1 +nγ b_1)

where α,β,γ∈. Hence s_m,n=0 is equivalent to the linear Diophantine equation

    α b_1c_1 +mβ c_1 +nγ b_1=0,

which can be easily solved.

Case (3): one matrix has distinct eigenvalues and the other has a single eigenvalue of multiplicity 2. We consider only the case when B has distinct eigenvalues and C has a single eigenvalue because the other case is similar.

Suppose B=[ b_1 b_3;   0 b_2 ], where b_1≠ b_2, and C=[ c_1 c_2;   0 c_1 ]. By Lemma <ref> we have

    B^m = [                 b_1^m b_3b_1^m-b_2^mb_1-b_2;                     0                 b_2^m ]  and   
      C^n = [       c_1^n nc_2c_1^n-1;           0       c_1^n ].

Multiplying these matrices we obtain:

    B^mC^n = [                 b_1^m b_3b_1^m-b_2^mb_1-b_2;                     0                 b_2^m ][       c_1^n nc_2c_1^n-1;           0       c_1^n ]
      = [                                         b_1^mc_1^n b_3b_1^mc_1^n-b_2^mc_1^nb_1-b_2 + nc_2b_1^mc_1^n-1;                                                  0                                         b_2^mc_1^n ].

Note that the entries of B^mC^n are equal to linear combinations of b_1^mc_1^n, b_2^mc_1^n and nb_1^mc_1^n-1 with rational coefficients. Therefore,

    s_m,n = 𝐮^⊤ B^m C^n 𝐯 = α b_1^mc_1^n +β b_2^mc_1^n +γ nb_1^mc_1^n-1 = b_1^mc_1^n-1(α c_1 +β c_1(b_2/b_1)^m +γ n)

where α,β,γ∈. Hence s_m,n=0 is equivalent to

    α c_1 +β c_1(b_2/b_1)^m +γ n=0.

If β=0 then the solution is trivial. If β≠ 0, then after multiplying the above equation by the product of denominators of α,β,γ and c_1 we can rewrite it as

    cs^m/t^m = a+bn,

where a,b,c,s,t∈, t>0, (s,t)=1 and st=b_2b_1. If t>1, then it is not hard to see that the left hand side can be integer only for finitely many values of m, which can be effectively found, and for each of these values of m one can check if there exists corresponding n∈. If t=1, then the above equation reduces to

    cs^m≡ a  b.

This equation can also be algorithmically solved. For instance, one can start computing the values cs^m  b for m=0,1,2,…. Since there are only b-1 different residues modulo b, this sequence will be eventually periodic, and so we can decide whether cs^m  b is equal to a  b for some m and in fact find all such m.



It is interesting to note that in Cases (1) and (2) the solutions (m,n) of the equation s_m,n=0 are described by linear Diophantine equations, and only in Case (3) we have a linear-exponential equation. This agrees with an example from Proposition <ref>, in which matrix A has a single eigenvalue 1 of multiplicity 2 and matrix B has distinct eigenvalues 1 and 2.



In the above argument we used Theorem <ref> to obtain a bound on the
solutions of the equation as^mr^n+bs^mt^n+cq^mt^n=0, which is a special type of an S-unit
equation. This leaves open an interesting question of whether any S-unit equation can be encoded
into the ABCD-Z problem.


The obvious question is how hard would it be to solve n-LRSs, or in general multiplicative matrix
equations, in low dimensions. In fact we can show that the Skolem problem for n-LRSs of depth 2 is 
NP-hard. It is not direct but an easy corollary following the hardness proof of the mortality problem for 2 × 2 matrices <cit.>.


The mortality problem for integer matrices of dimension two is NP-hard.



Determining if the zero set of an n-LRS of depth 2 is empty is NP-hard.




In the paper <cit.> it was shown that the mortality problem is NP-hard for matrices from  extended by singular 2 × 2 matrices.
Actually without changing the class of matrices from the generator it is possible to 
design a matrix equation with 2 × 2 matrices from this generator such that the zero matrix is reachable if and only if
the solution of this matrix equation exist. Let us remind the main parts of the construction
proposed in <cit.>.



The structure of the  zero product can be only reached via a path represented in Figure <ref> which is encoding of the Subset Sum Problem.
Let us remind that every transition can be represented by a matrix of a polynomial size comparing to binary representation of powers used for  encoding of the Subset Sum Problem with k numbers.  Let us assume that each matrix representing the encoding of the transition from the node i to the node j with a label c is denoted as M_i,j,c.
Then one can encode in a single equation which is covering all possible paths in the graph represented in Figure <ref>, where 
alternative pair of paths need to be listed sequentially. Please note that alternative transitions will be used only ones in the equation to follow the path
that can lead to zero matrix. 

Although  we can encode original graph in Figure <ref> the solution could be modified to make the equation to be shorter
as the second identity does not need to be constructed because the whole length of possible paths can be fixed by the equation length. Here is the form
of the equation with unknowns y_1, … , y_2k+3 for which the problem is NP-hard: 

    M_P,1,^y_1 M_1,2,a^s_1^y_2 M_1,2,^y_3·…·  M_k,k+1,a^s_k^y_2k M_k,k+1,^y_2k+1 M_k+1,S,a^-x^y_2k+2
    M_S, P,^y_2k+3 = _2 × 2


Since matrix P in the above construction from  <cit.> is of the form
[ 1 0; 0 0 ]
 the whole product is equal to zero matrix if and only if the element (1,1) is equal to zero.
So determining if the zero set of an 2k+3-LRS of depth 2 based on the following form is empty

    [ 1 0 ]·  M_P,1,^y_1 M_1,2,a^s_1^y_2 M_1,2,^y_3·…·  M_k,k+1,a^s_k^y_2k M_k,k+1,^y_2k+1 M_k+1,S,a^-x^y_2k+2
    M_S, P,^y_2k+3·[ 1; 0 ]

should be NP-hard.


Another interesting observation is that the zero set of a 2-LRS is not necessarily semilinear, in contrast to the situation for 1-LRSs, which indicates that the Skolem problem for 2-LRSs is likely to be significantly harder than the Skolem problem for 1-LRSs even for sequences of small depth.


There exists a 2-LRS of depth 2 for which the zero set is not semilinear. 




Let u = (0, 1)^T, v = (1, -1)^T, A = [ 1 0; 1 1 ] and B = [ 1 0; 0 2 ]. Define

    s_n,m = u^TA^nB^mv =  (0,1)[ 1 0; 1 1 ]^n[ 1 0; 0 2 ]^m[  1; -1 ] =n-2^m.

Then s_n,m=0 if and only if n=2^m. Clearly, the zero set is not semilinear.






