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?

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