Calculating the trace of a matrix to the power k

Question

I need to calculate the trace of a matrix to the power of 3 and 4 and it needs to be as fast as it can get.

The matrix here is an adjacency matrix of a simple graph, therefore it is square, symmetric, its entries are always 1 or 0 and the diagonal elements are always 0.

Optimization is trivial for the trace of the matrix to the power of 2:

• We only need the diagonal entries (i,i) for the trace, skip all others
• As the matrix is symmetric these entries are just the entries of the i-th row squared and summed up
• And as the entries are just 1 or 0 the square-operation can be skipped

Another idea I found on wikipedia was summing up all elements of the Hadamard product, i.e. entry-wise multiplication, but I don't know how to extend this method to the power of 3 and 4.

See http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties

Maybe I'm just blind but I can't think of a simple solution.

In the end I need a C++ implementation, but I think that's not important to the question.

Thanks in advance for any help.

Answer 1

Ok, I just figured this one out myself. The important thing I did not know was this:

If A is the adjacency matrix of the directed or undirected graph G, then the matrix An (i.e., the matrix product of n copies of A) has an interesting interpretation: the entry in row i and column j gives the number of (directed or undirected) walks of length n from vertex i to vertex j. This implies, for example, that the number of triangles in an undirected graph G is exactly the trace of A^3 divided by 6.

(Copied from http://en.wikipedia.org/wiki/Adjacency_matrix#Properties)

Retrieving the number of paths of a given length from node i to i for all n nodes can essentially be done in O(n) when dealing with sparse graphs and using adjacency lists instead of matrices.

Nevertheless, thanks for your answers!