[Rhapso]

Just spending 30 seconds looking at it, think of it like the bit shifting solution to multiplication, do a related faster operation then correct.

You can reduce A^k to be a lot faster if you calculate A^2 then A^4 then A^8 .. A^N where N is 2^(Log(k)-1) (log base 2) then multiply A^N by A^(k-N) (which you can speedup using the same method if it is larger then 4)

That was a bit rough and quick, but the basic idea, is that doing (nxn)^k would likely be reduced to O(log(k)n^2.373) versus the more naive O(kn^2.373) which is a speedup of O(k/log(k)) (or it's inverse, I am not sure how it is best to represent the ratio) which is decent, I am sure there is a better solution out there.

[wbhart]

Multiplying k arbitrary matrices can be done in less time than O(kn^omega). But certainly for k > 3 you wouldn't multiply naively k times as you've pointed out.