Given a set of (0,1)-vectors, find a subset which adds to the zero vector mod 2

Question

I am reading Quadratic sieve in wiki and it present the next problem:

Given a set of (0,1)-vectors, find a subset which adds to the zero vector mod 2

My question is simple: How to solve it? Wiki suggest using Gaussian elimination but I don't get it.

Answer 1

Gaussian elimination on such a set of vectors, written simultaneously in the solution domain and in problem domain:

Given: I have a set of products of powers of primes, $x_i = p_1^{\alpha_{i,1}} \cdot p_2^{\alpha_{i,2}} \dots p_k^{\alpha_{i,k}}$. I wish to find subsets of these where the product of the members of the subsets is a square. That is, I want to find subsets of these whose product has all even exponents. Since I only care whether the resulting exponents are even or odd, I encode these as vectors $x_i \mapsto (\alpha_{i,1} \pmod 2, \alpha_{i,2} \pmod 2, \dots, \alpha_{i,k} \pmod 2)$. Collect these vectors together into a matrix, where each vector is one row. Gaussian eliminate this matrix:

1. Declare all vectors unfinished.
2. Find a vector with a nonzero column $1$, associated with $x_{k_1}$. Sort that vector to the top of the unfinished set. Add that vector to every other vector that has a $1$ in the first column. Since $1+1 \pmod{2} = 0$, this leaves only the first vector with a $1$ in the first column. Say $p_1 = 2$. We have found an $x_{k_1}$ having an odd power of $2$ in its prime power representation. We have multiplied it with every other $x_i$ that has an odd power of $2$, yielding combinations of the $x_i$ whose products have an even power of $2$.
3. Ignore the first row and repeat the procedure on the remaining rows, where now we only eliminate "$1$"s in the second column. That is, we replace the remaining $x_i$ with their products with one of the $x_i$ that has an odd power of $3$. Then we "backsubstitute": if the first row had a "$1$" in the second column, we eliminate that one as well with the new second row.
4. Recurse until you exhaust columns or rows. If you find a column of all zeroes, skip that column, because you need take no action to clear the "$1$"s from that column; either your procedure for generating the $x_i$ didn't include any odd powers of that prime, or the multiplications that you have been performing during Gaussian elimination have made combinations of the $x_i$ that now have only even powers of that prime.
5. You now have a matrix where each column only contains one "$1$" and the rows with those "$1$"s have been sorted to the top of the matrix. It is possible that you have rows containing only zeroes. These rows correspond to products of the $x_i$ that have only even powers of the primes involved. If oyu ran out of rows first, you probably have no rows that are all zeroes -- we need more vectors, so we need to go generate more $x_i$, append them to this table, use the existing "finished vectors" to eliminate "$1$"s in the new vectors and hope we can accumulate enough $x_i$ to produce a row of all zeroes.

Thus, you go from a collection of smooth numbers to a collection of square smooth numbers. (Possibly less smooth if you are using large prime variants.) Note that to explicitly have these combinations, it is useful to have another column (or set of columns) in which you track which combinations of the $x_i$ have been combined to make the row you currently have during the elimination stage.

Edit:

Given $k$ primes and $m$ smooth numbers ...

Termination: In each round of elimination, we find a single row retaining a "$1$" in the current clearing column, or the entire column is "$0$"s. Either way, we finish one more column and may finish one more row (sorted to the top of the unfinished part). At every round we reduce the number of uncleared columns by at least one and reduce the number of "has more than one '$1$'s" rows by at least zero. If we can complete $k$ rounds, we must have cleared all the columns. If we cannot complete $k$ rounds, but have cleared all the columns (due to discovering columns of "$0$"s), we still terminate. If we finish the last column first, then the "$1$" in the last column is in the lowest row with a "$1$" remaining in it. All lower rows contain only "$0$"s, so no further reduction is possible in those rows. (This is good, rows of all "$0$"s correspond to combinations of the $x_i$ whose product is a square.) If we finish the last round, but we now have a "$1$" in each row, we need at least one more $x_i$ to reduce with these to get a square combination; go find one. If we cannot complete $k$ rounds because we have run out of lower rows to sort to the top of the unfinished part of the matrix, we terminate without finding combinations of the $x_i$ which produce squares; go get more $x_i$ so that we can continue. In all cases, the elimination terminates. In some of those cases, the Quadratic Sieve must go find more smooth numbers to provide to the elimination. It is convenient to keep the matrix you have to allow for rapid reduction of new $x_i$.

Efficiency: Each step involves at most $m$ vector additions involving at most $k$ of $\pmod 2$ additions. This is at most $O(k m)$ bit operations to clear the "$1$"s from a column, so at most $O(k^2 m)$ bit operations to perform the entire elimination. (In practice, it isn't this bad: not every column is all "$1$"s by the time you are clearing it.)