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…
I agree. That *is* interesting. (And I'm also not sure how we can find the determinant.)
ReplyDeleteWhat is the pattern of determinants (as a function of n) that we are looking for in this case?
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