Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@Yuki, i need solution for general case, now i can propose only brute force. –  Yola Aug 15 '12 at 10:15
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.