3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Alex Silva Apr 5 at 20:42
  • $\begingroup$ @AlexSilva I'm a little confused. What are $c$ and $a$ here? How are they related to $T$ and $v$? $\endgroup$ – Sriotchilism O'Zaic Apr 5 at 20:52
  • $\begingroup$ $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}$. $\endgroup$ – Alex Silva Apr 5 at 21:03
  • $\begingroup$ @AlexSilva Then $c_i=p_i(P^{-1}v)_i$? $\endgroup$ – Sriotchilism O'Zaic Apr 5 at 21:30
  • $\begingroup$ Yes! Exactly! :) $\endgroup$ – Alex Silva Apr 5 at 21:41
2
+250
$\begingroup$

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

Here are a few links and partial results:

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.

$\endgroup$
  • $\begingroup$ Wow thanks! That's a bit unfortunate. I haven't read the last two sources in their entirety (I'm going to take a more careful look when I have the time), but I was wondering if you were aware of any large sub-classes for which there are known algorithms. $\endgroup$ – Sriotchilism O'Zaic Apr 6 at 0:12
  • 1
    $\begingroup$ 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. $\endgroup$ – sdcvvc Apr 6 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.