5
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$ May 16, 2011 at 8:04
  • $\begingroup$ 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 $\endgroup$ May 16, 2011 at 8:05
  • 10
    $\begingroup$ 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. $\endgroup$ May 16, 2011 at 9:02
  • 1
    $\begingroup$ @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. $\endgroup$ May 16, 2011 at 9:16
  • 3
    $\begingroup$ 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. $\endgroup$ May 16, 2011 at 16:04

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ May 16, 2011 at 8:19
  • $\begingroup$ @Qiaochu Yuan: Yes $\endgroup$
    – adamo
    May 16, 2011 at 8:29
  • $\begingroup$ @QiaochuYuan: more simply stated: "A path can never reviist the same node, but a walk can"". (Corollary: paths are finite (on a finite graph), but walks can be infinite). Also, I believe these definitions are near-universal. $\endgroup$
    – smci
    Mar 21, 2020 at 11:14
0
$\begingroup$

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 enter image description here

$\endgroup$
3
-1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ May 16, 2011 at 9:15
  • $\begingroup$ @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. $\endgroup$ May 16, 2011 at 9:22
  • $\begingroup$ 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$. $\endgroup$ Jun 13, 2011 at 16:54
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2011 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.