
Help: matrix problem
Hello, I have a problem about the division of matrix. Hope someone can help.
(1) Problem:
A sparse matrix "H", its elements are only "0" or "1", and the dimension is M*N.
Now, I want to divide the matrix "H" into two submatrixes by column, "H1" and "H2", satisfying: 1) both of the two submatrixes have the dimension M*(2/N); 2) there are even number of 1's in each row of the submatrix "H1" (if it is impossible, the number of rows with even number of 1's in "H1" should be maximazed).
Actually, this problem is equivalent to choose a proper set of columns of "H" to form "H1", is there any similar mathematical problem?
(2) Example:
H=
0 1 1 0 0 1 0 1 0 1
1 0 1 1 1 0 1 0 0 0
0 1 0 0 1 1 0 0 1 1
0 1 1 0 0 0 1 0 1 0
1 0 0 1 0 0 1 1 0 1
Then, obviously, one possible "H1" is made up of the first five columns.
(3) Possible solution:
1) Exhaustion method. This would be impractical when N becomes large;
2) Greedy method. Each time I assign a new column to the submatrix "H1", I choose the one from the rest of columns of "H", which maximizes the current number of rows with even number of 1's in "H1". Obviously, this greedy algorithm is not the optimal solution, it there any better method?
(4) Matlab code for examine algorithms:
M = 500; %the number of rows in H
N = 1000; %the number of coluns in H
%generate the submatrix H_1
%there should be even number of 1's in each row of H_1 by the following way
H_1_1 = sprand(500,250,0.1);
H_1_1(H_1_1<0.5) = 0;
H_1_1(H_1_1>=0.5) = 1;
H_1 = [H_1_1,H_1_1];
%generate the submatrix H_2
H_2 = sprand(500,500,0.1);
H_2(H_2<0.5) = 0;
H_2(H_2>=0.5) = 1;
%the sparse matrix H
H = [H_1,H_2];
H = H(:,randperm(N)); %random interleaving
In the matrix "H" generated by the above matlab codes, there must be "H_1". Thus, one can check their algorithm used the "H" generated above.