Minimal basis for set of binary vectors using XOR - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:48:23Z https://cs.stackexchange.com/feeds/question/53331 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/53331 8 Minimal basis for set of binary vectors using XOR Martin Ender https://cs.stackexchange.com/users/25735 2016-02-19T11:10:33Z 2016-02-19T12:52:11Z <p>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).</p> <p>In a way, this is a form of <a href="https://en.wikipedia.org/wiki/Principal_component_analysis">PCA</a> for binary vectors. While searching for literature on this problem, I came across the <a href="http://people.mpi-inf.mpg.de/~pmiettin/papers/dbp.pdf">Discrete Basis Problem</a> also discussed in <a href="https://helda.helsinki.fi/bitstream/handle/10138/21376/matrixde.pdf">this PhD thesis</a>, 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.</p> https://cs.stackexchange.com/questions/53331/-/53337#53337 11 Answer by Yuval Filmus for Minimal basis for set of binary vectors using XOR Yuval Filmus https://cs.stackexchange.com/users/683 2016-02-19T12:26:57Z 2016-02-19T12:26:57Z <p>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.) </p>