My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 30th, 2012, 08: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.
tweedle is offline  
 
June 4th, 2012, 11:27 PM   #2
Newbie
 
Joined: May 2012

Posts: 3
Thanks: 0

Re: Help: matrix problem

Can someone offer help? Thank you!
tweedle is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

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 03:23 AM
Help with Matrix problem littlebu Algebra 6 December 6th, 2010 06:13 PM
Matrix Problem knowledgegain Linear Algebra 3 April 29th, 2009 06:49 AM
Matrix problem jlfr Linear Algebra 2 March 30th, 2008 08:02 PM
Matrix problem...help..help.. rere Linear Algebra 1 March 20th, 2008 04:47 AM





Copyright © 2019 My Math Forum. All rights reserved.