BumbleBee's blog

Find nth power of a square matrix in O((d^3)log(n))
By BumbleBee, history, 6 years ago, In English

I was studying about matrix exponentiation here and it requires a prerequisite which says that I need to know how to find the nth power of a square matrix of dimension d in O((d^3)log(n)).

But I couldn't find any well-explained article on this topic. Can anyone please provide me with some links to blogs/articles that explain this technique?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

You should first know fast exponentiation for numbers. Then you can just do that for matrix, but the multiplying in matrix of size d, takes d^3 time

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

multiplcation
exponentiation

→ Reply