Matrix Exponentiation

Authors: Benjamin Qi, Neo Wang

Repeatedly multiplying a square matrix by itself.

Edit This Page

Prerequisites

Gold - Introduction to DP

Example - Fibonacci Proof by Induction Implementation Problems


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 – read through this problem before continuing!

The fibonacci numbers are defined by the following matrix relation

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:

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

Base case ( $n=1$ ):

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+1$ ):

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 \in \mathbb{N}$ .

Implementation

Time complexity: $\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

Source	Problem Name	Difficulty	Tags
CSES	Graph Paths I	Easy	Show Tags Exponentiation, Matrix
CSES	Graph Paths II	Easy	Show Tags Exponentiation, Matrix
CF	Xor-sequences	Easy	Show Tags Exponentiation, Matrix
CF	Sasha and Array	Normal	Show Tags Exponentiation, Matrix, PURS
Baltic OI	2007 - Connected Points	Normal	Show Tags Exponentiation, Matrix
Balkan OI	2009 - Reading	Normal	Show Tags Exponentiation, Matrix
DMOJ	Ray Needs Help	Normal	Show Tags Exponentiation, Matrix
Plat	COWBASIC	Hard	Show Tags Exponentiation, Matrix

Table of Contents

Matrix Exponentiation

Prerequisites

Table of Contents

Example - Fibonacci

Proof by Induction

Implementation

Problems

Module Progress:

Table of Contents

Matrix Exponentiation

Prerequisites

Table of Contents

Example - Fibonacci

Proof by Induction

Implementation

Problems

Module Progress:Not Started

Module Progress: