Algo: Matrix Exponentiation for Recurrences

Computing the nth term of a sequence defined by a linear recurrence, like the Fibonacci numbers, using a naive iterative approach takes $O(n)$ time, which becomes prohibitively slow for very large $n$. By reformulating the recurrence as a matrix multiplication, you can leverage fast matrix exponentiation to compute the result in $O(\log n)$ time. This powerful paradigm shift is essential for competitive programming, efficient algorithm design, and solving complex problems in combinatorics and graph theory.

From Linear Recurrences to Matrix Form

A linear recurrence relation defines each term of a sequence as a linear combination of its previous terms. For a $k$-th order recurrence, the $n$-th term $a_n$ is expressed as: $$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$$ where $c_1,c_2,\dots ,c_k$ are constant coefficients. The key insight is that such a recurrence can be captured by a state transition matrix. You can represent the current "state" of the sequence, typically a vector containing the last $k$ terms, and define a matrix that, when multiplied with this state vector, produces the next state vector. This transforms the problem of stepping through the recurrence $n$ times into computing the $n$-th power of a fixed matrix and applying it to an initial state vector. This matrix formulation is the bridge to applying fast exponentiation techniques.

Fast Exponentiation via Repeated Squaring

Once you have expressed your recurrence as a matrix multiplication $S_n=M\cdot S_{n-1}$, where $S$ is the state vector and $M$ is the transition matrix, finding the $n$-th term requires computing $S_n=M^n\cdot S_0$. Computing $M^n$ directly by multiplying $M$ by itself $n$ times would be $O(n)$ matrix multiplications, offering no advantage. The breakthrough comes from the repeated squaring algorithm for exponentiation.

The algorithm works for numbers and matrices alike. To compute $M^n$:

1. Initialize a result matrix to the identity matrix $I$ (the matrix equivalent of 1).
2. While $n>0$:

• If $n$ is odd, multiply the current result by $M$.
• Square the matrix $M$ (i.e., set $M=M\times M$).
• Halve $n$ (using integer division $n=\lfloor n/2\rfloor$).

Each iteration either performs a multiplication with the result or squares the base matrix. Since squaring a $k\times k$ matrix takes $O(k^3)$ time using standard multiplication, and you perform $O(\log n)$ such squaring operations, the overall time complexity is $O(k^3\log n)$. For a fixed, small $k$ (like 2 for Fibonacci), this is effectively $O(\log n)$, a dramatic improvement over linear time.

The Fibonacci Case Study

The Fibonacci sequence, defined by $F_0=0,F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\ge 2$, is the canonical example. To convert this into matrix form, define a state vector containing two consecutive terms: $$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]$$

We need a matrix $M$ such that: $$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]=M\cdot \left[\begin{array}{c}{F}_{n-1}\\ F_{n-2}\end{array}\right]$$

From the recurrence $F_n=1\cdot F_{n-1}+1\cdot F_{n-2}$ and $F_{n-1}=1\cdot F_{n-1}+0\cdot F_{n-2}$, we can construct $M$: $$M=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$

Therefore, to find $F_n$, you compute: $$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]=M^n\cdot \left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\cdot \left[\begin{array}{c}1\\ 0\end{array}\right]$$

Using repeated squaring to compute $M^n$ in $O(\log n)$ time, you then multiply the result by the initial vector to extract $F_n$. This method directly generalizes to any similar two-term recurrence.

Generalizing to k-th Order Linear Recurrences

The process for a general $k$-th order recurrence $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$ follows a precise template. The state vector is: $$S_{n-1}=\left[\begin{array}{c}{a}_{n-1}\\ a_{n-2}\\ ⋮\\ a_{n-k}\end{array}\right]$$

The $k\times k$ transition matrix $M$ is constructed so that $S_n=M\cdot S_{n-1}$. The first row of $M$ contains the coefficients $[c_1,c_2,\dots ,c_k]$, as it defines the new term $a_n$. The remaining rows form an identity-like structure that shifts the previous terms down: $$M=\left[\begin{array}{cccccc}{c}_1& c_2& c_3& \dots & c_{k-1}& c_k\\ 1& 0& 0& \dots & 0& 0\\ 0& 1& 0& \dots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& \dots & 1& 0& 0\\ 0& 0& \dots & 0& 1& 0\end{array}\right]$$

