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

Improve this question
$\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$
    – Qiaochu Yuan
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Johan Wästlund
    Commented 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$
    – Qiaochu Yuan
    Commented 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$
    – Richard Stanley
    Commented May 16, 2011 at 16:04

4 Answers 4

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\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$
    – Qiaochu Yuan
    Commented May 16, 2011 at 8:19
  • $\begingroup$ @Qiaochu Yuan: Yes $\endgroup$
    – adamo
    Commented 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
    Commented 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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This is too vague. What is a "way", for example. And its the matrix entries that matter. $\endgroup$
    – Chris Godsil
    Commented Nov 13, 2015 at 14:34
  • 1
    $\begingroup$ I hope now it is more clear @ChrisGodsil $\endgroup$
    – Mohammed
    Commented Nov 13, 2015 at 15:17
  • $\begingroup$ images.slideplayer.com/14/4238895/slides/slide_7.jpg $\endgroup$
    – ARZ
    Commented Nov 10, 2021 at 17:08
-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.

Improve this answer
$\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$
    – Qiaochu Yuan
    Commented 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$
    – Mark Meilstrup
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – David Harris
    Commented Jun 27, 2011 at 17:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .