I am studying graph theories, and I am not sure about how power of adjacency works. I know $k$-th powers of A tells connection in graph, and I can read lengths between a vertex to vertex after taking powers of adjacency. My question is: why can powers of adjacency matrix determine connections in graph, and how many powers need to determine it?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I will give you a hint on how to proceed.
As you mentioned, the entries of the adjacency matrix gives you the connections between vertices. If you take powers, then you are really concatenating walks. The $ij$th entry of the $k$th power of the adjacency matrix tells you the number of walks of length $k$ from vertex $i$ to vertex $j$.
To prove this using induction, try this fact.