1

How do you read product of adjacency matrix multiplying itself that has not only 1 and 0 but other numbers?

For example
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
1 0 1 0 1
1 0 0 1 0
so squaring the above matrix is
3 0 2 1 1
0 2 0 2 1
2 0 2 0 1
1 2 0 3 1
1 1 1 1 2

I know how to read if the entries are only 1 and 0. But how do you interpret such as 3 and 2?

Andy
  • 123

2 Answers2

5

the coefficient i,j of $A^2$ gives the number of paths of length $2$ from i to j.

generalization :

the coefficient i,j of $A^k$ gives the number of paths of length $k$ from i to j.

Proof by recurrence : It is obviously true for $k=1$ by definition of the adjacency matrix.

Suppose it is true for $k\geq 1$. Then a path of length $k+1$ from $i$ to $j$ is a path from $i$ to a vertex $l$ (of witch there are $A^k_{i,l}$) that is connected to $j$ (given by $A_{l,j}$). Therefore the number of paths from $i$ to $j$ whose last stop is $l$ is $A^k_{i,l}A_{l,j}$.

Summing those for all values of $l$ gives the total number of paths from $i$ to $j$ of length $k+1$, and matches exactly $(A^k A)_{i,j}=A^{k+1}_{i,j}$.

It is therefore true for $k+1$, therefore it works for all values of $k$.

imj
  • 1,430
  • Maybe you could explain why or give a reference so your answer is self contained and the OP can accept it? – Dominique Mar 06 '13 at 14:58
  • sure, it is done. – imj Mar 06 '13 at 15:11
  • Thank you. But I'm not sure if I understand it quite right. Does it mean A11 is a loop and has 3 paths of length 2 from 1 to 1? – Andy Mar 06 '13 at 15:40
  • There are indeed 3 paths of length 2 from 1 to 1, as $A_{1,1}^2=3$. Those paths are simple loops going from vertex 1 to one of the three adjacent vertices, and back to vertex 1 again : 1-2-1, 1-4-1 and 1-5-1 – imj Mar 06 '13 at 15:52
  • Sorry for my late reply. Thank you so much! – Andy Mar 09 '13 at 17:41
0

As imj said, the $A^k_{ij}$ entry is the number of paths from node $i$ to node$j$

Learner
  • 2,696