Thursday, December 11, 2014

December 11

Square cells in a rectangular grid; neighborhood defined as edges, vertices, but not self.

These are the blocks:

0 1 0…
1 0 1…
0 1 0…

1 1 0…
1 1 1…
0 1 1…

0 0 0…
0 0 0…
0 0 0…

To see the pattern, let the first of the blocks be A, the second B, and the third C. 


The 3x3 adjacency matrix:

A B C
B A B
C B A


The 3x4 adjacency matrix:

0 1 0 0 1 1 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 0 0 0
0 1 0 1 0 1 1 1 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0
1 1 0 0 0 1 0 0 1 1 0 0
1 1 1 0 1 0 1 0 1 1 1 0
0 1 1 1 0 1 0 1 0 1 1 1
0 0 1 1 0 0 1 0 0 0 1 1
0 0 0 0 1 1 0 0 0 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 1 1 1 0 1 0 1
0 0 0 0 0 0 1 1 0 0 1 0

So, if we think about it in terms of the blocks, a 3x4 looks like:
A B C
B A B
C B A

Which is the same as the 3x3. We can note that the blocks are now 3x4 instead of 3x3 like they were for the 3x3.

Now, let's look at a 4x4:

0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0
0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0
0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0
0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0

If we convert to blocks, the 4x4 looks like:

A B C C
B A B C
C B A B
C C B A

Now, let's think about what the blocks are. A is the 1xn adjacency matrix for square cells in a rectangular grid including edges and not self, and C is all 0s. B is a 1xn adjacency matrix for square cells in a rectangular grid including edges and self. This is interesting.

I'm not sure how we can find the determinant… 

2 comments:

  1. I agree. That *is* interesting. (And I'm also not sure how we can find the determinant.)

    What is the pattern of determinants (as a function of n) that we are looking for in this case?

    ReplyDelete
  2. I just spent 30 minutes playing with row reducing these by hand and trying to find a method. No success yet and I must get back to grading finals. (This problem is much more interesting)

    ReplyDelete