edsmiley

oddball
So, one of the oddball things about this way of thinking is that essentially you are multiplying two graphs together!.

zero fill
If you have two graphs, one with N points and one with M points (N>M) you can express each graph as a matrix, but zero fill the MXM matrix with extra columns and rows of zeros. This also presupposes that you have chosen a particular one to one correspondence between M of your points.

trivial example
Let there be three points p0, p1, p2 as vertices where the graph looks like this:
p0—p1—p2

OK I said this was a pretty trivial graph. (you didn’t believe me?)

Now we can express this as:

| 0 1 0 |
| 1 0 1 |
| 0 1 0 |

Squaring this gives
| 1 0 1 |
| 0 2 0 |
| 1 0 1 |

mutant graph
Which would be interpreted as a new topology and weighting: putting a self-loop on each point, but with a weight of 2 on p1, and connecting p0 to p2 and bypassing p1!
(Sorry there is no way to draw this easily to with ASCII art, and I am too lazy to do more.)

Now this appears to be more complicated, so we would expect that if we obtained the cube of this simple matrix, it would get even weirder.

surprise
Instead, cubing the original matrix reverts to the original but with weights of 2 on the edges!
| 0 2 0 |
| 2 0 2 |
| 0 2 0 |

            2     2
         p0---p1---p2

And a little computation reveals that alternate odd and even powers alternate, but keep doubling their magnitude. Now this is pretty trivial as far as matrix math is concerned, but it is a really interesting way to interpret the results graphically.

exercise!
The lazy textbook writer commonly ends at this point by copping out with the rest is left as an exercise for the student.

Of course I am extremely lazy but I will note the interesting generalization that many graphs follow this pattern when raised to powers, alternately breaking edges between vertices
and attaching vertices that were not connected on one power, reverting to a multiple of the original matrix on the other, alternate, power.

So for example, a simple tree with root at p0,
p0
/ \
p1 p2

where p0 is connected to p1 and p2 will create the loops and detach p0 but attach p1 to p2.

And a four point generalization for like the above case
p0—p1—p2–p3
will attach the unattached pairs (p0,p2) and (p1,p3) put self-loops on each of then with different weights, and on alternate powers revert to the original matrix (except for scale)!

OK, confirmation is left as an exercise for the student. Heh.