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?

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_{r1}(A) = p_r(A) + (\DeltaI)p_{r2}(A) $$ If $\Phi(X,t)$ is the generating function $\sum_r p_r(A)t^r$, it follows that $$ (ItA+t^2(\DeltaI)) \Phi(X,t) = (1t^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. 


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 


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

