Adjacency matrix property

[vrakas]

Hello !
I am studying about adjacency matrices and i cannot understand the following:
"It is sometimes helpful to use the fact that the (i,j) entry of the adjacency matrix raised to the k-th power gives the number of paths from vertex i to vertex j consisting of exactly k edges. "
Can someone help me?

[mik2718]

It often helps to work through a simple example

take this graph

1 ------- 2
|         |
|         |
4 ------- 3

here is the adjacency matrix

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

if we square it we should find paths of length 2, the square is

2 0 2 0
0 2 0 2
2 0 2 0
0 2 0 2

hmmm, so we have two paths from vertex 1 to vertex 1. These must be 1-2-1 and 1-4-1.
we also have two paths from 1 to 3. These must be 1-2-3 and 1-4-3

etc.

[vrakas]

Thanks a lot :)