Given m & n, we have to find out the number of possible matrices of order m*n with the property that A(i,j) can be either 0 or 1 and that no contiguous sub-matrix of both length > 1 & breadth > 1 should have same entries i.e. all of its cells shouldn't be 0 or 1. For example if m = 2 & n = 2, the answer is 14: Total possibilities : 2 ^ (2 * 2); Invalid cases: when all 4 cells are 0 or 1. Therefore answer is 2 ^ (2 * 2) - 2 = 14. A sub-matrix of length > 1 & breadth = 1, also breadth > 1 & length = 1 is valid.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ It suffices that your matrix avoids $2 \times 2$-submatrices with all entries equal, since if you have a forbidden $3\times 3$-matrix or larger, it will automatically also contain a forbidden $2 \times 2$-matrix. Is it possible to count these using recursion maybe? $\endgroup$– Per AlexanderssonCommented Nov 11, 2012 at 15:20
-
$\begingroup$ @Per Alexandersson: It is evident that we'll have (m - 1) * (n - 1) sub-matrices of order 2 * 2. My strategy is: start picking up 2 * 2 sub-matrices starting from top-left corner i.e. containing cells A(0,0), A(0,1), A(1,0), A(1,1) of main matrix; fill it with 0 and count the total number of matrices having these cells filled in this manner. Now, I proceed on to counting those matrices where the next 2 * 2 matrix i.e. A(0,1), A(0,2), A(1,1), A(1,2) are filled with 0. However, I am not able to count the repeating cases of 2nd matrix which already appeared in the first case. How to achieve this? $\endgroup$– jigsawmncCommented Nov 11, 2012 at 15:56
-
$\begingroup$ Could you clarify the term "contiguous sub-matrix"? $\endgroup$– Pietro MajerCommented Nov 11, 2012 at 17:52
-
$\begingroup$ @Pietro Majer: Contiguous means that the rows and columns of the chosen sub-matrix should be adjascent. $\endgroup$– jigsawmncCommented Nov 11, 2012 at 19:38
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
Let $a_n$ be the number of $2 \times n$ -matrices avoiding constant 2*2-submatrices. Then
$$a_n = \frac{2^{-n} \left(4 \left(17+4 \sqrt{17}\right) \left(3+\sqrt{17}\right)^n+\left(\sqrt{17}-17\right) \left(\sqrt{17}-3\right)^n e^{i \pi n}\right)}{17 \left(3+\sqrt{17}\right)}$$
This should be fairly straightforward to prove, let $v(n)=(e_{01}(n),e_{10}(n),e_{00}(n),e_{11}(n))$ be the vector of number of $2\times n$-matrices ending with column 01, 10, 00 resp. 11.
We then have the recursion $$v(n+1)=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{pmatrix} v(n)$$
Since this is symmetric, we may diagonalize this and from here, it should be straightforward to find the formula above. (I cheated a bit in Mathematica).
EDIT: Of course, $e_{01}(n)=e_{10}(n)$ and $e_{00}(n)=e_{11}(n)$ by symmetry, so one can of course reduce the above to a 2 by 2 matrix recursion instead, with entries 2,2 and 2,1. Eigenvalues of this matrix are $1/2 (3 + \sqrt{17}), 1/2 (3 - \sqrt{17})$ which explains the strange formula above.
answered Nov 11, 2012 at 17:48
-
$\begingroup$ How does m fit in this formula? $\endgroup$ Commented Nov 11, 2012 at 19:41
-
3$\begingroup$ This can be generalized to $m \times n$ matrices with fixed $m$, using a $2^m \times 2^m$ matrix with rows and columns indexed by the members of $\{0,1\}^m$. For example, the matrix in the $m=3$ case is $$\left[ \begin {array}{cccccccc} 0&0&1&1&0&1&1&1\\ 0&0&1&1&1&1&1&1\\ 1&1&1&1&1&1&1&1 \\1&1&1&0&1&1&1&0\\ 0&1&1&1&0&1&1 &1\\ 1&1&1&1&1&1&1&1\\ 1&1&1&1&1&1 &0&0\\ 1&1&1&0&1&1&0&0\end {array} \right]$$ $\endgroup$ Commented Nov 11, 2012 at 19:47
-
1$\begingroup$ If my Maple calculations are correct, the result in the case $m=3$ is then $$\sum_r \frac{17 + 9 r - 6 r^2}{15 r^n}$$ where the sum is over the roots of the polynomial $2 z^3 - 3 z^2 - 6 z + 1$. $\endgroup$ Commented Nov 11, 2012 at 19:57
-
-
3$\begingroup$ The $2^m \times 2^m$ matrix $A$ for the recursion is obtained as follows: $A_{ij} = 0$ if for some $k$, $1 \le k \le m$, the $k$'th and $k+1$'th binary digits of $i-1$ and $j-1$ (allowing leading $0$'s) are all equal, otherwise $A_{ij} = 0$. Thus in the case $m=3$ I had $A_{84} = 0$ because $7 = (111)_2$ and $3 = (011)_2$. Then $a_n = (1,\ldots,1) M^{n-1} (1,\ldots,1)^T$. $\endgroup$ Commented Nov 11, 2012 at 23:17
$\begingroup$
$\endgroup$
3
EDIT : I've edited the argument to make it stronger Suppose that $m\geq 3$ and $n\geq 5$ so that there is a 3x5 submatrix A. I show that the number of possibilities is zero in this case.
In A, there are at least two rows with at least there $1$'s each (up to relabeling the symbols). Since we cannot have a constant 2x2 submatrix, we may assume that the first two rows of the matrix are [11100] and [00111].
To avoid a 2x2 contant submatrix, the first two entries of the third row must be different, but then, whatever choice we make for the third one, we will get a constant 2x2-submatrix in the first and third row.
The answer for $m=1$ and $m=2$ is not hard to calculate explicitly.
Together with the answer above, this reduces the problem to checking the following cases (which is not too hard): 3x3,3x4,4x4.
-
$\begingroup$ What about the case when m = 5 & n = 5 and the matrix is: 0 1 0 1 0 | 0 1 0 1 0 | 0 1 0 1 0 | 0 1 0 1 0 | 0 0 1 1 0 The above is a valid case. $\endgroup$ Commented Nov 11, 2012 at 16:11
-
1$\begingroup$ I assumed that you meant any sub-matrix, but now I see that you meant only submatrices consisting of adjacent rows and columns. Maybe you should clarify your question. $\endgroup$– verretCommented Nov 11, 2012 at 16:13
-
1$\begingroup$ This is kind of irrelevant now that we know OP meant avoiding constant submatrices of adjacent rows and columns, but you can get a $3 \times 5$ matrix A avoiding constant $2 \times 2$ (general) submatrices by choosing $(1,0,0,0,1)$ as the third row; this choice is ok because your argument doesn't require the third row to have three $1$'s. $\endgroup$ Commented Nov 11, 2012 at 16:48