Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Per Alexandersson Nov 11 '12 at 15:20
    
@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? –  jigsawmnc Nov 11 '12 at 15:56
    
Could you clarify the term "contiguous sub-matrix"? –  Pietro Majer Nov 11 '12 at 17:52
    
@Pietro Majer: Contiguous means that the rows and columns of the chosen sub-matrix should be adjascent. –  jigsawmnc Nov 11 '12 at 19:38

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
How does m fit in this formula? –  jigsawmnc Nov 11 '12 at 19:41
3  
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]$$ –  Robert Israel Nov 11 '12 at 19:47
1  
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$. –  Robert Israel Nov 11 '12 at 19:57
    
See also oeis.org/A133129 –  Robert Israel Nov 11 '12 at 20:02
3  
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$. –  Robert Israel Nov 11 '12 at 23:17

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.

share|improve this answer
    
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. –  jigsawmnc Nov 11 '12 at 16:11
1  
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. –  verret Nov 11 '12 at 16:13
1  
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. –  Yuichiro Fujiwara Nov 11 '12 at 16:48

Perhaps this could help.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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