4
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 18, 2013 at 23:49
  • $\begingroup$ 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? $\endgroup$
    – Andre
    Jun 19, 2013 at 3:34

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Andre
    Jun 19, 2013 at 12:16
  • $\begingroup$ That was very nonobvious and I have taken the liberty of editing the question to reflect it. $\endgroup$ Jun 19, 2013 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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