WIL's blog

Question about matrix exponentiation?
By WIL, 9 years ago, In English

I'm looking for a good tutorial about matrix exponentiation, where explain how can i solve a recurrence like this: f(n)=f(n-1)+n*2

I know how to use matrix exponentiation to solve a recurrence where are used anterior terms, but i don't know when the recurrence have one term that depend to the position of the term.

thank you!!!

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

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

I think you meant f(N)=F(N-1)+2*n;

well that reccurence can be solved using a forumula (if you factor out the 2)

there is also a way to solve it using matrix exponentiantion:

Well as you know its hard (or atleast i dont know how) to solve when you have to add a different number every time , but what if you add a constant?

thats easier , that can be done , a function like f(x)=f(x-1) +Constant can be exponentiated if you want

lets reduce the original problem to one wich has only constant C's

For that , we have to keep track 2 variables , instead of one :

The position , & , The current value

now :

value[i]=value[i-1]+position[i-1]+2

position[i]=position[i-1]+2

see now ? now what i need to add its constant (its 2) and this type or recurennce is liniar , you can solve this by matrix exponential

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

    Oh and if you wonder how to solve for the constant , here is my idea : keep a third variable wich is constant ! lol

    TWO[i]=TWO[i-1]

    value[i]=value[i-1]+position[i-1]+TWO[i-1]

    position[i]=position[i-1]+TWO[i-1]

    now youve got nothing to add

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

How is f(n) = f(n) + 2.n a valid recurrence? f(n) should depend on f(n - 1) or f(n - 2) or some other previous term but it cannot depend on itself.

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

    I fixed the question, thank!!!

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

The recurrence you have written simply evaluates to n * (n + 1).

f(n) = f(n — 1) + 2 * n
= f(n — 2) + 2 * (n + (n — 1))
and so on.
Hence, f(n) = 2 * (1 + 2 + ... + n)

Also, any recurrence of the form of f(n) = f(n — 1) + p(n) can be solved in a similar way without matrix exponentiation.

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

Thank everybody, i understand now how to solve this kind of problem. And I share with all of you a page very interesting that i found.

This is the link.

So, the answer is to make enother function for keep the position, something like this:

  • My 1rt recurrences: f(n)=f(n-1)+2*n

  • The part n (the position), can transform in another recurrence, like this: g(n)=g(n-1)+1 (is ease to see).

  • And for concluding make the matrix exponentiation:

|1 2 0| |f(n)|
|0 1 1|*|g(n)|=
|0 0 1| | 1 |
|f(n+1)|
|g(n+1)|
| 1 |
And this is all, i hope that help you!!!

→ Reply