- #1

nomadreid

Gold Member

- 1,463

- 148

[1] I read:

"Consider a directed graph and a positive integer k. Then the number of directed walks from node i to node j of length k is the entry on row i and column j of the matrix A

^{k}..." [where A is the adjacency matrix of a non-directed non-weighted graph, and the exponentiation being normal matrix multiplication in examples on the site]. From http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture2/lecture2.html

OK, that seems straightforward. But then I look on another site,

http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html

where they give an example of A

^{2}, A

^{3}, etc., with a method that is not clear but is definitely not by normal matrix multiplication: specifically

in the example, A =

0 0 1 0 0

0 0 0 1 0

0 1 0 0 1

0 1 0 0 0

1 0 1 0 0

and the site gives

0 0 1 0 0

0 0 0 1 0

0 1 0 1 1

0 1 0 1 0

1 0 1 0 0

as A

^{2}, whereas using normal matrix multiplication, one gets A

^{2}=

0 1 0 0 1

0 1 0 0 0

1 0 1 1 0

0 0 0 1 0

0 1 1 0 1

which is evidently very different. So what is going on here?

[2] beyond the use of adjacency matrices for

(a) a table (to see what is connected to what) ,

(b) the above application (to see how many paths exist between two points),

(c) to illustrate the Coates method for solving simultaneous equations,

are there any uses for adjacency matrices?

Thanks for any help.