Timeline for How many matrices are possible for the given arrangement?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 12, 2012 at 10:32 | vote | accept | jigsawmnc | ||
| Nov 11, 2012 at 23:23 | comment | added | Robert Israel | See also oeis.org/A181245 . This is stated as "no 2X2 circuit having pattern 0101 in any orientation", but that's equivalent if you switch $0$'s and $1$'s in a checkerboard pattern. | |
| Nov 11, 2012 at 23:17 | comment | added | Robert Israel | 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$. | |
| Nov 11, 2012 at 20:56 | comment | added | Per Alexandersson | I wonder if the sequence of characteristic polynomials obtained from these matrices have nice properties. They're certainly real-rooted, I wonder maybe if they can be found recursively in a nice manner... | |
| Nov 11, 2012 at 20:35 | comment | added | jigsawmnc | Given that I know the value for m * m matrix. Can this value help me in finding the answer for m * (m + 1), m * (m + 2), ... matrices? | |
| Nov 11, 2012 at 20:30 | comment | added | jigsawmnc | @Robert Israel: m's max value can be 6 and n's max value can be 2^63. Can you tell me how are you able to deduce the matrix based on m's value. Is it some algorithmic technique or just by observing it. Also, can there be derived any recursive relation? | |
| Nov 11, 2012 at 20:02 | comment | added | Robert Israel | See also oeis.org/A133129 | |
| Nov 11, 2012 at 19:57 | comment | added | Robert Israel | 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$. | |
| Nov 11, 2012 at 19:47 | comment | added | Robert Israel | 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]$$ | |
| Nov 11, 2012 at 19:41 | comment | added | jigsawmnc | How does m fit in this formula? | |
| Nov 11, 2012 at 17:54 | history | edited | Per Alexandersson | CC BY-SA 3.0 |
added 301 characters in body
|
| Nov 11, 2012 at 17:48 | history | answered | Per Alexandersson | CC BY-SA 3.0 |