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 comment:

  1. This is a great step. A couple comments:

    1) The second time you took the column determinant, the first row would have been easier and have given the same result.

    2) Do you remember that some of the determinants are negative. (+ for first position, - for second, + for third etc.) You might want to look at your lin alg book. That should help you get the alternating negatives into your proof, when you turn this into an induction proof.

    3) show your base cases, and use your findings of how the determinants relate to each other, and I think you'll be there....

    4) This may require making up some variables and naming them. Like A_k for the adjacency matrix for a 1xk grid

    ReplyDelete