# How to solve sparse binary system of linear equations

I have a binary square matrix $$A$$ of size $$n=n_1+n_2$$. I have to solve system of linear equations $$AX=b$$. I known for each row out of first $$n_1$$ entries $$l_1$$ are 1 and next $$n_2$$ entries $$l_2$$ are 1 where $$l_1\ll n_1$$ and $$l_2 \ll n_2$$. So matrix is very much sparse. What is the time complexity to find the solution? My matrix is very sparse like $$n_2=2^{20}$$ and $$l_2=20$$.

• Are you assuming conventional arithmetic or arithmetic modulo 2? Do you want to find an integer solution, or would a real solution be OK? – Brian Borchers Jan 6 at 23:25
• Operations are Arithmetic mod 2 and I need binary solutions. – user12290 Jan 8 at 0:45