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.

A graph has a path from node $j$ to node $i$ if and only if its adjacency matrix has a positive element $(i,j)$ of $A^k$ for some integer $k.$

A proof for this statement will be highly appreciated.

share|improve this question
add comment

3 Answers

Hint. In fact there are $A_{ij}^m$ walks of length at most $m$ from $i$ to $j$. The inductive proof of this is pretty much identical to the one you're asking asking for, and your question follows a corollary.

Hint 2. Use $A_{ij}^m=\sum_{k=1}^n A_{ik}^{m-1}A_{kj}$.

share|improve this answer
    
I think you mean walks of length exactly $m$. –  Erick Wong Mar 10 '13 at 16:35
add comment

You may prove by mathematical induction. The base case is trivial. For the $k$-th iteration, note that $(A^k)_{ij}\not=0$ iff $(A^{k-1})_{i\ell}$ and $A_{\ell j}$ are both nonzero for some index $\ell$.

share|improve this answer
add comment

You can prove by induction. See Section 2.1 of this

share|improve this answer
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.