If the matrix is diagonalizable, then it can be raised to any power in O(n^3) independent of k. Find the eigenvalue/eigenvector decomposition of the matrix, raise the eigenvalues to power k, and then multiply on the right and left by the matrix of eigenvectors and its inverse, respectively.
Dave On Jan 12, 6:58 am, bittu <shashank7andr...@gmail.com> wrote: > How will you raise a n x n matrix to the power k efficiently. What's > the time complexity and space complexity of you algorithm? How will > you optimize this? > > Thanks &Regards > Shashank "Don't b Evil U Can Earn While U Learn" -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.