Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
I think you mean walks of length exactly $m$. – Erick Wong Mar 10 '13 at 16:35

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|cite|improve this answer

You can prove by induction. See Section 2.1 of this

share|cite|improve this answer

Your Answer


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.