PrevNext
Rare
 0/9

Matrix Exponentiation

Authors: Benjamin Qi, Harshini Rayasam, Neo Wang

Repeatedly multiplying a square matrix by itself.

Edit This Page
Resources
CP2
5.9 - Powers of a Square Matrix
CPH
23 - Matrices
CF
Errichto - Matrix Exponentiation

video + problemset

CF
Cool tricks using Matrix Exponential

interesting applications of mat exp

Mostafa
Matrix Power Applications

powerpoint of matrix exponentiation

Example - Fibonacci

Fibonacci Numbers
CSES - Easy

Focus Problem – try your best to solve this problem before continuing!

The fibonacci numbers are defined by the following matrix relation

A=[1110]n=[Fn+1FnFnFn−1]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+Fn−1\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=A An=[1110][Fn+1FnFnFn−1]=[Fn+1+FnFn+Fn−1Fn+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 n∈Nn \in \mathbb{N}.

C++

Implementation

Time complexity: O(log⁡n)\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) {

Python

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):

Problems

StatusSourceProblem NameDifficultyTags
CSES
Graph Paths I
Easy
Show TagsExponentiation, Matrix
CSES
Graph Paths II
Easy
Show TagsExponentiation, Matrix
CF
Xor-sequences
Easy
Show TagsExponentiation, Matrix
CF
Sasha and Array
Normal
Show TagsExponentiation, Matrix, PURS
Baltic OI
2007 - Connected Points
Normal
Show TagsExponentiation, Matrix
Balkan OI
2009 - Reading
Normal
Show TagsExponentiation, Matrix
DMOJ
Ray Needs Help
Normal
Show TagsExponentiation, Matrix
Plat
COWBASIC
Hard
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!

Join Forum
PrevNext