Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
It doesn't have a simple interpretation in terms of paths; the adjacency matrix is naturally suited for studying walks. This is not really an appropriate question for MO; you might want to try math.stackexchange.com. –  Qiaochu Yuan May 16 '11 at 8:04
    
That's too bad, because the answer is so nice in terms of walks. It is hard to relate to pure paths because of not knowing how to eliminate nicely the cyclic portion of the walk. If you have some more information on the situation, such as n is very small, or the graph has very few cycles, then you might be able to describe such a relation. Without that, the best you can do in general is an upper bound. Gerhard "Ask Me About System Design" Paseman, 2011.05.16 –  Gerhard Paseman May 16 '11 at 8:05
6  
I'm not sure I understand exactly what is being asked for, but an efficient algorithm counting self-avoiding walks of given length between two given vertices would lead to an efficient algorithm deciding hamiltonicity. Unless P=NP this is harder than matrix multiplication. –  Johan Wästlund May 16 '11 at 9:02
1  
@adamo: there isn't a way to directly transfer questions between sites from different generations (math.SE is 2.0). You could repost it, but I think what's been said so far is already pretty good. –  Qiaochu Yuan May 16 '11 at 9:16
1  
There is a theory of loop-erased random walks on a graph, where one does a random walk and erases a loop (cycle) as soon as it is created. This gives a model for a random path that is closely connected to random spanning trees. See en.wikipedia.org/wiki/Loop-erased_random_walk. However, this model has little connection with powers of the adjacency matrix. –  Richard Stanley May 16 '11 at 16:04
add comment

3 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
My guess is that a walk is a sequence of vertices connected by edges and a path is a sequence of distinct vertices connected by edges. –  Qiaochu Yuan May 16 '11 at 8:19
    
@Qiaochu Yuan: Yes –  adamo May 16 '11 at 8:29
add comment

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.

share|improve this answer
    
Note that as Johan indicates in the comments this is much less efficient than taking powers of a matrix, since you can't use binary exponentiation: you really have to multiply (and modify the diagonal) $n$ times. –  Qiaochu Yuan May 16 '11 at 9:15
    
@Qiauchu - I never claimed it was efficient, although in my opinion it is 'simple'. But then I realized it doesn't completely work - see edit. –  Mark Meilstrup May 16 '11 at 9:22
    
If you define $P_n$ to be the matrix whose $u,v$ entry is $t$ if the minimum distance from $u$ to $v$ is $n$ and there are $t$ minimal walks of that length, then $P_{n+1}=(P_nA)*$ if instead you let $(\cdot)^*$ mean zero out everything which was non-zero for any $m \le n$. –  Aaron Meyerowitz Jun 13 '11 at 16:54
    
This doesn't work. This would give a polynomial-time algorithm for Hamiltonian path (i.e. a cycle-free path from $a$ to $b$ of length exactly $n$) but that is NP-complete. –  David Harris Jun 27 '11 at 17:30
add comment

Your Answer

 
discard

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.