Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to find another set of binary $n$-vectors $B \subset \{0,1\}^n$, with minimal size $|B|$, such that every vector in $S$ can be expressed by the XOR results of some subset of $B$ (so $B$ is essentially a basis for $S$ using XOR instead of addition and allowing only binary coefficients in the linear combination).

In a way, this is a form of PCA for binary vectors. While searching for literature on this problem, I came across the Discrete Basis Problem also discussed in this PhD thesis, which seems closely related. Instead of XOR it uses OR, and here $|B|$ is an additional input (and the task is it to minimise the error in representing $S$ with vectors from $B$). This problem is NP-hard. Does the same apply to the problem I've presented above, or is there an efficient solution? Any pointers to existing literature would be much appreciated.

share|cite|improve this question
up vote 11 down vote accepted

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)

share|cite|improve this answer
That's a great opportunity to brush up your linear algebra. – Yuval Filmus Feb 19 at 12:34
Thanks for making me facepalm pretty hard. It's really obvious now... ;) – Martin Ender Feb 19 at 13:00

Your Answer


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.