Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m $

and a vector $ v \in (\mathbb Z/2 \mathbb Z)^m $

I need to find the better algorithm which answers the question:

Does $v$ is in the vector space spanned by $e_1,\dots,e_n $ ?

share|improve this question
3  
What's wrong with Gaussian elimination? –  Tony Huynh Aug 28 '12 at 15:02
2  
Or if you don't like Gaussian elimination, there's always (or at least, recently) eecs.berkeley.edu/~prasad/linsystems.pdf. –  Noah Stein Aug 28 '12 at 16:20
1  
About Gaussian elimination: if you want to test many $v$s for the same $\lbrace e_i\rbrace$ then start by putting the vectors into reduced row-echelon form. Then the test just a few vector additions. Also if you are serious about practical efficiency, use 1 bit for each entry and bitwise exclusive OR for vector addition. –  Brendan McKay Aug 29 '12 at 0:22
add comment

1 Answer 1

Thinking of your vectors as (column) bitvectors, here is a concrete description of how you can proceed, using (non-reduced) column-echelon form for a basis of $\langle e_1,\ldots,e_n\rangle$. Separate your vectors $e_i$ into a "basis" (initally empty) and a "rest" (initially everything). For each bit position in order, search a vector in the rest where this bit is set (1). If one is found, move that vector into the basis, and clear any bits that are set in that position in the rest, and in $v$, by adding (XOR) that basis vector. If no vector in the rest is found, but the bit in that position in $v$ is set, then this proves $v\notin\langle e_1,\ldots,e_n\rangle$; conclude that and stop. If you reach the final bit position without this happening then $v$ has been reduced to $0$ which proves $v\in\langle e_1,\ldots,e_n\rangle$.

If you have just one vector $v$, then you can replace the basis by the bitbucket, as its vectors are clearly never used once they have settled there. If you have more vectors to test though, keeping a list of basis vectors and their initial set bit positions may speed up the test for successive $v$s. I'll let you estimate the complexity of this procedure yourself; I don't think there is much hope of doing better.

share|improve this answer
add comment

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.