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

Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in the affine $\mathbb R$-span of $\{x_1,\ldots,x_N\}$?

By "efficient" I mean faster than having to test linear independence, i.e., something that exploits the fact that the vectors are binary.

share|improve this question
3  
Isn't this problem essentially equivalent to testing for linear independence? (That is, determining if a new binary vector is in the span of a collection of presumed-independent binary vectors.) That is, if we could do your problem quickly, then we could also test for dependence quickly, and vice versa, presumably exploiting the binary nature of the vectors in both cases. –  Joel David Hamkins Jun 18 '13 at 23:49
    
A fast algorithm for testing the linear independence of binary vectors would solve the problem (by just appending an extra unit coordinate to all the vectors and do the linear independence test). I don't know if the other direction also holds. But: is there such a fast algorithm, for either the affine or linear independence case? –  Andre Jun 19 '13 at 3:34
add comment

1 Answer 1

Finding relations among binary vectors is a key step in the number field sieve. I'm not sure what the state of the art is now, but one of the earliest efficient methods that was used applies if your system of vectors is sparse. (It is a probabilistic algorithm.)

Peter L. Montgomery. A block Lanczos algorithm for finding dependencies over $GF(2)$, Advances in Cryptology – EUROCRYPT ’95, Lecture Notes in Computer Science, vol. 921, Springer-Verlag, 1995, pp. 106–120.

There are references to a number of earlier algorithms in the introduction.

share|improve this answer
    
Thanks for the pointers. However, my problem is not in GF(2): all vectors are binary, but we're still in the field of real numbers (with the usual addition and not GF(2) addition). The coefficients of the affine combination can be arbitrary, not necessarily binary-valued. –  Andre Jun 19 '13 at 12:16
    
That was very nonobvious and I have taken the liberty of editing the question to reflect it. –  Allen Knutson Jun 19 '13 at 13:32
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.