Square cells in a rectangular grid; neighborhood defined as edges, vertices, but not self.
From an earlier post, I had these determinants, and I just added more.
For 1 x n, the determinants were:
1x1: 0
1x2: -1
1x3: 0
1x4: 1
1x5: 0
1x6: -1
The pattern: for n equiv 0 (mod 2), the determinant is either -1 or 1. (We have proved this to be true.)
For 2 x n, the determinants were:
1x2: -1
2x2: -3 = -1*3
2x3: 7 (4th prime)
2x4: 5 (3rd prime)
2x5: -33 = -1*3*11
2x6: 13 (6th prime)
2x7: 119 = 7 * 17
2x8: -171 = -1*3*57
2x9: -305 = 5 * 61
It appears that the absolute value of all these determinants is either prime or the product of 2 primes.
And for 3 x n, determinants:
3x3: 0
3x4: 9 = 3^2
3x5: 0
3x6: -497 = 7*71
3x7: 0
3x8: -8687 = 7*241
Friday, December 12, 2014
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…
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…
Monday, December 1, 2014
December 1
Square cells in a rectangular grid; neighborhood defined as edges, vertices, but not self.
Let's look at the adjacency matrix for a 3x3.
0 1 0 1 1 0 0 0 0
1 0 1 1 1 1 0 0 0
0 1 0 0 1 1 0 0 0
1 1 0 0 1 0 1 1 0
1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 0 1 0
0 0 0 1 1 1 1 0 1
0 0 0 0 1 1 0 1 0
This seems to be made of the following 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. From this, the adjacency matrix for a 3x3 is:
A B C
B A B
C B A
So we see that the diagonal is made up of As.
Let's look at the adjacency matrix for a 3x3.
0 1 0 1 1 0 0 0 0
1 0 1 1 1 1 0 0 0
0 1 0 0 1 1 0 0 0
1 1 0 0 1 0 1 1 0
1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 0 1 0
0 0 0 1 1 1 1 0 1
0 0 0 0 1 1 0 1 0
This seems to be made of the following 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. From this, the adjacency matrix for a 3x3 is:
A B C
B A B
C B A
So we see that the diagonal is made up of As.
Monday, October 27, 2014
October 27
Square cells in a rectangular grid, the neighborhood defined as edges, vertices, but not self
1 x n:
A 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
Taking the determinant by the first column would result in the negative determinant of:
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...
By using the first column again, we would subtract the determinant of:
0 1 0 0 0 ...
1 0 1 0 0 ...
0 1 0 1 0 ...
from the determinant of:
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...
Now, the base cases...
Let A_k be the adjacency matrix for a 1 x k grid.
A_1 = 0
det(A_1) = 0
A_2 =
0 1
1 0
det(A_2) = -1
A_3 =
0 1 0
1 0 1
0 1 0
det(A_3) = 0
A_4 =
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
det(A_4) = 1
We want to show that:
det(A_k) = 0 - det(A_(k-2)) = det(A_(k-2))
This works for A_3 and A_4:
det(A_3) = - det(A_1) = 0
det(A_4) = - det(A_2) = - (-1) = 1
So we assume that this holds for all A_i for i < or = k, and we want to show that this holds for A_(k+1).
A_(k+1) looks like this:
0 1 0 ...
1 0 1 ...
and so on.
If we take the determinant by the first column,
det(A_(k+1)) = -det(
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...)
= det(
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...)
-
0 1 0...
1 0 1 ...
= 0 - det(A_(k-1))
1 x n:
A 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
Taking the determinant by the first column would result in the negative determinant of:
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...
By using the first column again, we would subtract the determinant of:
0 1 0 0 0 ...
1 0 1 0 0 ...
0 1 0 1 0 ...
from the determinant of:
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...
Let A_k be the adjacency matrix for a 1 x k grid.
A_1 = 0
det(A_1) = 0
A_2 =
0 1
1 0
det(A_2) = -1
A_3 =
0 1 0
1 0 1
0 1 0
det(A_3) = 0
A_4 =
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
det(A_4) = 1
We want to show that:
det(A_k) = 0 - det(A_(k-2)) = det(A_(k-2))
This works for A_3 and A_4:
det(A_3) = - det(A_1) = 0
det(A_4) = - det(A_2) = - (-1) = 1
So we assume that this holds for all A_i for i < or = k, and we want to show that this holds for A_(k+1).
A_(k+1) looks like this:
0 1 0 ...
1 0 1 ...
and so on.
If we take the determinant by the first column,
det(A_(k+1)) = -det(
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...)
= det(
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...)
-
0 1 0...
1 0 1 ...
= 0 - det(A_(k-1))
Friday, October 24, 2014
October 24
Square cells in a rectangular grid, the neighborhood defined as edges, vertices, but not self
1 x n:
If we look at the adjacency matrices, the diagonal is always 0s because self is not included.
So for a 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
If we take the determinant, we can use the first column, which leaves us taking the determinant of:
1 0 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
If we us the first column again, we add the determinants of:
0 1 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0 0...
0 0 1 ...
and:
0 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 ....
0 0 1 0 1...
The first of these looks the same as what we started with, and the second has a row of 0s so its determinant is 0.
1 x n:
If we look at the adjacency matrices, the diagonal is always 0s because self is not included.
So for a 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
If we take the determinant, we can use the first column, which leaves us taking the determinant of:
1 0 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
If we us the first column again, we add the determinants of:
0 1 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0 0...
0 0 1 ...
and:
0 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 ....
0 0 1 0 1...
The first of these looks the same as what we started with, and the second has a row of 0s so its determinant is 0.
Thursday, October 23, 2014
October 23
For 1 x n, the determinants were:
1x1: 0
1x2: -1
1x3: 0
1x4: 1
1x5: 0
1x6: -1
The pattern: for n equiv 0 (mod 2), the determinant is either -1 or 1
For 2 x n, the determinants were:
2x2: -3
2x3: 7
2x4: 5
2x5: -33
And for 3 x n, determinants:
3x3: 0
3x4: 9
3x5: 0
I'm not sure what it is for mxn yet.
But I think that this is the rule for solvability: it seems that for 1xm, if m is even it's solvable. In general, it seems that if one or both dimensions are even, then the puzzle is solvable.
I'll work on the nx1 case next time.
Tuesday, October 7, 2014
October 7
Revised version of the sidelength 3 case:
Matrices:
If we start to look at the determinant... Also, just as a note, this is how I was numbering the cells [in increasing order from left to right by row.]
Here is the side length of 2 case:
The determinant is clearly 0. One thing we can note about the starting matrix, is that it has a diagonal of 0s and it is symmetrical over that diagonal. Since we can take either row or column to do the determinant by, in the following case, there is always either a row or column that has only one 1 in it. If we take that, it is simple to do the determinant.
Here is the side length 3 case:
Now, we see that there is a column of all 0s. If we did the determinant by this column, the result will clearly be 0.
To make the result more clear: (The green is the column I went down to take the determinant, the orange is the row that was ignored for the only 1 there.)
...not sure how helpful this is.
Thinking about Triangles:
In any given triangle, we know that the bottom row looks like this:
Now, if we have the numbers filled in like this:
So for the kth cell in this row, the number a_k is equal to 1 if k is even or 0 if k is odd.
If k is odd, then the kth slot is a 0 and the (k-1)th and (k+1)th slots are 1. The rest of the grid is filled with Os, so all Xs have to be in the bottom row. From the 1s, we know there has to be an X in some of the following slots: (k-2), k, (k+2). This particular area is ambiguous.
If k is even, then the kth slot is a 1 and the (k-1)th and (k+1)th are 0. From here, we know that either (k-1) or (k+1) contains an X.
Subscribe to:
Posts (Atom)






