Adjacency Matrix Proof for Triangles in a Graph | A^3[i,i] and A^3[i,j]

[pupeye11]

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...

 

[tmccullough]

I'm just guessing, but an interpretation of the entries of A^2 was probably discussed before the going right to A^3.

If you haven't really thought about A^2, start there - it should shed some light. From there, it's not too hard to interpret A^n for any n\in\mathbb{N}.

 

[Dick]

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]?

 

[pupeye11]

Well the adjacency matrix is how many edges between the two vertices so A[i,j] would be 1

 

[Dick]

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?

 

[pupeye11]

I was assuming I was working with a simple graph only.

 

[Dick]

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?

 

[pupeye11]

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?

 

[Dick]

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.

 

[pupeye11]

A^2[i,j] = A[i,j]*A[i,j]. Wouldn't this double the number of ways to get from i to j?

 

[Dick]

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.

 

[pupeye11]

I am really not getting this, the matrix multiplication makes sense but I don't get how to interpret it.

 

[Dick]

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.

 

[pupeye11]

A^2 would be the total number of ways to get from i to j wouldn't it?

 

[Dick]

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?

 

[pupeye11]

so A^3[i,j] would be the total number of ways to get from i to j transversing exactly 3 edges.

 

[Dick]

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.

 

[pupeye11]

alright, thanks for your help