Atypical equation over matrices Let $M$ be a $n\times n$ matrix over $GF(2)$. Is there any standard algorithm to solve equations of the form
$M^{n-1}v_0 + M^{n-2}v_1+...+M^0v_{n-1}=const$
where $v_i$ are vectors with exactly one bit set? By "solve" I mean find all vectors $v_i$ that satisfy the equation. Is this a special case of some more generic "type" of equations?
 A: If we generalize it a bit, then the problem becomes NP-complete. Instead of taking powers of $M$ we take arbitrary matrices $M_0,\ldots,M_{n-1}$. So given a vector $c$, we ask whether there is a choice of one column from each $M_i$ that sum together (over $GF(2)$) to $c$.
The problem is clearly in NP, and here is a reduction from 3SAT. Suppose there are $m$ clauses and $n$ variables. Our column vectors will be of length $3m$, three bits for each clause. For each variable we will have a matrix with two non-zero columns, corresponding to the two assignment to the variable. The column will have a $1$ whenever the corresponding literal is true. For example, if the first clause is $x\lor y\lor z$ then the column corresponding to $x=1$ will start $100\ldots$, and the column corresponding to $x=0$ will start $000\ldots$. For each clause we will have another matrix with six different non-zero columns (and at least one zero column), each of which only non-zero on the corresponding three bits, and containing one of the values $100,010,001,110,101,011$. The target vector is the all one vector. I will leave you to check that the formula is satisfiable if and only if there is a solution to this instance.
What happens when you restrict the matrices to powers of some base matrix, I have no idea.
