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