PrevNext
Rare
 0/8

Matrix Exponentiation

Authors: Benjamin Qi, Neo Wang

Repeatedly multiplying a square matrix by itself.

Edit This Page
Resources
CP2
CPH
CF

video + problemset

CF

interesting applications of mat exp

Mostafa

powerpoint of matrix exponentiation

Example - Fibonacci

Focus Problem – read through this problem before continuing!

The fibonacci numbers are defined by the following matrix relation

A=[1110]n=[Fn+1FnFnFn1]A = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{bmatrix}

Proof by Induction

The fibonacci numbers are defined as follows:

F0=0F1=1Fn+1=Fn+Fn1\begin{align*} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+1} &= F_{n} + F_{n-1} \end{align*}

Base case (n=1n=1):

A1=[1110]=[F2F1F1F0]A^1 = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} = \begin{bmatrix}F_2 & F_1 \\ F_1 & F_0\end{bmatrix}

Induction step (n+1n+1):

An+1=AAn=[1110][Fn+1FnFnFn1]=[Fn+1+FnFn+Fn1Fn+1Fn]=[Fn+2Fn+1Fn+1Fn]A^{n+1}=A\,A^n=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix}=\begin{bmatrix} F_{n+1}+F_n & F_{n}+F_{n-1} \\ F_{n+1} & F_{n} \end{bmatrix}=\begin{bmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{bmatrix}

The base case is true, and the induction step is true. Therefore the formula holds for all nNn \in \mathbb{N}.

Implementation

Time complexity: O(logn)\mathcal{O}(\log n)

#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) {

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsExponentiation, Matrix
CSESEasy
Show TagsExponentiation, Matrix
Baltic OINormal
Show TagsExponentiation, Matrix
CFEasy
Show TagsExponentiation, Matrix
Balkan OINormal
Show TagsExponentiation, Matrix
DMOJNormal
Show TagsExponentiation, Matrix
PlatHard
Show TagsExponentiation, Matrix

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext