5
$\begingroup$

What is the number of binary $n\times n$ matrices whose every contiguous $2\times 2$ submatrix has exactly two ones (zeroes)?

That is, if $a_{ij}\in\{0,1\}$ for $i,j\in\{1,2,\dots,n\}$ are matrix entries, then $$a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1}= 2$$

for $i \in \{1,\dots,n-1\}$ and $j \in \{1,\dots,n-1\}$, where $n\ge 2$.

After writing out some cases for small $n$, it appears to me that the answer might be $2^{n+1}-2$.

Is there an elegant way to prove this?


For example, for $n=2$ we have $6$ matrices

$$ \begin{bmatrix} 1 &0 \\ 1 &0 \\ \end{bmatrix}, \begin{bmatrix} 1 &1 \\ 0 &0 \\ \end{bmatrix}, \begin{bmatrix} 1 &0 \\ 0 &1 \\ \end{bmatrix}, \begin{bmatrix} 0 &1 \\ 1 &0 \\ \end{bmatrix}, \begin{bmatrix} 0 &0 \\ 1 &1 \\ \end{bmatrix}, \begin{bmatrix} 0 &1 \\ 0 &1 \\ \end{bmatrix}. $$

For example, for $n=3$ we have $14$ matrices:

  1. $4$ rotations of $\begin{bmatrix} 1 &0 &1 \\ 1 &0 &1 \\ 0 &1 &0 \\ \end{bmatrix}$, $2$ rotations of $\begin{bmatrix} 1 &0 &1 \\ 1 &0 &1 \\ 1 &0 &1 \\ \end{bmatrix}$, $1$ matrix $\begin{bmatrix} 1 &0 &1 \\ 0 &1 &0 \\ 1 &0 &1 \\ \end{bmatrix}$.
  2. One additional $(J-M)$ matrix for every of $7$ matrices $M$ from previous case.

$J$ is a matrix filled with $1$'s at every entry.

$\endgroup$
0
4
$\begingroup$

The first row can be any of the $2^n$ members of $\{0,1\}^n$. Given the $k$'th row $(x_1, \ldots, x_n)$, the $k+1$'th row can always be $(1-x_1, \ldots, 1-x_n)$. The only other possibility is that the $k+1$'th row is $(x_1,\ldots, x_n)$, but only if the $k$'th row is alternating $(0,1,0,1,\ldots)$ or $(1,0,1,0,\ldots)$. Now use induction on the number of rows...

$\endgroup$
2
  • $\begingroup$ Induction on rows (columns), neat! $\endgroup$ – Eod J. Jan 24 at 18:43
  • $\begingroup$ Your solution is incorrect because you're missing some cases. If your second case happens there is no need of the row to be alternating but it can repeat, too. Also your proof of the first case doesn't contain that this method counts all cases. $\endgroup$ – Aryaaaaan Jan 24 at 18:52
4
$\begingroup$

We will casework on the numbers in the first row of the $n*n$ table in two cases:

  1. The first row is $1,0,1,0,\dotsb$ or $0,1,0,1,\dotsb$
  2. There are two consecutive elements in the first set. First of all, it is clear that in the first case the answer is exactly $2^n$:
    Name every row without consecutive elements as simple rows. Now if the first case happens, each row can be a simple row and it is all of the cases without consecutive elements in the first row so, the first case is of $2^n$ cases.
    On the other in the second case we will prove that the rest of the table can be constructed uniquely:
    The two unit squares under the two consecutive elements of the first row are chosen uniquely and based on these two, the rest of the second row is constructed uniquely. Similarly, the second row has at least two consecutive elements (the two unit squares under the two consecutive elements in the first row are the same) so the third row is constructed uniquely and so on. So in the second case, the rest of the table is constructed uniquely. So the number of cases of the tables of the second kind is equal to the number of binary sets except the two simple sets which is $2^n-2$ so the answer is equal to $2^n+2^n-2=2^{n+1}-2$
$\endgroup$
1
  • $\begingroup$ Further note: two consecutive elements mean two unit squares with equal numbers that are adjacent to each other $\endgroup$ – Aryaaaaan Jan 24 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.