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 Proof

  1. Jun 23, 2010 #1
    1. The problem statement, all variables and given/known data

    Let A be the adjacency matrix for the graph G=(V,E)

    (a) Show that A^3[i,i] equals twice the number of triangles containing vertex i. (A triangle is a cycle of length 3

    (b) Find an interpretation for A^3[i,j] when i does not equal j similar to the above. Prove that your interpretation is correct.

    3. The attempt at a solution

    I have no clue how to even start this proof...
     
  2. jcsd
  3. Jun 23, 2010 #2
    I'm just guessing, but an interpretation of the entries of [tex]A^2[/tex] was probably discussed before the going right to [tex]A^3.[/tex]

    If you haven't really thought about [tex]A^2,[/tex] start there - it should shed some light. From there, it's not too hard to interpret [tex]A^n[/tex] for any [tex]n\in\mathbb{N}.[/tex]
     
  4. Jun 23, 2010 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Just to back up tmccullough, "I have no clue how to even start this proof..." is a pretty poor start. You must know something. What's the definition of the adjacency matrix A? What's A[i,j]?
     
  5. Jun 23, 2010 #4
    Well the adjacency matrix is how many edges between the two vertices so A[i,j] would be 1
     
  6. Jun 23, 2010 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Doesn't A[i,j] depend on the graph? How can it always be 1?
     
  7. Jun 23, 2010 #6
    I was assuming I was working with a simple graph only.
     
  8. Jun 23, 2010 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, now I've got to look up graph theory terms. Even if it's a simple graph some vertices may not be connected. You don't need to assume it's simple to do the problem. But, yes, A[i,j] is the number of ways to get from i to j by traversing a single edge. Now what's A^2 in terms of A using index notation?
     
  9. Jun 23, 2010 #8
    I am not sure what index notation is but are you trying to get at the fact that each entry in the matrix will then be 2^n-1 if we are looking at A^n?
     
  10. Jun 23, 2010 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, you shouldn't assume the matrix is full of 1's. And it's not even 2^(n-1) unless the matrix is 2x2. The graph may not be that simple. The question is "what is the definition of matrix multiplication". How would you write A^2[i,j] in terms of the components of A (A[i,j]). That's what I mean by index notation. Then interpret that in terms of ways to get from i to j by traversing edges.
     
    Last edited: Jun 23, 2010
  11. Jun 23, 2010 #10
    A^2[i,j] = A[i,j]*A[i,j]. Wouldn't this double the number of ways to get from i to j?
     
  12. Jun 23, 2010 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That is so bogus. That's not even matrix multiplication, it's more like an inner product. And even that wouldn't double things, it would square them. Look up matrix multiplication. A^2[i,j]=A[i,k]*A[k,j] where k is summed over all vertices. Now interpret that in terms of graph traversal.
     
  13. Jun 23, 2010 #12
    I am really not getting this, the matrix multiplication makes sense but I don't get how to interpret it.
     
  14. Jun 23, 2010 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    A[i,k] is the number of ways to get from i to k by tranversing a single edge. A[k,j] is the number of ways to get from k to j by tranversing a single edge. That means the number of ways to get from i to j via k is A[i,k]*A[k,j]. If you sum over all possible k then what might the interpretation of A^2[i,j] be? You've really got to think here. Please help me.
     
  15. Jun 23, 2010 #14
    A^2 would be the total number of ways to get from i to j wouldn't it?
     
  16. Jun 23, 2010 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You meant to say A^2[i,j] would be the number of ways to get from i to j by traversing exactly two edges, I sincerely hope you meant to say. What might A^3[i,j] mean?
     
  17. Jun 23, 2010 #16
    so A^3[i,j] would be the total number of ways to get from i to j transversing exactly 3 edges.
     
  18. Jun 23, 2010 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right! Now might need to think about what 'triangle' means and you may indeed need to make the assumption that it's a simple graph, but I think you've got the notion of what A^n means in terms of adjacency.
     
  19. Jun 23, 2010 #18
    alright, thanks for your help
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook