Homework Help: Adjacency matrix and probability matrix

1. Feb 2, 2016

TheMathNoob

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.

R
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.
Proof
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. Feb 8, 2016