Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 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.

share|improve this answer
    
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
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. –  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

share|improve this answer
    
$\mathbf P$ is often termed the Pascal matrix. –  J. M. 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.