# Matrix Exponentiation for Recurrence Relations

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?

-
I 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. –  Matt Calhoun May 12 '11 at 15:55

## 2 Answers

No, if by "quadratic recurrence" you mean a recurrence where an element of a sequence is written as a quadratic function of previous terms. Unlike linear recurrences, which are relatively well-behaved, quadratic recurrences such as the logistic map can exhibit chaotic behavior, so it's extremely unlikely that they would have a simple description in terms of matrices.

-
I am talking about recurrences like C(n,k) = C(n-1,k-1) + C(n-1,k). –  fR0DDY May 12 '11 at 9:54
@fRoDDy: that is not what is usually meant by a "quadratic recurrence." It's still a linear recurrence, just in more variables, and can be handled (in a sense) by multivariate generating functions, although this doesn't lead to an efficient method of computation. –  Qiaochu Yuan May 12 '11 at 9:59

@ "For example can we use matrix exponentiation for calculating nCr"
There is a simple matrix as logarithm of P (which contains the binomial-coefficients):

$\qquad \exp(L) = P$

where
$\qquad L = \small \begin{array} {rrrrrrr} 0 & . & . & . & . & . & . & . \\ 1 & 0 & . & . & . & . & . & . \\ 0 & 2 & 0 & . & . & . & . & . \\ 0 & 0 & 3 & 0 & . & . & . & . \\ 0 & 0 & 0 & 4 & 0 & . & . & . \\ 0 & 0 & 0 & 0 & 5 & 0 & . & . \\ 0 & 0 & 0 & 0 & 0 & 6 & 0 & . \\ 0 & 0 & 0 & 0 & 0 & 0 & 7 & 0 \end{array}$
and
$\qquad P =\small \begin{array} {rrrrrrr} 1 & . & . & . & . & . & . & . \\ 1 & 1 & . & . & . & . & . & . \\ 1 & 2 & 1 & . & . & . & . & . \\ 1 & 3 & 3 & 1 & . & . & . & . \\ 1 & 4 & 6 & 4 & 1 & . & . & . \\ 1 & 5 & 10 & 10 & 5 & 1 & . & . \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & . \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \end{array}$

L and P can be extended to arbitrary size in the obvious way

-
$\mathbf P$ is often termed the Pascal matrix. –  Ｊ. Ｍ. May 12 '11 at 12:46
Can you tell me how did you get L from the recurrence relation? –  fR0DDY May 12 '11 at 14:40
@fRoDDY: I didn't use the recurrence relation (I've not yet understood your introducing remark in your question). I just wanted to help with an answer to the (supposed) partial problem: "for example can we use matrix exponentiation for calculation nCr?" <hr> (I'd actually like to understand the connection between matrix-exponential and the recurrence-problem myself...). –  Gottfried Helms May 12 '11 at 15:14
@gottfried-helms Look here for linear recurrence in one variable comeoncodeon.wordpress.com/2011/05/08/… –  fR0DDY May 12 '11 at 15:41
@fRoDDY: Ah, I see - just the same as I explained it recently ( I'm using a set of statndard routines in Pari/GP for this). From your blog I understand that you use the matrix-exponential for the fractional/continuous iterate - so this makes now completely sense to me. If you use the matrix P for your recursion, then you can use L for fractional iterates/fractional powers of P –  Gottfried Helms May 12 '11 at 16:15