1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Adjacency matrix and probability matrix

  1. Feb 2, 2016 #1
    1. The problem statement, all variables and given/known data
    If Γ is a k-regular simple graph and Γ its directed double, show that the matrix ˜ S for Γ (as per the FEATURED ARTICLE ) is a multiple of the adjacency matrix ˜ for Γ. Find the multiple. Assume k > 1.
    The matrix S is the probability matrix. The probability of going from one node to another node based on the number of lines coming out of each node.

    2. Relevant equations

    3. The attempt at a solution
    So it looks like the factor that maps T->S is 1/k so T*1/k=S.
    This makes sense because the idea of adjacency is preserved on both matrices and their nonzero entries differ by a factor of 1/k because in S each nonzero entry represents the probability of going from one vertex to another adjacent vertex. In this case, it will always be 1/k because the number of lines leaving each node is always k. In T we just assert the adjacency between vertices by putting a 1.

    That's a good start. I don't how to set this up, so it proves that the factor is 1/k
    Last edited: Feb 2, 2016
  2. jcsd
  3. Feb 8, 2016 #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. Feb 9, 2016 #3


    User Avatar
    Science Advisor

    The phrase "as per the featured article" indicates that there is more to this problem that you have not told us!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted