# Checking if a binary vector lies in the affine span of given binary vectors

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.

-
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

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.