Decision procedure on linear transformations of integer vectors.

Question

I have an linear transformation of $k$-vectors of integers, $T$, and a vector of integers $v$. I would like to determine if there is some $n$ such that $T^nv$ is a vector that starts with zero.

$$ \exists n:(T^nv)_0 = 0 $$

For example if

$$ T = \left[\begin{array}{cccc} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array}\right] \\ v = \begin{bmatrix}-4\\0\\-1\\1\end{bmatrix} $$

then

$$ \begin{array}{rl} T^4v &= \left[\begin{array}{cccc} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array}\right]^4 \begin{bmatrix}-4\\0\\-1\\1\end{bmatrix} \\ &= \left[\begin{array}{cccc} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array}\right]^3 \begin{bmatrix}-1\\-4\\1\\1\end{bmatrix} \\ &=\left[\begin{array}{cccc} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array}\right]^2 \begin{bmatrix}-1\\-1\\-3\\1\end{bmatrix} \\ &=\left[\begin{array}{cccc} 0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array}\right] \begin{bmatrix}-6\\-1\\0\\1\end{bmatrix} \\ &= \begin{bmatrix}\color{red}0\\-6\\0\\1\end{bmatrix} \end{array} $$

So $n=4$. But for the vector

$$ v = \begin{bmatrix}1\\1\\1\\1\end{bmatrix} $$

There is pretty clearly no $n$ that satisfies (we can use induction to show that all the entries of the vector will remain positive).

I have been trying to come up with a general decision procedure but I have not been able to get much of anywhere.

What procedure could I use to determine if there is such an $n$?

Answer 1

Unfortunately, existence of an algorithm for this problem is open.

Here are a few links and partial results:

• Skolem problem at Wikipedia
• Terence Tao's blog: effective Skolem-Mahler-Lech theorem
• Proof that the set is semilinear
• Skolem's Problem - On the Border between Decidability and Undecidability

The problem in those links is stated using a linear recurrence relation, which is equivalent to the matrix formulation (see, for example, lemma 1.1 in the last link)

It definitely feels that there should be an algorithm, but we haven't found it yet. If the input contains multiple matrices $M_1, \dots, M_k$ and you're interested whether the product $M_{i_1} M_{i_2} \dots M_{i_n}$ has a 0 entry in a corner, this is known to be undecidable: see this link about the matrix mortality problem.