Given an nxn Adjacency matrix, how can one compute the number of triangles in the graph (Matlab)?

Question

I wrote a function that, given n, generates random nxn adjacency matrices. I was wondering if there is a way to count the number a triangles in the graph represented by the matrix.

Answer 1

The (i, j) element in the n'th power of an adjacency matrix A counts the number of paths of length n starting at i and ending at j.

A triangle is a path of length 3 that starts and ends at the same node. Therefore the i'th diagonal element of the 3rd power of A counts the number of triangles that contain i as one of the nodes.

Each distinct triangle will be counted twice for each of the three nodes in the graph (once in each direction, clockwise and anticlockwise).

Therefore the number of distinct triangles is trace(A^3) / 6.