Linear Algebra and Its Applications · Problem 2.5.21

Vector Spaces — Gilbert Strang

Mathematics · graphs-and-networks

Problem

The adjacency matrix of a graph has

M_{ij} = 1

if nodes

i

and

j

are connected by an edge (otherwise

M_{ij} = 0

). For the graph in Problem 6 with 6 nodes and 4 edges, write down

M

and also

M^2

. Why does

(M^2)_{ij}

count the number of 2-step paths from node

i

to node

j