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.