# Checking a long product of matrices

Given a set of n-by-n integer matrices $\{A_1, \dots, A_m\}$, for a word $w=w_1 w_2\cdots w_l$ over $\{1, \dots, m\}$, we define $A_w:=A_{w_1}\cdots A_{w_l}$.

The question is to decide, given $\{A_1, \dots, A_m\}$ and a natural number $k$ in binary, whether there exists a word $w$ over $\{1, \dots, m\}$ whose length is bounded by $k$ such that $[A_w]_{1,1}>0$.

This problem is decidable, but its complexity is not clear to me. In particular, is it in PSPACE? (Note that because $k$ is given in binary, one cannot just guess a word $w$ in PSPACE.)

• If $n$ is a constant, the analysis is probably simpler. In that case, one can guess $w$ and the computation is inductively dominated by the product of two numbers of $k/2$ bits, so this should at least be in nondeterministic time bounded by $k^2$, hence NEXPTIME. If $n$ is not constant, this should also go through, but you have to account for matrix multiplication. Do you have any hint as of why this could go as low as PSPACE? Jan 16 '17 at 14:51
• no, I do not have a clue. I actually want to show it is exptime-hard at least, but do not know exactly how. Jan 16 '17 at 15:31
• So the important condition is that k ia given in binary. Jan 16 '17 at 15:51
• A related post (you might have already been aware about the content) can be found here: cstheory.stackexchange.com/questions/18319/… Jan 16 '17 at 17:47
• I would suspect that this is NEXP-complete (the upper bound follows from Michael's comment above). For the hardness, a much restricted variant of the unary version of this problem (same as above, but $k$ specified in unary now) with $A_i$ taken to be matrix representations of the generators of a finite group can encode subset sum/knapsack. And usually, by padding the binary version should be NEXP-hard (I'm waving my hands heavily here) Does this make sense? or is there an obvious flaw? May 17 '17 at 23:04