Assume a family of $n\times n$ integer matrices $\{M_a \mid a\in A\}$ for some finite set $A$, I want to decide whether for given vectors $\alpha$ and $\beta$,
$\alpha M(w) \beta=0$ for all $w\in A^{\leq n}$. Here $M(w)= M_{a_1}\cdot M_{a_2}\cdots M_{a_m}$ when $w=a_1\cdots a_m$, and $A^{\leq n}$ denotes the set of words over $A$ whose length is less than $n$.
I think this problem can be reduced to polynomial identity testing and has an RNC algorithm. But is there a better upper-bound or any nontrivial lower-bound?
