Results 1 to 6 of 6

Math Help - Boolean Matrix : Minimum number of columns

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    3

    Boolean Matrix : Minimum number of columns

    Hi all,

    I was trying to solve a programming problem.. and it narrowed down to this question.

    I am given N and M (both non-zero integers and M<N).. I need to construct a boolean matrix such that
    1. Number of rows have to be equal to N
    2. Every column must have M 1's exactly(rest 0)
    3. No two rows should be the same.

    I need to get the minimum number of columns for it, given N and M.

    For eg: Assume, I am given (4,2)..
    I can have a matrix like,
    00
    01
    10
    11

    satisfying all the above conditions. So the answer here would be 2 columns.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by narjunkumar View Post
    Hi all,

    I was trying to solve a programming problem.. and it narrowed down to this question.

    I am given N and M (both non-zero integers and M<N).. I need to construct a boolean matrix such that
    1. Number of rows have to be equal to N
    2. Every column must have M 1's exactly(rest 0)
    3. No two rows should be the same.

    I need to get the minimum number of columns for it, given N and M.

    For eg: Assume, I am given (4,2)..
    I can have a matrix like,
    00
    01
    10
    11

    satisfying all the above conditions. So the answer here would be 2 columns.
    You need to construct the matrix AND get the minimum number of columns, or would it be enough just to get the minimum number of columns?

    There is an easy lower bound which is ceil(log(N)/log(2)).

    The lower bound can't also be the answer though because consider (N,M)=(5,4)

    Each column has exactly one 0. Therefore if we try to construct with lower bound of 3 columns, we must have at least two rows filled with 1's, thus we need 4 columns.

    Possibly a generalization can be found from here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    3
    We need to get the minimum number of columns only. Since there could be multiple matrices with the same conditions as above. Let me put down the original question.. so that we can think of the approach.

    The question is that I have N cards.. each card having M numbers.. (M<N).. you think of a number.. and I show you each card asking whether your number is there or not.. so that I can guess the number. Given, N and M, what is the minimum number of cards I need so that I can correctly guess the number in your mind.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by narjunkumar View Post
    We need to get the minimum number of columns only. Since there could be multiple matrices with the same conditions as above. Let me put down the original question.. so that we can think of the approach.

    The question is that I have N cards.. each card having M numbers.. (M<N).. you think of a number.. and I show you each card asking whether your number is there or not.. so that I can guess the number. Given, N and M, what is the minimum number of cards I need so that I can correctly guess the number in your mind.
    What kind of "numbers" are we talking about? Must they be distinct? The problem is terribly vague.

    Maybe if you gave a concrete example with N=4 or N=5 we would be able to understand what you mean.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2010
    Posts
    3
    Let me give you an example with N=4, and M=2. Now, you can think of any number from 1 to 4. I am going to show you cards, with each card having 2 numbers in it, where each number is between 1 to 4. (Since M=2). For this problem, I know that 2 cards would be enough.
    I show you Card1(1,2) and Card2(2,3).. and ask you whether the number you thought of is there or not. And based on your answer I can ascertain what number you thought of. (00 - 4; 01 = 3; 10 - 1; 11 - 2).

    For a case, where N=3, and M=1.. the answer is that I would have to show you two cards at least.. each card having 1 number written in it.. to make the guess.

    So for any N and M.. my idea was that.. assume you need minimum K cards.. so I would get a boolean number as answer. Every answer, I map to a particular number in N.. (lets say... 000111.. (length K) is mapped to 1). Thus you would have N possible answers, which means the boolean matrix will have N rows.. and it will have K columns.. with each column having exactly M 1's. (since every card has M numbers in it).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by narjunkumar View Post
    Let me give you an example with N=4, and M=2. Now, you can think of any number from 1 to 4. I am going to show you cards, with each card having 2 numbers in it, where each number is between 1 to 4. (Since M=2). For this problem, I know that 2 cards would be enough.
    I show you Card1(1,2) and Card2(2,3).. and ask you whether the number you thought of is there or not. And based on your answer I can ascertain what number you thought of. (00 - 4; 01 = 3; 10 - 1; 11 - 2).

    For a case, where N=3, and M=1.. the answer is that I would have to show you two cards at least.. each card having 1 number written in it.. to make the guess.

    So for any N and M.. my idea was that.. assume you need minimum K cards.. so I would get a boolean number as answer. Every answer, I map to a particular number in N.. (lets say... 000111.. (length K) is mapped to 1). Thus you would have N possible answers, which means the boolean matrix will have N rows.. and it will have K columns.. with each column having exactly M 1's. (since every card has M numbers in it).
    Thanks, it's a lot clearer now. I think you successfully came up with an equivalent problem to the original.

    Let f(N,M) represent the minimum number of columns. We can simplify by noticing that f(N,M)=f(N,N-M) and thus we only need to consider M up to floor(N/2).

    While drawing diagrams to get a handle on things, note that: switching any two rows of the matrix has no effect. Thus we can assume that all the 1's in the first column appear in the upper left, with the rest of the cells in that column being zero.

    Also, switching columns has no effect, so we can draw our diagrams basically working from the upper left to the lower right.

    This is what I draw for (N,M)=(7,3)



    This suggests a possible algorithm, which may or may not be suitable for the constraints of the problem. Please give more information about the constraints on N, and number of test cases.

    Also I'm curious to know where this problem came from. I am fairly active on SPOJ these days, plus some other sites sometimes.
    Attached Thumbnails Attached Thumbnails Boolean Matrix : Minimum number of columns-guessmatr.png  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Null space for Matrix with similar columns
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 17th 2011, 02:08 PM
  2. Finding recessive rows and columns in a matrix
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 21st 2011, 11:23 AM
  3. linear dependence of matrix columns
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 27th 2011, 09:29 AM
  4. Smallest number of linearly dependent columns?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 3rd 2009, 04:40 PM
  5. Figuring out rows and columns after matrix multiplication
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 23rd 2009, 05:18 AM

Search Tags


/mathhelpforum @mathhelpforum