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!

Answer 2

The trace is the sum of the eigenvalues and the eigenvalues of a matrix power are just the eigenvalues to that power.

That is, if l_1,...,l_n are the eigenvalues of your matrix then trace(M^p) = 1_1^p + l_2^p +...+l_n^p.

Depending on your matrix you may want to go with computing the eigenvalues and then summing. If your matrix has low rank (or can be well approximated with a low rank matrix) you can compute the eigenvalues very cheaply (a partial eigendecomposition has complexity O(n*k^2) where k is the rank).

Edit: You mention in the comments that it's 1600x1600 in which case finding all the eigenvalues should be no problem. Here's one of many C++ codes that you can use for this http://code.google.com/p/redsvd/