User Name Remember Me? Password

 Linear Algebra Linear Algebra Math Forum

 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 sub-matrixes by column, "H1" and "H2", satisfying: 1) both of the two sub-matrixes 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 sub-matrix "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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post gadmich Linear Algebra 2 June 11th, 2013 02:23 AM littlebu Algebra 6 December 6th, 2010 05:13 PM knowledgegain Linear Algebra 3 April 29th, 2009 05:49 AM jlfr Linear Algebra 2 March 30th, 2008 07:02 PM rere Linear Algebra 1 March 20th, 2008 03:47 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.      