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.



Complexity class of matrix generalization of knapsack problem
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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.45&rep=rep1&type=pdf).


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