To find $a_n$, you compute $S_n=M^n\cdot S_0$, where $S_0$ is the vector of initial terms $[a_{k-1},a_{k-2},\dots ,a_0{]}^T$. The element at the top of the resulting vector is $a_n$. The $O(k^3\log n)$ complexity makes this feasible for moderate $k$ and very large $n$.

Practical Applications: Counting Paths and Tilings

The power of matrix exponentiation extends beyond simple sequences to model state transitions in more complex systems. Two classic applications are counting paths in graphs and solving tiling problems.

For counting paths in a graph, if you have an adjacency matrix $A$ of a graph, the entry $(A^n{)}_{ij}$ gives the number of walks of length exactly $n$ from vertex $i$ to vertex $j$. By exponentiating the adjacency matrix using repeated squaring, you can answer queries about long paths efficiently. This is directly applicable to problems like counting the number of ways to travel between cities with a certain number of flights.

Tiling problems often reduce to linear recurrences. Consider tiling a $2\times n$ board with dominoes ($2\times 1$ tiles) and trominoes. The number of ways $T_n$ to tile the board can often be expressed as a recurrence like $T_n=T_{n-1}+2T_{n-2}+\dots$. By identifying the correct state (e.g., representing the configuration of the last column), you can derive a transition matrix between states. Exponentiating this matrix then computes $T_n$ for large $n$ almost instantly, where a naive dynamic programming solution would be too slow.

Common Pitfalls

1. Incorrect Matrix Dimensions or Construction: The most frequent error is misconstructing the transition matrix, especially for higher-order recurrences. Ensure the first row contains the coefficients in the correct order, and the sub-diagonal of 1s properly shifts the state vector. Always verify your matrix by manually multiplying it with a small example state vector.

• Correction: Derive the matrix systematically. Write down the state vector $S_{n-1}$ and explicitly define each entry of $S_n=M\cdot S_{n-1}$ using the recurrence. The equations you write directly give you the rows of $M$.

1. Off-by-One Errors in Initial State: Using the wrong initial state vector $S_0$ will propagate errors. For a $k$-th order recurrence, $S_0$ must contain the $k$ initial terms in reverse order: $[a_{k-1},a_{k-2},\dots ,a_0{]}^T$, not $[a_0,a_1,\dots ,a_{k-1}{]}^T$.

• Correction: Remember that after applying $M$ once, $S_1$ should equal $[a_k,a_{k-1},\dots ,a_1{]}^T$. Test with $n=1$ to confirm your $M$ and $S_0$ are correct.

1. Ignoring the Cost of Matrix Multiplication: While the exponentiation is $O(\log n)$, each matrix multiply is $O(k^3)$. For very large $k$, this can dominate the runtime, making the algorithm impractical. Sometimes, specialized algorithms like Cayley-Hamilton theorem can offer better constants.

• Correction: Be aware of the $k^3$ factor. For problems where $k$ is large (e.g., 100), consider if the recurrence can be simplified or if an alternative method exists.

1. Overflow in Intermediate Calculations: When dealing with large $n$, the matrix entries can grow exponentially, leading to integer overflow even before you extract the final answer.

• Correction: Use a data type with sufficient capacity (e.g., 64-bit integers or arbitrary-precision libraries) or perform all operations under a required modulus from the start, which is common in programming contests.

Summary

• Core Idea: Any linear recurrence relation can be expressed as a state transition using matrix multiplication, converting the problem of computing the $n$-th term into computing the $n$-th power of a fixed matrix.
• Key Algorithm: Repeated squaring allows for $O(\log n)$ matrix exponentiation, reducing the time complexity from linear to logarithmic for fixed-order recurrences.
• General Template: For a $k$-th order recurrence $a_n={\sum }_{i=1}^k{c}_i{a}_{n-i}$, construct a $k\times k$ transition matrix with the coefficients $c_i$ in the first row and a sub-diagonal of 1s to shift the state vector.
• Beyond Sequences: This technique is widely applicable to problems involving state transitions, such as counting paths of a given length in a graph or solving combinatorial tiling problems efficiently.
• Critical Check: Always validate your derived matrix and initial state vector with small, manually computable values of $n$ to avoid construction errors.
• Practical Consideration: Remember the $O(k^3)$ cost per matrix multiplication; the overall $O(k^3\log n)$ complexity is excellent for small $k$ and large $n$, but may need reconsideration for large $k$.