4

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?

Peter Purecell
  • 41
  • 1
  • 2
    Is the family ${M_a : a \in A}$ fixed and $n$ is the only input? Or is the family also part of the input? Related question: http://cstheory.stackexchange.com/questions/17713/checking-if-all-products-of-a-set-of-matrices-eventually-equal-zero/17748#17748 – Joshua Grochow Feb 11 '14 at 18:11

0 Answers0