I know how to use Matrix Exponentiation to solve problems having linear Recurrence relations (for example Fibonacci sequence). I would like to know, can we use it for linear recurrence in more than one variable too? For example can we use matrix exponentiation for calculating ${}_n C_r$ which follows the recurrence C(n,k) = C(n-1,k) + C(n-1,k-1). Also how do we get the required matrix for a general recurrence relation in more than one variable?
Matrix Exponentiation for Recurrence Relations
1
$\begingroup$
matrices
recurrence-relations
-
0I once tried to do exactly this for the mandelbrot set recurrence relation, $z_{n+1}=z_n^2+z_0$. It didn't work because each iteration led to a new transformation matrix with it's own eigenvalues and eigenvectors. – 2011-05-12