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

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

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

Dick
Homework Helper
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?

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

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

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
Homework Helper
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:
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
Homework Helper
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.

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

Dick
Homework Helper
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.

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

Dick
Homework Helper
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?

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

Dick