# Thread: Binary matrix combinatorics

1. ## 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!

2. 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

?

3. 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

4. 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.

5. 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.

6. 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.

7. You are right again. Sorry!