## How to divide a matrix under certain constraints ?

As to a sparse binary matrix "H", its dimension is M*N. I want to get a submatrix "H_s" from "H", satisfying that the dimension of "H" is M*(2/N), and there are even number of 1's in each row of the submatrix "H_s" (if it is impossible, how to maximaze the number of rows with even number of 1's in "H_s" ).

How to choose the proper set of columns to form "H_s"? Is there any similar mathmatical problem?

I have tried the greedy algorithm, of course, it's not the best solution.