How many matrices are possible for the given arrangement? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:30:23Z http://mathoverflow.net/feeds/question/112074 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement How many matrices are possible for the given arrangement? jigsawmnc 2012-11-11T14:04:10Z 2012-11-12T13:56:05Z <p>Given m &amp; 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 &amp; breadth > 1 should have same entries i.e. all of its cells shouldn't be 0 or 1. For example if m = 2 &amp; 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 &amp; breadth = 1, also breadth > 1 &amp; length = 1 is valid.</p> http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112083#112083 Answer by verret for How many matrices are possible for the given arrangement? verret 2012-11-11T15:49:20Z 2012-11-11T16:11:29Z <p>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.</p> <p>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].</p> <p>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.</p> <p>The answer for $m=1$ and $m=2$ is not hard to calculate explicitly.</p> <p>Together with the answer above, this reduces the problem to checking the following cases (which is not too hard): 3x3,3x4,4x4.</p> http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112093#112093 Answer by Per Alexandersson for How many matrices are possible for the given arrangement? Per Alexandersson 2012-11-11T17:48:42Z 2012-11-11T17:54:29Z <p>Let $a_n$ be the number of $2 \times n$ -matrices avoiding constant 2*2-submatrices. Then </p> <p>$$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)}$$</p> <p>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.</p> <p>We then have the recursion <code>$$v(n+1)=\begin{pmatrix} 1 &amp; 1 &amp; 1 &amp; 1 \\ 1 &amp; 1 &amp; 1 &amp; 1 \\ 1 &amp; 1 &amp; 0 &amp; 1 \\ 1 &amp; 1 &amp; 1 &amp; 0 \\ \end{pmatrix} v(n)$$</code></p> <p>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).</p> <p>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.</p> http://mathoverflow.net/questions/112074/how-many-matrices-are-possible-for-the-given-arrangement/112176#112176 Answer by jigsawmnc for How many matrices are possible for the given arrangement? jigsawmnc 2012-11-12T13:56:05Z 2012-11-12T13:56:05Z <p>Perhaps <a href="http://discuss.codechef.com/questions/3706/cbars-editorial" rel="nofollow">this</a> could help.</p>