ivplay's blog

my idea LightOj 1142(matrix exponentiation)
By ivplay, 10 years ago, In English

  • 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.
  • Vote: I like it
  • +19
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice explanation. I think there is a typo in the else part, it should be odd rather than even.

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

nice.

→ Reply
»
10 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

nice explanation.
complexity seems to be (where is the size of matrix ).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think so. Nobody can mutiply matrices in O(n2).

    We can maintain needed powers of A, so complexity is

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah thanks i mistyped initially. edited the comment now.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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).

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great explanation thanks

→ Reply