Results 1 to 7 of 7

Math Help - Binary matrix combinatorics

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    Binary matrix combinatorics

    Hello,
    the problem is to count how many n \times n binary matrices there are with following properties
    i. every column must have even number of 1's
    ii. every row must have even number of 1's

    For 1 \times 1 matrices there is none. For 2 \times 2 matrices there is one:

    \left(\begin{array}{cc}1&1\\1&1\end{array}\right)

    I think for 3x3 there isn't any. Atleast I couldn't construct one, but I suck at Sudoku's.

    The number of square n \times n binary matrices is calculated with 2^{n^2}{. So, I though maybe substracting the matrices without even number of 1's from that number would help, but then we come the problem, how to pick out the correct matrices.

    Any help is appreciated. Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    To understand the question better
    1.
    Isn't for 2x2

    0 0
    0 0

    a valid answer?

    2. For 3x3
    how about
    1 1 0
    0 1 1
    1 0 1

    and

    1 1 0
    1 1 0
    0 0 0

    ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    I think the answer is 2^{(n-1)^2}
    (if the cases i listed above are right answer, which I think should be)

    Hint - induction. Can you attempt it with this hint?

    PS: It is a nice problem. Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39
    Yeah, you are right, those cases should be included too. Fooled myself to think, when there's no [mAth]1[/tex]'s in row/column, the amount is not even or odd (kinda undecidable or something). That's clearly wrong. I think I can make inductive proof for your formula. Thanks very much for help! It clarified my thoughts very well.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39
    Hmm. There's one problem with your formula. For 2 \times 2 it gives 4. But I think there's only 2 of those 2 \times 2 matrices. All 2 \times 2 matrices:

    0. \left(\begin{array}{cc}0&0\\0&0\end{array}\right)

    1. \left(\begin{array}{cc}0&0\\0&1\end{array}\right)

    2. \left(\begin{array}{cc}0&0\\1&0\end{array}\right)

    3. \left(\begin{array}{cc}0&0\\1&1\end{array}\right)

    4. \left(\begin{array}{cc}0&1\\0&0\end{array}\right)

    5. \left(\begin{array}{cc}0&1\\0&1\end{array}\right)

    6. \left(\begin{array}{cc}0&1\\1&0\end{array}\right)

    7. \left(\begin{array}{cc}0&1\\1&1\end{array}\right)

    8. \left(\begin{array}{cc}1&0\\0&0\end{array}\right)

    9. \left(\begin{array}{cc}1&0\\0&1\end{array}\right)

    10. \left(\begin{array}{cc}1&0\\1&0\end{array}\right)

    11. \left(\begin{array}{cc}1&0\\1&1\end{array}\right)

    12. \left(\begin{array}{cc}1&1\\0&0\end{array}\right)

    13. \left(\begin{array}{cc}1&1\\0&1\end{array}\right)

    14. \left(\begin{array}{cc}1&1\\1&0\end{array}\right)

    15. \left(\begin{array}{cc}1&1\\1&1\end{array}\right)

    Only 0. and 15. qualify, I think. So, we need new equation or I'm completely lost. Thanks.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Greg98 View Post
    Hmm. There's one problem with your formula. For 2 \times 2 it gives 4. But I think there's only 2 of those 2 \times 2 matrices. All 2 \times 2 matrices:

    0. \left(\begin{array}{cc}0&0\\0&0\end{array}\right)

    1. \left(\begin{array}{cc}0&0\\0&1\end{array}\right)

    2. \left(\begin{array}{cc}0&0\\1&0\end{array}\right)

    3. \left(\begin{array}{cc}0&0\\1&1\end{array}\right)

    4. \left(\begin{array}{cc}0&1\\0&0\end{array}\right)

    5. \left(\begin{array}{cc}0&1\\0&1\end{array}\right)

    6. \left(\begin{array}{cc}0&1\\1&0\end{array}\right)

    7. \left(\begin{array}{cc}0&1\\1&1\end{array}\right)

    8. \left(\begin{array}{cc}1&0\\0&0\end{array}\right)

    9. \left(\begin{array}{cc}1&0\\0&1\end{array}\right)

    10. \left(\begin{array}{cc}1&0\\1&0\end{array}\right)

    11. \left(\begin{array}{cc}1&0\\1&1\end{array}\right)

    12. \left(\begin{array}{cc}1&1\\0&0\end{array}\right)

    13. \left(\begin{array}{cc}1&1\\0&1\end{array}\right)

    14. \left(\begin{array}{cc}1&1\\1&0\end{array}\right)

    15. \left(\begin{array}{cc}1&1\\1&1\end{array}\right)

    Only 0. and 15. qualify, I think. So, we need new equation or I'm completely lost. Thanks.
    No, the formula I got gives 2 as well. Plz check again. In my formula n = 2. So you get 2^1 = 2.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39
    You are right again. Sorry!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of unique permutations random binary matrix
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 11th 2011, 09:51 AM
  2. Binary
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 20th 2009, 09:30 PM
  3. Binary Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 6th 2009, 01:05 PM
  4. Binary
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 1st 2008, 01:28 PM
  5. Binary Matrix
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 2nd 2008, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum