1
$\begingroup$

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?

  • 0
    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.2011-05-12

2 Answers 2

2

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.

  • 2
    @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.2011-05-12
1

@ "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

  • 0
    @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***2011-05-12