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

Gold Member
Two questions, both about adjacency matrices (graphs). The first, specific, the second, general.
"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 Ak..." [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 A2, A3, 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 A2, whereas using normal matrix multiplication, one gets A2=
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?

 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.

Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?

Gold Member
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 Ak..."
But then I look on another site,
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html
where they give an example of A2, A3, 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".)

• 