Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 21, 2014 #1
    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 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?

    [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.
     
  2. jcsd
  3. Nov 26, 2014 #2
    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?
     
  4. Nov 26, 2014 #3
    To make the question simpler: if you multiply an adjacency matrix (unweighted) by itself, what can you conclude about the product?
     
  5. Nov 27, 2014 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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 :

    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".)
     
  6. Nov 27, 2014 #5
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Adjacency matrices: (a) notation discrepancy, and (b) applications
  1. Matrices ? (Replies: 6)

  2. On Matrices (Replies: 8)

  3. Notation (Replies: 2)

  4. Matrices and notation (Replies: 1)

Loading...