# Decision procedure on linear transformations of integer vectors.

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$$?

• If 𝑇 is diagonalisable, then your problem is equivalent to verify whether $\exists n \in \mathbb{N}$ such that $\sum_{i}^{k}c_{i}a_{i}^{n}=0$, for $c_{i}, a_{i} \in \mathbb{C}$. I do not know if it is an easy task – Alex Silva Apr 5 at 20:42
• @AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$? – Sriotchilism O'Zaic Apr 5 at 20:52
• $T^{n} = PD^{n}P^{-1}$. Thus, $(PD^{n}P^{-1})v=[0;u]$. The first row of $PD^{n}$ is $[p_{1}\lambda_{1}^{n} \cdots p_{k}\lambda_{k}^{n}]$, where $\lambda_{i}$ are the diagonal elements of $D$. Now $P^{-1}v$ is a column vector, say $w$. Then $$[p_{1}\lambda_{1}^{n} \cdots p_{k}\lambda_{k}^{n}]w = 0 \implies$$ $$\sum_{i}^{k}c_{i}\lambda_{i}^{n} = 0.$$ Actually, $a_{i}=\lambda_{i}$. – Alex Silva Apr 5 at 21:03
• @AlexSilva Then $c_i=p_i(P^{-1}v)_i$? – Sriotchilism O'Zaic Apr 5 at 21:30
• Yes! Exactly! :) – Alex Silva Apr 5 at 21:41

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.
• I don't know much more about the problem, behind what I could skim from the sources. Wikipedia states that there is a known algorithm for recurrences of degree at most 4 (this probably translates to 4x4 matrices), and additionally it's decidable whether set of $n$'s is finite or infinite; but if it's finite, we can't tell whether it's empty or not. – sdcvvc Apr 6 at 0:19