Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You should try to prove this by induction. It's a good exercise. –  wj32 Nov 7 '12 at 2:25
    
So say nth power of adjacency is a connected graph. Start with base step that saying when n=1, (P(n) (any nth power of adjacency matrix determines n-th connection in graph), P(1)=A^1 is true (Which means graph is connected, and nth tells length). And go to induction step that P(n)=A^n is true then P(n+1)=A^(n+1) is also true? –  Uka Nov 7 '12 at 2:47
add comment

1 Answer 1

up vote 3 down vote accepted

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.

To form a walk of length $k+1$ from vertex $i$ to $j$, you must first have a walk of length $k$ from vertex $i$ to some vertex $v$ and then a walk of length $1$ from vertex $v$ to vertex $j$.

share|improve this answer
    
This is very helpful. Thank you so much! –  Uka Nov 7 '12 at 3:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.