Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.