0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ What's wrong with Gaussian elimination? $\endgroup$
    – Tony Huynh
    Commented Aug 28, 2012 at 15:02
  • 2
    $\begingroup$ Or if you don't like Gaussian elimination, there's always (or at least, recently) eecs.berkeley.edu/~prasad/linsystems.pdf. $\endgroup$
    – Noah Stein
    Commented Aug 28, 2012 at 16:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Aug 29, 2012 at 0:22

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .