# Find all linearly dependent subsets of this set of vectors

I have vectors in such form

(1 1 1 0 1 0)
(0 0 1 0 0 0)
(1 0 0 0 0 0)
(0 0 0 1 0 0)
(1 1 0 0 1 0)
(0 0 1 1 0 0)
(1 0 1 1 0 0)


I need to find all linear dependent subsets over $Z_2$.

For example 1,2,5 and 3,6,7.

EDIT (after @rschwieb)

The answer for presented vectors: 521 642 763 6541 7432 75431 765321

I did by brute force. I mean i wrote program to iterate through all variants in $${7 \choose 3} {7 \choose 4} {7 \choose 5} {7 \choose 6} {7 \choose 7}$$ 99 in total.

But i just thought what some method exist for such task. For now im trying to implement http://en.wikipedia.org/wiki/Quadratic_sieve . Code incorporated in whole program. I plan to put it here then i organize it well.

-
@Yuki, i need solution for general case, now i can propose only brute force. – Yola Aug 15 '12 at 10:15

## 2 Answers

Let us denote with $M$ (the transpose) of your matrix, $$M= \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$ As rschwieb already noted, a vector $v$ with $Mv=0$ solves your problem.

Using elementary row operation (modulo 2), we can easily bring it on the row echelon form $$M' = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$

Now, it is easy to see that the vectors $$v = \begin{pmatrix} \alpha \\ \alpha +\beta +\gamma \\ \gamma \\ \beta +\gamma \\ \alpha \\ \beta \\ \gamma \\ \end{pmatrix}$$ parameterized by $\alpha$, $\beta$, $\gamma$ are in the kernel of $M'$ and thus in the kernel of $M$. Setting $\alpha =0,1$, $\beta=0,1$, and $\gamma=0,1$, we obtain the $2^3=8$ solutions. The solution with $\alpha=\beta=\gamma=0$ is trivial, so there are 7 nontrivial solutions.

-

If I consider what you wrote as a matrix $M$, every linearly dependent subset will be uncovered by finding a nonzero vector $x$ such that $xM=0$.

Since $x$ has 7 unknown binary entries, you can just look at the system of equations in seven unknowns $xM=0$, and do cases. That would be $2^7$ possiblities for $x$, however some of them will be ruled out by the system of equations, so this is less work than 'brute force'.

FYI if you format your question more politely (and include an actual question in the body of your post) and include any partial work you have done, you will get more help faster.

-