What is the n-th power of the adjacency matrix equal to? A friend (who works on social networking analysis) asked this over at twitter:
What is the n-th power of the adjacency matrix equal to, in terms of paths, NOT walks?
EDIT: Complimentary question: "Is there any algorithm counting paths between pairs of nodes, given the adjacency list or matrix?"
(If there's a way to transfer the question to math.SE as a more appropriate forum, please help me do so).
 A: As far as what it is exactly equal to, not so much after $n=0,1$ and $n=2$ with the diagonal erased. This is not deep, but something is revealed by those entries where $A^n$ is positive but $A^{m}$, for $m \lt n$, never is: looking at the first $v-1$ (or, usually, fewer) powers  of the adjacency matrix $A$ can inform you of the length of the shortest path (which will be a walk) connecting each pair of vertices as well as how many shortest walks there are.   Start with two  blank $v \times v$ matrices $D$  and $P$ and  then compute in order the powers of $A$ starting with $A^0=I$. If the $i,j$ entry of $D$ is blank and that of $A^d$ is $p>0$ then record $D_{ij}=D_{ji}=d$ and $P_{ij}=P_{ji}=p.$ You can stop when $A^d$ has $0$ everywhere that $D$ is blank.
A: I would need to know what exactly is the definition you are using for a "path" and not a "walk", based on which this answer may be either useful or useless. But the $n^{th}$ power of the adjacency matrix's $ij$ element, i.e. $(A_G^n)_{ij}$, represents the number of ways you can go from vertex $i$ to vertex $j$ in the original graph. 
A: the n-th power of the adjacency matrix  represent the number of paths between two nodes (source ,destination) you can get by n transition
here is an example 
A: EDIT -- This actually doesn't completely work.  For instance, a path 'abc' followed by the path 'cbd' does not give a path from a to d, but rather includes the cycle 'bcb'.  I guess my method only discounts some of the non-paths.

As you want to avoid cycles in your path, you should be able to achieve this algorithmically by "zero-ing out" the diagonal of your matrix after each multiplication.  Thus whenever a cycle gets counted in $A^n$, we discount it by changing the diagonal entry to 0, and then all future paths won't use that cycle either.
In particular, if $A$ is the adjacency matrix, define $P_1=A$, and $P_{n+1}=(P_n A)^*$, where I use the * to mean "change all diagonal entries to 0".
Then the matrix $P_n$ gives the number of paths of length $n$ between vertices.
