power of adjacency matrix Suppose A is the adjacency matrix of a graph G. It is well known that the number of walks of length $\ell$ in G, from $v_i$ to $v_j$, is the entry in position $(i,j)$ of the matrix $A^\ell$.
My question is that can we construct a matrix, say H, of a graph G, such that the number of paths of length $\ell$ in G, from $v_i$ to $v_j$, is the entry in position $(i,j)$ of the matrix $H^\ell$. If no, why?
 A: Call a walk in $X$ reduced if it does not contain any subsequence of the form $uvu$, and let $p_r(A)$ denote the matrix whose $uv$-entry is the number of reduced walks from $u$ to $v$. Let $\Delta$ be the disgonal matrix such that $\Delta_{u,u}$ is the valency of $u$. Then if $r>2$, we have
$$
  Ap_{r-1}(A) = p_r(A) + (\Delta-I)p_{r-2}(A)
$$
If $\Phi(X,t)$ is the generating function $\sum_r p_r(A)t^r$, it follows that
$$
  (I-tA+t^2(\Delta-I)) \Phi(X,t) = (1-t^2)I.
$$
It follows that we can effectively count reduced walks. And if $X$ is a tree, then $\Phi(X,t)$
is actually a polynomial. [So $K_2$ is not a problem :-) ]
Of course I agree with Richard Stanley's remark about the general case.
A: Let us take the graph G to be $K_2$.  Your proposed H would have to be a zero
matrix for all powers of H greater than 1.  However, H would have to be nonnilpotent to record the
paths of length 1.  The upshot is that the path enumeration does not correspond to matrix multiplication.
I would be surprised if any graphs G had an H that would work as you specify even for values of l at most 3.
Gerhard "Ask Me About System Design" Paseman, 2013.01.03
A: You can certainly do this by cheating and making an outrageous expansion of the set of vertices. Let the vertices of the original graph by $V$. Now you form a new directed graph with vertices $V\times \mathcal P(V)$ (where $\mathcal P$ denotes power set).
For each edge $i\to j$ in the original graph, and for each set $S$ containing $i$ but not $j$, define an edge $(i,S)\to (j,S\cup\lbrace j\rbrace)$. This new monster graph keeps track of all the places you've been and only lets you visit new vertices. 
Let $\bar A$ be the adjacency matrix of this new directed graph. 
Finally, let $B$ be the $|V|\cdot 2^{|V|}\times |V|$ matrix with $B_{j\times S,j}=1$ for each $S$, and 0 and equal to 0 for all other entries.
The number of walks from $i$ to $j$ in the original graph of length $l$ is given by $(A^lB)_{(i,\lbrace i\rbrace),j}$.
Of course, this is absolutely not a practical way to compute anything...
