May 30th, 2012, 07:06 PM  #1 
Newbie Joined: May 2012 Posts: 3 Thanks: 0  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. 
June 4th, 2012, 10:27 PM  #2 
Newbie Joined: May 2012 Posts: 3 Thanks: 0  Re: Help: matrix problem
Can someone offer help? Thank you!


Tags 
matrix, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Matrix  problem  gadmich  Linear Algebra  2  June 11th, 2013 02:23 AM 
Help with Matrix problem  littlebu  Algebra  6  December 6th, 2010 05:13 PM 
Matrix Problem  knowledgegain  Linear Algebra  3  April 29th, 2009 05:49 AM 
Matrix problem  jlfr  Linear Algebra  2  March 30th, 2008 07:02 PM 
Matrix problem...help..help..  rere  Linear Algebra  1  March 20th, 2008 03:47 AM 