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

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/