Find trace of matrix M^k in optimum way.

Question

I have to find the trace of every matrix $M^1,M^2.....M^k$ in optimum way. One way is to multiply $M$ every time but complexity increases to $k*n^3$. Is there any better approach?

Answer 1

You should find the eigenvalues of $M$. Let's call them $\lambda_i$.

Then the trace of $m$ is $\sum \lambda_i$, and the trace of $M^k$ is $\sum \lambda_i^k$.

Finding the eigenvalues of $M$ is fast, and almost no other information about the other powers of $M$ are necessary.

Answer 2

Another approach would be to do calculate $M^2, M^4, M^8,\cdots$ and then calculating any other $M^k$ requires at most $log_2(k)$ multiplications and you can parallellize it well. If this is any good compared to other methods depends on $k$,the size of $M$, is it sparse or dense and do you have parallelization capabilities on your hardware and software.

And once you have the $M^{2^n}$ you don't need to calculate the others, just their traces.