Adjacency matrices: (a) notation discrepancy, and (b) applications

[nomadreid]

Two questions, both about adjacency matrices (graphs). The first, specific, the second, general.
[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², A³, 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², whereas using normal matrix multiplication, one gets A²=
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.

 

[nomadreid]

To make the question simpler: if you multiply an adjacency matrix (unweighted) by itself, what can you conclude about the product?

 

[Stephen Tashi]

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

But then I look on another site,
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html
where they give an example of A², A³, etc.,

I don't know graph theory, but a casual look shows that the second site is explaning "Warshall's algorithm". According to http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L17-Warshall.htm :

Warshall's algorithm determines whether there is a path between any two nodes in the graph. It does not give the number of the paths between two nodes.

So "whether there is a path" between two give nodes is a different question than "the number of paths" or "the number of paths of length k" between two given nodes.

I think your second link is using superscripts on the matrix that do not mean exponentiation.

(In my brief web searching on this topic, I get the impression that many authors of computer science material don't write precisely. I don't think Warshall's algorithm "determines whether there is a path between any two nodes in the graph". I think it "determines for each pair of nodes on the graph whether there is a path between them".)

 

[nomadreid]

Thank you very much, Stephen Tashi. When I look again with the aid of the website you provided, you are right: the second website I provided is using the superscripts to explain Warshall's algorithm, and is simply sloppy in its notation, so that it is easy to mistake them (as I did) for exponents. The website you provided is more careful with its notation, and the explanation is much better. Anyway, that perfectly explains the discrepancy between the two websites I was comparing: the first website I provided was very explicit about the superscripts meaning exponentiation (so I guess that does, unlike Warshall's algorithm, give the number of paths when you sum up all the powers of the adjacency matrix.) So, thanks again!