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))


2 comments:

  1. Great, you didn't really need A_3 and A_4, but in the informal blog it's nice to check that that works. It'll be fun getting this into power point, but I think you've got all the elements.

    ReplyDelete
  2. Yes, this is great!

    Let's see... things to work on next include:

    1) Starting work on the poster? I think Susa sent you a template to help get started? (Susa -- is that template the right size for printing B/W?)

    2) Polishing the proof for the 1xn that you wrote about in this blog post. You have all the necessary ingredients... it just isn't written up formally. See, e.g., the induction proofs that are written out fully in your discrete textbook... can we emulate them more closely? (You could either do this in LaTeX, which we could transfer into the poster as an image, or you could type it directly into PowerPoint.)

    3) It would also be nice to try to wrap up the "mxn" case for this scenario -- but I'm not sure if you have time. The poster printing deadline is sneaking up on us...

    ReplyDelete