Complexity class of matrix generalization of knapsack problem

Question

Let $n$ be a natural number, $u_+,v_+,u_-,v_-$ be real or complex column vectors of length $n$, and $M_1,M_2,\ldots,M_k$ be a finite collection of $n\times n$ real or complex matrices.

Consider the problem of determining whether there exists a tuple $(\lambda_1,\lambda_2,\ldots,\lambda_\ell)$ of any finite length $\ell$ such that $u_+^T\left(\prod_{i=1}^\ell M_{\lambda_i}\right)v_+>1$, while $u_-^T\left(\prod_{i=1}^\ell M_{\lambda_i}\right)v_-<1$. What bounds can we place on the complexity class of this problem?

It is at least NP-hard, as it contains the knapsack problem, but I suspect it is much harder.

Answer 1

It is undecidable. I'll use this result: Given an finite set of integer matrices, it is undecidable whether there is a product with 0 in the upper-right corner. See for example this article.

So take such a finite set $S$ of $n\times n$ integer matrices and extend them to $(n{+}1)\times(n{+}1)$ by bordering with an additional row and column that are zero apart from 1 in the bottom right. Let $A'$ be the extended version of $A$. We obviously have $(A_1A_2)'=A'_1 A'_2$ for $A_1,A_2\in S$.

Now take these vectors of $n+1$ components: $u_+=(1,0,\ldots,0,2)^T$, $v_+=(0,\ldots,0,1,1)^T$, $u_-=(1,0,\ldots,0)^T$, $v_-=(0,\ldots,0,1,0)^T$. If I typed those in correctly, if the top-right entry of any product $P$ of members of $S$ is $\alpha$, then $u_+^TP'v_+=2+\alpha$ and $u_-^TP'v_-=\alpha$. Since $\alpha$ is an integer, $2+\alpha>1$ and $\alpha<1$ together imply that $\alpha=0$.