The orbit problem is the decision problem of determining, for a square matrix 
and vectors 
and 
over the rational numbers,
whether there is a nonnegative integer 
such that
 |
Equivalently, it asks whether 
belongs to the forward orbit 
. Kannan and Lipton (1986) proved that the orbit
problem is decidable in polynomial time.
A higher-dimensional variant replaces the target vector by a subspace 
and asks whether
 |
for some nonnegative integer 
. If 
is the hyperplane 
, this condition is equivalent to 
for 
. The recurrence
sequence 
satisfies a linear recurrence equation,
so this special case is the Skolem problem.
