# Graph of a matrix and a positive power for the the matrix

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.

-

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}$.

-
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$.

-

You can prove by induction. See Section 2.1 of this

-