Powers of the Adjacency Matrix

Theorem: Let be the adjacency matrix of an unweighted graph $($could be directed$/$undirected$,$ simple$/$multigraph$).$ For any $,$ contains the following elements: $,$ which is the element in row and column of $,$ is the number of walks of length from node to node $.$

Proof: The proof of this statement follows from induction with the following base cases: For $,$ the statement is true by the definition of an adjacency matrix. For $,$ let be row of and be column of $.$ By definition, the entries of are the number of walks of length from node to any other node. Similarly, the entries of are the number of walks of length from any other node to node $.$ Since entry is the vector inner product of and it is then also equal to the number of walks of length from node to via all possible intermediate nodes.

Inductively, we assume that is equal to the number of walks with length from node to node $.$ Then

We can see now that will be zero if there is no walk from to $,$ and it will be equal to if there is$.$ Thus is equal to the number of walks of length from node to and the proof is completed.

Adjacency Matrix $-$ Walks of Length $2$ and $3$

$2$ points possible $($graded$)$

Consider the following adjacency matrix:

Let the nodes be numbered $,,$ and $,$ with representing the number of directed edges from node to node $.$

$1.$ How many walks of length are there from node to $?$

unanswered

$2.$ How many walks of length are there from node to $?$

unanswered