Calculation of trace matrix up to degree k

Question

I need to calculate the matrix trace to degrees 3 and 4, and it should be as fast as it is.

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

Optimization is trivial for a trace matrix up to degree 2:

• We only need diagonal entries (i, i) for tracing, skip all the rest
• Since the matrix is ​​symmetric, these entries are only entries of the square of the i-th row and are summed
• And since the entries are only 1 or 0, a square operation may be skipped.

Another idea that I found on Wikipedia was to summarize all the elements of the Hadamard product, i.e. multiplication by input, but I do not know how to extend this method to degrees 3 and 4.

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

I may be just blind, but I cannot come up with a simple solution.

In the end, I need a C ++ implementation, but I think this is not important for the question.

Thanks in advance for your help.

Answer 1

Ok, I just thought about that. An important thing that I did not know is:

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

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

Extracting 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 working with sparse graphs and using adjacency lists instead of matrices.

Thanks, however, for your answers!

Answer 2

The trace is the sum of the eigenvalues, and the eigenvalues ​​of the matrix power are only the eigenvalues ​​of this power.

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

Depending on your matrix, you may want to calculate your own values ​​and then add up. If your matrix has a low rank (or can be well approximated by a low rank matrix), you can calculate the eigenvalues ​​very cheaply (the partial eigendecomposition function has complexity O (n * k ^ 2), where k is the rank).

Edit: You mentioned in the comments that this is 1600x1600, in which case finding all eigenvalues ​​should not be a problem. Here is one of many C ++ codes you can use for this http://code.google.com/p/redsvd/