# 1/6 of trace(A^3)? [Graph theory]

• Oct 21st 2013, 11:20 AM
loui1410
1/6 of trace(A^3)? [Graph theory]
Hello,

I've read somewhere that if A is an adjacency matrix then (1/6)*trace(A^3) equals the number of triangles in the graph. Can someone explain why?

Thanks.
• Oct 21st 2013, 11:24 PM
SlipEternal
Re: 1/6 of trace(A^3)? [Graph theory]
The adjacency matrix is symmetric across its diagonal. So, when multiplying $A\cdot A$, consider the first column of $A$ times the first row of $A$. Every 1 and every 0 is in the same spot. So, you get the degree of each vertex across the diagonal. What happens when the first column is multiplied with the second row? In position $a_{2,1}$ of $A^2$, you get the number of vertices adjacent to both $v_1$ and $v_2$. Similarly for the rest of the entries.

Now, what happens when you multiply $A^2$ by $A$? The top row of $A^2$ lists the number of vertices adjacent to both $v_1$ and $v_k$ for each position $a_{1,k}$. Each vertex that is adjacent to both $v_1$ and $v_k$ forms a triangle. When you multiply this by the first column of $A$, the entry $a_{1,1}$ of $A^3$ will have twice the number of triangles adjacent to $v_1$. I say twice because if we have a triangle $v_1v_iv_j$, it will be counted by both $v_i$ and $v_j$, but since $a_{1,1} = 0$ in $A$ (since $v_1$ is not considered adjacent to itself), the triangle $v_1v_iv_j$ will not be counted by $v_1$ itself. So, in $a_{1,1}$, you have twice the number of triangles adjacent to $v_1$. In $a_{i,i}$ you get twice the number of triangles adjacent to $v_i$ (which includes the same triangle already counted twice in $a_{1,1}$. Then, that same triangle is counted another two times in $a_{j,j}$. Taking the trace adds up all numbers on the diagonal. You get six times the count of triangles in the graph.