Graphs, Matrices and Walks

  1. Let \(G\) be a directed graph (possibly with self-loops) with vertices \(v_1, \dots , v_n\). Let \(M\) be the adjacency matrix of \(G\). Prove that \(M_{ij}^k\) (i.e., that \([i][j]^{th}\) entry of \(M^k\)) is equal to the number of length-\(k\) walks from \(v_i\) to \(v_j\).

  2. Using the above result, design an \(O(n^{\omega})\) time algorithm to count the number of triangles (cycles of length 3) in a given directed graph. Here, \(O(n^{\omega})\) is the running time of multiplying two matrices.

Source: folklore

Related Content