You could factor the matrix into eigenvalues and eigenvectors. Then you get
M = V * D * V^-1
Where V is the eigenvector matrix and D is a diagonal matrix. To raise this to the Nth power, you get something like:
M^n = (V * D * V^-1) * (V * D * V^-1) * ... * (V * D * V^-1)
= V * D^n * V^-1
Because all the V and V^-1 terms cancel.
Since D is diagonal, you just have to raise a bunch of (real) numbers to the nth power, rather than full matrices. You can do that in logarithmic time in n.
Calculating eigenvalues and eigenvectors is r^3 (where r is the number of rows/columns of M). Depending on the relative sizes of r and n, this might be faster or not.