# 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?

-
What do you mean by "bit set"? – Qiaochu Yuan Jun 1 '12 at 14:27
@QiaochuYuan: $v$ has i-th bit set iff i-th element is equal to 1. I wanted to express, that there's exactly one 1 in every vector. – zxc Jun 1 '12 at 15:36

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.