### ivplay's blog

By ivplay, 7 years ago,
• This post is for those beginners who want to learn and practice matrix exponentiation. I am just here to share my idea on a very basic problem form lightoj(1142).

• Task is simple A + A^2 + A^3 + ... + A^k =? where A is a n*n matrix.

• First time I thought ans will progress as geometric sum = (A*((A^k)-1))/A-1. or we can say... (A^(k+1) — A)/(A-1) where one is an Identity matrix. I was stuck in the matrix division portion for a long time. I don't know whether my geometric sum idea is right or wrong but i have another idea that can avoid that division.
• say A + A^2 + A^3 + ... + A^k = f(k)
• if(k is even,say k= 2x) we can write
• f(k=2x) = [A + A^2 + A^3 + ... + A^x ] + [A^(x+1) + A^(x+2) + .... + A^(x+x)]
• = [A + A^2 + A^3 + ... + A^x ] + [A^x(A + A^2 + A^3 + ... + A^x)]
• = [A + A^2 + A^3 + ... + A^x ] * (A^x + 1)
• = f(k/2) * (A^(k/2) + 1)
• else if K is odd we can write
• f(K)= [A + A^2 + A^3 + ... A^(k-1)] + A^k = f(k-1)+A^k
• very good problem for beginners. You can try if you have just started to learn matrix exponentiation.

• +19

 » 7 years ago, # |   +1 Nice explanation. I think there is a typo in the else part, it should be odd rather than even.
•  » » 7 years ago, # ^ |   0 yes, sorry and thanks :)
 » 7 years ago, # |   +1 nice.
 » 7 years ago, # | ← Rev. 5 →   0 nice explanation. complexity seems to be (where is the size of matrix ).
•  » » 7 years ago, # ^ |   0 I don't think so. Nobody can mutiply matrices in O(n2).We can maintain needed powers of A, so complexity is
•  » » » 7 years ago, # ^ |   0 yeah thanks i mistyped initially. edited the comment now.
 » 6 years ago, # | ← Rev. 2 →   0 What about the correctness of this way, sum = (A^(k+1) — A)/(A-1) ? Is this method right? If it is right, we calculate in O((logk) * n^3).
 » 4 years ago, # |   0 Can't we write the recurrence as F(k)=A(1+A(A+A^2+...+A^k-1))=A(1+A*F(k-1))=(A^2)F(k-1)+A
 » 8 months ago, # |   0 great explanation thanks