Adjacency Matrix Proof

  • Thread starter pupeye11
  • Start date
  • #1
100
0

Homework Statement



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.

The Attempt at a Solution



I have no clue how to even start this proof...
 

Answers and Replies

  • #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]
 
  • #3
Dick
Science Advisor
Homework Helper
26,263
619
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]?
 
  • #4
100
0
Well the adjacency matrix is how many edges between the two vertices so A[i,j] would be 1
 
  • #5
Dick
Science Advisor
Homework Helper
26,263
619
Well the adjacency matrix is how many edges between the two vertices so A[i,j] would be 1

Doesn't A[i,j] depend on the graph? How can it always be 1?
 
  • #6
100
0
I was assuming I was working with a simple graph only.
 
  • #7
Dick
Science Advisor
Homework Helper
26,263
619
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?
 
  • #8
100
0
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?
 
  • #9
Dick
Science Advisor
Homework Helper
26,263
619
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?

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:
  • #10
100
0
A^2[i,j] = A[i,j]*A[i,j]. Wouldn't this double the number of ways to get from i to j?
 
  • #11
Dick
Science Advisor
Homework Helper
26,263
619
A^2[i,j] = A[i,j]*A[i,j]. Wouldn't this double the number of ways to get from i to j?

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.
 
  • #12
100
0
I am really not getting this, the matrix multiplication makes sense but I don't get how to interpret it.
 
  • #13
Dick
Science Advisor
Homework Helper
26,263
619
I am really not getting this, the matrix multiplication makes sense but I don't get how to interpret it.

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.
 
  • #14
100
0
A^2 would be the total number of ways to get from i to j wouldn't it?
 
  • #15
Dick
Science Advisor
Homework Helper
26,263
619
A^2 would be the total number of ways to get from i to j wouldn't it?

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?
 
  • #16
100
0
so A^3[i,j] would be the total number of ways to get from i to j transversing exactly 3 edges.
 
  • #17
Dick
Science Advisor
Homework Helper
26,263
619
so A^3[i,j] would be the total number of ways to get from i to j transversing exactly 3 edges.

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.
 
  • #18
100
0
alright, thanks for your help
 

Related Threads on Adjacency Matrix Proof

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
861
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
860
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
836
  • Last Post
Replies
6
Views
990
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
3
Views
655
Top