Matrix Exponentiation

Example - Fibonacci

The Fibonacci numbers are defined as follows:

We can also write them using the following matrix recurrence:

Proof by Induction

Base case ($n=1$):

Inductive step ($n+1$):

With this, we've shown that the formula holds for all $n \in \mathbb{N}$.

Implementation

Time Complexity: $\mathcal{O}(\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll MOD = 1e9 + 7;

using Matrix = array<array<ll, 2>, 2>;

Matrix mul(Matrix a, Matrix b) {

Copy
from typing import List

MOD = 10**9 + 7


def mul(A: List[List[int]], B: List[List[int]], MOD: int) -> List[List[int]]:
	C = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			for k in range(2):

Finding the Right Matrix - Generalized Linear Recurrences

We can generalize the technique above to calculate values in any linear recurrence. The tricky part is finding the correct matrix for the problem. Let's see how we can find this matrix $M$. We know that following equation must hold:

Here, we use the values of $a_1, \dots, a_n$ to find $a_{k+1}$. We can also discard $a_1$ since it won't be used to calculate $a_{k+2}$. If we thinking about the matrix multiplication, we notice that there is a diagonal of $1$s shifted to the right by $1$ since $a_i \rarr a_{i + 1}$ for $i < k$. So now we have (using $k = 5$ as an example):

To find the bottom row, we use the recurrence formula:

With this $M$, the equation always holds.

Implementation

Time Complexity: $\mathcal{O}(K^3 \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1e9;

template <typename T> void matmul(vector<vector<T>> &a, vector<vector<T>> b) {
	int n = a.size(), m = a[0].size(), p = b[0].size();
	assert(m == b.size());
	vector<vector<T>> c(n, vector<T>(p));

Takeaway

The takeaway here is not the exact matrix used in linear recurrences, but the method in deriving it. The process of thinking about a vector before and after applying $M$, then deducing $M$ through logic, is a technique that generalizes far beyond standard linear recurrences. For example, see if you can find the equation needed and correct matrix (using $k = 5$ as an example) to solve this modified recurrence for $i > k$:

where $C$ is a given constant.

Problems