# Binary matrix combinatorics

• Jan 18th 2011, 09:21 PM
Greg98
Binary matrix combinatorics
Hello,
the problem is to count how many $\displaystyle n \times n$ binary matrices there are with following properties
i. every column must have even number of $\displaystyle 1$'s
ii. every row must have even number of $\displaystyle 1$'s

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

$\displaystyle \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 $\displaystyle n \times n$ binary matrices is calculated with $\displaystyle 2^{n^2}{$. So, I though maybe substracting the matrices without even number of $\displaystyle 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!
• Jan 18th 2011, 09:48 PM
aman_cc
To understand the question better
1.
Isn't for 2x2

0 0
0 0

2. For 3x3
1 1 0
0 1 1
1 0 1

and

1 1 0
1 1 0
0 0 0

?
• Jan 18th 2011, 10:20 PM
aman_cc
I think the answer is $\displaystyle 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
• Jan 19th 2011, 05:00 AM
Greg98
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.
• Jan 19th 2011, 05:19 AM
Greg98
Hmm. There's one problem with your formula. For $\displaystyle 2 \times 2$ it gives $\displaystyle 4$. But I think there's only $\displaystyle 2$ of those $\displaystyle 2 \times 2$ matrices. All $\displaystyle 2 \times 2$ matrices:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. $\displaystyle \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.
• Jan 19th 2011, 06:45 PM
aman_cc
Quote:

Originally Posted by Greg98
Hmm. There's one problem with your formula. For $\displaystyle 2 \times 2$ it gives $\displaystyle 4$. But I think there's only $\displaystyle 2$ of those $\displaystyle 2 \times 2$ matrices. All $\displaystyle 2 \times 2$ matrices:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. $\displaystyle \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.
• Jan 19th 2011, 08:05 PM
Greg98
You are right again. Sorry!